Evgeniy
Каким-то образом прошла по времени
Uladzimir
Каждый элемент может хранить в себе знания о том сколько дней до него было с <= ценой, когда встречается следующий день, то мы можем снять со стека предыдущий день и достать оттуда чиселку сколько consecutive дней было меньше до него и всё: добавить для текущего значения и положить на стек. Таким образом не надо постоянно бегать назад и проверять сколько же чисел меньше данного. Это снижает сложность с O(N^2) до O(N), в худшем случае придётся накопить и размотать весь стек целиком один раз, ну и память O(N) под стек.
O(n) под стек из-за того, что его длина зависит от n? сорри за нубские вопросы 🙂
Viktor
O(n) под стек из-за того, что его длина зависит от n? сорри за нубские вопросы 🙂
Ага, типа в худшем случае придётся положить в стек все элементы, но не более
Evgeniy
У вас сколько по времени получилось?
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Короче как я понял. эту задачку на плючах бессмысленно решать
Порридж В Ко-ливинге
Или у меня руки не от туда (я на плюсах 2ой месяц прогаю всего)
Порридж В Ко-ливинге
Или На JS хорошо оптимизировалли
Порридж В Ко-ливинге
Ну не такая сложная, как изначально казалось, мне казалось такая простая “оптимизация” не поможет
Порридж В Ко-ливинге
Uladzimir
пока последовательность возрастает, надо на стек складывать, как только возрастание прерывается, надо размотать и сложить на стек последнюю цену + чиселку, которая показывает как раз длину этого отрезка, на будущее.
я что-то за вчера так и не догнал, как это сделать
тот же пример из [100, 80, 60, 70, 60, 75, 85] разбивает это суммирование. попадается 85 - и надо все равно заново по всему стеку идти и проверять, что толку, что ты знаешь сумму на 75, если добавляется еще 80?
Порридж В Ко-ливинге
Uladzimir
о, не дочитал)
Порридж В Ко-ливинге
Да, просто там постоянно должны быть числа меньше
Порридж В Ко-ливинге
Т.е. в порядке уменьшения
Uladzimir
а все, возврастающую последовательность просто заменять на один элемент стека, вот оно что
Порридж В Ко-ливинге
Да
Uladzimir
а я все думал рядом с числом результат до этого числа кэшировать, но все равно получалось, что надо все заново просчитывать
Uladzimir
супер, ща попробую переделать. с обычным стеком тоже прошло
Viktor
Не мудрствуя лукаво сегодняшнюю задачу решил через dfs + stack, наверняка, там можно без дополнительной памяти, но уже не кайф думать 🙁
Viktor
точнее не так, без дополнительной нельзя, т.е. надо дерево обходить, но без стека.
Evgeniy
https://leetcode.com/problems/kth-smallest-element-in-a-bst/discuss/642056/C-O(n)-iterative-and-recursive-DFS-solutions
Evgeniy
Решение без стека по времени немного быстрее
Evgeniy
Возможно из-за недостаточно сложных проверочных тестов
Evgeniy
https://leetcode.com/problems/implement-magic-dictionary/description/
Evgeniy
Как бы вы эту задачу решали?
Evgeniy
Мне пока пришло в голову только хранение строки в Trie с прямым и с обратным порядком символов.
Viktor
Я тоже подумал про Trie. Представь, что ты бежишь по префиксу и если у тебя буква очередная не нашлась, ты ее пропускаешь и бежишь дальше - если добежал молодец, нашёл слово, если и дальше где-то споткнулся значит уже надо как минимум 2 символа удалить и можно останавливаться.
Viktor
Типа примерно так же как поиск в обычном trie только с правом на ошибку ровно один раз.
Viktor
Хотя не совсем, я гоню - там не удалить разрешается, а поменять на другой символ.
Viktor
Тогда нужен backtracking.
Viktor
Там где споткнулся - надо пробежаться по всем деткам и проверить вдруг там слово найдётся.
Evgeniy
Вообще эта задача предлагалась после Implement Trie
Viktor
Любопытная задачка. Доберусь до лаптопа попробую реализовать вот как выше написал.
Viktor
Согласен с идеей?
Evgeniy
Там где споткнулся - надо пробежаться по всем деткам и проверить вдруг там слово найдётся.
Ну кстати да... Вариант с пропуском вполне подходит!
Viktor
Мне пока пришло в голову только хранение строки в Trie с прямым и с обратным порядком символов.
А зачем обратный порядок?
Evgeniy
А зачем обратный порядок?
Чтобы пройтись два раза, в разные стороны, и надеяться, что в итоге мы дойдем до одной и той же несовпадающей буквы
Evgeniy
И ещё длину придётся считать
Evgeniy
Чтобы leftToRight.Len + rightToLeft.Len + 1 = string.Len
Evgeniy
Как то вот так
Viktor
Ну, кстати, может сработать.
Viktor
Ну кстати да... Вариант с пропуском вполне подходит!
попробовал закодить. пропустил важное условие — надо не 0 или 1 изменение, а ровно одно изменение. т.е. если слово просто матчится в словаре, то это false. и сыплюсь на кейсе когда в словаре hallo и hello, слово для проверки hello, типа если бы не было hallo, то это false, но раз он есть, то можно e поменять на a и это уже true
Viktor
классная задачка, короче 😄
Evgeniy
Во, как. И правда этот вариант не рассматривали)
Порридж В Ко-ливинге
Порридж В Ко-ливинге
ЭТО ПРАНК!?
Viktor
@Glazomer47 в чем прикол?
Порридж В Ко-ливинге
лол. не имею понятия почему это работает 😄
Там же в примере все числа от 1 до max
Порридж В Ко-ливинге
Ну, я думаю: “опять конченные примеры указали”
Viktor
это конечно очень смешно. вроде явно в условии это не сказано было 😄
Viktor
но если бы было указано явно, то отличное решение.
Порридж В Ко-ливинге
“Давай по реалистичнее, буду возвращать k, пока не будет норм примера”
Порридж В Ко-ливинге
Потом былпример с 0
Порридж В Ко-ливинге
Я решил на него проверку сделать
Порридж В Ко-ливинге
И ОБАНА! 🤣
Порридж В Ко-ливинге
Все, прошел
Viktor
🔥
Порридж В Ко-ливинге
Так и не дошел до примеров хороших 🤣🤣
Viktor
ну что, сегодня дпшечка 😄
Viktor
good luck 😄
Evgeniy
! проверяет на положительное число и возвращает 1?
Viktor
Есть исключение с нулем, правда