Если правильно понимаю, в некоторых случаях операции с хешем могут стремиться к O(logN)=> общее время будет приближаться к O(N*logN). Где N- длинна строки т.к. операции выполняются дважды, а размер сета в худшем случае будет N/2 (Среднее членов арифметической прогрессии(An+A1)/2). 1/2*2=1 П.с. Часа полтора потратил что бы понять что что-бы решит проблему коллизий при хешировании нам надо выделять примерно "очень много" памяти на каждый сет, установить жесткое ограничение в размере строки и используемом наборе символов а так же тратиться на сжать/разжать данные в этой строке
Саша, спасибо за разборы. Косательно этого решения догадался про указатель `right`, что нет смысла увеличивать его, но не догадался про перемещение left.
Кстати на днях сидел решал эту задачу на leetcode , и она у меня не прошла последний тест из-за Time Limit Exceeded (986 / 987 testcases passed). Мой подход был такой - я собирал все уникальные подстроки (в отдельном методе я проверял что подстрока состоит из уникальных символов) в лист и затем с помощью компаратора сортировал по длине и возвращал длину последнего элемента
@@ghostlynomad7788 не мудрено, что по времени не прошел. Мало того, что собирал лист со сложностью n в квадрате, а то и n в кубе, так потом еще и добавил n*log(n) (я про сортировку). Ничего медленнее мне кажется тут уже не придумать))
Саша, привет! Спасибо за интересное видео. Единственное, ты слегка меня запутал когда сказал, что "удаляем, пока в сете есть повторяющиеся символы" - по факту, в сете они не повторяются. Наверное, лучше было бы сказать что удаляем, пока не удалим ПОВТОРИВШИЙСЯ символ)
простой перебор можно сократить и до n^2, если просто обновлять сет после первого цикла а is_acceptable = True оставить на своём месте. ну и третий цикл можно будет убрать. На лит коде даже заработало. Для скользящего окна вот ещё альтернатива, с помощью словаря на python: def longest_substr(s): answer = 0 left = 0 hash_set = {} for right in range(len(s)): char = s[right] if char in hash_set and hash_set[char] >= left: left = hash_set[char] + 1 else: answer = max(answer, right - left + 1) hash_set[char] = right return answer Спасибо за видео
И даже еще проще брутфорс можно сделать - вообще без этого is_acceptable, просто если в сете есть новая буква, то выходим из второго цикла, а потом проверяем больше ли сайз нашего сета, чем наш ответ и все.
Привет, хотел выразить тебе огромное спасибо. Посмле просмотра видео про гугл и инжерена. Мне вернулся дух программиста. Начал вести фриланс и параллельно изучаю собесы
Очень хорошо объясняешь, респект. Алгоритм полного перебора можно немного оптимизировать, если не перебирать тупо все подстроки, а начинать с самой большой и двигаться к уменьшению, или, если уже нашли подстроку длиной 3, рассматривать только большие, это чуть-чуть сократит затраты, но, конечно, не будет лучше, чем скользящий алгоритм.
что-то я не понял, на 5:13 мы проверяем и удаляем символы, на которые указывает left, но в алгоритме на java на 7:53 мы проверяем в while символ, на который указывает right, а не left. почему так? объясните, пожалуйста
не понял на 5:16 говорится "удаляем пока в подстроке нету повторяющихся символов", хотя указатель на left - С и в подстроке остается С, тоесть они указывают на одинаковый символ , почему его он не удаляется как все предыдущие?
Когда это два указателя стали чем-то удивительным(учусь в школе, смотрел пару записей собесов, почти в каждом были два указателя, так что думал, что это база)
Я конечно дико извиняюсь, но это круто и изящно! Придумал на лету тоже вариант O(n), но он немного сложнее и кушает больше памяти - на каждый индекс массива создавать отдельный сет и добавлять в него пока "дубль" символа не встретится. Метод скользящего окна намного красивее!
Спасибо за видео! Сам около года назад сидел плотно в литкоде, задачи на скользящее окно были одними из любимых) Увидел условие, решил проверить сам себя, решу ли ее сейчас. Минут за 5 решил, не с первого раза, сначала подзабыл немного последовательность действий, пошел по неправильному пути. Оставлю тут свое решение (на js правда), оно немного отличается от решения в видео (вместо двух while у меня for и внутри него while, ну и без if/else, более линейно) function maxLen(str) { let maxLen = 0 let left = 0 const uniques = new Set() for (let right = 0; right < str.length; right++) { const current = str[right] while(uniques.has(current)) { uniques.delete(str[left]) left++ } uniques.add(current) maxLen = Math.max(maxLen, right - left + 1) } return maxLen } console.log(maxLen('axbxcxd')) // 3
Подумав, решил методом похожим на скользящее окно, правда вместо указателей я бы воспользовался List(C#, System.Collections.Generic), но не уверен, что List подойдёт по оптимизации лучше и сопоставимо, чем указатели. Спасибо за видео.
Клевый способ. А можно подгонкой размеров окна подобным способом находить всякие локальные максимумы, точки перегиба и прочее на каком ть временном ряде? По скольку они там формируются в вообще произвольной периодичностью.. ))) Было бы как раз...
Спасибо за видео! У меня появился вопрос касательно быстрого решения. В видео говорится, что скорость O(n), но ведь по сути мы используем два цикла, один из которых вложен. представим, что в функцию отдается строка из одинаковых символов и тогда во все итерации кроме первой будет падать во вложенный цикл. а на сколько я помню скорость считается исходя из худшего случая. Почему в этом случае скорость O(n)? буду очень благодарен за ответ!
Возник тот же вопрос, задал его chatGPT и он ответил, что "каждый символ строки рассматривается и обрабатывается один раз либо указателем right, либо указателем left.
Быстрое решение вроде как упрощенно "два указателя"(не шарю в алгоритмах). Но мне показалось, что когда мы пришли к повтору, то нет нужды уменьшать окно, можно двигать вправо ОБА указателя одновременно, ведь нас не интересуют размеры подстрок меньше максимальной из уже найденных. Вопрос правда реализуемо ли это(эффективнее), т.к. второй пункт(сужение) выполняет задачу убрать дубль. Чтобы продемонстрировать логику, на питоне: def longest_substring(s): left = 0 for right in range(len(s)): if len(set(s[left: right + 1]))
У интерфейса Set, метод add и так делает проверку на наличие, можно лишний раз не вызывать contains. public static int longestSubstring(String in) { int max = 0; LinkedHashSet set = new LinkedHashSet(); for (char c : in.toCharArray()) { while (!set.add(c)) { max = Math.max(max, set.size()); set.removeFirst(); } } return Math.max(max, set.size()); }
Приветствую, во втором случае можно немного оптимизировать решение: предположим, что есть текущая уникальная подстрока и мы нашли следующий неуникальный символ, если размер "хвоста" меньше чем размер найденной подстроки, то можно прекратить поиск и вернуть результат. Очевидно, что выигрыш невелик, но все же.
Я бы построчным вводом добавлял , сортировал массив и сравнивал первую и вторую позиции и как только они равны записал бы размер массива-1, а потом начинал бы со второго символа.
Первое, что пришло в голову, это то, что Вы назвали "метод скользящего окна". Я бы, наверное, это писал на компилируемом языке, если бы такое было позволено.
Это решение более эффективно, чем предложенное автором. class Solution: def lengthOfLongestSubstring(self, s: str) -> int: d = {} i, j = 0, 0 ans = 0 while j
Эффективно только, если рассматривать с позиции лаконичности записи. У меня словарь тоже был первой идеей из-за возможности хранить индекс по ключу символа, но что-то меня смутило и в итоге быстро переделал через сет, почти 1 в 1 как у Саши с небольшой незначительной поправкой. Реализация со словарём конечно красива, и строчек кода на две меньше, ввиду отсутствия цикла удаления ненужных ключей, но перфоманс у неё хромает. Для лучшего случая по скорости на 20% хуже сета, в среднем в 2 раза медленнее, а для худшего случая решение со словарём медленнее почти в 4 раза. Это конечно все равно и тут, и там O(N), но такая разница немного удивила. Но не привыкать, в питоне не все то, что красивее выглядит, быстрее работает, зачастую как раз наоборот.
Без лишних слов, Превосходный контент и знания! СПАСИБО!!!! Вопрос: Английский вариант названия алгоритма "метод скользящего окна" ? The Sliding window ?
@@МихаилТихомиров-м8ч принято считать что работа с сетом это константа. адепты лога будут негодовать, но на деле, чтобы сет постоянно уходил в лог - это надо нехило так постараться. плюс надо точно знать, а что под капотом у данной конкретной реализации сета, вдруг там реально обычное дерево, а не хэшмап. обычно совмещают оба два сразу. ну а в данной задачке, если символы ограничены - то можно реализовать свой собственный сет, который будет абсолютной константой, к которой уже невозможно будет придраться.
@@SayXaNow ну вообще джавовский hashset это как раз О(1), насчет пайтона я не знаю. Просто это может быть вопрос на засыпку от интервьювера, стоит об этом помнить.
Хочу поделиться своим решением, на момент ответа видео не досмотрел. Сравниваем элементы с помощью бинарного дерева. В цикле начинаем сравнивать , если элемент меньше идём в лево, если равно continue. Если след узел null то тогда записываем в дерево элемент и увеличиваем count ++. После цикла выводим count. У нас получится уникальное бинарное дерево, с счётчиком count.
Мне кажется что первый алгоритм выполняет не n в кубе операций , а (n+n*n) /2 так как right пробегает от i до n символа, где i - положение left; у второго алгоритма максимальная скорость O(n) , а минимальная O(n*n) потому что right точно пробежит один раз строку, а left может остаться в начале (если все символы разные) или пробежать все символы (если все символы одинаковы) P. S. Укажите если не прав
О да, это очень классный алгоритм. Его еще называют методом двух указателей. Все, кто к ЕГЭ по информатике готовится, учат его, довольно эффективный и гибкий алгоритм
Насколько я понимаю, удаление с начала масива очень долгое, потому что нужно создать другой масив и перекопировать все значения в него. Поэтому, когда у нас будет очень длинная подстрока, придётся много раз пересоздавать масив внутри сета. Лучше уж после каждой итерации поставить проверку (result < right - left + 1). Но может сет в Java работает не так как я думаю, надеюсь на отзыв.
можно просто 1 раз идти по масиву и добавлять колличество уникальних елементов до первого повоторения в новий масив, потом повторять подсчет с последнего уникального елемента, а потом просто взять наибольшое число нового масива.
Неплохое решение, но вот другое - за один проход, запоминая последний индекс символа. Swift: func lengthOfLongestSubstring(_ s: String) -> Int { var map: [Character: Int] = [:] var result = 0 var left = 0 for (i, c) in s.enumerated() { if let j = map[c] { left = max(left, j + 1) } result = max(result, i - left + 1) map[c] = i } return result }
Попросил ИИ переписать на АХК скрипт +вернуть саму строку: lengthOfLongestSubstring(s, ByRef longestSubstring = ""){ map := {} result := 0 left := 0 longestSubstring := ""
Loop, Parse, s { c := A_LoopField if (map.HasKey(c)) { left := Max(left, map[c] + 1) } result := Max(result, A_Index - left) map[c] := A_Index - 1 if result longestSubstring := SubStr(s, left, result) } } return result }
на java public class LongestSubstringLength { public static int lengthOfLongestSubstring(String s) { HashMap map = new HashMap(); int result = 0; int left = 0; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (map.containsKey(c)) { left = Math.max(left, map.get(c) + 1); } result = Math.max(result, i - left + 1); map.put(c, i); } return result; }
есть способ в котором только r будет один раз пройтись по строке, этот код работает за O(n), а не O(2n). Но это почти ничего не меняет. def solve(n,s): ans=0 l,r=0,0 hash_mp={} while r
Я на практике редко пользуюсь конструкцией while. В 1 проценте случаев) Можно еще решить вот так. Решение без скользящего окна. Хотя суть очень похожа. fun getMaxUniqueWithSet(input: String): Int { var maxSequence = 0 val set = mutableSetOf() input.forEach { c -> if (set.contains(c)) { if (set.size > maxSequence) { maxSequence = set.size } set.clear() } set.add(c) } return max(maxSequence, set.size) }
а этот алгоритм разве не называется методом двух указателей? насколько я знаю из подготовки к егэ, скользящее окно -- это метод, при котором в какую-то сумму непрерывной подпоследовательности добавляется следующий элемент и вычитается из неё самый первый, так, экономно можно сдвигать интервал, в котором считается сумма, по массиву данных
остановил на 2:07 и мне показалось что первое очевидное решение на самом деле сложное и неочевдиным, очевидным решением для меня пробежаться по всем символам с хэшсетом накапливая его и фиксируя максимальный результат при наличии символа уже в нём, при этом сбрасывая его и возвращаясь назад на величину r-1, сча посмотри какое решение предложит автор
@sashalukin, а почему это считается O(n) если в худшем случае понадобится в понадобится 2 раза полностью проходить по каждому символу строки? получается O(n^2)
Интересно, что этот алгоритм начали спрашивать сейчас. Решал его еще года 3-4 на леткоде тогда он мне попался где-то 5 по счету. То что додумался до решения сам конечно тешет мое самолюбие. Но вот то что часа полтора два у меня ушло чтобы выдать рабочий код на go нет).
Прикольно. Лайк. Я только погружаюсь в программирование. Будет ли полезно в первом цикле (где увеличиваем подстроку) не прогонять её по минимальным значениям а сразу увеличить на Макс. Длинну, уже записанную в сет? Так мы пропустим (в данном примере) проверку сетов cb и db.
@furtherance6042 если я тебя правильно понял, то, если ты будешь пропускать символы, тогда сет не будет хранить все символы подстроки => ты можешь не понять, что случился повтор
Цифры Пифагора. Если у треугольника длины сторон 3, 4 и 5 метров, то он -- прямоугольный. Или 6, 8 и 10 метров. И т. д. Эти волшебные цифры позволяют на местности рисовать прямые углы. Размечать местность под фундамент, например.
Почему последний алгоритм работает за O(N)? Я не разбираюсь в подсчете продолжительности процессов и мне казалось, что добавление цикла увеличивает степень на 1, а тут как раз 2 цикла
1. Непонятно зачем использовать set если мы можем пройтись по уже существующей строке 2. Удаление пока не пропадут все повторяющиеся символы? Если ты добавляешь 1 символ, то куда проще будет проверить повторяется ли этот символ и потом найти индекс первого вхождения и удалить все символы до него
@@tonylayz тот while выполнится не более N раз за всю работу кода, следовательно его плюсуют к N, а не умножают на N. А твой проход выполнятся будет в среднем N/2 за каждую итерацию внешнего цикла, поэтому его умножают на N.
тоже не самое быстрое решение, можно создать словарь, в котором будет храниться индекс последнего элемента, имеющего такое значение, что нынешний, на котором, находится правый указатель(по умолчанию поставим индекс -1, для проверки, либо множество опять же используем). Соответственно нам теперь не нужно постоянно перемещать левый указатель на 1, а мы сразу переместим его на нужный индекс, с которой начинается подходящая подстрока
@@Oldy573 разве? в такой задаче максимальная длина у строки будет 256 или 128, не помню. Вот если взять какую-нибудь другую вариацию, то да, ошибка будет
но вы же второй при перемещении left тоже опять перебираете, не проще ли использовать std::map, хранить там позицию символа и сразу смещать позицию на искомый символ+1
а можно вместо set завести массив длинной в алфавит и держать в нем последний индекс, содержащий данную букву. Двигаем правый указатель, смотрим, была ли текущая буква в окне, если нет - запоминаем, идем дальше. Если буква была - стоп, проверяем, не больше ли текущее окно лучшего, если нашли лучшее - запоминаем окно и переставляем левый указатель сразу после буквы, которая повторилась. по сути - то же, но не надо двигать левый указатель по одному шагу, ну и обратиться к массиву - быстрее, чем добавлять-убирать из сета.
можно даже не индекс, а просто true, если встретилась и false, если нет. boolean меньше памяти занимает (хотя у тебя немного побыстрее работает). Потом в цикле проверяешь, если текущая буква уже встречалась, то двигаешь левый указатель, пока не уберешь предыдущее вхождение
@@jaggman2134 честно говоря, у меня старая нелюбовь к хашмэпам, несколько раз сталкивался с тем, что сет на хэше работает в разы медленнее, чем обычный сет (вероятно на дереве). Если храним строки, получение хэша пробегает каждую строку до конца, а сравнение на < обычно кончается на первой же букве.
Спасибо за видео. Какой инструмент используется для демонстрации ? Очень удобно отображать скрытый код при нажатии. Сам часто делаю тех презентации и такой инструмент очень бы сильно помог, а то ливкодинг глючит )))
Создал Telegram канал, в котором рассказываю о работе в Google, подготовке к собеседованиям и жизни в Лондоне. Подписывайтесь: t.me/saschalukin
Саша, сделай уже, плз, плейлисты на канале☝🏼☝🏼 С задачами, пр. и тд. Скомпонуй видосы.
Оаоаао что это?! Метод двух указателей!
Если правильно понимаю, в некоторых случаях операции с хешем могут стремиться к O(logN)=> общее время будет приближаться к O(N*logN). Где N- длинна строки т.к. операции выполняются дважды, а размер сета в худшем случае будет N/2 (Среднее членов арифметической прогрессии(An+A1)/2). 1/2*2=1
П.с. Часа полтора потратил что бы понять что что-бы решит проблему коллизий при хешировании нам надо выделять примерно "очень много" памяти на каждый сет, установить жесткое ограничение в размере строки и используемом наборе символов а так же тратиться на сжать/разжать данные в этой строке
один из редких каналов, где разбирают и объясняют по-человечески без лишнего пафоса. жду с нетерпением каждого разбора.
Как же я долго ждал нового видео, спасибо тебе огромное! Вот бы они выходили чаще)
Саша, спасибо за разборы.
Косательно этого решения догадался про указатель `right`, что нет смысла увеличивать его, но не догадался про перемещение left.
spasibo, Sasha za detalniy razbor. Видосы становятся все лучше и лучше по качеству, харош
Спасибо ОГРОМНОЕ за такой подробное объяснение, всё понятно теперь) Было бы круто увидеть подобное объяснение но про деревья))
Я только что решал задачу: Longest Substring Without Repeating Characters, и вуаля, тут видео на sliding window подъехало 🔥 Спасибо!
Кстати на днях сидел решал эту задачу на leetcode , и она у меня не прошла последний тест из-за Time Limit Exceeded (986 / 987 testcases passed).
Мой подход был такой - я собирал все уникальные подстроки (в отдельном методе я проверял что подстрока состоит из уникальных символов) в лист и затем с помощью компаратора сортировал по длине и возвращал длину последнего элемента
Да просто алгосы везде одинаковые +-
@@ghostlynomad7788 не мудрено, что по времени не прошел. Мало того, что собирал лист со сложностью n в квадрате, а то и n в кубе, так потом еще и добавил n*log(n) (я про сортировку). Ничего медленнее мне кажется тут уже не придумать))
@@Дмитрий-л3я7ы больше ни до чего не додумался ) и да, сложность сборки листа n в кубе🙈
@@Дмитрий-л3я7ы n в кубе на самом деле)
но больше ни до чего не додумался за пару дней
Ура ура! С возвращением, Сань :)
Круто что ты стал записывать видео чаще))
Саша, привет!
Спасибо за интересное видео. Единственное, ты слегка меня запутал когда сказал, что "удаляем, пока в сете есть повторяющиеся символы" - по факту, в сете они не повторяются. Наверное, лучше было бы сказать что удаляем, пока не удалим ПОВТОРИВШИЙСЯ символ)
На пробнике ЕГЭ подобная задача попадалась (24-е задание).
Решил очень похожим способом
Видео, как всегда, интересное. Благодарю за контент!
тоже сдаю егэ, как раз захотел выучить алгоритм чтобы если что использовать) да и в целом полезная вещь
но там тебе на сложность наплевать в егэ
@@romanpritkov1107 не, n^3 такие задачи не делает, либо сотню условий надо проставлять, чтобы там скипало
простой перебор можно сократить и до n^2, если просто обновлять сет после первого цикла а is_acceptable = True оставить на своём месте. ну и третий цикл можно будет убрать. На лит коде даже заработало.
Для скользящего окна вот ещё альтернатива, с помощью словаря на python:
def longest_substr(s):
answer = 0
left = 0
hash_set = {}
for right in range(len(s)):
char = s[right]
if char in hash_set and hash_set[char] >= left:
left = hash_set[char] + 1
else:
answer = max(answer, right - left + 1)
hash_set[char] = right
return answer
Спасибо за видео
И даже еще проще брутфорс можно сделать - вообще без этого is_acceptable, просто если в сете есть новая буква, то выходим из второго цикла, а потом проверяем больше ли сайз нашего сета, чем наш ответ и все.
Привет, хотел выразить тебе огромное спасибо. Посмле просмотра видео про гугл и инжерена. Мне вернулся дух программиста. Начал вести фриланс и параллельно изучаю собесы
Спасибо, отличная подача. Без воды и смс. Успехов.
Привет, пожалуста продолжай, очень полезно и информативно, сейчас активно пытаюсь прокачать алгоритмы и твои видосы прям то-что нужно!!!
Очень хорошо объясняешь, респект. Алгоритм полного перебора можно немного оптимизировать, если не перебирать тупо все подстроки, а начинать с самой большой и двигаться к уменьшению, или, если уже нашли подстроку длиной 3, рассматривать только большие, это чуть-чуть сократит затраты, но, конечно, не будет лучше, чем скользящий алгоритм.
Избыточность в расчете answer. Его стоит пересчитывать в случае повторения буквы и последний раз когда заканчиваем всю функцию.
На асимптотику это не влияет, + можно написать контртест для которого пересчёт все равно будет происходить на каждом шаге
Да и ещё можно оптимизировать удаление из множества. Там не нужен поиск в множестве, достаточно простого сравнения символов.
@@crimfi на асимптотику не влияет, а на константу влияет
@@TurboGamasek228 можно написать тест, для которого константа не изменится, при оценке рассматриваем худший случай
Отличное видео! Спасибо! Делай, пожалуйста, побольше такого контента на виды алгоритмов. И да, мы скучаем по Java)
Спасибо за классное объяснение, а то я когда на литкоде пыхтел над этими задачами с окном, чуть мозг не сломал, разбирая этот алгоритм
Круто! Давно искал подобный канал с разборами задач, спасибо!
Спасибо, что сделал это ценой 2 свичей
Было интересно изучить. Главное с апреля начать
что-то я не понял, на 5:13 мы проверяем и удаляем символы, на которые указывает left, но в алгоритме на java на 7:53 мы проверяем в while символ, на который указывает right, а не left. почему так? объясните, пожалуйста
не понял на 5:16 говорится "удаляем пока в подстроке нету повторяющихся символов", хотя указатель на left - С и в подстроке остается С, тоесть они указывают на одинаковый символ , почему его он не удаляется как все предыдущие?
это повторяющийся символ из предыдущей подстроки, с него будет начинаться новая подстрока
Когда это два указателя стали чем-то удивительным(учусь в школе, смотрел пару записей собесов, почти в каждом были два указателя, так что думал, что это база)
За Иннополис за заднем фоне превью лайк)
Крутецки всё объяснил! Спасибо!
реализация "простого" решения убила... я даже и не подумал что так можно XD
Это отличное объяснение, я серьёзно
spasibo, Sasha za detalniy razbor.
Спасибо! Эффективность ваших видео O(n)!
Приятно осознавать, что я бы решил подобным образом.
Я конечно дико извиняюсь, но это круто и изящно! Придумал на лету тоже вариант O(n), но он немного сложнее и кушает больше памяти - на каждый индекс массива создавать отдельный сет и добавлять в него пока "дубль" символа не встретится. Метод скользящего окна намного красивее!
по моему алгоритм можно улучшить используя bitset для хранения мапы элементов и то сколько раз они встретились
Первый раз за 10 лет в айти нашел нормально объясняющего на русском человека. Мне это конечно не пригодится, но было интересно 👍
Спасибо за видео! Сам около года назад сидел плотно в литкоде, задачи на скользящее окно были одними из любимых) Увидел условие, решил проверить сам себя, решу ли ее сейчас. Минут за 5 решил, не с первого раза, сначала подзабыл немного последовательность действий, пошел по неправильному пути. Оставлю тут свое решение (на js правда), оно немного отличается от решения в видео (вместо двух while у меня for и внутри него while, ну и без if/else, более линейно)
function maxLen(str) {
let maxLen = 0
let left = 0
const uniques = new Set()
for (let right = 0; right < str.length; right++) {
const current = str[right]
while(uniques.has(current)) {
uniques.delete(str[left])
left++
}
uniques.add(current)
maxLen = Math.max(maxLen, right - left + 1)
}
return maxLen
}
console.log(maxLen('axbxcxd')) // 3
какая асимптотика?
@@rof3leo O(n) по времени и памяти
Подумав, решил методом похожим на скользящее окно, правда вместо указателей я бы воспользовался List(C#, System.Collections.Generic), но не уверен, что List подойдёт по оптимизации лучше и сопоставимо, чем указатели.
Спасибо за видео.
Клевый способ. А можно подгонкой размеров окна подобным способом находить всякие локальные максимумы, точки перегиба и прочее на каком ть временном ряде? По скольку они там формируются в вообще произвольной периодичностью.. ))) Было бы как раз...
Очень крутое объяснение, спасибо!
Ооо, мы этот алгоритм в школе называли "Метод двух индексов". Он очень помогал в 24 задании ЕГЭ по Информатике
Хотелось бы больше примеров на Java ) спасибо 😊
Буду благодарен, если сделаете ролик с roadmap по алгоритмам и то какие задачи решать
Это кстати носит более распространенное название -- "метод двух указателей"
Отличное видео! Спасибо!
Спасибо за видео! У меня появился вопрос касательно быстрого решения. В видео говорится, что скорость O(n), но ведь по сути мы используем два цикла, один из которых вложен. представим, что в функцию отдается строка из одинаковых символов и тогда во все итерации кроме первой будет падать во вложенный цикл. а на сколько я помню скорость считается исходя из худшего случая. Почему в этом случае скорость O(n)? буду очень благодарен за ответ!
Если исходить из худшего случая, то и set можно выкинуть, т.к. он там по добавлению будет равен O(n), а не O(1).
Возник тот же вопрос, задал его chatGPT и он ответил, что "каждый символ строки рассматривается и обрабатывается один раз либо указателем right, либо указателем left.
Быстрое решение вроде как упрощенно "два указателя"(не шарю в алгоритмах). Но мне показалось, что когда мы пришли к повтору, то нет нужды уменьшать окно, можно двигать вправо ОБА указателя одновременно, ведь нас не интересуют размеры подстрок меньше максимальной из уже найденных. Вопрос правда реализуемо ли это(эффективнее), т.к. второй пункт(сужение) выполняет задачу убрать дубль.
Чтобы продемонстрировать логику, на питоне:
def longest_substring(s):
left = 0
for right in range(len(s)):
if len(set(s[left: right + 1]))
У интерфейса Set, метод add и так делает проверку на наличие, можно лишний раз не вызывать contains.
public static int longestSubstring(String in) {
int max = 0;
LinkedHashSet set = new LinkedHashSet();
for (char c : in.toCharArray()) {
while (!set.add(c)) {
max = Math.max(max, set.size());
set.removeFirst();
}
}
return Math.max(max, set.size());
}
Приветствую, во втором случае можно немного оптимизировать решение: предположим, что есть текущая уникальная подстрока и мы нашли следующий неуникальный символ, если размер "хвоста" меньше чем размер найденной подстроки, то можно прекратить поиск и вернуть результат. Очевидно, что выигрыш невелик, но все же.
Я бы построчным вводом добавлял , сортировал массив и сравнивал первую и вторую позиции и как только они равны записал бы размер массива-1, а потом начинал бы со второго символа.
А проверка того что буква уже в сете за проверку не считается и проходит мгновенно?
3:30 можно обойтись без флага используя такой синтаксис:
for bla bla bla:
print('Стоп')
break
else:
print('Цикл завершен без остановки')
Нормально, 24 задание ЕГЭ, поехали
Первое, что пришло в голову, это то, что Вы назвали "метод скользящего окна". Я бы, наверное, это писал на компилируемом языке, если бы такое было позволено.
Было бы интересно послушать про работу различных структур данных
Спасибо за видео, всё понятно
Попалась такая на входных экзаменах на стажировку в тинек)
Вместо Set я бы использовал Map и хранил в значении индекс элемента который буду удалять, чтобы не пробегаться по циклу while
Это решение более эффективно, чем предложенное автором.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
d = {}
i, j = 0, 0
ans = 0
while j
Эффективно только, если рассматривать с позиции лаконичности записи. У меня словарь тоже был первой идеей из-за возможности хранить индекс по ключу символа, но что-то меня смутило и в итоге быстро переделал через сет, почти 1 в 1 как у Саши с небольшой незначительной поправкой. Реализация со словарём конечно красива, и строчек кода на две меньше, ввиду отсутствия цикла удаления ненужных ключей, но перфоманс у неё хромает. Для лучшего случая по скорости на 20% хуже сета, в среднем в 2 раза медленнее, а для худшего случая решение со словарём медленнее почти в 4 раза. Это конечно все равно и тут, и там O(N), но такая разница немного удивила. Но не привыкать, в питоне не все то, что красивее выглядит, быстрее работает, зачастую как раз наоборот.
Без лишних слов, Превосходный контент и знания! СПАСИБО!!!! Вопрос: Английский вариант названия алгоритма "метод скользящего окна" ? The Sliding window ?
Да
Отличное видео, спасибо
Изначально пришёл 2 вариант на ум, до первого даже догадаться не смог.
По времени заняло минуты 2-3.
Очень крутое видео, спасибо!
Неплохое объяснение, но не оценивается вставка и поиск в Set, интервьювер разве не укажет на этот момент?
Уже несколько подобных комментов тут. Что вы так ополчились на сэты, что плохого они вам сделали?
@@emptyspaces4067 "мы" это разные люди, я за себя говорю, мне стало интересно, потому что это вопрос на засыпку.
@@МихаилТихомиров-м8ч принято считать что работа с сетом это константа. адепты лога будут негодовать, но на деле, чтобы сет постоянно уходил в лог - это надо нехило так постараться. плюс надо точно знать, а что под капотом у данной конкретной реализации сета, вдруг там реально обычное дерево, а не хэшмап. обычно совмещают оба два сразу. ну а в данной задачке, если символы ограничены - то можно реализовать свой собственный сет, который будет абсолютной константой, к которой уже невозможно будет придраться.
@@SayXaNow ну вообще джавовский hashset это как раз О(1), насчет пайтона я не знаю. Просто это может быть вопрос на засыпку от интервьювера, стоит об этом помнить.
@@МихаилТихомиров-м8ч у пайтона как я знаю тоже
Хочу поделиться своим решением, на момент ответа видео не досмотрел.
Сравниваем элементы с помощью бинарного дерева.
В цикле начинаем сравнивать , если элемент меньше идём в лево, если равно continue. Если след узел null то тогда записываем в дерево элемент и увеличиваем count ++.
После цикла выводим count.
У нас получится уникальное бинарное дерево, с счётчиком count.
Очень интересно, но ничего не понятно. Можно код, желательно на жабе или питоне?
Мне кажется что первый алгоритм выполняет не n в кубе операций , а (n+n*n) /2 так как right пробегает от i до n символа, где i - положение left; у второго алгоритма максимальная скорость O(n) , а минимальная O(n*n) потому что right точно пробежит один раз строку, а left может остаться в начале (если все символы разные) или пробежать все символы (если все символы одинаковы) P. S. Укажите если не прав
О да, это очень классный алгоритм. Его еще называют методом двух указателей. Все, кто к ЕГЭ по информатике готовится, учат его, довольно эффективный и гибкий алгоритм
Насколько я понимаю, удаление с начала масива очень долгое, потому что нужно создать другой масив и перекопировать все значения в него. Поэтому, когда у нас будет очень длинная подстрока, придётся много раз пересоздавать масив внутри сета.
Лучше уж после каждой итерации поставить проверку (result < right - left + 1).
Но может сет в Java работает не так как я думаю, надеюсь на отзыв.
Не пересоздается сет после удаления слева. Если не удалять - то не будет работать contains().
@@oleksandr2234 Спасибо за ответ!
спасибо интересный алгоритм!
Операции над set'ом же за ln(n) выполняются. Поэтому сложность с sliding window O(n*ln(n)), а без O(n^3 * ln(n))
он использовал unordered_set, где клюли хешируются за O(1)
можно просто 1 раз идти по масиву и добавлять колличество уникальних елементов до первого повоторения в новий масив, потом повторять подсчет с последнего уникального елемента, а потом просто взять наибольшое число нового масива.
Неплохое решение, но вот другое - за один проход, запоминая последний индекс символа. Swift:
func lengthOfLongestSubstring(_ s: String) -> Int {
var map: [Character: Int] = [:]
var result = 0
var left = 0
for (i, c) in s.enumerated() {
if let j = map[c] {
left = max(left, j + 1)
}
result = max(result, i - left + 1)
map[c] = i
}
return result
}
Попросил ИИ переписать на АХК скрипт +вернуть саму строку:
lengthOfLongestSubstring(s, ByRef longestSubstring = ""){
map := {}
result := 0
left := 0
longestSubstring := ""
Loop, Parse, s
{
c := A_LoopField
if (map.HasKey(c)) {
left := Max(left, map[c] + 1)
}
result := Max(result, A_Index - left)
map[c] := A_Index - 1
if result
longestSubstring := SubStr(s, left, result)
}
}
return result
}
на java
public class LongestSubstringLength {
public static int lengthOfLongestSubstring(String s) {
HashMap map = new HashMap();
int result = 0;
int left = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
left = Math.max(left, map.get(c) + 1);
}
result = Math.max(result, i - left + 1);
map.put(c, i);
}
return result;
}
С мапой очень плохое решение. Используется доп память. И не забывайте о том как растет мапа - это тоже далеко не бесплатно.
на питоне бы...
@@st.kevichочень плохое решение в видео и растет оно
Символов у тебя фиксированное количество в отличие от букв
есть способ в котором только r будет один раз пройтись по строке, этот код работает за O(n), а не O(2n). Но это почти ничего не меняет.
def solve(n,s):
ans=0
l,r=0,0
hash_mp={}
while r
Я на практике редко пользуюсь конструкцией while. В 1 проценте случаев)
Можно еще решить вот так. Решение без скользящего окна.
Хотя суть очень похожа.
fun getMaxUniqueWithSet(input: String): Int {
var maxSequence = 0
val set = mutableSetOf()
input.forEach { c ->
if (set.contains(c)) {
if (set.size > maxSequence) {
maxSequence = set.size
}
set.clear()
}
set.add(c)
}
return max(maxSequence, set.size)
}
а этот алгоритм разве не называется методом двух указателей?
насколько я знаю из подготовки к егэ, скользящее окно -- это метод, при котором в какую-то сумму непрерывной подпоследовательности добавляется следующий элемент и вычитается из неё самый первый, так, экономно можно сдвигать интервал, в котором считается сумма, по массиву данных
остановил на 2:07 и мне показалось что первое очевидное решение на самом деле сложное и неочевдиным, очевидным решением для меня пробежаться по всем символам с хэшсетом накапливая его и фиксируя максимальный результат при наличии символа уже в нём, при этом сбрасывая его и возвращаясь назад на величину r-1, сча посмотри какое решение предложит автор
Объясните пожалуйста, почему последний пример на джава который, если заменить Set на List то не работает,выводит исключение вышли за границы листа
Спасибо за видео! Какие еще задачи можно решать методом скользящего окна?
Спасибо за видео!
Немного запутанное объяснение либо такое ощущение, что какие-то кадры ошибочно вырезаны с видео. Либо плохо разобрался)
Привет! Было бы круто, если бы разобрал задачу Medium from two sorted arrays. Нигде не могу найти хорошого объяснения
@sashalukin, а почему это считается O(n) если в худшем случае понадобится в понадобится 2 раза полностью проходить по каждому символу строки? получается O(n^2)
-300 iq moment
зачем вычислять answer, когда можно вернуть размер сета в конце?
Потому что размер сета в конце может быть меньше максимального своего размера
Вы могли записать видео про метод двух указателей?
элементарный алгоритм и первое что приходит в голову. Ну а первый вариант очевидно отвергается сразу. Я удивлён простотой.
Интересно, что этот алгоритм начали спрашивать сейчас. Решал его еще года 3-4 на леткоде тогда он мне попался где-то 5 по счету. То что додумался до решения сам конечно тешет мое самолюбие. Но вот то что часа полтора два у меня ушло чтобы выдать рабочий код на go нет).
Спасибо за видео! А что это за софт со спойлерами и где можно рисовать?
подскажите что за приложение в котором вы стрелки по элементам так красиво двигали?
Интересно, конечно :)
Этот алгоритм напомнил мне метод указателей можно ли в данном случае его использовать?
Спасибо за видео! Можете пожалуйста посоветовать с чего начать изучение алгоритмов, если только только изучил основы python?
Прикольно. Лайк.
Я только погружаюсь в программирование.
Будет ли полезно в первом цикле (где увеличиваем подстроку) не прогонять её по минимальным значениям а сразу увеличить на Макс. Длинну, уже записанную в сет? Так мы пропустим (в данном примере) проверку сетов cb и db.
@furtherance6042 если я тебя правильно понял, то, если ты будешь пропускать символы, тогда сет не будет хранить все символы подстроки => ты можешь не понять, что случился повтор
Цифры Пифагора. Если у треугольника длины сторон 3, 4 и 5 метров, то он -- прямоугольный. Или 6, 8 и 10 метров. И т. д. Эти волшебные цифры позволяют на местности рисовать прямые углы. Размечать местность под фундамент, например.
спасибо, больше разборов задач. Не подскажете, что за второй монитор у вас?
Почему последний алгоритм работает за O(N)? Я не разбираюсь в подсчете продолжительности процессов и мне казалось, что добавление цикла увеличивает степень на 1, а тут как раз 2 цикла
1. Непонятно зачем использовать set если мы можем пройтись по уже существующей строке
2. Удаление пока не пропадут все повторяющиеся символы? Если ты добавляешь 1 символ, то куда проще будет проверить повторяется ли этот символ и потом найти индекс первого вхождения и удалить все символы до него
Без сета ты улетишь в O(n*(n+1)/2) = O(n^2) по сложности для худшего случая.
@@SayXaNow там и так O(n^2) из-за while
@@tonylayz тот while выполнится не более N раз за всю работу кода, следовательно его плюсуют к N, а не умножают на N. А твой проход выполнятся будет в среднем N/2 за каждую итерацию внешнего цикла, поэтому его умножают на N.
тоже не самое быстрое решение, можно создать словарь, в котором будет храниться индекс последнего элемента, имеющего такое значение, что нынешний, на котором, находится правый указатель(по умолчанию поставим индекс -1, для проверки, либо множество опять же используем). Соответственно нам теперь не нужно постоянно перемещать левый указатель на 1, а мы сразу переместим его на нужный индекс, с которой начинается подходящая подстрока
Да, причем это грубейшая ошибка, которая приведет к эксепшену по памяти на огромных строках
Интересно, автор в команде оптимизации гугл хрома?
@@Oldy573 ахахаххаха
@@Oldy573 разве? в такой задаче максимальная длина у строки будет 256 или 128, не помню. Вот если взять какую-нибудь другую вариацию, то да, ошибка будет
Зачем второй цикл для указателя left?
Мы и так попадаем в исключение которое говорит о том, что Set имеет данную букву и ёё нужно удалить.
но вы же второй при перемещении left тоже опять перебираете, не проще ли использовать std::map, хранить там позицию символа и сразу смещать позицию на искомый символ+1
а можно вместо set завести массив длинной в алфавит и держать в нем последний индекс, содержащий данную букву. Двигаем правый указатель, смотрим, была ли текущая буква в окне, если нет - запоминаем, идем дальше. Если буква была - стоп, проверяем, не больше ли текущее окно лучшего, если нашли лучшее - запоминаем окно и переставляем левый указатель сразу после буквы, которая повторилась.
по сути - то же, но не надо двигать левый указатель по одному шагу, ну и обратиться к массиву - быстрее, чем добавлять-убирать из сета.
Первая мысль такая же была, только не с алфавитом, а в общем случае - хэшмапой
можно даже не индекс, а просто true, если встретилась и false, если нет. boolean меньше памяти занимает (хотя у тебя немного побыстрее работает). Потом в цикле проверяешь, если текущая буква уже встречалась, то двигаешь левый указатель, пока не уберешь предыдущее вхождение
@@rof3leo тогда придется на каждом шаге отбегать до начала текущей последовательности?
@@jaggman2134 честно говоря, у меня старая нелюбовь к хашмэпам, несколько раз сталкивался с тем, что сет на хэше работает в разы медленнее, чем обычный сет (вероятно на дереве). Если храним строки, получение хэша пробегает каждую строку до конца, а сравнение на < обычно кончается на первой же букве.
О а не подскажите через что вы делаете скрытие контента а потом его появление, по клику ?
Откуда у вас эти стрОку, подстрОку?
Ведь строкА, а значит строкУ, а не стрОку?
Спасибо за видео.
Какой инструмент используется для демонстрации ? Очень удобно отображать скрытый код при нажатии. Сам часто делаю тех презентации и такой инструмент очень бы сильно помог, а то ливкодинг глючит )))