27.07.2024 10:13
idsulik 19 790 Источник

Постановка задачи(официальная)

Ссылка на задачу: https://leetcode.com/problems/fruit-into-baskets

Вы посещаете ферму, на которой деревья выстроены в один ряд слева направо. Деревья представлены целочисленным массивом fruits, где fruits[i] — это тип фруктов на i-ом дереве.

Вы хотите собрать как можно больше фруктов, но владелец фермы установил следующие правила:

  1. У вас есть две корзины, каждая из которых может содержать только один тип фруктов.

  2. В каждой корзине может быть неограниченное количество фруктов.

  3. Начиная с любого дерева, вы должны собирать фрукты с каждого дерева (включая стартовое), двигаясь вправо.

  4. Если вы встречаете дерево, фрукты которого не могут поместиться в ваши корзины, вы должны остановиться.

Задача состоит в том, чтобы найти максимальное количество фруктов, которые можно собрать, соблюдая эти правила.

Упрощенная версия постановки

Дан массив fruits, где каждый элемент представляет дерево, а его значение указывает тип фрукта, который растет на этом дереве. У нас есть две корзины, каждая из которых может содержать неограниченное количество фруктов одного типа(к примеру, в одну корзину можем положить все фрукты типа 4, а во вторую корзину положить все фрукты типа 7). Наша цель — собрать как можно больше фруктов, непрерывно двигаясь слева направо от любого начального дерева, пока не встретим тип фрукта, который не помещается в корзины(к примеру, в одной корзине фрукты типа 4, в другой корзине фрукты типа 7, а сейчас мы рядом с деревом на котором растет фрукт типа 2, мы не можем добавить этот тип ни в одну корзину, т.к. в корзине может находиться фрукты только одного типа).

Подход к решению

Для решения задачи мы будем использовать технику "скользящего окна" (sliding window) и хэш-таблицу для отслеживания количества каждого типа фруктов в текущем окне.

Почему именно этот подход?

  1. Эффективность: Метод скользящего окна позволяет пройти по массиву всего один раз, что обеспечивает линейную временную сложность O(n). Это оптимально для больших массивов.

  2. Отслеживание состояния: Хеш-таблица помогает быстро проверять и обновлять количество типов фруктов в текущем окне.

  3. Гибкость: С помощью сдвига границ окна можно динамически адаптироваться к изменениям типов фруктов и корректировать размер окна.

Алгоритм

  1. Инициализация переменных:

    • res для хранения результата (максимальное количество фруктов).

    • type_counter для отслеживания количества каждого типа фруктов в текущем окне.

    • left для обозначения левой границы окна.

  2. Проход по массиву fruits:

    • Используем переменную right для обозначения правой границы окна.

    • Увеличиваем счетчик для текущего типа фрукта right_fruit.

  3. Проверка условия допустимости окна:

    • Если количество типов фруктов в окне становится больше двух (len(type_counter) == 3), сдвигаем левую границу окна left вправо, уменьшая счетчики для фруктов и удаляя типы фруктов с нулевым счетчиком.

  4. Обновление результата:

    • На каждой итерации обновляем res, вычисляя длину текущего окна.

Код решения

from collections import defaultdict
from typing import List

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        res = 0
        type_counter = defaultdict(int)
        left = 0  # левая граница окна

        for right in range(len(fruits)):  # правая граница окна
            right_fruit = fruits[right]
            type_counter[right_fruit] += 1

            # Когда в словаре становится 3 различных типа фруктов, сдвигаем левую границу окна
            # Это делается для того, чтобы в окне всегда было не больше 2 различных типов фруктов
            while len(type_counter) == 3:
                left_fruit = fruits[left]
                type_counter[left_fruit] -= 1
                if type_counter[left_fruit] == 0:
                    del type_counter[left_fruit]
                left += 1

            # Обновляем максимальную длину окна
            # Длина текущего окна равна (right - left + 1)
            res = max(res, right - left + 1)

        return res

