Решение задачи с собеседования Fruit Into Baskets [+ ВИДЕО]
Постановка задачи
Вы посещаете ферму, на которой деревья выстроены в один ряд слева направо. Деревья представлены целочисленным массивом fruits, где fruits[i] — это тип фруктов на i-ом дереве.
Вы хотите собрать как можно больше фруктов, но владелец фермы установил следующие правила:
У вас есть две корзины, каждая из которых может содержать только один тип фруктов.
В каждой корзине может быть неограниченное количество фруктов.
Начиная с любого дерева, вы должны собирать фрукты с каждого дерева (включая стартовое), двигаясь вправо.
Если вы встречаете дерево, фрукты которого не могут поместиться в ваши корзины, вы должны остановиться.
Задача состоит в том, чтобы найти максимальное количество фруктов, которые можно собрать, соблюдая эти правила.
Подход к решению
Для решения задачи мы будем использовать технику «скользящего окна» (sliding window) и хэш-таблицу для отслеживания количества каждого типа фруктов в текущем окне.
Алгоритм
Инициализация переменных:
resдля хранения результата (максимальное количество фруктов).type_counterдля отслеживания количества каждого типа фруктов в текущем окне.leftдля обозначения левой границы окна.
Проход по массиву
fruits:Используем переменную
rightдля обозначения правой границы окна.Увеличиваем счетчик для текущего типа фрукта
right_fruit.
Проверка условия допустимости окна:
Если количество типов фруктов в окне становится больше двух (
len(type_counter) == 3), сдвигаем левую границу окнаleftвправо, уменьшая счетчики для фруктов и удаляя типы фруктов с нулевым счетчиком.
Обновление результата:
Код решения
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
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
res = max(res, right - left + 1)
return resОбъяснение кода
Инициализация:
res— переменная для хранения максимального количества фруктов.type_counter— хэш-таблица для отслеживания количества каждого типа фруктов в текущем окне.left— индекс левой границы окна.
Основной цикл:
Уменьшение окна:
Если количество типов фруктов в окне превышает два (
len(type_counter) == 3), сдвигаем левую границу окна вправо до тех пор, пока количество типов фруктов не станет допустимым (два или меньше).
Обновление результата:
Визуализация решения
Рассмотрим массив 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).
