Комментарии 19
Если ставите минус, то большая просьба отписаться, чтобы я знал что не так и мог исправить)
Я всегда рад аргументированной критике
Я не ставил минус, но формулировка задачи довольно мутная (если это перевод, то претензия не к вам, разумеется). Только из примера решения понял, что надо найти длину максимального непрерывного ряда деревьев, на котором не более двух видов фруктов.
Текстовая формулировка или на видео? На leetcode специально делают описание мутной, чтобы усложнить решение, тут я буквально процитировал, а на видео своими словами объяснил
Текстовая. Видео не смотрел.
А где ссылка на литкод? Если честно, не помню там задачек которые запутывают описаниями. А так, задачка решается просто за один проход без всякого окна, что-то типа такого:
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, но обошлось без него, так что можно отдельные переменные.
Ха, у вас очень интересная идея поддерживать не просто пару фруктов, а упорядоченную пару по позиции последнего дерева. Код так получается гораздо короче.
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.
Отличное решение, спасибо что поделились.
А задач на литкоде с запутанным описанием хватает) порой стоит чуть перефразировать и решение сразу приходит в голову
Объяснение кода - очень неудачное. Тут надо объяснить почему код работает, а не повторять код программы на человеческом языке. Нужно отвечать на вопрос КАК, а не ЧТО. Что код делает, итак видно.
Стоило бы начать с наивного решения и по этапам ускорять его, в итоге прийдя вот к этому вот решению. Потому что вот так вот очень тяжело понять, почему делается именно так и как оно работает. Надо показать какие идеи и догадки позволяют прийти к решению этой задачи.
А то получается какая-то черная магия, что если как-то вот так работать с окном, то оно работает. И вы на примерах это и демонстрируете, но не показываете никакого понимания сути решения. Такой подход не позволяет решать даже чуть чуть измененные задачи.
В идеале, вообще хорошо бы решение еще и формально доказать (в смысле, человеческими рассуждениями и математикой, а не какой-то системой формальной верификации кода). Например, можно рассмотреть все множества собранных деревьев для всех возможных начал и доказать, что это отрезки из двух типов деревьев с каким-то третьим типом справа, и потом показать, почему вот этот вот код их все рассмотрит.
Я же как раз начинаю с наивного решения, показываю минус, а потом рассказываю про оптимальный вариант, показывают и рассказываю как это работает и только потом пишу код, тоже сначала наивный вариант, а потом уже оптимальный вариант.
Но в целом очень полезный фидбек, спасибо большое! постараюсь учесть в будущих видео
Я же как раз начинаю с наивного решения, показываю минус
В тексте этого не вижу.
показывают и рассказываю как это работает и только потом пишу код
Видео посмотрел теперь, там есть наивное решение, но нет никакого логического перехода к умному решению. И плюс вижу там тоже самое: объяснения уровня "вот у нас цикл", "добавляем в set", "в этом случае выходим из внутреннего цикла". Опять лишь пересказывание кода, а не объяснение его. Никакого объяснения идей.
И во время написания кода у вас таже самая проблема: делаем итерацию, берем максимум, добавляем в set.
Ваши объяснения должны быть про концепции и абстракции. Например: двигаем правую границу окна, фактически перебирая все возможные варианты конца отрезка собранных деревьев. Если в окне более 2 типов деревьев, то его надо сократить, дивгая левую границу. Так мы получим самое длинное из возможных корректных окон с этим концом. Ведь левая граница не может быть левее предыдущего окна, потому что оно тогда бы целиком лежало в новом, а значит предыдущее было бы не самым длинным.
Постараюсь поработать над этим, потому что даже такое "сырое" объяснение удается с трудом, после каждого видео на 10-15 минут, у меня в корзине собирается больше 100 неудачных дублей) Видимо пока опыта не хватает, в будущем планирую перезаписывать старые видео, но уже с лучшим качеством и с более опытным объяснением
По сути задача сводится к нахождению самой длинной последовательности из двух чисел. И вроде как для такой задачи достаточно только 4 интов и одного цикла. То есть мы начинаем с одного фрукта запоминаем тип, потом встречаем второй, запоминаем тип, и, ключевое, что при каждой смене типа фрукта запоминаем индекс начала новой цепи новых фруктов (то есть последовательности одинаковых чисел) пусть будет z0. Когда встречаем третий тип (не равный двум предыдущим) записываем максимум цепи, и новую цепь начинаем с z0 (начало последней череды одинаковых символов). То есть по сути отличие в том что мы сразу знаем от куда начинать нам не надо сокращать левую границу она всегда известна.
Будет круто, если напишете код, звучит очень интересно, но до конца не понял и вряд ли смогу написать код.
Вообще да. Вы правы, что не надо сдвигать левую границу по одному дереву. Надо сдвинуть сразу так, чтобы целиком выкинуть один из типов фруктов. Т.е. сдвинуться на последнюю позицию из двух фруктов.
Я сначала не понял ваш комментарий, подумал что вы предлагаете при третьем фрукте начинать с пустого отрезка, и написал код, как делать правильно. Но у вас тоже самое же, оказывается. Но раз код уже написал, пусть будет комментарий.
@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". Тут написано почему делается вот это вот. В терминах задачи. Примерно так и стоит вам делать в ваших видо и статьях, только по-подробнее.
Главный плюс решения автора в том, что оно легко, прямо вот "из коробки", обобщается на случай k корзин, оставаясь O(n) по скорости и O(k) по памяти. Достаточно заменить == 3 на > k, и всё. А решениям из комментариев для этого потребуется изрядный напильник.
Решение задачи с собеседования Fruit Into Baskets [+ ВИДЕО]