Объяснение кода

  1. Инициализация:

    • res - переменная для хранения максимального количества фруктов.

    • type_counter - хэш-таблица для отслеживания количества каждого типа фруктов в текущем окне.

    • left - индекс левой границы окна.

  2. Основной цикл:

    • Проходим по массиву fruits с правой границей окна right.

    • Увеличиваем счетчик для текущего типа фрукта right_fruit.

  3. Уменьшение окна:

    • Если количество типов фруктов в окне превышает два (len(type_counter) == 3), сдвигаем левую границу окна вправо до тех пор, пока количество типов фруктов не станет допустимым (два или меньше).

  4. Обновление результата:

    • На каждой итерации обновляем res, вычисляя текущую длину окна (right - left + 1).

Визуализация решения

Рассмотрим массив fruits = [1, 2, 1, 2, 3, 3, 2, 1] и визуализируем шаги решения задачи, показывая текущее состояние скользящего окна.

Шаги выполнения:

Итерация 0:

  • Текущий фрукт: 1

  • Окно: [1], 2, 1, 2, 3, 3, 4, 1, 2

  • type_counter: {1: 1}

  • Длина окна: 1

Итерация 1:

  • Текущий фрукт: 2

  • Окно: [1, 2], 1, 2, 3, 3, 4, 1, 2

  • type_counter: {1: 1, 2: 1}

  • Длина окна: 2

Итерация 2:

  • Текущий фрукт: 1

  • Окно: [1, 2, 1], 2, 3, 3, 4, 1, 2

  • type_counter: {1: 2, 2: 1}

  • Длина окна: 3

Итерация 3:

  • Текущий фрукт: 2

  • Окно: [1, 2, 1, 2], 3, 3, 4, 1, 2

  • type_counter: {1: 2, 2: 2}

  • Длина окна: 4

Итерация 4:

  • Текущий фрукт: 3

  • Окно: [1, 2, 1, 2, 3], 3, 4, 1, 2

  • type_counter: {1: 2, 2: 2, 3: 1}

  • Длина окна: 5

  • Сокращение окна:

    • left: 1

    • Окно после сокращения: 1, [2, 1, 2, 3], 3, 4, 1, 2

    • type_counter: {1: 1, 2: 2, 3: 1}

    • Длина окна: 4

    • left: 2

    • Окно после сокращения: 1, 2, [1, 2, 3], 3, 4, 1, 2

    • type_counter: {1: 1, 2: 1, 3: 1}

    • Длина окна: 3

    • left: 3

    • Окно после сокращения: 1, 2, 1, [2, 3], 3, 4, 1, 2

    • type_counter: {2: 1, 3: 1}

    • Длина окна: 2

  • Окно после обновления результата: 1, 2, 1, [2, 3], 3, 4, 1, 2

  • Текущий максимум: 4

Итерация 5:

  • Текущий фрукт: 3

  • Окно: 1, 2, 1, [2, 3, 3], 4, 1, 2

  • type_counter: {2: 1, 3: 2}

  • Длина окна: 3

Итерация 6:

  • Текущий фрукт: 4

  • Окно: 1, 2, 1, [2, 3, 3, 4], 1, 2

  • type_counter: {2: 1, 3: 2, 4: 1}

  • Длина окна: 4

  • Сокращение окна:

    • left: 4

    • Окно после сокращения: 1, 2, 1, 2, [3, 3, 4], 1, 2

    • type_counter: {3: 2, 4: 1}

    • Длина окна: 3

  • Окно после обновления результата: 1, 2, 1, 2, [3, 3, 4], 1, 2

  • Текущий максимум: 4

Итерация 7:

  • Текущий фрукт: 1

  • Окно: 1, 2, 1, 2, [3, 3, 4, 1], 2

  • type_counter: {3: 2, 4: 1, 1: 1}

  • Длина окна: 4

  • Сокращение окна:

    • left: 5

    • Окно после сокращения: 1, 2, 1, 2, 3, [3, 4, 1], 2

    • type_counter: {3: 1, 4: 1, 1: 1}

    • Длина окна: 3

    • left: 6

    • Окно после сокращения: 1, 2, 1, 2, 3, 3, [4, 1], 2

    • type_counter: {4: 1, 1: 1}

    • Длина окна: 2

  • Окно после обновления результата: 1, 2, 1, 2, 3, 3, [4, 1], 2

  • Текущий максимум: 4

Итерация 8:

  • Текущий фрукт: 2

  • Окно: 1, 2, 1, 2, 3, 3, [4, 1, 2]

  • type_counter: {4: 1, 1: 1, 2: 1}

  • Длина окна: 3

  • Сокращение окна:

    • left: 7

    • Окно после сокращения: 1, 2, 1, 2, 3, 3, 4, [1, 2]

    • type_counter: {1: 1, 2: 1}

    • Длина окна: 2

  • Окно после обновления результата: 1, 2, 1, 2, 3, 3, 4, [1, 2]

  • Текущий максимум: 4

После всех итераций максимальное количество фруктов, которые можно собрать, равно 4.

Асимптотическая сложность

Сложность по времени: O(n)

  • Мы проходим по массиву fruits один раз с помощью правой границы окна (right).

  • В худшем случае левая граница окна (left) также проходит по каждому элементу массива один раз.

  • В результате, каждый элемент массива обрабатывается не более двух раз, что приводит к линейной временной сложности O(n), где n — длина массива fruits.

Сложность по памяти: O(1)

  • Мы используем хэш-таблицу type_counter для хранения количества каждого типа фруктов в текущем окне.

  • Максимальное количество различных типов фруктов в хэш-таблице ограничено двумя, так как у нас есть только две корзины.

  • Следовательно, количество памяти, необходимой для хранения данных в хэш-таблице, не зависит от размера входного массива и остается постоянным.

  • Это приводит к постоянной сложности по памяти O(1).

Комментарии (19)


  1. idsulik Автор
    27.07.2024 11:15
    #27093614

    Если ставите минус, то большая просьба отписаться, чтобы я знал что не так и мог исправить)
    Я всегда рад аргументированной критике


    1. Alexandroppolus
      27.07.2024 11:15
      #27093680

      Я не ставил минус, но формулировка задачи довольно мутная (если это перевод, то претензия не к вам, разумеется). Только из примера решения понял, что надо найти длину максимального непрерывного ряда деревьев, на котором не более двух видов фруктов.


      1. idsulik Автор
        27.07.2024 11:15
        #27093684

        Текстовая формулировка или на видео? На leetcode специально делают описание мутной, чтобы усложнить решение, тут я буквально процитировал, а на видео своими словами объяснил


        1. Alexandroppolus
          27.07.2024 11:15
          #27093690

          Текстовая. Видео не смотрел.


          1. idsulik Автор
            27.07.2024 11:15
            #27093712

            Там был перевод официального описания, ниже добавил упрощенную версию от себя, так лучше?)


        1. Politura
          27.07.2024 11:15
          #27094520

          А где ссылка на литкод? Если честно, не помню там задачек которые запутывают описаниями. А так, задачка решается просто за один проход без всякого окна, что-то типа такого:

              def totalFruit(self, fruits: List[int]) -> int:
        currentFruits = [-1, -1]
        flipIndex, currentLength, result = 0, 0, 0
        for i, fruit in enumerate(fruits):
            if fruit != currentFruits[0]:
                if currentFruits[1] >= 0 and fruit != currentFruits[1]:
                    currentLength = i - flipIndex
                flipIndex = i
                currentFruits = [fruit, currentFruits[0]]
            currentLength += 1
            result = max(result, currentLength)
        return result

          Наверняка можно упростить, делал массив currentFruits т.к. думал, что надо будет проверять условие fruit in currentFruits, но обошлось без него, так что можно отдельные переменные.


          1. wataru
            27.07.2024 11:15
            #27094560

            Ха, у вас очень интересная идея поддерживать не просто пару фруктов, а упорядоченную пару по позиции последнего дерева. Код так получается гораздо короче.


          1. idsulik Автор
            27.07.2024 11:15
            #27094598

            https://leetcode.com/problems/fruit-into-baskets/

            Описание:

            You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.

            You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

            • You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.

            • Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.

            • Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

            Given the integer array fruits, return the maximum number of fruits you can pick.


          1. idsulik Автор
            27.07.2024 11:15
            #27094614

            Отличное решение, спасибо что поделились.
            А задач на литкоде с запутанным описанием хватает) порой стоит чуть перефразировать и решение сразу приходит в голову


  1. wataru
    27.07.2024 11:15
    #27093668
    +4

    Объяснение кода - очень неудачное. Тут надо объяснить почему код работает, а не повторять код программы на человеческом языке. Нужно отвечать на вопрос КАК, а не ЧТО. Что код делает, итак видно.

    Стоило бы начать с наивного решения и по этапам ускорять его, в итоге прийдя вот к этому вот решению. Потому что вот так вот очень тяжело понять, почему делается именно так и как оно работает. Надо показать какие идеи и догадки позволяют прийти к решению этой задачи.

    А то получается какая-то черная магия, что если как-то вот так работать с окном, то оно работает. И вы на примерах это и демонстрируете, но не показываете никакого понимания сути решения. Такой подход не позволяет решать даже чуть чуть измененные задачи.

    В идеале, вообще хорошо бы решение еще и формально доказать (в смысле, человеческими рассуждениями и математикой, а не какой-то системой формальной верификации кода). Например, можно рассмотреть все множества собранных деревьев для всех возможных начал и доказать, что это отрезки из двух типов деревьев с каким-то третьим типом справа, и потом показать, почему вот этот вот код их все рассмотрит.


    1. idsulik Автор
      27.07.2024 11:15
      #27093676

      Я же как раз начинаю с наивного решения, показываю минус, а потом рассказываю про оптимальный вариант, показывают и рассказываю как это работает и только потом пишу код, тоже сначала наивный вариант, а потом уже оптимальный вариант.

      Но в целом очень полезный фидбек, спасибо большое! постараюсь учесть в будущих видео


      1. wataru
        27.07.2024 11:15
        #27093752

        Я же как раз начинаю с наивного решения, показываю минус

        В тексте этого не вижу.

        показывают и рассказываю как это работает и только потом пишу код

        Видео посмотрел теперь, там есть наивное решение, но нет никакого логического перехода к умному решению. И плюс вижу там тоже самое: объяснения уровня "вот у нас цикл", "добавляем в set", "в этом случае выходим из внутреннего цикла". Опять лишь пересказывание кода, а не объяснение его. Никакого объяснения идей.

        И во время написания кода у вас таже самая проблема: делаем итерацию, берем максимум, добавляем в set.

        Ваши объяснения должны быть про концепции и абстракции. Например: двигаем правую границу окна, фактически перебирая все возможные варианты конца отрезка собранных деревьев. Если в окне более 2 типов деревьев, то его надо сократить, дивгая левую границу. Так мы получим самое длинное из возможных корректных окон с этим концом. Ведь левая граница не может быть левее предыдущего окна, потому что оно тогда бы целиком лежало в новом, а значит предыдущее было бы не самым длинным.


        1. idsulik Автор
          27.07.2024 11:15
          #27094214

          Постараюсь поработать над этим, потому что даже такое "сырое" объяснение удается с трудом, после каждого видео на 10-15 минут, у меня в корзине собирается больше 100 неудачных дублей) Видимо пока опыта не хватает, в будущем планирую перезаписывать старые видео, но уже с лучшим качеством и с более опытным объяснением


  1. Ardni0
    27.07.2024 11:15
    #27094216
    +1

    По сути задача сводится к нахождению самой длинной последовательности из двух чисел. И вроде как для такой задачи достаточно только 4 интов и одного цикла. То есть мы начинаем с одного фрукта запоминаем тип, потом встречаем второй, запоминаем тип, и, ключевое, что при каждой смене типа фрукта запоминаем индекс начала новой цепи новых фруктов (то есть последовательности одинаковых чисел) пусть будет z0. Когда встречаем третий тип (не равный двум предыдущим) записываем максимум цепи, и новую цепь начинаем с z0 (начало последней череды одинаковых символов). То есть по сути отличие в том что мы сразу знаем от куда начинать нам не надо сокращать левую границу она всегда известна.


    1. idsulik Автор
      27.07.2024 11:15
      #27094222

      Будет круто, если напишете код, звучит очень интересно, но до конца не понял и вряд ли смогу написать код.


    1. wataru
      27.07.2024 11:15
      #27094278
      +1

      Вообще да. Вы правы, что не надо сдвигать левую границу по одному дереву. Надо сдвинуть сразу так, чтобы целиком выкинуть один из типов фруктов. Т.е. сдвинуться на последнюю позицию из двух фруктов.

      Я сначала не понял ваш комментарий, подумал что вы предлагаете при третьем фрукте начинать с пустого отрезка, и написал код, как делать правильно. Но у вас тоже самое же, оказывается. Но раз код уже написал, пусть будет комментарий.


      @idsulik вы хотели код этого решения, вот он:

      int active_type[2] = {-1, -1};  // типы фруктов в корзинах.
int last_pos[2] = {0, 0};  // позиция последнего дерево этого типа пока что.
int start_pos = 0;  // начало текущего отрезка максимум с 2 типами фруктов.
int result = 0;  // тут считаем ответ.
for (size_t i = 0; i < a.size(); ++i) { 
  int &cur_type = a[i];
  // Можно занять пустую корзину.
  if (active_type[0] == -1) active_type[0] = cur_type;
  else if (active_type[0] != cur_type && active_type[1] == -1) active_type[1] = cur_type;
  // Если есть корзина для этого фрукта - кладем туда.
  if (cur_type == active_type[0]) {
    last_pos[0] = i;
    continue;
  }
  if (cur_type == active_type[1]) {
    last_pos[1] = i;
    continue;
  }
  // Корзины нет, надо выбросить один из двух фруктов.
  // Считаем текущий отрезок как вариант ответа.
  result = max(result, i - start_pos);
  // Выбросим тот фрукт, который закончился левее в отрезке.
  // После этой позиции есть только второй фрукт.
  const int removed_type = (last_pos[0] < last_pos[1]) ? 0 : 1;
  active_type[removed_type] = cur_type;
  start_pos = last_pos[removed_type] + 1;
  last_pos[removed_type] = i;
}
// Не забываем обработать последний отрезок.
return max(a.size() - start_pos, result);

      Edit: Вот эти комментарии, это как раз то, что надо писать в статье. Тут нет фразы "делаем цикл", "выходим из цикла" или "записываем в start_pos значение +1". Тут написано почему делается вот это вот. В терминах задачи. Примерно так и стоит вам делать в ваших видо и статьях, только по-подробнее.


      1. idsulik Автор
        27.07.2024 11:15
        #27094438

        это какой-то следующий уровень, круто, спасибо!

        Насчет комментариев, согласен, учту!


  1. Alexandroppolus
    27.07.2024 11:15
    #27095598
    +1

    Главный плюс решения автора в том, что оно легко, прямо вот "из коробки", обобщается на случай k корзин, оставаясь O(n) по скорости и O(k) по памяти. Достаточно заменить == 3 на > k, и всё. А решениям из комментариев для этого потребуется изрядный напильник.


    1. idsulik Автор
      27.07.2024 11:15
      #27095682

      У каждого свои плюсы и минусы) в задаче сказано про две корзины и для этой задачи решение из коммента более оптимально, но если речь про заложить фундамент на будущее или решить задачу на интервью, то мой подход лучше, т.к. легче