Блог

Видео текст:

[00:00] => В этом курсе вы узнаете, как решать 10 очень популярных проблем с собеседованием по кодированию,
[00:05] => и вы изучите теорию, лежащую в основе решений, так что вы будете лучше подготовлены к решению других типов
[00:10] => а также о проблемах. Мы придем к 10 популярные проблемы с собеседованием по кодированию курс 10
[00:16] => хорошо подобранные задачи, охватывающие различные алгоритмы и структуры данных. Темы
[00:20] => чтобы расширить свои знания и подготовиться к собеседованиям.
[00:23] => Пожалуйста, попробуйте решить, прежде чем смотреть решение подготовьтесь и увидимся на первой лекции
[00:36] => Добро пожаловать в это видео, где мы решим первую задачу этого курса «Действительная анаграмма»
[00:40] => приобретенная легкая задача по сравнению с желаниями Knucks, нам даны две строки s один и S два, и мы
[00:47] => попросили проверить, есть ли у них анаграммы. Две строки являются анаграммами, если они состоят из одних и тех же символов
[00:54] => с той же частотой, только в другом порядке. Например, с сильным стандартом и садом,
[00:59] => мы возьмем один из них и переставим его персонажей, и мы получаем другого.
[01:05] => Как мы собираемся решить эту проблему? Мы знаем , что две строки являются анаграммами, если они имеют
[01:10] => одни и те же символы с одинаковой частотой. И что мы можем сделать, это рассчитать частоту каждого
[01:15] => символ и как один, вычислите частоту каждого символа в s два и сравните результаты.
[01:22] => Но какую структуру мы используем для этого, чтобы мы могли использовать массив, где каждая ячейка представляет число
[01:27] => частот, все они начинаются с нуля, затем для каждого символа в строке будет увеличиваться
[01:32] => соответствующая ячейка. Это решение подходит когда алфавит невелик, в то время как количество
[01:38] => количество возможных персонажей невелико. Например, если строки могут быть выполнены только в нижнем регистре
[01:44] => буквенные буквы, потребуется массив из 26 элементы, все в порядке. Но это не обязательно
[01:50] => случай. Они могут содержать все символы. И у нас есть 1000 и 1000 существующих возможных
[01:57] => символов, массив занял бы много времени и места, чтобы создать его и пройти по нему.
[02:02] => Лучшей структурой для нашей проблемы является структура хэш -таблицы, которая сопоставляет уникальные ключи со значениями.
[02:08] => В нашем случае ключом будет кока-кола к другим значениям количество вхождений.
[02:14] => Например, если у вас есть безымянный и продавец чье имя было, мы получаем эту хэш-таблицу.
[02:18] => И продавец, которого мы получаем вот этим. Имеют ли они одинаковые ключи с одинаковыми значениями, чтобы они были равны?
[02:25] => Это означает, что безымянный и продавцы — это анаграммы.
[02:32] => Закодируйте, кто первым показал, что обе строки имеют одинаковую длину, потому что если они не,
[02:36] => они не могут быть анаграммами. Затем кто объединит наши две хэш-таблицы, и мы приступим к нашему
[02:44] => для каждого символа и как один, если ключ уже существует. И для того, кто действительно увеличивает
[02:49] => в противном случае мы создали новое значение, равное единице, чем для нас с той же логикой, но с частотой. Два. И
[02:57] => теперь, когда мы наполнили их друг другом, они имеют одни и те же ценности. Для каждой тростниковой лягушки по одной,
[03:02] => если он не существует в лягушке два, или для качество не может переключиться на другое,
[03:06] => возвращает false. Это означает, что либо характер одного из нас не существует в нашем рагу, либо их нет
[03:11] => появляется одинаковое количество раз после цикла, если мы не нашли никакой разницы, мы возвращаем true.
[03:21] => И в Python нам никогда не нужно писать все это, потому что у нас есть класс
[03:24] => именованный счетчик в модуле коллекций, который создает таблицу вхождений, просто передавая
[03:29] => строка в качестве аргумента. И мы можем сравнить словари с оператором равенства.
[03:34] => Так что на самом деле тот, кто возвращается , отсчитывается как один, равный двум.
[03:41] => Для временной сложности, в худшем случае, а также для того, чтобы иметь одинаковую длину. Давайте назовем это
[03:47] => поскольку мы проходим N символов не более трех раз, и Суджан. Вставка в хэш-таблицу
[03:53] => затраты в среднем составляют один, вышел, усилитель был выключен и был выключен, и мы дадим некоторые из усилителей по сложности.
[04:00] => А для космической сложности у нас есть час для каждой таблицы, поскольку они могут содержать до
[04:05] => ключи у каждого из нас часто бывают космической сложности. Нам все еще нужно обсудить другое решение.
[04:13] => Вы должны знать две анаграммы, как одна и та же лексикографически отсортированная строка,
[04:18] => например, с безымянным и продавцом. Если мы проданный безымянным, мы получаем ELMN s s. Я буду продавцом
[04:26] => то же самое. Итак, во втором решении, кто сделайте соляные позы и сравните результаты
[04:32] => в коде после условия равенства возвращается сортировка, так как единица равна отсортированной
[04:39] => как двое. Но сортировка строки символов из-за n логарифмического времени мы делаем это дважды
[04:45] => было после сравнения. У нас есть n-логарифмическая сложность по времени. И для космической сложности,
[04:51] => у нас часто бывает, что для отсортированного результата дважды мы получаем сложность вне воздушного пространства.
[04:58] => Кто в конце этого видео? свисток действительной подземной проблемы,
[05:02] => Я надеюсь, что вы поняли суть вопроса решения и увидел следующее
[05:13] => Добро пожаловать обратно на курс в этом правиле лекции. Итак, проблема первой и последней позиции,
[05:18] => вам дается отсортированный массив целых чисел, являющихся целочисленной целью. И нас просят найти индекс
[05:24] => первой и последней позиции цели и нашего если цель не может быть найдена в нашем возвращении минус один
[05:30] => минус один. Например, если наш номер 245-555-5799, а целевой — пять, то у автора будет шесть
[05:39] => потому что первая позиция цели — «до», а его последняя позиция — «шесть».
[05:45] => Прежде всего, поскольку массив отсортирован, все элементы с одинаковым значением будут
[05:49] => быть на века влюбленными друг в друга. Например, здесь все позиции значения пять являются последовательными.
[05:55] => Это означает, что первое возможное решение состоит в том, чтобы начните обход массива с самого начала
[06:00] => для первой позиции цели и продолжайте ходьба до тех пор, пока не найдешь последнюю позицию.
[06:05] => В нашем примере у нас есть две четверки, пятеро, которые нашли первую позицию
[06:10] => мы можем войти, у нас 5555. Этот — самый последний, мы нашли позицию, мы поворачиваем их
[06:19] => в коде мы начинаем обход индексов нашего, и если наш phi равен целевому, это означает, что мы нашли
[06:25] => исходное положение. Теперь мы продолжаем идти, пока следующий элемент существует и равен целевому y плюс
[06:32] => один меньше длины нашего и наших пяти плюс один равен целевому приращению i. После
[06:39] => цикл while. INR представляет позицию последнего вхождения. Вот почему мы возвращаемся к началу i
[06:46] => и если падение закончится без вернув результат,
[06:49] => это означает, что мы вообще не нашли цель в нашем возвращении минус один минус один.
[06:56] => Знайте, что возможно получить желаемую должность равно и положение, это происходит, когда есть
[07:01] => существует только один случай нацеливания на нашу временную сложность на цели, которая
[07:07] => покрывает часть перед первой позицией, третьей последовательность событий и где это не так,
[07:13] => который охватывает целый массив. В обоих случаях, которые покрытия почти добавляют элементы, где n — число
[07:18] => из элементов нашего у нас есть временная сложность добавления стоимости и пространственной сложности, потому что
[07:25] => мы просто используем n переменных. Это решение использует линейный сэр, чтобы дать представление о временной сложности.
[07:35] => Оба прибегли, так что мы можем подумать об использовании двоичного поиск. Давайте попробуем использовать двоичный поиск, чтобы найти
[07:41] => исходное положение. С помощью двоичного поиска вы можете найти положение элемента в отсортированном массиве.
[07:47] => Но здесь мы не ищем какую-либо позицию цели, мы ищем первую.
[07:54] => R — первая позиция цели , если r равно цели, очевидно,
[07:58] => но также r из i минус один должен быть меньше чем цель меньше, потому что массив отсортирован.
[08:05] => Поэтому мы будем использовать двоичный поиск в обычном режиме, но чтобы добавить второе условие перед возвращением.
[08:12] => Давайте попробуем сделать это на нашем примере. Слева и справа сплошной первый и последний наш элемент, как обычно.
[08:18] => Чувак, его левый пароль делим на два, получаем четыре здесь верно, что наша четверка равна цели,
[08:24] => но этого недостаточно, наши четыре минус один не меньше цели. Так что мед — это не тот
[08:29] => исходное положение цели. Но должны ли вы перейдите в левую часть или в правую часть прямо сейчас,
[08:35] => наше сделанное не создано по назначению. Таким образом, первая позиция может быть только в левой части
[08:41] => мы продолжаем делать сейчас ноль с плюсом три делим на два получаем один,
[08:46] => наш телефон меньше, чем target. Итак, начало позиция может быть только в правой части, мы продолжаем
[08:52] => сделано теперь два плюс три, деленное на два, то есть мясо равно цели, а наш самец минус
[08:58] => один меньше, чем цель. Таким образом, мета представляет первую позицию цели, мы возвращаем ее.
[09:05] => В коде мы собираемся сначала провести ранний условие выхода для случая, когда первый
[09:09] => элемент равен цели с помощью DACA, знайте, что ноль — это начальная позиция, возвращенная нулем.
[09:15] => Кстати, в решениях, основанных на бинарных ищите, ставьте как можно больше условий раннего выхода
[09:20] => насколько это возможно, чтобы справиться с крайними случаями и избежать проблем, выходящих за рамки.
[09:25] => После этого мы инициализируем левое и правое в ноль и минус один соответственно.
[09:30] => Ноль и r минус один являются индексами первого и последнего элемента R. Теперь, когда из
[09:35] => меньше или равно правому, мы вычисляем средний индекс слева плюс rho, деленный на два. Впоследствии,
[09:42] => у нас есть три случая, когда соблюдаются оба условия . где альфа равна цели на
[09:48] => наша бета минус один меньше, чем цель. Оно означает, что сделанное — это своего рода позиция, которую мы поворачиваем
[09:55] => второй корпус сделан меньше целевого. Это значит, что мы все еще впереди
[09:59] => отправная точка. позиция. Вот почему мы берем левую и среднюю плюс одну, чтобы начать снова в
[10:03] => правильная часть. В противном случае это означает, что мы превысили последовательную последовательность, или мы взволнованы, но
[10:10] => не другое начало. Так что начинать можно только в левую часть мы берем ратомид минус одна часть стены
[10:19] => не вернул результат означает, что цель у него нет существующего нашего возврата минус один.
[10:26] => Теперь мы нашли эту мысль у экспертов, нам все еще нужно найти конечный индекс,
[10:31] => мы можем подумать о том, чтобы просто идти, начиная с начинайте, пока мы не найдем последнюю позицию цели.
[10:36] => Но это разрушило бы все, что мы сделали, потому что в худшем случае,
[10:39] => нам нужно пройти весь массив, что приводит к сложности старого Антона, такой же, как
[10:44] => первое решение, которое вы, ребята, сделали, чтобы найти конечный индекс, мы также будем использовать двоичный поиск.
[10:51] => Но условие немного отличается от первого раза при поиске начальной позиции
[10:56] => являются мужчинами, как быть равными цели и нашему мужчине минус один меньше цели. И для конца
[11:02] => позиция, наш средний показатель должен быть равен цели, а наш средний плюс один должен быть встречен на цели.
[11:09] => Следующий элемент должен быть больше, потому что он означало бы, что справа мы не
[11:12] => в последовательных целевых элементах больше, поэтому фактическая позиция является последней позицией цели.
[11:20] => В коде мы просто меняем несколько вещей, единственное условие выхода возникает теперь, когда последний элемент
[11:25] => равно разговору, это означает, что последняя позиция цели находится в последнем индексе нашего n минус один
[11:31] => без возврата. Затем в трех случаях, случаях, когда мы включим midis, когда наш сделанный
[11:37] => равно цели, и наш met плюс один больше , чем цель. За два оставшихся он выиграл
[11:44] => наша главная цель больше цели, затем мы превысили последовательную последовательность, мы пойдем влево
[11:49] => часть, правая становится просто минус еще одна, это означает , что либо будет для последовательной последовательности
[11:55] => или подстрекал, но не в конце, поэтому и может только быть в правой части, левая становится средней плюс один.
[12:03] => Теперь у нас есть наша функция тонкой соли, у нас есть наша находка и функция,
[12:07] => мы можем перейти к основной функции решения. Прежде всего, у нас есть некоторые условия досрочного выхода,
[12:14] => кто может выявить по крайней мере три случая где мы не можем найти целевую роль.
[12:18] => Когда в массиве нет элементов, один целевой объект меньше первого элемента. И когда цель
[12:22] => больше, чем последний элемент в двух последних. Поскольку массив отсортирован, кто может вывести
[12:28] => цель не равна всем остальным элементам. Если по крайней мере, одно из этих условий верно, без
[12:39] => доходность минус один минус одно здоровье, которое соучредитель стремился предоставить позицию на складе, которую мы
[12:40] => позвоните шрифту и найдите конечную позицию и дождитесь старта. И если Цель не существует в нашем
[12:47] => отсортированный годовой результат вернулся минус одна ванна, мы все равно получили ожидаемый результат.
[12:54] => Для временной сложности мы используем двоичный обыщите дважды. И двоичный поиск имеет
[12:59] => ужасно много и трудоемко, потому что мы продолжаем делить размер входного сигнала на два,
[13:03] => два раза работы и дает нам всю логарифмическую временную сложность.
[13:08] => Добавьте к этому сложность пространства, и вы получите все одно, потому что мы используем всего восемь переменных.
[13:15] => Прежде чем закончить эту лекцию, я хочу сказать вам , что если вас не устраивает бинарный поиск,
[13:20] => вам действительно следует поработать над этим, потому что это фундаментальный алгоритм.
[13:23] => это проявляется во многих проблемах на этом, найдите посмотрите первую плохую версию и многие другие.
[13:32] => Проиграв эту лекцию, я надеюсь, что вы поняли решения и увидели следующую.
[13:44] => Добро пожаловать обратно на курс этой лекции, мы решит проблему с самым большим элементом утеса,
[13:49] => вам дается массив целых чисел и целое число k. И нас просят найти
[13:53] => восьмой по величине элемент K. Например, если у вас есть равны четырем, чтобы
[14:00] => и k равно четырем, выход будет шесть, потому что самый большой элемент равен девяти,
[14:05] => второй по величине — семь, третий самый большой — семь, а четвертый по величине — шесть
[14:13] => Первое возможное решение, которое мы можем придумать , состоит в том, чтобы удалить максимальный элемент k минус один раз
[14:19] => потому что после этого следующий максимум представляет собой восьмой по величине элемент K.
[14:24] => Например, в нашем массиве K равно четырем. Так мы удаляем максимальный элемент три раза
[14:30] => первая итерация Макс моя, мы ее удаляем, вторая максимальная итерация — семь, мы переносим ее на третью итерацию
[14:38] => Максимум семь, мы удаляем его теперь, когда закончили три итерации, максимум в оставшихся
[14:44] => элементы — пятый по величине элемент исходного массива, его вернули шесть человек.
[14:51] => В коде у нас есть несколько повторяющихся k минус один, умноженный на один, удаляет максимальный элемент
[14:57] => после цикла верните максимум всех, кроме временной сложности, подходящей для максимальной стоимости n,
[15:04] => где n — количество элементов и удаление это от стоимости массива, и в худшем случае,
[15:09] => потому что нам может понадобиться сдвинуть все n минус один элемент, и наш цикл повторяется k минус
[15:15] => один раз у нас будет k минус один раз, чтобы добавить, плюс добавить для нахождения последнего наибольшего элемента.
[15:22] => В общей сложности у нас есть k минус один умноженный на два n плюс n, что в два раза больше k, умноженного на n минус n,
[15:28] => что дает нам в k раз больше нашей временной сложности, где n — количество элементов нашего
[15:35] => собственный, хотя в действительности во время итераций и будет уменьшаться, потому что
[15:38] => у нас все меньше и меньше элементов, но мы получаем сложность образца. И для космической сложности,
[15:44] => мы не используем переменные, связанные с размером ввода , у нас постоянная сложность пространства.
[15:49] => Это решение немного медленное. Давайте перейдем к следующему. Идея второго решения состоит в том, чтобы
[15:55] => начните с сортировки массива, потому что, делая это, мы знайте, что самый большой элемент — это другая последняя ячейка,
[16:00] => второй по величине элемент непосредственно перед ним, третий по величине непосредственно перед ним, и так далее с нашим
[16:06] => массив был отсортирован, и k равно четырем. Итак, верните четвертый элемент, начиная с конца,
[16:12] => мягко говоря, мы продали наши и превращаем наши n минус k, а минус k представляет индекс
[16:18] => из ключевых элементов, начиная с конца. Для временной сложности у нас есть как аналоговые, так и для
[16:24] => сортируя массив и все одно для доступа, мы получаем O n логарифмической сложности по времени.
[16:30] => А что касается сложности пространства, то это зависит от сложности пространства или функции сортировки.
[16:36] => Это решение намного быстрее первого , за исключением некоторых случаев, но у нас все еще есть
[16:40] => все решение, которое нужно найти. В первом решение, которое нам не нужно было решать, это хорошо,
[16:47] => но поиск максимальной стоимости на каждом итерация, которая замедляет процесс.
[16:52] => Что делать, если вместо получения максимальной стоимости выход возможен только для вас, используя приоритет
[16:58] => очередь. Приоритетная очередь — это очередь, в которой следующий элемент, подлежащий удалению, не является первым, который
[17:03] => вошел с тем, у кого наивысший приоритет. И обычно это реализуется с помощью кучи. Если ты
[17:08] => не знаю о кучах и очередях приоритетов, вам действительно стоит посмотреть мое видео на YouTube на
[17:12] => тему вы найдете по ссылке ниже или можете просто поискать в кучах кода на YouTube.
[17:20] => И после построения нашей очереди приоритетов, выскакиваем следующий элемент из-за работы.,
[17:25] => таким образом, мы просто должны оплатить стоимость создания очереди приоритетов, которая является add.
[17:29] => Например, с нашим массивом, это то, что наш куча будет выглядеть так, вы можете видеть, что элемент
[17:34] => наверху находится самый большой из тех, кто извлек , и это стоит работы и перестановки заметок.
[17:41] => вторая итерация позволит извлечь первопричину работы и перестроить ее для поддержания порядка.
[17:47] => третья итерация, то же самое. Теперь, когда мы делаем к минус одна итерация, следующий извлеченный узел
[17:53] => восьмой по величине элемент, мы включим его здесь сейчас шесть. В Python у нас есть модуль hip Q
[18:01] => проблема в том, что она реализована с минимальной кучей, а не с максимальной кучей. Так что вершина найдет
[18:06] => наименьший элемент, не самый большой для счетчика , который просто умножит значения на минус один, чтобы
[18:11] => измените порядок в обратном порядке. Поэтому мы начинаем с замены нашего на минус ln для каждого элемента в нашем после этого,
[18:18] => мы нагромождаем наше, чтобы заставить его уважать кучу собственность. И теперь мы действительно начинаем извлекать,
[18:24] => мы извлекаем из него k минус один раз. После цикла мы извлекаем последний раз и возвращаем
[18:30] => результат, умноженный на минус один, очевидно, чтобы получить исходное число, хотя и было в нашем,
[18:36] => для временной сложности, которые заработали на постройку новый массив с обратными значениями и для увеличения
[18:41] => это, иди посмотри видео, чтобы узнать, почему. И затем у нас есть k минус одна итерация, каждая итерация
[18:47] => из-за работы и извлечения после цикла мы все решили извлечь еще раз.
[18:54] => В общей сложности у нас есть два n плюс k минус один раз log n плюс log n, что равно двум n плюс k log n,
[19:01] => что дает временную сложность из значений k log n, что немного лучше, чем у
[19:05] => предыдущее решение, потому что k не может превышать add. Для этого решения перестаньте давать интересные
[19:12] => разница во времени только тогда, когда n велико, а регистр мал. Потому что, когда k близко
[19:17] => за пределами кампуса k log n близко к O из n log n, временной сложности предыдущего решения.
[19:17] => Пауза, когда k близко к нулю, O из n плюс k log n близко к O из n для сложности пространства
[19:31] => у кого развернута приоритетная очередь, кто получил предложение и сложность пространства. Мы дошли до конца
[19:38] => из этого видео я надеюсь, что вы поняли три решения и посмотрите, каким будет следующее
[19:49] => возвращаясь к курсу, в этой лекции мы будем решите проблему симметричного дерева. У нас есть двоичный файл
[19:55] => дерево, и мы хотим посмотреть, симметрично ли оно. Другими словами, если это зеркало самого себя.
[20:01] => Например, это дерево симметрично, потому что, если мы возьмем его левую часть, перевернем ее, кто что
[20:06] => это правильная часть. И наоборот, если мы возьмем его правая часть, мы меняем ее на ту, которая получила свою левую часть.
[20:15] => Но этот не симметричен. Например, если мы переворачиваем его левую часть, мы не получаем правую
[20:19] => часть. Хорошо, как решить эту проблему? Чтобы проверить , симметрично ли дерево, нам действительно нужно
[20:27] => чтобы проверить, что левое и правое поддеревья являются симметричны друг другу. Кто сосредоточит на этом внимание
[20:34] => вам нужно знать, что для проблем с деревом решение обычно не является принудительным
[20:39] => мы обрабатываем корень, затем вызываем функцию на обоих поддеревьях, и мы объединяем результаты.
[20:44] => Например, чтобы получить сумму элементов двоичного дерева, у нас есть значение корня,
[20:49] => затем рекурсивно вызовите функцию для обоих поддеревьев, чтобы получить сумму их элементов.
[20:53] => После этого мы возвращаем корневое значение плюс некоторые из левое поддерево плюс часть правого поддерева. Таким образом
[21:00] => метод обхода называется поиском в глубину, и именно так мы решили большинство проблем с деревом.
[21:06] => Давайте вернемся к нашей проблеме, у нас есть два дерева, маршрут один и маршрут два, и мы хотим
[21:11] => чтобы проверить, симметричны ли они друг другу. В первом случае оба дерева пусты. В таком случае,
[21:16] => мы возвращаем true, потому что они все еще симметричны друг к другу, нет ничего, что нарушало бы
[21:20] => состояние. Во втором случае мы не будем существовать, а в другом — нет. В таком случае,
[21:26] => не позволяя ему использовать его и не симметричный потому что узел дерева, который существует
[21:31] => в другом даже не существует, оно пустое, мы возвращаем false.
[21:37] => В третьем случае оба дерева существуют, но корни не имеют одинакового значения. Здесь также,
[21:41] => они не симметричны, потому что в симметричном деревья, корни должны иметь одинаковое значение,
[21:46] => потому что, когда мы переворачиваем дерево, положение корня не меняется. И последний случай, оба дерева
[21:52] => существуют, и они имеют одно и то же корневое значение. В этом случае мы все еще можем сказать, что они симметричны,
[21:58] => потому что хорошо, корни имеют одинаковое значение. Но нам все еще нужно проверить их поддеревья,
[22:03] => одного и того же корневого значения недостаточно для обслуживания их клиентов.
[22:08] => И если мы возьмем два симметричных дерева, то сможем заметить, что они имеют одинаковое корневое значение,
[22:12] => хотя левое поддерево первого симметрично правому поддереву второго,
[22:17] => а правое поддерево первого симметрично левому поддереву второго.
[22:23] => Мы проверили, что корневые значения равны. Так нам нужно попробовать выполнить оставшиеся два условия.
[22:29] => И как мы собираемся это сделать, мы собираемся это сделать так рекурсивно, потому что, если вы подумаете об этом,
[22:34] => мы создаем функцию, которая проверяет если два бинарных дерева симметричны,
[22:37] => это именно то, что нам нужно. Вот почему мы будем использовать ту же функцию.
[22:42] => Это может показаться трудным для понимания, но именно в этом суть рекурсии
[22:46] => функция, вызывающая саму себя. Если вы не знакомы с рекурсией вам действительно следует взглянуть на
[22:51] => это перед продолжением этого курса, потому что мы будем использовать его снова в следующей задаче.
[22:56] => Если вы хотите изучить рекурсию, вы приходите к курсу, который я провел по этому предмету.
[23:00] => Это полный и хорошо оцененный курс , который позволит вам освоиться с рекурсией.
[23:06] => Давайте вернемся к нашей проблеме. Мы видели, что мы используем создаваемую нами функцию, мы видели, что мы используем
[23:12] => функция, которую мы создаем. Мы называем это маршрутом номер один точка слева и маршрутом номер два точка справа нас называют
[23:16] => на маршруте 1.1 и маршруте точка слева, и мы сообщаем вам , что оба вызова возвращают true, это означает, что оба
[23:22] => условия проверены, левое поддерево первого маршрута симметрично правому поддереву маршрута
[23:27] => с другой стороны, права первого маршрута симметричны слева от второго маршрута Юпитера.
[23:32] => Давайте быстро рассмотрим пример. Мы хотим чтобы проверить, является ли это дерево симметричным,
[23:37] => поэтому мы проверяем, симметричны ли его поддеревья друг другу.
[23:42] => Они имеют одинаковое корневое значение, поэтому мы проверяем левое поддерево корневого дерева с белыми носками от корня
[23:44] => два, одно и то же корневое значение, кто взял левое поддерево первого корня с правым поддеревом второго корня, то же самое
[23:52] => корневое значение, мы проверяем слева и справа, один и тот же корень ценность. Другие дети оба нормальные, они будут
[23:58] => повернись правдой. То же самое со значением и симметричными детьми. Все условия соблюдены, он возвращает true.
[24:05] => Теперь вплоть до фрукта один с большим количеством фруктов два, они имеют одинаковое корневое значение.
[24:10] => Их дети на обоих знают оба звонка верните значение true. Соблюдаются все условия.
[24:15] => Вызывающий абонент становится правдивым. Вернуться сюда, все условия соблюдаются. Колита — это правда.
[24:22] => Теперь рейты оффшорные на одну ногу с Латакией на двоих, они не имеют одинакового корневого значения,
[24:27] => вызов возвращает false. Не все условия соблюдаются. Вызов возвращает false.
[24:33] => Которым никогда не нужно проверять второй звонок потому что у нас уже есть неуважаемое условие.
[24:38] => Вызов возвращает false. Первоначальный вызов верните false, чтобы наше дерево не было симметричным.
[24:45] => В коде давайте сначала сделаем наш наш симметричный функция. В качестве параметра он принимает два дерева
[24:50] => маршрут один и маршрут два. Первый случай и то, и другое не существует без Q два и true.
[24:56] => Во втором случае один из них существует, а другой — нет. В третьем случае у них другой
[25:01] => корневое значение. В обоих этих случаях деревья не являются симметричными, поэтому возвращайте false
[25:07] => напишет, если корень один не равен к корню два не относится, или к корню одна точка val равна
[25:09] => не равный корню два, эта стена будет возвращает false. А теперь в последнем случае,
[25:17] => оба дерева существуют и имеют один и тот же корень ценность, нам все еще нужно выкинуть деревья,
[25:22] => которые будут бродить, я бы с удовольствием посмотрел, как много можно привязать к дроиду. И это корневое чудо пыталось
[25:23] => симметричен корню слева, мы делаем это рекурсивно, вызывая функцию дважды. Однажды с
[25:32] => корень одна точка слева и корень две точки справа и один раз с корнем один или два раза и маршрут две точки слева,
[25:38] => оба они должны возвращать true. Таким образом, мы превращаем результаты в сочетании с оператором добавления.
[25:44] => И теперь, когда наша основная функция решения симметрична, мы сначала проверяем, что входные
[25:49] => дерево существует, потому что если этого не произойдет, мы не сможем вернуть true, пустое дерево симметрично. Ещё,
[25:55] => что бы это ни было, поддеревья симметричны друг другу с функцией, которую сделал сейчас
[25:59] => мы возвращаем наших симметричных Рудольфа слева и рудоса. Верно. Это оно. Для временной сложности,
[26:06] => мы просто сначала проводим углубленный анализ поисковый обход входного дерева
[26:09] => и первая причина анти-м где n — количество узлов.
[26:14] => И для сложности пространства симметричное дерево должно быть сбалансировано. И размер стека вызовов
[26:19] => требуется рекурсивной функцией, которая пересекает сбалансированное двоичное дерево — это ужасный взгляд на то, кто получил
[26:24] => прогулочная и космическая сложность. Вот и все для этой лекции, мы столкнулись с интересной проблемой
[26:30] => на деревьях. Я надеюсь, что вы смогли понять решение, увиденное в следующей лекции
[26:42] => Добро пожаловать обратно на курс этой лекции, мы решит проблему создания круглых скобок,
[26:47] => проблема, которую мы решим с помощью обратного отслеживания. Кстати, в этот курс я стараюсь включать
[26:53] => проблемы, связанные с исследованием шпилей разных моделей отслеживание хэш-таблицы, глубина, первый поиск,
[26:59] => и так далее. Но одной проблемы и каждой из них недостаточно. Вот почему вам нужно изучить больше проблем.
[27:05] => Для этого я предлагаю вам взглянуть на мой 50 популярных курсов по проблемам собеседования с кодированием.
[27:10] => Он содержит 50 задач, отличных от задач этого курса, о многих структурах данных и
[27:15] => алгоритмические методы, вы можете ознакомиться с учебной программой и обзорами на главной странице.
[27:22] => В любом случае, давайте вернемся к нашей проблеме. Нам дают целое число n, и нас спрашивают
[27:26] => для генерации всех допустимых комбинаций из N пар скобок. Например, при значении, равном трем,
[27:32] => вот все допустимые комбинации. Прежде всего, что означает сочетание гласных и как
[27:38] => чтобы проверить, является ли комбинация действительной. Комбинация который содержит один тип круглых скобок, является допустимым.
[27:44] => Если каждая открывающая скобка имеет свою закрывающую скобка, и у нее нет закрывающего
[27:49] => скобка без использования конца открывающая скобка перед ним. Давайте рассмотрим несколько примеров.
[27:57] => Эта комбинация недопустима, поскольку эти открывающие скобки не имеют закрывающих скобок
[28:02] => синтаксис неверен. Второй пример эта комбинация недопустима, потому что мы
[28:07] => иметь закрывающую скобку без открывающей скобки конечного использования перед ней.
[28:12] => Последний пример, этот действителен, потому что каждая открывающая скобка имеет свою закрывающую,
[28:16] => и нет закрывающей скобки без неиспользуемой открывающей перед ней.
[28:22] => Теперь, как проверить, является ли комбинация действительной. Делать таким образом, мы можем поддерживать стек, в котором мы толкаем один, который мы
[28:28] => находим открывающую скобку, открываем одну и находим закрывающую. Условие состоит в том, что мы
[28:33] => не пытайтесь выскакивать из стека, когда он пуст, или стек должен быть пустым после того, как мы закончим
[28:38] => обход комбинации. Попытка выполнить запас, который пуст, означает, что у нас есть
[28:43] => закрывающая скобка без доступной открывающей скобки перед ней все, что мы нашли раньше, имеют
[28:48] => были сняты все закрывающие скобки. И второе условие состоит в том, что запас должен быть
[28:53] => пустой в конце. Потому что все еще наличие элементов в стеке после обхода означает, что у нас есть
[28:58] => открывающая скобка, которая еще не собрала закрывающую . В обоих случаях комбинация недопустима.
[29:07] => И потому, что у нас есть только один тип круглых скобок один раз,
[29:11] => нам никогда не нужны акции, кто может сделать, это использовать переменную div, которая представляет разницу
[29:15] => между числом открывающих скобок и числом закрывающих один раз. Это должно быть ноль в конце
[29:22] => и если он становится отрицательным во время процесса, то он недействителен.
[29:27] => Хорошо, но как это связано с возвращением назад? В этой задаче нас не просят проверять, является ли
[29:31] => комбинация действительна. Нас просят создать все допустимые комбинации из N пар. И мы используем
[29:38] => отступление, потому что на каждом этапе построения комбинации у нас есть две возможности: добавление
[29:43] => открывающая скобка и добавление закрывающей. И поскольку нам нужны все комбинации, мы пробуем их обе
[29:50] => потому что мы получаем новые, которые хотят добавить открывающий , и все они хотят добавить закрывающий.
[29:56] => Также в отступлении. У нас может быть состояние, при котором мы возвращаемся к продолжению,
[30:01] => это то, что мы знаем, что фактическая ветвь не будет приведи нас к правильному решению. В нашем случае,
[30:06] => если одна смерть становится отрицательной, это означает, что комбинация, которую мы построили до сих пор, недействительна,
[30:12] => бесполезно продолжать его строить, мы знаем , что это не даст нам действительной комбинации. В любом случае.
[30:18] => Давайте посмотрим на пример. При n, равном трем, мы получим это дерево рекурсии.
[30:24] => Если вам интересно, почему наш соус в шесть , потому что тогда данный нам ввод представляет
[30:29] => количество пар. И в n парах у нас есть два преимущества. Итак, мы умножаем на два, потому что мы
[30:34] => добавив одну скобку на первый уровень, мы идем влево, чтобы добавить открывающую скобку и увеличить div.
[30:40] => И когда мы идем вправо, чтобы добавить закрывающий и уменьшающийся, если
[30:46] => мы можем заметить, что у нас есть ветви , которые были остановлены ранее,
[30:49] => это ветви, которые отличались друг от друга. отрицательный. Как только они станут отрицательными,
[30:53] => мы останавливаем также Эвон с ветвями, которые создали комбинацию из N пар, мы не берем их все,
[31:00] => мы берем только тех, кто делится на ноль, помните об условии достоверности. Итак, в конце,
[31:06] => вот комбинации, которые добавляются в наш массив комбинаций.
[31:13] => Закодировать, кто остановился, создав рекурсивный функциональная стойка, которая будет заполнять комбинации
[31:17] => массив, он принимает наши параметры и количество оставшихся скобок для добавления,
[31:22] => определите разницу между открытием и закрытием скобки ОБОЗНАЧАЮТ фактическую комбинацию, которую мы
[31:27] => построение и составление теории комбинаций, той, которую мы ищем в нашей задаче.
[31:36] => Первый базовый случай — это один сложный негатив, попадание он с доктором Батрой Кодакой возвращается, чтобы вернуться в
[31:42] => предыдущий звонок. Второй базовый случай — это тот, который мы имеем смогли добавить все скобки, которые мы были
[31:48] => способен создать комбинацию. Но в этом случае мы не добавляем его автоматически в наш массив comps,
[31:54] => сначала мы проверяем, равен ли df нулю. Запомните это условие. Итак, если f равно нулю, мы рисуем
[32:00] => скобки нашей комбинации образуют строку , и мы добавляем ее в наш массив допустимых комбинаций.
[32:06] => В противном случае, у нас есть рекурсивный случай, мы сказали, что у нас есть две возможности,
[32:11] => добавление открывающей скобки и добавление закрывающей . Следовательно, у кого будет два рекурсивных вызова.
[32:17] => Для первого мы добавляем открывающую скобку к нашей комбинации, затем, когда мы вызываем и становится
[32:23] => n минус один, потому что у нас на одного родителя меньше , нужно добавить, и это становится плюсом, потому что
[32:29] => помните, что для добавления одного будет добавлено открытие скобка. После звонка мы перемещаем открытие
[32:36] => один мы добавили, чтобы поставить закрывающий. После выполнения поэтому мы снова вызываем функцию. Но на этот раз
[32:42] => разница становится разницей минус один. Помните, что мы вычитаем единицу, когда добавляем закрывающую скобку.
[32:49] => И после звонка мы убираем скобку мы добавили возможность вернуться к предыдущему вызову.
[32:54] => И мы выполнили свою функцию. Кстати, мы когда-нибудь сможем немного оптимизировать dotclear. Возвращающийся, если
[33:01] => div больше, чем add, потому что, если это так, это означает, что у нас недостаточно оставшихся
[33:06] => скобка, чтобы закрыть все наши открывающие скобки. div больше, чем n. Так что мы просто возвращаемся.
[33:13] => Если вы не понимаете, что происходит вот, взгляните еще раз на другое дерево рекурсии.
[33:18] => И самое главное, вы должны научиться подробнее о рекурсии и возврате назад.
[33:22] => Метод, который мы здесь используем для генерации всех возможных комбинаций,
[33:25] => это характерно для многих проблем, вам действительно должно быть комфортно с этим.
[33:31] => Теперь в основной функции решения мы сначала создайте массив comps, в который мы поместим наши действительные
[33:35] => комбинации, и мы вызываем нашу функцию контроля качества, чтобы заполнить ее. Но самое сложное здесь в том, что мы проходим два
[33:42] => раз n в качестве аргумента не добавляйте, потому что n заданный в качестве входных данных представляет собой количество пар,
[33:47] => также не указано количество скобок, и пара состоит из двух скобок. Так мы проходим два раза,
[33:54] => наши комбинации будут иметь длину в два раза больше. После заполнения заявки мы просто возвращаем ее
[34:01] => для временной сложности. В худшем случае, если добавить ноль, у нас будет стоимость присоединения к
[34:06] => в скобках мы пишем, что T от нуля равно добавлению n в рекурсивном случае и снова переходим от
[34:13] => комбинация стоит одного, но у нас есть два вызовы, при которых размер входного сигнала уменьшается на единицу
[34:18] => и становится добавленным минус один в общем количестве t из n равно двум умноженным u на r минус один плюс один.
[34:27] => Теперь мы продолжаем заменять t из n равным двум кратным t из n минус один плюс один. Набор из N минус один равен
[34:30] => равный двум кратным t из n минус два плюс один, мы замените или упростите, и мы получим четыре раза два
[34:40] => и минус два плюс три. Мы снова заменяем, t из n минус два равно два раза два от Армани три плюс
[34:46] => один заменит, упростит, и мы получим , что восемь раз T животного равно трем плюс семи.
[34:54] => Это рекуррентное соотношение является общим, мы можем уже обратите внимание на форму тренировки. Это т из н не так ли
[35:00] => К мощности k, умноженной на t от n минус k плюс две мощности k минус один, у нас значение T равно нулю, поэтому мы
[35:07] => нужно найти значение K, чтобы перейти к нулю T и минус k, равному нулю. Таким образом, k равно n,
[35:14] => где плюс k на n, кто получил t из n, равно двум мощность n, умноженная на T от нуля плюс к мощности n минус один.
[35:21] => Мы знаем, что T из нуля — заработанное рабочее место, мы получили t из n, равное двум степеням n раз
[35:27] => n плюс две степени n минус один дали бы нам O, умноженное на n, умноженное на n, сложность по времени.
[35:33] => Знайте, что здесь и представлена длина комбинации, которая в два раза
[35:37] => количество пар, предоставленных нам для ввода. Кроме того, n, умноженное на две степени n, не является точной мощностью,
[35:43] => количество операций будет меньше, чем это сделайте две ветви, где мы возвращаемся назад ранее,
[35:48] => O из n, умноженного на две степени n, будет точным связанный, если бы у нас не было условий для наших комбинаций.
[35:55] => Если вы не знаете, какой метод используется для определения временной сложности этой рекурсивной функции.
[35:59] => Это называется методом замещения, это важная техника, которую вы должны знать и которой должны научиться
[36:03] => об этом. А для космической сложности у нас есть n плюс один для стоимости, такой как размер, длина
[36:10] => самой длинной ветви в дереве рекурсии. Но нам также нужно подсчитать необходимое пространство для хранения
[36:15] => комбинации. Длина комбинации равна at, и она состоит из двух возможных символов. Так
[36:22] => у нас есть две силы и возможные комбинации. И длина каждого из них равна n. Поэтому мы
[36:27] => для их решения требуется n раз две степени n пространства. Мы сбился со времен мощи и космической сложности.
[36:34] => Но не все из них действительны, мы будем требуется намного меньше, чем n раз, чтобы включить n,
[36:39] => n, умноженное на две степени n, — это просто верхняя граница. И у всех нас есть необходимое пространство для комбинаций
[36:45] => в n раз больше количества элементов после заполнения массива связи. Мы дошли до конца
[36:51] => из этой лекции я надеюсь, что вы поняли это возвращаемся к решению и увидимся в следующем.
[37:04] => Добро пожаловать обратно на курс этой лекции даны правила или проблема с заправкой
[37:09] => круг — список заправочных станций, где мы можем перейти со станции II на станцию i плюс один,
[37:14] => и последний из них возвращается к первому.
[37:18] => И нас просят найти индекс станции , с которой мы начинаем, чтобы иметь возможность пройти все
[37:22] => станций и вернуться к начальной без кончается бензин. Знайте, что мы можем только двигаться
[37:30] => вперед, газовые баллоны, подумал пустой газ из i представляет количество газа на станции i
[37:35] => стоимость железа представляет собой стоимость перехода со станции на следующую, ответ таков
[37:40] => гарантированно будет уникальным. И если на станции мы будем поиск не существует возврат минус один мы
[37:44] => использовал или будет не более одной станции для большего мы можем пройти и быть в состоянии вернуться.
[37:52] => Например, если у нас есть эти 10 станций, то на выходе получается восемь, потому что, когда мы начинаем со станции
[37:57] => восемь, мы можем вернуться к этому, не выбегая из газа. Мы начинаем без газа, как уже упоминалось в
[38:02] => проблема, мы добавляем для газа станции восемь и мы платим одному за переход на следующую станцию, кто добавляет
[38:04] => пять заправок на заправочной линии, и мы платим два за переезд на следующей станции мы добавляем один и платим пять, кто
[38:11] => прибавляем пять и платим два, или три и платим два, или три и платим восемь, мы прибавляем пять и платим два,
[38:15] => или три и заплатим за то, что мы добавим один и заплатим два, или три и заплатим пять, и мы сможем вернуться
[38:26] => на восьмой станции вы могли видеть, что количество газа никогда не становилось отрицательным. Но это не так
[38:32] => для офисных станций, например, с первой станцией кто добавляет пять и платит два, или три и платит два,
[38:37] => или три. И если вы заплатите восьмерку, чтобы перейти на следующую станцию, количество газа станет отрицательным,
[38:44] => а это значит, что мы не можем продолжать, станция, с которой мы начали, не та.
[38:51] => Давайте решим эту проблему. Решение грубой силы , которое мрачно приходит нам на ум, состоит в том, чтобы просто
[38:56] => смоделируйте, что происходит с каждой станцией, и мы найдем ту, которая уважает условия, которые включают ее
[39:02] => индекс. Давайте попробуем сделать это на нашем примере. С первым мы добавляем один с пятеркой и стоимостью
[39:09] => становится отрицательным и устраняется. Следующий, мы добавляем пять и П два, у нас есть три и П два, у нас есть
[39:14] => три и восемь проветривают количество оставшегося газ стал отрицательным, а не этот. Следующий, третий
[39:22] => и PE два у нас есть три NP восемь и оставшиеся стал отрицательным. Следующий, у нас есть три или восемь
[39:29] => остальные стали отрицательными. Следующий, мы добавляем пять и платим два или три и платим за то, что мы добавляем один и
[39:35] => заплати два или три и заплати пять, а остальные стали отрицательный, только не этот. Следующий, мы добавляем три и
[39:42] => платите за негатив. Следующий, мы добавляем один и платим к следующему, у кого есть три, и заплатите пять
[39:48] => отрицательный следующий, у кого плюс четыре минус один плюс пять минус два плюс один минус пять плюс пять
[39:56] => минус два плюс три минус два плюс три минус восемь. было четыре минус два, плюс три минус четыре,
[40:02] => плюс один минус два плюс три минус пять. И мы смогли вернуться на станцию
[40:07] => с того места, где мы начали без альтернативы потому что мы знаем, что ответ уникален.
[40:14] => В коде мы создаем функцию, которая принимает наши параметры, теорию газа массива, стоимость,
[40:19] => и индекс формы станции, где, как мы думали , цель этой функции — сообщить нам, можем ли мы
[40:25] => завершите цикл, начав с первой мысли, нам сначала нужна переменная, остающаяся
[40:31] => этот источник оставшегося количества газа, мы также нужна переменная для хранения нашего фактического положения.
[40:36] => Наша начальная позиция — станция FOMO, мы подумали, что так инициализируем наш дополнительный старт.
[40:43] => И нам также нужна логическая переменная. чтобы знать, кто уже начал ходить или нет,
[40:48] => нам нужна эта переменная в нашем состоянии цикла. Мы нужно продолжать зацикливаться, пока мы не вернемся к началу,
[40:54] => мы пишем, почему не равно начинать или не начинать. Здесь важно не начинать,
[41:00] => потому что, если мы его не используем, мы даже не войдем в цикл. Помните, что я инициализирую акции.
[41:06] => Поэтому я установил наших равных, мы хотим, чтобы они будьте равны. Но после прохождения цикла,
[41:11] => не сейчас вот почему нам нужна начатая переменная чтобы знать, находимся ли мы в том случае, когда равно
[41:16] => начинай, потому что мы еще не начали. Или потому, что мы пересекаем цикл, и я вернулся к началу.
[41:23] => Давайте продолжим внутри цикла, который, как мы видели, начался с true, потому что мы начали, когда обновили оставшееся.
[41:29] => Мы увидели, что на станции i у нас есть количество газа в ней, и мы оплачиваем стоимость перехода на следующую
[41:35] => один. Поэтому мы добавляем газ к нашему ответу стоимость лекарств I. После этого, если мы в основном станем отрицательными,
[41:42] => это значит, что мы не могли вернуться к соли, мы не хватает бензина, мы возвращаем ложь, иначе,
[41:48] => мы переезжаем на следующую станцию. Следующая станция обычно — это я плюс один. Но нам нужно добавить модули
[41:54] => количество станций для обработки этого случая было последней станцией i, которая становится i плюс один дополнительный модуль
[42:00] => и все возвращается к нулю, мы правы, я становлюсь плюс один увеличивает количество станций.
[42:08] => И если мы закончим цикл, это будет означать, что мы закончили смог вернуться, чтобы начать возвращать истину.
[42:14] => Теперь в нашей основной функции решения мы просто попробовали функцию, которую мы сделали на каждой станции
[42:19] => как мы сделали в примере. И мы превращаем фактический станция, как только функция вернет значение true.
[42:25] => И если функция выйдет из строя со всеми станциями , будет n минус один для временной сложности,
[42:31] => потому что ответ уникален. A возможный наихудший случай — это один,
[42:35] => потому что, начиная с нулевой станции, которая охватывает n станций, прежде чем получить отрицательную сумму
[42:40] => от первой станции, которая охватывает n минус один от станция два, которая охватывает n минус два, и так далее,
[42:47] => мы получаем сумму n плюс n минус один плюс n минус два и так далее до единицы. После упрощения,
[42:54] => мы обнаружили, что это O из n в квадрате, мы будем получите O из n квадратов временной сложности,
[42:59] => или постоянная сложность пространства, потому что мы не используем переменные, связанные с размером ввода
[43:06] => из n в квадрате является низким. Для решения этой проблемы мы выход из n в квадрате, потому что для каждой станции,
[43:10] => мы снова проходим почти все станции, давайте посмотрим, как это оптимизировать. Главное, чтобы
[43:16] => вам нужно понять, что второе решение заключается в том, что если мы начнем со станции или индекса
[43:21] => подумал и достиг отрицательного значения станции Я затем все станции между Статен-Айлендом.
[43:27] => недействительны. Нам не нужно пробовать их с доктором Джоном, чтобы выбрать один. Позвольте мне сказать вам, почему. Мы
[43:34] => есть случай, когда газ мысли меньше чем стоимость старта. Он петля останавливается мрачно
[43:39] => поскольку оставшееся становится отрицательным, это останавливает нас , поэтому другие станции не задействованы.
[43:44] => Здесь не о чем говорить. Но когда гусов Начнет больше или равно стоимости соли, цикл
[43:51] => перемещается на все станции, он может пересечь множество станций, прежде чем оставшееся станет отрицательным.
[43:57] => Например, здесь, когда мы начинаем с четвертой станции, остаток становится отрицательным при индексе семь. Это
[44:02] => означает, что все станции 456 и семь недействительны. Мы снова начнем с первой, восьмой цели. Но почему
[44:09] => девушки будут стартовать больше или равно стоимости старта. В нашем случае разница составляет три.
[44:15] => Каждые три рассматриваются как преимущество перед начиная со следующих станций, это как бонус за
[44:21] => начиная с четвертой станции. У нас есть еще три заправки и установка со следующей, пятой станции.
[44:27] => И даже с этим бонусом у нас было недостаточно газ, чтобы сделать полный цикл. Мы остановились на станции
[44:33] => седьмая авеню в тот день мы не могли проехать через седьмую станцию. Так как же ты хочешь перейти
[44:38] => это без бонуса? Это похоже на то, что у вас есть 500 долларов, и их недостаточно, чтобы купить ПК с частицами. Тогда ты
[44:45] => скажите, что этих 500 долларов было недостаточно. Я попробую с четырьмя сотни, может быть, их будет достаточно. Это логичный
[44:55] => и вот почему, когда остаешься, становится отрицательным. Мы не пытаемся снова с той станции, которая приходит
[44:59] => после того, с чего мы начали, кто пропустил всех , кто прошел, мы начали переходить от IPO.
[45:05] => На нашем примере тех, кто начинает с самого начала, мы можем назвать отрицательными тех, кого учили на IPO
[45:10] => один на пять, и мы платим, два оставшихся становятся тремя , кому три, мы платим, два оставшихся становятся четырьмя,
[45:17] => кому еще мы платим восемь оставшихся, становится минус один минус. То, что мы собираемся сделать сейчас, это
[45:23] => закрепите старт снова отсюда, без повторяю попытку, от одной станции до трех,
[45:28] => кто добавит последующие действия к оставшимся, станет тремя, кому еще мы заплатим за оставшихся, станет Сью, кто
[45:33] => добавьте того, кто заплатит два оставшихся, станет тем, у кого есть свободная воля, на пять оставшихся станет минус один
[45:39] => отрицательный. Еще раз, без его мысли, снова, от i плюс один, мы добавляем четыре, мы платим один оставшийся
[45:46] => становится три, кто добавляет четыре, кто платит два оставшихся становится шесть, и мы заканчиваем обход массива,
[45:52] => кандидат — восьмая станция. Но это не так означает, что он может выполнить полный цикл, это просто означает
[45:58] => что мы можем добраться до конца массива без достижение отрицательного количества газа. Мы не проверяли
[46:03] => горшок перед ним. Вот почему я сказал «кандидат». Это потенциальная клапанная станция. Мы еще не знаем.
[46:10] => Сказать, что станция-кандидат действителен, начиная с их
[46:14] => оставшийся промах никогда не станет отрицательным, пройдя путь от кандидата до конца.
[46:18] => Но также и при прохождении пути от начала массива до предложения кандидата X.
[46:24] => Первая часть цикла — это то, что мы проверили во время обхода. И для второй части
[46:29] => цикл, мы только что вычислили сумму газа из ноль кандидату минус сумма затрат от нуля
[46:35] => для кандидата результат представляет собой оставшийся газ после прохождения этого горшка. И если путем добавления
[46:42] => если результат остается положительным, то кандидат является действительной станцией. Иначе у нас нет
[46:47] => действующая станция. Например, здесь сумма газа от нуля до исключительного кандидата равна 24.
[46:54] => Сумма курса от нуля до эксклюзива кандидата составляет 30. Разница составляет минус шесть. Что осталось
[47:01] => от кандидата до конца шесть, то, что остается в банке до кандидата, минус шесть, добавляя
[47:06] => их вместе мы получаем ноль, который является положительным. Так кандидат — это действительная станция. Вопрос. Что, если
[47:12] => здесь мы получили отрицательный результат, затем с Акутаном минус один, потому что нет действительных станций.
[47:19] => Но что делать, если действительная станция придет после кандидата, это невозможно. Еще раз,
[47:24] => форма станции, с которой мы начали. имеет преимущество перед соседними станциями,
[47:29] => мы знаем, что газ кандидата больше, чем или равна стоимости кандидата. Так что даже если с
[47:34] => этот бонус, мы получаем отрицательное оставшееся количество газа, так же будет и на следующих станциях.
[47:42] => Давайте перейдем к коду на стороне, где все это оставшееся начинается с нуля. И то же самое
[47:46] => вещь для кандидата, потому что в начале мы предполагаем, что первая станция — это кандидат,
[47:51] => потенциальная станция долины. Теперь мы начинаем обходить станции. Для каждой станции мы обновляем
[47:58] => оставшийся газ, мы являемся гостями нашего грузового автомобиля стоимость искусственного интеллекта. И если оставшееся становится отрицательным,
[48:04] => мы продаем, чтобы начать все сначала с малого, он становится новым кандидатом, а оставшийся становится
[48:09] => ноль, потому что мы начнем все сначала. После цикла мы рассчитываем оставшийся газ в котле до
[48:15] => кандидат сумма газа минус сумма затрат на горшок от нуля до кандидата X пункт IV.
[48:22] => Теперь у нас есть три возможных случая у нас есть случай или кандидат равен и
[48:27] => это означает, что мы достигли конца массива, не найдя потенциальной станции,
[48:31] => ни одна станция не добралась до конца массива, мы возвращаем минус
[48:35] => один. Таким образом, в случае, если у нас есть кандидат, но при добавлении оставшихся предыдущих мы обнаружили отрицательный
[48:40] => результат, это означает, что он остановился где -то в банке от нуля до возврата кандидата
[48:44] => минус один. И в-третьих, у нас есть кандидат и оставшееся плюс оставшаяся молитва не является отрицательным.
[48:51] => Так что кандидат — это ложная станция для большего, чем мы начните делать полный цикл, мы его вернем.
[48:59] => В коде. Если кандидаты равны протяженность газопровода, количество станций,
[49:03] => или оставшееся процветание меньше нуля, мы возвращаем минус один, еще мы возвращаем кандидата
[49:11] => кто может даже следить за тем, чтобы оставаться в первом цикл, чтобы избежать повторного обхода для вычисления
[49:16] => суммы. Для временной сложности у нас просто есть цикл это делает n итераций, все остальные операции выполняются в
[49:23] => над одним мы получаем сложность включения и выключения, где n — количество станций, намного превышающее O из n
[49:29] => возведенный в квадрат. Добавьте постоянную сложность пространства, потому что мы не используем входные данные всех связанных переменных.
[49:37] => По сути, в решении мы ищем кандидата на станцию, которая сделала
[49:40] => это до конца массива без достижение отрицательного количества газа.
[49:44] => Затем мы проверяем, все ли еще повышается при прохождении оставшихся станций,
[49:48] => те, кто в банке с начала массива и до возвращения к нему, кто в конце
[49:54] => из этого видео. Я надеюсь, что вы поняли оптимальное решение и посмотрите, что будет дальше
[50:06] => Добро пожаловать обратно на курс этой лекции правила курса запланированная задача,
[50:10] => у нас есть n курсов, помеченных от нуля до n минус один в пунктах, которые нам нужно пройти.
[50:16] => Но некоторые из них являются предпосылками другого, мы не можем пройти курс, не пройдя другой.
[50:22] => И мы должны определить, возможно ли закончить все курсы. Итак, нам дано целое число
[50:28] => как представляющее количество курсов и набор предварительных условий, которые являются предварительными условиями r, является
[50:33] => равное a b означает, что вам сначала нужно пройти курс P, прежде чем проходить курс a. Например,
[50:39] => если у нас есть этот ввод, то вывод должен быть ложным. Потому что, чтобы пройти третий курс, мы должны были пройти
[50:43] => нулевой курс, и чтобы пройти ее, зеро должен был пройти курс первый. И чтобы пройти первый курс, мы должны иметь
[50:44] => пройдя третий курс, это невозможно, это как будто у нас есть цикл зависимости. Это
[50:55] => почему мы не можем закончить все курсы? ложный. Но с этим вводом вывод верен,
[51:02] => мы можем взять или ноль, затем третий курс, затем курс первый, затем курс пятый, затем курс второй,
[51:05] => этот курс для каждого курса будет иметь свой обязательное условие, удовлетворенное при его приеме.
[51:12] => Как решить эту проблему. Здесь у нас есть элементы, курсы и взаимосвязи между ними,
[51:18] => конечно, быть одобренным означало быть романом курс. И каждый раз, когда мы сталкивались с такой ситуацией,
[51:23] => имея элементы и связи между ними, вам следует подумать об использовании графика.
[51:28] => Я не говорю, что это всегда даст лучшее решение. Но даже если этого не произойдет, это, по крайней мере, произойдет
[51:34] => дать вам возможность визуализировать проблему с вершины и связи между ними. В нашем случае,
[51:40] => вершины представляют собой трассы и ребра представлять зависимости и добавлять от u к
[51:45] => v означает, что сначала нам нужно пройти курс для вас, прежде чем мы сможем оплатить курс.
[51:52] => Хорошо, теперь мы строим наш график, у нас есть ориентированный график, что мы будем с ним делать.
[51:57] => Сейчас наша цель — найти цикл зависимости. Если мы его найдем, это будет означать, что это невозможно
[52:02] => для завершения всех курсов верните значение false. Иначе, если мы не находите его вообще, это значит, что это возможно
[52:08] => чтобы закончить родинку, верните true. По сути, мы поиск цикла в ориентированном графе. В одном
[52:16] => связанный список, классический способ проверить, есть ли цикл состоит в том, чтобы перемещаться по связанным спискам при сохранении
[52:21] => посещенные узлы. И если мы наступим на узел, который мы посещенный ранее, это означает, что существует цикл.
[52:28] => Мы можем подумать о применении той же логики для графа который охватывает поиск по глубине в первую очередь, например,
[52:33] => при использовании набора посещенных узлов. И если мы наступим на узел, который уже был посещен, это означает
[52:38] => что у нас есть цикл, возвращающий false. Кстати, если вы не знаете о полном поиске, это способ
[52:45] => о том, чтобы пересекать деревья и графики, погружаясь глубоко в направление, пока мы больше не сможем двигаться вперед.
[52:51] => Вернитесь назад, попробуйте пройти весь путь и так далее. Я сделал огромное видео на эту тему, которое вы можете посмотреть.
[52:57] => Вам нужно знать о DFS, прежде чем продолжить , это видео является обязательным условием для каламбура.
[53:04] => Но эта стратегия не всегда работает работа. Вот встречный пример.
[53:09] => У нас есть этот график, давайте начнем обход. Мы начните, например, с двух мы помещаем его в посещаем его
[53:14] => мы движемся к нулю, мы втягиваем его, и он будет переходим к трем, мы притворяемся, что пришли в гости. У этого есть
[53:20] => никаких исходящих других, мы возвращаемся назад, у этого есть не осталось соседей, которых можно было бы пересечь, и мы возвращаемся назад.
[53:27] => Отсюда мы переходим ко второму соседу, мы помещаем его в визит, он переместится в четыре, мы помещаем его
[53:31] => в посещенном. Затем отсюда мы переходим к трем , и это уже в посещении, поэтому наша стратегия
[53:36] => вернет false. Что неправильно, потому что мы можем полностью закончить все курсы здесь.
[53:42] => Мы можем начать с двух, затем с нуля, затем с трех, чем с одного, чем с четырех, все предварительные условия соблюдены.
[53:50] => Было ли принято решение? Что ж, позвольте мне сначала поговорим о топологической сортировке.
[53:55] => У нас есть ориентированный граф, где вершины представляют задачи, а объявление от u до v означает, что u равно
[54:00] => предпосылкой V. топологической сортировки является процесс нахождения линейного упорядочения вершин
[54:06] => таким образом, каждая вершина, следующая за, является привилегией. И все слова, для каждого ребра от u до v,
[54:12] => V должен следовать за вами в заказе. Для пример, для этого графика здесь приведен допустимый порядок.
[54:20] => Знайте, что действительный заказ не всегда уникален, можно найти все заказы, которые
[54:24] => удовлетворяйте условию. Но логическая сортировка не всегда возможна. Это невозможно, когда
[54:31] => график содержит цикл, подобный этому. B — это a предпосылка C, C является предпосылкой D, D
[54:38] => является предпосылкой E, а E является предпосылкой Б, так что у нас нет возможности заказать их. К счастью,
[54:45] => выполняя топологическую сортировку, мы можем обнаружить существование цикла. Если это произойдет,
[54:50] => мы просто останавливаемся и говорим, что у нас не может быть правильного порядка вершин. И это именно то, что мы
[54:56] => хочу заняться нашей проблемой, у кого есть курсы. Некоторые из них являются предпосылками для других,
[55:01] => и мы хотим знать, можем ли мы пройти все курсы и все условия, если существует действительный заказ.
[55:07] => Следовательно, кто будет использовать биологический источник и если во время процесса мы обнаружили цикл
[55:12] => возвращает false. В противном случае верните true, потому что это означает, что мы смогли сделать заказ.
[55:19] => Хорошо, но как работает топологическая соль? A возможный способ реализации биологического источника
[55:24] => это поиск в первую очередь по глубине. Давайте, например, мягко вспенивая эту вершину, мы помещаем ее в прошлый стек,
[55:30] => таблица содержит вершины фактического пути. B — его сосед, мы идем к нему, и мы
[55:37] => кладем его на прошлую стопку — это его сосед, мы идем к нему, и мы помещаем его в стек путей. Он
[55:43] => его сосед, мы идем к нему, и мы помещаем его в стек путей.
[55:47] => Теперь у него нет соседей, это значит, что мы можем смело включить его в наш заказ,
[55:51] => поскольку нет вершин, которые должны появиться после того, как они никому не принадлежат, мы помещаем их в
[55:57] => заказ складывается, и мы возвращаемся к предыдущему узлу. Следующий сосед — я пойду к нему, и мы наденем его
[56:04] => стек путей. Опять же, у него нет соседей, которые удаляют его из стека путей и вытаскивают
[56:10] => на всем стеке. И мы возвращаемся назад. Следующий сосед — это если мы пойдем к нему, J — сосед, мы пойдем к нему,
[56:18] => у него нет соседей, мы перемещаем его из стека путей , помещаем во весь их стек и возвращаемся назад.
[56:24] => Следующий сосед — это все, но его уже посетили. Оно больше не имеет непрошенных соседей, поэтому все вершины
[56:30] => должны прийти после этого при заказе нашего визита, мы можем смело поставить это и вернуться назад.
[56:37] => У этого тоже больше нет непрошеных соседей, мы можем привести его в порядок, и мы возвращаемся.
[56:44] => И этот процесс продолжается в том же духе. До тех пор мы проходим весь график конца,
[56:49] => мы получаем этот порядок, мы меняем его вместе от начала до конца. Теперь все наоборот. зашифровать
[56:57] => наша функция DFS предоставляет нам параметры для построения графика вершины, с которой мы начинаем путь.,
[57:02] => самый старый стек и набор посещенных узлов. Мы начните с добавления нашей вершины в прошлое, как раз тогда, когда
[57:10] => мы начинаем обходить его, затем для каждого непрошеного сосед, который первым добавил его в гости, и мы зовем
[57:16] => DFS с ним в качестве аргумента для его прохождения. После этого для всех соседей, которые могут безопасно положить
[57:22] => фактическая вершина в самом старом стеке появится из прошлого стека и передаст ее всему стеку.
[57:29] => И в нашей основной функции сортировки сверху она принимает нас в качестве аргумента список смежности нашего графика,
[57:34] => это соответствует самому посещению, Бастоку, старшему стеку,
[57:38] => затем он посещает каждую не посещенную вершину с DFS. Сделав это, другой
[57:43] => стек заполняется поворотами в обратном порядке от первой вершины к последней.
[57:48] => Теперь все наоборот. И начиная с этого алгоритм, мы можем добавить инструкции для обнаружения цикла
[57:56] => мы находим цикл, когда вы находите заднюю дугу, и когда она переходит от вершины u к вершине V,
[58:02] => где V уже находится в стеке путей. Как здесь у нас есть B, C, D, E, затем у него плохой сосед,
[58:09] => который уже находится в стеке путей. Этот график содержит цикл B и E, зависит друг от друга.
[58:17] => В коде наша функция DFS не будет булевой функцией. Он возвращается, если да или нет, мы были
[58:22] => возможность сделать заказ. Что мы добавляем, так это то, что прежде чем переехать к соседу, мы проверяем, не
[58:28] => уже в стопке. Если это так, то без возврат false, мы не можем сделать действительный заказ.
[58:34] => Кроме того, если включение обхода возвращает false, это означает , что мы нашли цикл, идущий оттуда. Этот
[58:40] => вот почему, если рекурсивный код окажется ложным, будет также верните здесь false. И если бы мы смогли
[58:46] => пересекать соседей, не получая отрицательного результат возвращает true, мы могли бы сделать заказ.
[58:53] => Знайте, что для оптимизации проверки наличия фактической вершины в стеке,
[58:57] => лучше использовать набор вместо списка поиск и утверждение — это старый одноразовый средний
[59:02] => pass doc теперь имеет тип, установленный в начале, мы добавляем к нему нашу вершину после того, как Lupu переместит ее в
[59:08] => добавьте его ко всей стопке. И в нашем главном решении функции, нам сначала нужно построить график
[59:16] => потому что на входе будет указано количество курсов и список необходимых условий. Теперь список смежности
[59:23] => чтобы построить список смежности, мы знаем количество вершин, поэтому создаем
[59:27] => массив из N пустых массивов. Каждый из них будет содержать соседей по курсу I
[59:33] => знать, какие первые предпосылки проблемы говорит, что предпосылка одного должна прийти раньше
[59:38] => предпосылка нулевая. Поэтому создайте объявление из предпосылка одного два предпосылка нуля.
[59:44] => Другими словами, кто добавляет предпосылку для У 02 соседей есть один из них.
[59:50] => Теперь, когда мы создали список смежности, мы можем начните обход, но до того, как мы создадим визит
[59:55] => сама по себе, прошедшая дуга, которая также является набором в стеке заказов, для каждого и посещенного курса,
[60:02] => кто добавил в гости, и если звонит в DFS с этим возвращает false, это означает, что мы не смогли построить
[60:07] => старый, мы нашли цикл. Так что возвращайся ложь, которая не может изучить все курсы
[60:13] => выход из цикла не возвращает false, это означает , что мы могли бы найти порядок, потому что все
[60:18] => порядок курсов возвращает значение true. И мы смогли чтобы решить нашу проблему. Для временной сложности,
[60:26] => мы просто выполняем дублирование для поиска на графике. И временная сложность DFS часто для v плюс
[60:32] => длина E, длина v — это количество вершин, а длина E — количество ребер,
[60:38] => т.е. количество вершин — это количество ходов и, и количество ребер
[60:42] => это M для длины списка предварительных требований, который поступил за пределы кампуса и обнаружил сложность.
[60:49] => А для сложности пространства у нас есть пространство для длины списка смежности v плюс длина
[60:53] => из E, пространство для посещенной заданной длины v, пространство для стека путей и более старого стека
[60:59] => длина v и пространство для стека вызовов длина v в общей сложности, кто получил полную временную длину
[61:05] => из v плюс длина v, которая является ужасной длиной v плюс длина v, у кого есть яблоки.
[61:12] => Знайте, что вы можете найти аналогичное решение. Но с воротниками каждая вершина может иметь белый цвет,
[61:17] => серый или черный. По сравнению с нашим решением, что означает и посещал. Зеленый означает посещенный
[61:23] => и в прошлом темный, а черный означает посещенный добавить больше не в прошлом,
[61:28] => мы привели это в порядок. И если мы нашли замечательного соседа,
[61:32] => это означает, что он находится на правильном пути, и мы нашел его снова. Таким образом, у нас есть цикл, возвращающий false.
[61:42] => Не реализована топологическая сортировка с поиском по глубине. Но мы также можем это реализовать
[61:46] => с первым поиском вширь. Позвольте мне показать вам, как это делается. Если вы не знаете о ширине, сначала выполните поиск,
[61:51] => Я снял об этом видео на YouTube, рекомендую вам посмотреть его, прежде чем продолжить.
[61:58] => Общая идея нашего второго решения состоит в том, чтобы разделить наш ориентированный граф на уровни
[62:03] => и на первом уровне у нас есть вершины, которые не имеют предварительные условия, мы проведем эту мысль, изучая
[62:07] => их. Как только мы закончим, мы сможем удалить их с графика, удалив их с графика. Так
[62:14] => у вершин больше не будет предварительных условий, потому что их предварительными условиями были курсы, которые мы только начали
[62:19] => и они довольны. И эти вершины представляют второй уровень, мы поместим их в
[62:25] => наш заказ и удалите их после удаления, чтобы у вершин больше не было предварительных условий,
[62:32] => они представляют собой третий уровень, мы ставим их в нашем заказе и удалите их.
[62:37] => И этот процесс продолжается до тех пор, пока у нас больше не останется вершин.
[62:44] => И то, и другое удаление вершин из графика требует времени, потому что нам нужно обновить список смежности.
[62:49] => Вместо этого мы будем отслеживать интеграл каждой вершины
[62:53] => и когда мы пересекаем вершину, мы уменьшаем интеграл всех этих соседей,
[62:58] => степень in вершины — это количество ребер , входящих в нее. Например, интеграл
[63:03] => этой вершины, поэтому, когда мы удаляем вершину , которая идет к ней, она уменьшается в степени
[63:10] => и если интеграл вершины становится равным нулю, он чувствует, что все его предпосылки удовлетворены,
[63:15] => кто может его пересечь, мы ставим его в очередь. С помощью этого графика мы называем интеграл каждой вершины,
[63:22] => мы ищем вершины с интегралом из нуля, мы ставим их в очередь, и вы
[63:26] => примените классический обход BFS. Разница в том, что когда мы извлекаем узел из очереди,
[63:32] => которые начинают с того, что помещают его в упорядочивающий массив потому что у него нет оставшихся предпосылок,
[63:36] => также хотите пересечь соседа с уменьшается в степени, и если оно становится равным нулю,
[63:41] => мы ставим его в очередь. Последнее, что было бы не нуждаемся в посещаемом наборе, потому что мы не
[63:47] => помещаем вершину в очередь до тех пор, пока мы не закончим обход всех вершин, которые идут к ней.
[63:52] => Таким образом, у нас нет риска снова пересечь вершину. С этим графиком происходит вот что.
[64:19] => Encode создаст массив пустых массивов, как мы сделали с DFS,
[64:24] => но мы также добавим массив из N нулей решить интеграл от каждой вершины.
[64:29] => Теперь при заполнении списка смежности также будет увеличиваться степень предварительного условия до нуля
[64:34] => потому что предпосылкой нуля является вершина где входит ребро, так увеличивается в степени
[64:40] => теперь мы создадим массив, в котором мы разместим наш заказ и выстроим очередь.
[64:44] => Очередь изначально содержит вершины мотыги в градусах нуля,
[64:48] => после того, как он начнет перемещаться, пока cool все еще содержит элементы, появится вершина, которую мы
[64:54] => добавьте его в заказ, потому что в нем нет неудовлетворенных предпосылки, и мы пересекаем его соседей для
[64:59] => каждый из них имеет разные методы по степени, и если он становится равным нулю, мы включаем его, как объяснялось ранее.
[65:06] => После цикла другой массив не заполнен, мы верни его. На этот раз нам не нужно ничего менять
[65:11] => потому что мы начали с размещения вершин уровня ноль больше единицы и так далее. С этим топологическим
[65:18] => алгоритм сортировки, мы также можем обнаруживать циклы. Когда график содержит циклы. Что происходит
[65:23] => заключается в том, что в какой-то момент процесса мы будем у вас больше нет вершин с нулевым индексом,
[65:28] => это означает, что ничего не будет вставлено в очередь, процесс остановится раньше, массив будет
[65:33] => содержат меньше общего числа вершин, которые сделают вывод, что процесс не мог продолжаться
[65:38] => потому что существует цикл. И в нашей проблеме, кто просто хочу знать, можем ли мы сделать заказ или
[65:43] => нет, вот почему после цикла, кто просто сравните длину массива заказов с добавлением
[65:48] => количество курсов либо равно, алгоритм возвращает true, либо возвращает false.
[65:56] => Таким образом, мы сохраняем тот же код, который только что изменил оператор возврата с длиной заказа
[66:00] => равно добавлению. Что касается временной сложности, мы просто применяем поиск в ширину в первую очередь,
[66:07] => который имеет длину от плюс длины временной сложности O n плюс m в нашей задаче.
[66:13] => А для сложности пространства у нас есть длина v плюс длина a для списка смежности,
[66:18] => длина v для массива в градусах и длина v для очереди упорядоченного массива,
[66:23] => трехкратная длина v плюс длина V дает значение для v плюс длина E,
[66:27] => что составляет m плюс m, и наша проблема в том, что мы получаем сложность пространства за пределами кампуса M.
[66:34] => Мы дошли до конца этого видео, в этом мы решаем проблему совместного расписания
[66:38] => двумя разными способами. Я надеюсь, что вы поняли их обоих и увидели следующее.
[66:49] => Добро пожаловать обратно на курс этой лекции, мы решит проблему перестановки Киета с
[66:54] => диапазон чисел от одного до n в предложении IV, который может сделать n факторных перестановок.
[67:00] => пометив их в порядке, начиная с одного, вас попросят вернуть перестановку Кейта.
[67:06] => Например, при n, равном трем, и k равно трем, вот три
[67:09] => факториальные перестановки из 123 помеченных аниматоров K равно трем, поэтому мы превращаем третье число в одно, три.
[67:18] => Первое решение, которое может прийти вам в голову, очевидно, является решением грубой силы,
[67:22] => генерация всех перестановок не возвращает регистр один, мы даем функции диапазон
[67:28] => от единицы до n в шкафу, затем мы возвращаем единицу с индексом k минус один. Помните, что массив равен нулю
[67:34] => проиндексирован, так что Кит один находится с индексом k минус один. Но проблема с этим решением заключается в том, что с
[67:41] => n элементов, мы можем сделать n факторных перестановок легких, добавив, что это стоит n раз n факториалов, чтобы
[67:47] => генерируя их, мы получаем n или m умноженных на n факторных временных сложностей Soulshine, что чрезвычайно
[67:52] => медленный. Мы действительно использовали дерево для решения этой проблемы , чтобы иметь возможность найти перестановку без
[67:59] => генерация перестановок. И это то, что посмотрим, как это сделать. Давайте примем n равным четырем. Сейчас
[68:06] => возьмите бумагу или программное обеспечение для блокнота, перечислите все перестановки 1234 по порядку и скажите мне, что
[68:12] => мы заметили, я хочу, чтобы вы потратили несколько минут на анализ структуры этих перестановок.
[68:20] => Вот все перестановки, которые у нас есть всего четыре факторных перестановки 24.
[68:27] => Кто может заметить, что эти 24 перестановки можно разделить на четыре части. Первый из них содержит
[68:32] => перестановки, начинающиеся с одной, вторая содержит перестановки, начинающиеся с двух,
[68:37] => и так далее. Давайте предположим, что мы хотим найти 16-ю перестановку k, равную 16.
[68:45] => Если мы помечаем их, начиная с нуля, это означает , что мы хотим найти перестановку 15.
[68:50] => Поскольку 16 — это единица, мы помечаем их, начиная с единицы. Теперь вопрос в том, можем ли мы найти, какую часть
[68:56] => среди этих четырех частей перестановки 15 будет быть? Ответ — да, с помощью математики. Мы знаем
[69:03] => что первая часть содержит перестановки из от нуля до пяти в пункте, второй из шести
[69:08] => до 11 в шкафу, третий с 12 до 17, в шкаф, и последний с 18 до 23. В Шкафу.
[69:16] => Чтобы найти, какой из них мы просто разделим K на длина детали, которая в нашем случае равна шести.
[69:22] => 15, разделенное на шесть, дает два, поэтому перестановка 15 не будет в банке ноль не будет в банке один,
[69:29] => но это будет во второй части. Теперь, когда мы работаем с маркировкой с нулевым индексом,
[69:36] => мы знаем, что вторая часть содержит перестановки , начинающиеся с трех. Итак, мы уже знаем, что
[69:41] => наша перестановка Кита начнется с тройки , и это будет одна из таких перестановок.
[69:47] => Давайте продолжим. Что сейчас произойдет , так это то, что пространство для поиска сократится.
[69:52] => Теперь мы знаем, что в нашем случае перестановка будет в этих шести перестановках.
[69:56] => Нам нужно обновить переменные. K должно быть больше Изначально мы искали перестановку
[70:02] => 15 Среди всех перестановок, но в этой группе из шести перестановок мы ищем
[70:07] => для перестановки три, почему три, потому что 15 и модель шесть, длина модуля равна трем.
[70:15] => Случай 15, когда мы начинаем с нулевой перестановки, но в этой конкретной части он будет помечен
[70:20] => перестановка, начинающаяся с нуля, решение которой для перестановки три, а также представляет собой число
[70:27] => из оставшихся элементов перестановки нужно найти и найти один, поэтому мы уменьшаем и получаем три
[70:34] => и факториал также меняется, он становится трехфакторным шестым. То же самое касается длины горшка,
[70:40] => он также обновляется, шесть, разделенное на три, равно двум. Мы также удаляем три элемента из новостей, потому что
[70:47] => мы уже нашли его место в перестановке, и наша перестановка не содержит дубликатов.
[70:55] => Кто может разделить эти шесть перестановок на три части из двух элементов, первая часть
[70:59] => содержит перестановки, второй элемент равен единице, вторая часть содержит перестановки
[71:04] => хосты второй элемент относится к другим третьим частям содержит перестановки, которые являются третьим элементом
[71:11] => 41214. Все элементы или два, которые мы не использовал его в нашей перестановке.
[71:16] => Случай третий теперь мы можем найти ящик с травкой перестановка принадлежит да, еще раз мы разделяем
[71:22] => по длине горшка три, разделенные на два, дают один, так что перестановка случая будет в первой части.
[71:29] => И мы знаем, что перестановки Часть первая относится к нашему второму элементу,
[71:33] => таким образом, второй элемент нашей перестановки будет быть, снова пространство поиска будет сокращено, мы
[71:39] => знайте, что наша детская перестановка будет в этих двух перестановках. Вот почему мы обновляем
[71:44] => переменные k изменяются, как мы делали ранее, они становятся k моделями длины третьей части
[71:50] => модели два дают один, это означает, что среди этих двух перестановки, мы переключаемся на первую перестановку,
[71:58] => и уменьшается, становится два, что изменяет значение n факториала два факториала равно два.
[72:03] => Что также изменяет длину части значения, а факториал, деленный на n, делится на два
[72:08] => на два, что равно единице. Мы можем разделить эти два перестановки в две части одной перестановки,
[72:15] => первая часть содержит перестановки удерживает третий элемент один,
[72:19] => а вторая часть содержит перестановки удерживает третий элемент для,
[72:24] => чтобы узнать, кому принадлежит путь или перестановка регистров , разделенная на портленд, длина пути здесь
[72:29] => есть одно, и одно, разделенное на одно, дает одно, наше перестановка будет в первой части. перестановки
[72:36] => из части первой как для третьего элемента, так что третьим элементом нашей перестановки будет четыре.
[72:43] => Мы действительно используем пространство поиска, мы знаем, что наша перестановка будет в этой части
[72:47] => одна перестановка, мы обновляем переменные, k становится k моделирует длину порта, одна модель равна одному нулю, и
[72:54] => становится единицей, а факториал становится длиной одного банка становится единым целым, и мы переходим к элементам новостей.
[73:01] => Мы разделяем эту одну перестановку на одну часть одной перестановки.
[73:05] => Первая часть будет содержать узел перестановок, один из которых является четвертым элементом, длиной части
[73:10] => равно единице, а k, деленное на единицу, дает ноль. Так что наш К перестановка будет в нулевом модуле. И перестановки
[73:18] => из стручка ноль у одного есть четвертый элемент. Таким образом, четвертым элементом нашей перестановки будет один
[73:26] => теперь и становится равным нулю, и он получает уменьшенный. Так что мы закончим этот процесс.
[73:29] => Случайная перестановка — 3241, кто ее нашел без создания всех перестановок.
[73:39] => Если вы не поняли, что мы делали вот, позвольте мне показать вам это по-другому.
[73:44] => Сначала вам нужно понять как наши перестановки порождали
[73:47] => это те, у кого нет выбора, формирующего этот пример.
[73:51] => И поскольку нам нужны все возможные варианты, мы пробуем все возможности. Когда мы добавляем один, когда мы добавляем
[73:56] => 212 и три, добавьте один, добавьте четыре, вот почему вы видите, что четыре ветви — это начало.
[74:03] => И мы говорим о перестановках без повторения. Поэтому, когда мы берем элемент,
[74:08] => мы исключаем его из возможных вариантов. Вот почему , когда мы берем два других начала, например,
[74:13] => ветвь lat создает только три ветви, а не 411111, три и один, мы добавляем четыре,
[74:20] => вы можете видеть, что мы снова не добавили два . И когда мы возьмем, например, четыре,
[74:25] => у нас осталось два варианта: один или три, мы получаем только две новые ветки.
[74:29] => Затем, когда мы берем одного из них, у нас остается один выбор, тот, который мы не выбрали
[74:35] => часть нашей проблемы мы хотим найти в первом случае. Мы решаем эту проблему с помощью математики
[74:40] => чтобы рассчитать, из какой ветви мы должны идти чтобы достичь комбинации, которую мы ищем.
[74:48] => Представьте, что у вас есть 1000 книг, помеченных от от нуля до 999. Допустим, вы ищете
[74:54] => для книги 436 Вы помните, что эти книги организованы в коробки по очереди, состоящие из 100 элементов.
[75:02] => Первый содержит книги с нуля до 99, второй — от 100 до 199,
[75:07] => и так далее, как узнать, какую книгу искать, и вы просто делите номер книги, которую вы ищете
[75:13] => ищем по размеру коробки, потому что здесь они имеют одинаковый размер. 436, деленное на 100, равно
[75:20] => в-четвертых, мы искали в четвертом ящике, мы все еще не нашли книгу, но мы сократили пространство поиска.
[75:28] => Теперь мы будем искать книгу 36 В этом ящике 100. Почему, потому что 436 модулей 100, длина горшка
[75:36] => выдает квитанции. Еще раз, 100 книг из четырех книг организованы в 10 коробках
[75:42] => по 10 книг в каждой, первая содержит книги из от нуля до девяти после сотни, вторая
[75:48] => с 10 до 19, после сотни и так далее. Размер книги 1036, деленный на 10, дает три,
[75:55] => мы ищем в третьем ящике. В этой третьей коробке мы ищите шестую книгу, потому что 36 модуль 10 равен шести,
[76:04] => и так далее, и так далее, пока мы не нашли книгу, не пройдя все книги.
[76:09] => И в основном это то, что мы сделали это, чтобы решить эту проблему.
[76:13] => Давайте попробуем обобщить или в начале мы будем есть n k добавить в нас, который содержит элементы в
[76:19] => диапазон от одного до добавления предложения, если сейчас, когда n равно больше нуля, который остановился на вычислении
[76:24] => длина порта, это факториал, деленный на n. После этого мы вычисляем индекс следующего
[76:31] => элемент, который нужно вставить в перестановку. Помните, что мы рассчитали, разделив кабель на длину порта,
[76:37] => после того, как мы рассчитали, мы добавляем использование либо перестановки, либо удаленной из неиспользуемого
[76:43] => которые добавляют использование масла, потому что оно представляет собой общий элемент в части if. Затем мы уменьшаем
[76:50] => n и k становятся K моделируют длину пятна, чтобы получить его новое положение на выбранном нами пути.
[76:58] => которые продолжают повторять это, и когда a становится ноль, у нас есть наша случайная перестановка, и мы
[77:03] => решите проблему. В коде у нас есть функция который принимает в качестве параметров и ключа заданный ввод
[77:10] => или создайте пустой массив для перестановки мы ищем. Когда вы создаете и используете,
[77:14] => он содержит элементы предложения run хочу добавить в, если впоследствии, чтобы избежать всего этого
[77:20] => пересчитывая наш факториал, сам факт, что мы его учитываем, представляет собой факториал,
[77:26] => он содержит n плюс один элемент, чтобы иметь значения от нулевого факториала до n факториала.
[77:32] => Чтобы заполнить его, мы знаем, что нулевой факториал равен единице. А для остальных элементов мы просто берем значение
[77:37] => предыдущей ячейки и мы умножаем ее на I, для пример, с пятью, которые получили 1126 24 120. Теперь мы
[77:47] => декремент K, поскольку K представляет собой позицию перестановки с одного индекса маркировки,
[77:53] => но мы работаем с маркировкой с нулевым индексом, хорошо , становится k минус один, чтобы соответствовать. Мы работаем с
[77:59] => маркировка с нулевым индексом. Чтобы упростить математику, мы получаем правильный результат, когда делим и используем модули.
[78:08] => Кто может начать цикл сейчас, пока n больше нуля, Портленд является факторным фактором
[78:14] => n, деленное на единицу, — индекс элемент, который нужно взять, равен k, деленному на потлак.
[78:20] => После получения индекса следующего элемента, который является
[78:24] => которые не привыкли к нашей перестановке, и мы удаляем элемент с индексом i из N использованных
[78:30] => прежде чем перейти к следующей перестановке с уменьшите N, и k станет длиной горшка модели k.
[78:37] => После того, как цикл, наша перестановка построена, мы просто соедините его элементы в строку и верните ее
[78:43] => вернет перестановку регистров в соответствии с требованиями проблемы.
[78:48] => В принципе, решение теперь может использовать эту математику для продолжения расчета части дела
[78:52] => перестановка принадлежит, потому что, зная это, мы знайте, какой следующий элемент нужно взять из неиспользуемого
[78:58] => и использовать, который представляет собой массив элементов, которые мы еще не пользовался. Для временной сложности,
[79:04] => затраты на создание новостей и создание заводских затрат составляют плюс один и затраты на получение фильма. И
[79:10] => затем цикл while повторяется во время и больше нуля. И Ангус рекомендовал
[79:14] => что каждая итерация, поэтому количество итераций равно начальному значению внутри нее,
[79:21] => все операции выполняются в одном, за исключением выскакивания элемент, который я нашел и использовал, может иметь случай, когда
[79:26] => нам нужно сдвинуть все элементы влево и ввести все элементы перестановки
[79:33] => было четыре n плюс n в квадрате плюс один, получивший O из n квадратов временной сложности, намного лучше, чем O из
[79:39] => n раз n факториал первого решения. И для космической сложности у нас есть n для новости
[79:45] => и перестановка, и n плюс один для массива фактов, два m плюс один дает нам O из n космической сложности.
[79:53] => Где конец этого видео? Я надеюсь, что вы, по крайней мере, поняли общую идею
[79:57] => второе решение, заключающееся в разделении азиатов по периметру на группы с общим
[80:01] => элемент и вычисление, какая часть ключа перестановка принадлежит увидимся на следующей лекции
[80:13] => Добро пожаловать обратно на курс этой лекции, мы решит проблему минимальной подстроки окна,
[80:19] => у нас есть две строки SN T, и нас просят найти самую короткую подстроку из нас, которая содержит
[80:24] => все персонажи T. Если такая подстрока не существует, верните пустую строку.
[80:30] => Например, если у нас есть этот ввод в качестве вывода, мы get C E A, B, E, ba — самая короткая подстрока
[80:37] => нашей соли содержит все символы t во всех словах, два A, один B и один C. Прежде всего,
[80:45] => как мы можем знать, что строка содержит все характеры другого человека, который не может знать этого по
[80:50] => наличие встречных частот каждой строки, той, которую мы используем в задаче с допустимой анаграммой,
[80:56] => если запись является счетчиком как один, а для счетчика как два, для каждого отдельного символа
[81:01] => как два для одного из CH должно быть больше или равно чтобы для двух из них, другими словами, поскольку один должен иметь
[81:08] => по крайней мере, количество вхождений CH и s для кодирования будет записываться для каждого подбородка по два.
[81:15] => Если rec один из CH меньше частоты, два из CH вернет false после того, как цикл вернет true.
[81:22] => Зная это, мы не можем на самом деле думать о решение, решение грубой силы, которое охватывает
[81:27] => все возможные подстроки нас, отслеживая при этом самую короткую стену, содержащую все символы.
[81:33] => В коде воз может добавить условие досрочного выхода. Если t длиннее нас, мы не сможем найти подстроку
[81:39] => это удовлетворяет условию, но недостаточно символы без клея присоединяются к пустой строке.
[81:44] => Тот же результат, когда t пусто, кто может вернуть пустую строку,
[81:48] => потому что технически пустая строка содержит все символы пустой строки.
[81:54] => Другой, кто сначала создаст счетчик для T, чтобы узнать частоту каждого символа в нем,
[81:59] => давайте назовем это для t. Нам также нужна строка кратчайший, представляющий кратчайший допустимый
[82:04] => подстрока, которую мы нашли до сих пор, изначально имеет образцы одного символа, чтобы быть уверенным, что он получает
[82:10] => обновлено, как только мы нашли действующий поезд метро. Теперь мы начинаем обходить наши подстроки, чтобы сделать это
[82:17] => мы начнем с прохождения по длине, потому что мы будем начните с обхода подстрок из одного символа
[82:22] => чем подстроки из двух символов и так далее. Вот почему обучение переходит от одного к добавлению предложений
[82:30] => внутри него, в зависимости от исходных позиций, потому что при той же длине у нас есть подстрока,
[82:35] => источник с нулевым индексом, источник воды с первым индексом и так далее. Но это продолжается не до конца
[82:43] => чтобы избежать выхода за рамки при добавлении длина I идет от нуля до n минус длина в
[82:49] => предложение, если у нас есть исходная позиция, которая У меня будет длина фактической подстроки.
[82:56] => Таким образом, мы можем извлечь фактическую подстроку — это та между I в пункте 11 i плюс пункты об исправлении длины.
[83:04] => Теперь, когда у нас есть подстрока, мы создадим счетчик для этого. Давайте назовем его для нас, в честь него
[83:10] => даст фактическую подстроку, заменяющую самую короткую, найденную до сих пор,
[83:15] => для этих двух условий фактическая подстрока должна содержать все символы t,
[83:20] => мы не можем знать этого, когда функция, которую мы создали и он должен быть короче, чем самый короткий на самом деле.
[83:26] => Длина фактической подстроки равна длине. Так что, если длина меньше длины кратчайшего
[83:31] => заменит самую короткую подстроку. После цикла, кто этого не делает, не цитируйте по кратчайшему,
[83:38] => потому что, возможно, мы не нашли ни одной подстроки, содержащей все символы
[83:42] => знать, что мы выбрали самую короткую длину. Если это все еще n плюс один,
[83:47] => это означает, что он не обновляется, мы возвращаем пустую строку, как того требует проблема,
[83:52] => в противном случае возвращайтесь быстрее. В принципе, мы возвращаемся самый короткий — это длина не более n.
[83:59] => Для временной сложности давайте скажем, что n и m все длины Sn T соответственно,
[84:04] => будет иметь N для построения для T и n плюс один для создания кратчайшего. Тогда у нас есть n итераций для
[84:10] => жизнь животного внешнего цикла плюс одна итерация для внутреннего цикла. И внутри него стоимость
[84:16] => извлечение подстроки. И генерация счетчика зависит от длины. У нас также есть
[84:21] => стоимость проверки того, содержит ли он все символы, что связано с тем, что в функции, которая охватывает
[84:26] => символов reg T, их количество не более m, мы получите эту сумму, равную единице, деленной на шесть
[84:33] => умноженное на n умноженное на m плюс один умноженное на три M плюс два и плюс четыре было упрощением. И в худшем случае,
[84:40] => T короче, чем s. Таким образом, M меньше, чем n. Мы уходим и усложняем задачу.
[84:46] => А для космической сложности у нас есть амфифильные Образцы, один для кратчайшего и для sub n n для
[84:52] => скандал, мы получим три образца, а Пол — один, что выдает их за образцы и сложность пространства.
[85:00] => Это решение, очевидно, очень медленное , не самое лучшее. Вот почему мы будем двигаться
[85:04] => ко второму решению. Внутри внутреннего цикл, у нас есть стоимость длины для извлечения
[85:10] => стоимость длины, которая генерирует счетчик и стоимость arm, чтобы проверить, содержит ли он все символы?
[85:16] => Что, если мы попытаемся снизить эту стоимость более чем до одной? Чтобы получить постоянную стоимость за итерацию цикла?
[85:22] => Следуйте за мной хорошо, как мы можем извлечь подстроку и старую? В реальности,
[85:27] => нам нужно будет извлечь подстроку и наш второе решение, кто будет просто работать с самого начала
[85:32] => и конечные индексы подстроки? Которые я и я плюс длина, мы их уже знаем. Вторая вещь,
[85:38] => как мы можем сгенерировать счетчик фактической подстроки и, во-первых, хитрость в том, чтобы не всегда
[85:44] => снова создайте счетчик, который будет использовать одну из предыдущих подстрок. Позвольте мне показать вам, как это делается.
[85:51] => Очевидно, что у нас есть эта строка, US ABC abc BAC.
[85:58] => И в первом треугольнике продаж из пяти символов есть этот счетчик: две буквы «А», одна буква «В», одна буква «С» и одна Такая.
[86:05] => Начиная с этого счетчика, как мы можем получить счетчик следующей подстроки из пяти символов,
[86:10] => который из них этот? Делать. Поэтому мы просто увеличим количество вхождений персонажа, который
[86:15] => вышел из окна и увеличил количество появлений персонажа, вошедшего в
[86:20] => к окну. Тот, который вышел, — это то, что было в первой подстроке, но не во второй
[86:26] => с уменьшением доли А, это становится больше , чем тот, который вошел, он находится в
[86:33] => вторая подстрока, но не в первой, которая увеличивается на x из e, становится единицей.
[86:39] => И мы получили новый, противостоящий старому, потому что независимо от длины подстроки,
[86:44] => нам нужно поработать над двумя персонажами, только над тем, который вышел, и над тем, который вошел,
[86:49] => их всегда будет только двое, потому что мы продвигаемся на одну позицию за раз.
[86:55] => Затем для следующей подстроки. Та же логика, та , которая вышла, — это B, поэтому с командой для X из B
[87:01] => и тот, который стал НПС. Таким образом, приращение для x из C. И этот процесс продолжается в том же духе в течение
[87:07] => все подстроки длиной пять. Техника мы используем здесь так называемое раздвижное окно.
[87:14] => В нашем примере мы использовали окно длиной пять. Затем, чтобы перейти к следующей подстроке, мы не
[87:20] => начнем все сначала, мы просто переместим окно, выполнив необходимые изменения. И мы
[87:26] => просто сосредоточьтесь на том, что вышло из окна и что вошло, а не на том, что внутри, потому что это не изменится.
[87:34] => Последнее, что нужно сделать, чтобы оптимизировать затраты на проверку того, содержит ли он все символы,
[87:38] => стоимость на самом деле составляет M, потому что нам нужно пересечь символы rec T Mobile, позвольте мне
[87:43] => покажу вам, как его оптимизировать. В нашем примере T равно AB Ca он имеет три различных символа A, B и
[87:50] => C. Итак, у нас есть три условия, которые необходимо соблюдать, чтобы сказать , что наша подстрока содержит все символы t,
[87:57] => условиями являются, по крайней мере, два вхождения a, по крайней мере, одно вхождение b, по крайней мере
[88:02] => одно из проявлений C. Идея избегать всегда обход всех символов, которые могут вызвать
[88:08] => гм, это отслеживать, сколько условий выполнено. И для фактической подстроки,
[88:14] => количество удовлетворенных условий равно длина regT, которая имеет ряд различных
[88:19] => символы t, затем фактическая подстрока содержит все символы T, это допустимый символ.
[88:26] => Хорошо, но некоторые персонажи вылетают из окна, и некоторые из них точны,
[88:30] => это означает, что при перемещении окна некоторые удовлетворенные условия могут стать неудовлетворенными,
[88:35] => и наоборот. Некоторые неудовлетворенные условия могут стать удовлетворительными, как с этим справиться.
[88:42] => Для этого, после увеличения количества вхождений счетчика, который вошел,
[88:47] => если это на самом деле Т и фраккеры хотят n становится равным разрыву в точке n,
[88:52] => это означает, что у нас не было достаточного количества появлений персонажей, которые вошли. И теперь мы делаем
[88:56] => таким образом, выполняется новое условие, которое увеличивает удовлетворенное.
[89:03] => И перед уменьшением количество появлений персонажа, который вышел
[89:07] => если это на самом деле T и для нас один выход равен для активного выхода, это означает, что у нас было достаточно
[89:12] => появления персонажей, которые вышли, но после уменьшения мы не будем, потому что для нас одного
[89:18] => выход будет меньше, чем требуется. Вот почему мы Дикманна удовлетворили, условие, которое
[89:23] => был удовлетворен раньше, больше не удовлетворен. И мы, очевидно, уменьшаем значение x на единицу.
[89:31] => Например здесь у нас есть эти строки SN t и у нас есть это окно из семи символов,
[89:36] => условиями являются по крайней мере два вхождения a по крайней мере одно вхождение p
[89:41] => по крайней мере одно вхождение C. Здесь мы имеем одно вхождение a два вхождения B и одно
[89:47] => возникновение C. Выполняются только два условия недостаточно. Давайте отодвинем окно. Теперь он хочет
[89:54] => вышел, но нам все равно, потому что это не символ t с командой для X, но ничего не происходит.
[90:01] => И a вошло в приращение воз для X A , и оно становится равным перелому A,
[90:06] => мы выполнили новое условие, количество условий равно длине рек t.
[90:11] => Таким образом, подстрока действительна, она содержит все символы правила T, все условия выполнены.
[90:19] => Мы перемещаем окно, теперь видим, что находится за окном, и количество вхождений в
[90:24] => подстрока равна числу вхождений в t. Итак, когда мы уменьшаем, потому что это один из,
[90:30] => условие становится неудовлетворенным. У нас больше не хватает троек.
[90:35] => И ответ — это окно. Но мы мне все равно. Это не характерно для.
[90:40] => Теперь количество удовлетворенных условий стало меньше чем то, что требуется. Эта подстрока не
[90:45] => содержать все символы t. И этот процесс продолжается в том же духе. Еще раз, неважно
[90:52] => длина окна, мы имеем дело с двумя персонажи, только тот, который вошел, и тот, который
[90:57] => это погасло. Поэтому, проверяя, действительна ли фактическая подстрока , мы смогли
[91:04] => оптимизируйте извлечение подстроки, генерацию счетчика и проверку правильности подстроки.
[91:10] => Мы видели, как все это делается в старом. Но он еще не видел кода. Давайте перейдем к коду.
[91:18] => Мы сохраняем то же самое старое условие выхода, мы генерируем счетчик t. Но теперь мы этого не делаем
[91:22] => сохраните саму самую короткую строку. Мы просто сохраняем это начало и положение. Изначально самые короткие источники
[91:29] => строка образцов состоит из одного символа, поэтому инициализируйте мысль и и ноль и образцы один соответственно.
[91:36] => Теперь мы начинаем пересекать длины. Кем мы были в примере выполняется обновление лягушек в соответствии
[91:42] => к символам, которые входили и выходили по сравнению с предыдущим положением окна. Но сделать это,
[91:48] => сначала мы сделали начальное окно, которое также равно нулю, а длина шланга равна длине
[91:53] => стрелка, пересеките ее нормально, чтобы заполнить лягушек и подсчитать количество выполненных условий.
[91:59] => Мы создаем трещины и воссоздаем удовлетворенный переменная для отслеживания количества удовлетворенных
[92:04] => условия. Изначально он начинается с нуля, потому что мы еще не начали пересекать персонажей,
[92:10] => мы не выполнили ни одного условия. Затем мы проходим символы первого окна,
[92:16] => для каждого символа ch будет увеличиваться поток ch. И если CH является символом T и потока
[92:22] => CH становится равным react, теперь у вас есть ch , количество вхождений CH стало достаточным,
[92:28] => выполняется новое условие, которое увеличивает удовлетворенное. После обработки первого окна,
[92:34] => мы проверяем, является ли это допустимой подстрокой, прежде чем двигаться для всех, и если это должно заменить
[92:39] => на самом деле самый короткий. Если удовлетворено равно длина reg t, количество условий и
[92:45] => длина меньше длины фактического самая короткая подстрока, которая является добавлением минус мысли
[92:50] => заменить, начало N становится равным нулю, а длина соответственно, границы первого окна.
[92:58] => Теперь мы можем начать обход всех вложенных строк одинаковой длины,
[93:02] => Я начинаю с единицы и нуля потому что первая подстрока,
[93:05] => которое является первым окном, уже обработанный, мы начинаем со второго.
[93:12] => Мы хотим работать с персонажем, который вышел из окна, и с тем, который вошел.,
[93:16] => где они. Фактическая подстрока находится между индексами I в предложениях, когда я публикую исключительную длину,
[93:24] => персонаж, который вышел, появляется прямо перед окном. Таким образом, его индекс равен i минус один.
[93:29] => И тот, который вошел, является последним символом окна, его индекс равен i плюс длина минус один,
[93:36] => мы можем начать работать, персонаж, вошедший в окно, — это ии плюс длина минус один.
[93:42] => Таким образом, приращение для x s Ai плюс длина минус единица. Теперь, если это символ T и его номер
[93:48] => вхождений и подстрока стала равной числу в t, это означает, что новое условие
[93:53] => удовлетворен, мы пишем, если по состоянию на длину яблок минус один на самом деле T и поток часов глазных яблок
[93:59] => длина минус единица равна частоте T из s из i плюс длина минус один, мы увеличиваем удовлетворенный.
[94:07] => После этого мы работаем с персонажем, который вышел с индексом i минус один, если это коктейль из
[94:14] => T и S количество вхождений и подстрока равно его числу вхождений в
[94:18] => это означает, что условие было выполнено, но больше нет, потому что мы будем уменьшать для x из s
[94:23] => из n минус один. Таким образом, он станет меньше, чем частота s из i минус одно недостаточное количество вхождений
[94:28] => из x из i минус один больше. Мы пишем, если по состоянию на i минус один на самом деле T и для x из s из i минус один
[94:36] => равное T из s из i минус единица с удовлетворенным тмином также будет выполнено условие
[94:43] => после этого с Каромонтом для x из s из i минус один.
[94:49] => Теперь, когда мы знаем количество удовлетворенных условий по фактической подстроке, которая находится между
[94:54] => я и я плюс Лэнг, которые могут проверить, заменяет ли он фактический самый короткий, мы пишем, если удовлетворен равным
[95:00] => к длине reg T, а длина меньше чем n минус мысль, мы заменяем мысль и
[95:05] => по i и i плюс длина соответственно, мы нашли более короткую строку, содержащую все символы.
[95:12] => После цикла смягчите и обозначьте границы кратчайшей подстроки,
[95:16] => но нашел только одного. Если подчеркнуть, что его мысль больше n, то мы не обновляли
[95:21] => начало и конец, мы перевернули пустую строку потому что мы не нашли ни одной допустимой подстроки.
[95:26] => В противном случае мы рассказали той части нас, которая находилась между началом событие пункта и шкаф X. А как насчет времени
[95:35] => сложность, у нас будет время для строительства для T n итераций для внешнего цикла. Затем внутри него,
[95:41] => мы связали итерации для первого цикла, и одна из них — итерации длины для второй связи,
[95:46] => и все операции в сознании одного плюс n для возвращения части нас
[95:52] => длина плюс и минус длина дает n, и мы можем игнорировать M, у нас есть O из n в квадрате
[95:57] => сложность времени, сложность пространства не менять. Вы можете видеть, что теперь мы смогли
[96:04] => уменьшите временную сложность с F и Q до off n в квадрате недостаточно. Нет, мы можем сделать лучше.
[96:12] => При использовании раздвижного окна мы имеем случай, когда размер окна фиксирован. Например, если у нас есть
[96:17] => массив целых чисел и просят найти ключевые последовательные элементы с наибольшей суммой,
[96:22] => мы используем окно размера k, мы будем перемещать это, но мы не будем изменять его размер, потому что
[96:27] => мы знаем, что массив, который мы ищем , имеет длину k. Однако в нашей проблеме,
[96:33] => мы не знаем размер самой короткой подстроки, содержащей все символы.
[96:37] => Вот почему мы перепробовали все возможные длины, которые являются подстроками длины один
[96:41] => чем те из них, и так далее, что привело к увеличению сложности времени в квадрате n.
[96:49] => Но у нас есть другой способ манипулировать окном, вместо того, чтобы двигать окно по
[96:53] => одна позиция. Другими словами, увеличьте его справа на единицу и уменьшите слева на единицу,
[96:59] => что мы можем сделать, так это расширить его справа на единицу, но уменьшить слева на несколько
[97:04] => время, которое находится между нулем и длиной окна. В зависимости от того, что мы хотим сделать.
[97:10] => Давайте обратимся к нашей проблеме.
[97:14] => Теория стратегии, которую мы собираемся использовать , состоит в том, чтобы найти кратчайшую подстроку, которая отвечает на
[97:18] => фактический индекс записи, учитывающий условие, содержащее все символы tea.
[97:25] => Очевидно, отслеживая кратчайший из них, тот, который будет возвращен нам через
[97:32] => давайте начнем с первого индекса, мы найдем A но ни одно условие не выполняется, нам нужно, как
[97:38] => следующий индекс, мы находим d, нас это не волнует. Следующим индексом мы находим, что условие c выполнено.
[97:46] => Следующий индекс, если нам все равно. Следующий индекс e нас не волнует. Следующий индекс B,
[97:53] => второе условие выполняется, но не все из них. Следующий индекс e нас не волнует. Следующий индекс
[98:00] => видите, у нас теперь есть два Cs, состояние все еще лучше потерянный. В следующий раз ему будет все равно. Следующий индекс
[98:08] => а, теперь у нас есть два А, чего достаточно, чтобы выполнить последнее условие.
[98:14] => Теперь все условия выполнены, это означает, что подстрока слева направо в предложении равна
[98:18] => действительный. Но это самый короткий вариант, который соответствует индексу, верно? Неправда. Потому что мы можем
[98:24] => есть персонажи, о которых мы не заботимся по персонажи, о которых мы не заботимся, я имею в виду
[98:29] => символы, которые мы можем удалить, не нарушая действительность фактической строки. И эти
[98:35] => символы — это символы, которых нет в TRL и исчисление t, которых в нашей подстроке в избытке.
[98:42] => Например, если нам нужно увидеть только, и у нас есть пять букв С в нашей подстроке, кто может удалить первую
[98:47] => третий хочет сделать подстроку короче, в то время как удовлетворяющий условию. Помните, что наша цель
[98:53] => состоит в том, чтобы получить самую короткую допустимую подстроку. Которые не могут удалить из металла, потому что символы
[99:00] => подстрока должна быть возрастной. И мы не можем удалить справа , потому что мы ищем кратчайший
[99:05] => допустимая подстрока, которая соответствует фактической позиции справа. Таким образом, мы можем удалить только слева
[99:11] => будет продолжать удаляться, пока положение персонажей левый — это персонаж, о котором мы не заботимся.
[99:18] => Здесь персонаж слева — это это в T, и это не избыток.
[99:23] => Нам нужны две пятерки, а у нас их ровно две. Так это очень важно. Мы не можем его удалить.
[99:29] => Заканчиваем удаление слева. Итак, самая короткая подстрока, которая отвечает правильно, — это эта
[99:34] => если длина меньше фактической кратчайшей , мы обновляем. Мы переходим к следующей позиции
[99:40] => Фрейд, который считает, что тот, кто слева, все еще важный. Так что самый короткий из них — вот этот.
[99:45] => Но мы не обновляем, потому что это не глобальная самый короткий. Следующая позиция, мы находим E в
[99:52] => счетчик слева по-прежнему важен. Следующая позиция, которую мы считаем оставленным персонажем, по-прежнему важна.
[99:59] => Следующее дополнение мы нашли в а, и вот тут все меняется, потому что персонаж слева
[100:05] => это больше не важно. Причина этого в том, что мы нашли еще одного А, а это значит, что
[100:10] => персонаж теперь в избытке, мы можем удалить первого, не нарушая проверку
[100:16] => он переместит а и с помощью команды — это количество вхождений.
[100:20] => Давайте посмотрим, сможем ли мы продолжить удаление D — это не важный символ, которого нет в T, мы его перемещаем
[100:27] => C находится в T, но у нас их более чем достаточно у нас есть две тройки, в то время как нам нужна только одна
[100:32] => мы перемещаем и уменьшаем количество вхождений не пусто. Удалить не пусто, удалите его.
[100:40] => Эти излишки мы убираем, это не пусто, мы уберите его. C — это inT, и его нет в избытке.
[100:48] => Поэтому мы перестали снимать. Мы выяснили, что самая короткая допустимая подстрока, указывающая на антитиреоидный
[100:53] => e a b e BA, и это похоже на то, что семь меньше длины самой короткой замены.
[101:01] => Давайте продолжим. Мы перейдем к следующей позиции справа. Кстати, если вам интересно, почему вы не
[101:08] => мы возвращаемся к началу и будем увеличивать правильно, потому что мы знаем, что персонажи раньше
[101:12] => фактическое положение любви не имеет значения. Нам не нужна фактическая подстрока.
[101:20] => Кто нашел D корову вверху слева , по-прежнему важно, и мы не обновляем
[101:24] => потому что длина не меньше семи.
[101:28] => Следующая позиция, кто найдет половину персонажей левый по-прежнему важен, и мы его не обновляем.
[101:34] => В следующей позиции мы находим место, что означает, что персонаж слева больше не важен.
[101:39] => Персонаж видит в избытке, мы можем удалить его не в Т, мы также удаляем это важно, потому что
[101:47] => это в T, и это не в избытке, мы перестали удалять, мы получаем B e b a DFC, который не
[101:54] => короче, чем на самом деле самый короткий. Мы не обновляем мы продолжаем с тем, что D и A по-прежнему важны.
[102:01] => Следующая позиция, которую мы находим f, по-прежнему важна. Следующая позиция, которую мы считаем важной.
[102:08] => В принципе, так будет продолжаться и в течение следующего пять позиций. И обновления нет, потому что
[102:13] => подстрока становится длиннее. Мы не в состоянии для удаления слева и в следующей позиции
[102:20] => мы находим восьмерку, так что та, что слева , больше не важна, мы ее удаляем. Эти в избытке
[102:26] => мы удаляем его не пустым, мы перемещаем его по-прежнему в Превосходить. Так что удаляйте его не в Excel. Поэтому мы останавливаемся
[102:36] => подстрока — это DFC, DFC BFC BA, но не короткая достаточно, чтобы обновить. последний индекс, мы находим d и a
[102:46] => по-прежнему важно, что мы не обновляем и заканчиваем обход как глобальную кратчайшую подстроку, которая
[102:52] => содержит все символы t, которые находятся между индексами семь и 13 и предложениями, это c a b e BA,
[103:01] => потратьте несколько секунд, чтобы осмыслить то, что вы получили видел до сих пор, прежде чем продолжить видео.
[103:09] => Давайте перейдем к коду. Мы сохраняем один и тот же URL-адрес условие выхода мы строим для него так, как мы это сделали
[103:14] => ранее мы инициализировали мысль и добавили ноль и соответственно. Мы инициализируем удовлетворенный
[103:19] => ноль сожалений о x, который пуст в начале. И мы добавляем переменную left, которая представляет левую
[103:25] => граница окна здесь и началась, а не n плюс один, потому что теперь Эндрю представляет последний
[103:32] => nfo окно находится в шкафу. Кроме того, вы можете видеть , что мы создали лягушек и удовлетворили за пределами
[103:38] => цикл, потому что мы не будем пересекать длины, как в предыдущем решении. Нам не нужно этого делать
[103:43] => будет затемненно пересекать позиции справа правую границу окна для каждой позиции справа
[103:50] => мы увеличиваем количество вхождений персонажа очевидно, что цель удовлетворена.
[103:54] => состояние, как мы делали в предыдущем решении, если по состоянию на право, на самом деле является T и потоком артрита
[104:00] => равно для активных, как Фрейд, которые удовлетворяют условию, поэтому приращения удовлетворяются. В основном это
[104:07] => путь до выполнения всех условий. Это то, что нам нужно сделать, только увеличив число
[104:12] => событий и проверка того, выполнили ли мы условие, помните, что мы расширяемся от
[104:17] => право только на меньшее остается нулевым. Но как только мы выполним все условия, которые мы сможем проверить
[104:25] => при этом выполняется условие, равное длине на самом деле мы можем начать удаление слева.
[104:31] => Мы не знаем, сколько персонажей мы собираемся убрать из окна. Поэтому мы используем некоторое время
[104:36] => петля. Мы видели, что мы продолжаем удалять персонажей , в то время как персонаж ушел, является важным
[104:42] => и персонаж, который не имеет значения. означает , что либо не является символом происхождения
[104:47] => доступ означает, что у нас есть больше, чем требуется. Мы напишите, в то время как по состоянию на последнее отмеченное для akti или потока
[104:53] => нас оставили больше, чем для активных, как левых. Внутри петли мы выводим машину, что означает
[105:00] => что мы уменьшаем его количество вхождений в лягушках и перемещаемся влево на следующую позицию.
[105:06] => Теперь, когда мы удалили все ненужные символы , которые идут по кратчайшей допустимой подстроке? Этот ответ
[105:11] => фактическое положение справа — это положение между левым и гниющим предложением, если
[105:17] => что нам теперь делать, мы проверяем, не так ли заменяет фактический глобальный кратчайший.
[105:22] => Длина подстроки, которую мы нашли сейчас , равна правой минус левой плюс один плюс один, потому что
[105:27] => на этот раз в окне отображается правая граница, которая является правильной. И длина
[105:33] => из фактических глобальных кратчайших один есть и минус один плюс один плюс один по той же причине.
[105:39] => Так что, если справа минус слева плюс один меньше чем и минус этот плюс один, мы обновляем,
[105:44] => начало и конец становятся левыми и соответственно. После цикла почти тот же оператор возврата,
[105:51] => мы просто добавляем плюс один, потому что и включено в окно. Теперь, если бы мы могли обновить хотя бы один раз
[105:57] => мы включили часть установленного видео ASP и добавили предложение if else, возвращающее пустую строку.
[106:04] => Кстати, вы можете видеть, что все это время мы не проверяли, не потеряли ли мы удовлетворенное условие.
[106:09] => Поскольку мы прекратили удаление, как только достигли минимально необходимого, вхождения никогда не будут
[106:14] => идите ниже этого. Вот почему, когда счетчик имел левый был важен. Мы вообще не снимали,
[106:20] => не так, как в предыдущем решении, когда мы были удаляя, несмотря ни на что. Для временной сложности,
[106:27] => у нас есть для построения для T, и внешний цикл выполняет n итераций
[106:32] => верно, что у нас есть внутренний цикл while, где сложность заключается в том, что его количество итераций
[106:36] => не превышает n в общей сложности. Я повторяю в целом. Почему? Просто потому, что на каждой итерации
[106:42] => во время цикла мы удаляем персонажа, и мы иметь n символов. остальные операции являются
[106:48] => принадлежал более чем одному. Так что стоимость внешнего контура еще не закончилась. И да, о, если бы и только не больше,
[106:55] => кто еще делает паузу и для извлечения выходных данных. И в общей сложности у нас достаточно амперсанда,
[107:00] => мы дадим вам немного времени сложность лучше, чем O из n в квадрате.
[107:06] => И для космической сложности, такой же, как и в предыдущем решение m плюс m. И мы смогли решить
[107:13] => проблема за пределами кампуса решается только за счет использования множества интересных оптимизаций.
[107:19] => Одна из них была сложной проблемой, я надеюсь, что вы поняли, как мы построили наше оптимальное решение
[107:24] => что вы сможете использовать его для решения всех проблем. Мы подошли к концу этого видео,
[107:30] => это был долгий разговор. Но я постарался подробно каждая операция, позволяющая вам понять, что такое
[107:34] => каждая строка кода делает и как работает алгоритм работает в целом. Увидимся в следующем видео.
[107:46] => Добро пожаловать обратно на курс этой лекции, мы решит самый большой прямоугольник на гистограмме
[107:50] => проблема. Нам дан массив высот, которые содержит высоту каждого столбца на гистограмме.
[107:56] => И нас просят вернуть площадь самого большого прямоугольника на гистограмме.
[108:00] => Знайте, что каждая полоса имеет ширину в единицу. Для пример, если у нас есть этот ввод, вот
[108:07] => самый большой прямоугольник. Это площадь семь раз по пять, что дает 35. Как мы можем решить эту проблему?
[108:14] => Давайте, например, возьмем этот бар, в нем есть высота два метра. Как, вы можете сказать мне, что
[108:19] => самый большой прямоугольник высотой два, который проходит от этого бара? Это один из них. Но как мы узнали?
[108:26] => Давайте начнем с этого бара и продолжим расширяться? Мочь мы расширяемся влево? Да, есть ли что-то большее? Мочь
[108:32] => мы расширяемся? Нет, потому что у нас больше нет бара слева ? С этого момента мы можем расширяться? Да,
[108:38] => четыре — это больше? Можем ли мы расширяться? Да, пять — это больше двух. Другими словами, этот бар является
[108:44] => выше, чтобы наш прямоугольник мог пройти от него. Можем ли мы расширяться? Да, семь — это жадность. Можем ли мы расширяться? Да,
[108:50] => шесть — это жадность. Можем ли мы расширяться? Нет, мы не можем расширяться отсюда, потому что один меньше двух. Так что, если
[108:56] => мы расширяемся, прямоугольник не будет полностью включен в гистограмму — это недопустимый прямоугольник.
[109:03] => Мы расширились как можно больше с обеих сторон, мы идем по самому большому прямоугольнику, который проходит через
[109:08] => начальный бар — вот этот, он имеет площадь 12 два умножить на шесть — высота, умноженная на ширину.
[109:16] => И мы можем применить эту стратегию на каждом баре отслеживая при этом наибольшую площадь
[109:21] => в конце концов, кто найдет наибольшую площадь, потому что самый большой прямоугольник обязательно
[109:26] => проходит от штанги, которая имеет ту же высоту, что и она сама. Причина этого заключается в том, что если
[109:31] => прямоугольник короче всех полос, из которых он проходит , это означает, что он не самый большой,
[109:36] => вы все еще можете сделать его больше, увеличив его высота. И если он выше хотя бы одной планки
[109:41] => learn не полностью включен в гистограмму. Это недопустимый прямоугольник. С помощью этого примера,
[109:49] => с первой полосой мы получаем этот прямоугольник, со второй полосой мы получаем этот прямоугольник и так далее.
[109:59] => В конце концов, самая большая площадь, которую мы находим, составляет 35. Площадь этого прямоугольника
[110:07] => кодируем мы инициализируем максимальную площадь до нуля, потому что мы не пересекали ни одного прямоугольника. Следовательно,
[110:12] => каждый бар, который я расширяю с обеих сторон с каждой стороны, мы продолжаем расширяться, пока бар все еще выше или
[110:19] => так же высоко, как наша планка. Поэтому мы остановились, когда нашли тот, что покороче, или когда у нас больше не осталось баров.
[110:27] => Левые мысли — это фактическая позиция, тогда в то время как предыдущий бар существует и составляет не менее
[110:31] => как бы высока ни была реальная планка, мы расширяемся, мы переместитесь влево на одну позицию влево.
[110:37] => Та же логика с правой стороны, но увеличиваясь, право начинается с I,
[110:41] => затем, пока существует следующая часть, и находится в по крайней мере, так высоко, как фактическая планка, мы расширяем,
[110:46] => мы двигаемся вправо на одну позицию вправо. Пока справа плюс один, меньший, чем N, и высота справа
[110:52] => плюс один, больший или равный высоте AI, мы увеличиваем y, чтобы повернуть его вправо.
[110:58] => Теперь, когда мы знаем границы нашего прямоугольник, нам нужно рассчитать его площадь.
[111:03] => Площадь прямоугольника — это высота, умноженная по ширине, высота здесь равна высоте
[111:08] => начальная высота стержня i, а для ширины — разница между левым и правым плюс один,
[111:14] => справа минус слева плюс один плюс один, потому что оба левый и правый включены в прямоугольник.
[111:21] => Теперь мы проверяем, становится ли максимальная площадь замены наибольшей между ее фактическим значением и
[111:26] => площадь фактической высоты нашего прямоугольника , умноженная на правую минус левую сторону.
[111:32] => После цикла мы просто возвращаем максимальную площадь.
[111:36] => Что касается временной сложности, мы пересекаем N баров, и для каждого бара при поиске левого
[111:41] => и правильные границы, которые могут пересечь весь гистограмма. Вот почему мы получаем O из n в квадрате
[111:46] => временная сложность. В худшем случае, в худшем случай возникает, когда все стержни имеют одинаковую высоту.
[111:53] => А что касается сложности пространства, то она постоянна, мы просто используем восемь переменных.
[111:59] => Это решение медленное. Давайте перейдем к следующему. Есть интересные свойства, которые нужно знать о
[112:05] => самый короткий бар. Первый из них заключается в том, что, начав чтобы сделать из него прямоугольник, мы можем расширить его
[112:11] => до границ гистограммы, потому что нет более короткого шара, чтобы остановить расширение.
[112:17] => Во-вторых, прямоугольник, начинающийся с любого другого шара, не может пройти через него,
[112:21] => за исключением случаев, когда он имеет одинаковую высоту, но в этом случае мы получаем один и тот же прямоугольник.
[112:26] => Таким образом, самая короткая часть похожа на стену, любую другую прямоугольник будет либо на его левой стороне, либо на
[112:31] => его правый бок. Исходя из этих двух сведений, мы можем принять решение, основанное на принципе «разделяй и властвуй».
[112:38] => Мы ищем самый короткий бар, и у нас есть прямоугольник, пересекающий всю гистограмму
[112:43] => будет также рекурсивно искать самый большой прямоугольник с левой стороны,
[112:46] => самый большой прямоугольник с правой стороны, и мы берем максимум среди этих прямоугольников,
[112:52] => он представляет собой самый большой прямоугольник во всей гистограмме. Причина этого в том, что
[112:57] => что, поскольку наш бар самый короткий, мы не может быть более высокого прямоугольника, соединяющего
[113:02] => слева с правой стороны более высокий прямоугольник будет либо быть в левой части, либо в правой части.
[113:08] => Так что мы не беспокоимся о том, чтобы пропустить более крупное прямоугольник, мы можем искать в каждой стороне отдельно.
[113:14] => Мы также рассматриваем прямоугольник, высота которого равна высоте самого короткого стержня, того
[113:18] => это пересекает всю гистограмму, потому что вполне возможно, что он будет самым большим,
[113:23] => даже если он имеет самую маленькую высоту, но его ширина может сделать его самым интересным прямоугольником.
[113:31] => Закодируйте рекрутер рекурсивную функцию, которая выводит нас из массива высот,
[113:35] => но также низкие и высокие границы той части гистограммы, в которой мы сейчас ищем. Или
[113:42] => вначале мы просматриваем всю гистограмму. Так низкий и высокий будут инициализированы индексом
[113:47] => первый и последний такт. Первый базовый вариант — это где фактическая часть пуста. В то время как низкий превышает
[113:53] => правильно, мы просто возвращаем ноль, у нас нет прямоугольника. Второй базовый вариант один, у нас есть только один бар,
[114:00] => один низкий уровень равен высокому. В этом случае мы просто вернули высоту этой планки.
[114:06] => В противном случае, у нас есть рекурсивный случай, мы начнем с вычисления положения кратчайшего стержня в
[114:10] => фактическая часть. Для этого мы рассчитали наименьшую высоту в фактической части
[114:16] => между низким и высоким в пункте IV, то мы снова найдите его индекс в заключительной части.
[114:22] => Теперь, когда он у нас есть, мы рекурсивно ищем наибольшую площадь и левую и правую стороны.
[114:28] => Для левой части мы ставим почтальона минус один в качестве правой границы. И для правильной части,
[114:33] => мы ставим почтальона почтальона в качестве левой границы. URL-адрес для короткого помещенного широкого прямоугольника, его высота
[114:39] => это минимальная высота, которую мы рассчитали ранее, а ее ширина — весь путь, по которому мы ищем
[114:45] => высокий минус низкий плюс один. Поэтому мы включаем максимальную между слева направо и средним восемь раз
[114:52] => высокий минус низкий плюс один. Этот представляет собой область короткого, но пока прямоугольника
[114:58] => нам также нужна функция длинного вопроса, чтобы вызвать эту функцию, начальные значения low и high
[115:03] => равны нулю и n минус один, индексу первого и последнего бара соответственно.
[115:08] => Что касается временной сложности, то в лучшем случае самая короткая полоса всегда находится посередине.
[115:13] => Поэтому в рекурсивных случаях мы делим размер ввода на два, у нас есть поиск информации. И для мужчин, и для двух
[115:19] => умножая t из n на два для скорописных вызовов, мы получаем, что t из n равно двум кратным t из n, деленным на два плюс
[115:25] => n. При использовании основного метода это рекуррентное соотношение дает n логарифмическую временную сложность.
[115:33] => Но в худшем случае самая короткая полоса всегда является первой или последней полосой. Например, когда
[115:38] => это первый, от любви, размер ввода становится равным нулю, мы приближаемся к нулю. Но с правой,
[115:44] => размер входного сигнала становится n минус один, мы получаем животных один плюс n для поиска минимального,
[115:50] => мы получили, что t из n равно t из n минус один плюс n. И если мы будем продолжать заменять, это повторяющееся соотношение
[115:57] => выдает n квадратов временной сложности, так же, как и предыдущее решение, как мы не часто делали
[116:04] => что замедляет процесс, так это поиск минимума его причин и поиск минимума
[116:09] => в бегах, которые ищут. Но мы можем оптимизировать это, например, используя дерево сегментов,
[116:14] => вы можете сократить затраты на поиск до минимума и организовать просмотр повторения
[116:19] => отношение становится t из n равно t из n минус один плюс логарифм n, мы получаем n логарифм n плюс
[116:26] => n чтобы построить дерево сегментов, у нас есть O из n запишите временную сложность n, но если n больше n в квадрате.
[116:34] => Но нам еще предстоит найти два решения.
[116:39] => Стратегия, которую мы используем в нашем первом решении, заключается в том, что для каждого бара мы ищем следующий более короткий бар
[116:44] => слева следующая более короткая полоса справа, и мы вычисляем площадь прямоугольной полосы
[116:50] => повторное повторное прохождение полос для поиска приводило к O из n квадратов временной сложности. Что, если мы
[116:56] => может ли пересечь гистограмму только для того, чтобы найти следующую более короткую полосу каждого бара? Да, это возможно
[117:02] => используя стек, мы можем поддерживать стек и в порядке возрастания. Например, у нас есть 2478,
[117:10] => затем мы хотим вставить пять, но это больше не будет увеличиваться. Так что мы будем продолжать появляться
[117:15] => пока мы не найдем меньший элемент. И мы толкаем она продолжает расти. С другой стороны, у нас будет
[117:22] => шесть 910 12/3. Чтобы вставить восемь, выскочит 12, будет поп сделал, мы вставляем мой и вставляем, и так далее.
[117:36] => И мы можем использовать этот принцип для нашей проблемы будет работать с высотой, будет поддерживать стек и
[117:43] => чтобы перейти к следующему более короткому столбцу слева от фактического бара, который продолжает появляться в верхней части
[117:47] => стек становится короче после того, как он также нажмите на фактическую планку для следующих итераций.
[117:54] => Позвольте мне показать вам, как это работает, на нашем примере. Мы можем добавить два столбика высоты минус один на
[118:00] => конечности, чтобы избежать наличия пустого стека минус один, чтобы быть уверенным, что они будут закорочены в любой
[118:05] => бар или начало, запас содержит нулевой бар и будет начинаться с первого бара.
[118:12] => Верхняя часть стека короче, кто уже найдено, что следующий более короткий находится на нулевом индексе. И
[118:18] => мы поднимем настоящую планку. Следующий индекс, верхняя часть стека выше, чем pop. Теперь он стал меньше,
[118:25] => индекс следующего более короткого равен нулю, и мы будем нажмите на фактическую планку. Следующий бар вверху стека
[118:32] => короче, мы уже нашли следующий более короткий индекс бара два, и мы нажимаем на фактический.
[118:39] => Следующий бар, то же самое, верхняя часть стопки короче. В следующем баре то же самое. Следующий
[118:44] => бар, который выступает, и мы находим его в следующем баре, мы нужно вытащить их все, кроме последнего
[118:51] => потому что все они выше. Следующий бар, верхняя часть стека очень короткая, ее индекс равен
[118:57] => семь, следующий такт действительно короче. И так продолжается на протяжении всей гистограммы.
[119:19] => Теперь мы получили индекс более короткого бара слева от каждого бара.
[119:22] => Но нам все еще нужен тот, что справа. Таким образом, мы можем применить тот же процесс, но справа.
[119:29] => Начало теперь изначально содержит крайнюю правую панель, ту, которую мы добавили оттуда, которая является
[119:33] => рост минус один. В первую очередь справа, верх уже короче, и мы толкаем. Следующий бар
[119:41] => мы ставим один раз и находим индекс, который мы также нажимаем следующая планка уже короче. Мы пишем и нажимаем.
[119:48] => Следующий бар, то же самое, что мы пишем, и мы нажимаем. В следующем баре то же самое. В следующем баре то же самое.
[119:56] => Следующий бар мы нажимаем дважды, пишем и нажимаем следующую полосу мы ставим, как только напишем, и нажимаем,
[120:03] => следующий такт, мы прокачиваем три раза, мы пишем, и мы нажимаем, и процесс продолжается в том же духе
[120:25] => теперь для каждого бара у нас есть индекс следующего более короткая полоса слева — индекс следующего
[120:30] => более короткая полоса справа, мы можем рассчитать самый большой прямоугольник, который проходит от фактического бара.
[120:35] => Например, для этого, следующего более короткая полоса слева равна нулю.
[120:39] => Справа — семь. Итак, мы получаем этот прямоугольник
[120:44] => чтобы получить самый большой прямоугольник во всей гистограмме, какой бы ни был самый большой прямоугольник каждого бара,
[120:48] => отслеживая при этом крупнейшую в мире , как мы это делали в первом решении,
[120:53] => но нам не нужно снова искать здесь. И у нас есть удалось решить проблему, пройдя через
[120:59] => гистограмма только трижды вместо n раз, что уменьшит нашу временную сложность до O из n.
[121:07] => Закодируйте, кто первый из этих двух столбиков высоты минус один, а не конечности, затем мы создадим массив
[121:13] => слева или слева от него представляет индекс следующего более короткого бара слева от бара,
[121:18] => Я также создам стек, который изначально содержит первый бар, тот, который мы добавили.
[121:25] => Теперь для каждой планки, кроме одного раза на конечностях, кто продолжайте выскакивать, в то время как планка на вершине стека
[121:30] => выше или так же высоко, как фактическая планка, мы пишем дикие высоты запаса минус один больше или
[121:36] => равный высоте масла, мы перекачиваем запас минус один, представляющий верхний элемент. После цикла,
[121:44] => следующая более короткая полоса слева находится в верхней части стека, мы назначаем ее слева, я также буду
[121:50] => нажмите на индекс фактического бара i. Мы закончили заполнение слева, кто будет делать то же самое слева
[121:57] => право, приобретенное справа, мы инициализируем запас, ставя только последнюю планку, и начинаем,
[122:04] => теперь мы пересекли бары, но в обратном порядке. Помните, что мы начинаем справа и двигаемся.
[122:11] => Та же логика для того, что находится внутри цикла. Но сейчас мы назначили его справа от себя.
[122:17] => После заполнения обоих массивов мы можем начать работаем над тем, чтобы инициализировать максимальную площадь до нуля, затем для
[122:23] => каждый бар, кто его взял, кто заменил Максимальную площадь, Макс площадь становится максимальной между ее фактическим значением
[122:29] => и площадь прямоугольника фактического бара. Высота фактического стержня — это высота
[122:34] => из искусственного интеллекта. И ширина равна fomite i минус от слева от i минус один минус один. Потому что следующий
[122:40] => более короткие полосы не входят в прямоугольник, мы не учитываем их ширину. Таким образом, площадь — это высота
[122:47] => из I раз справа от i минус слева от i минус один после того, как цикл вернет максимальную площадь.
[122:56] => Для временной сложности у нас есть n, чтобы добавить эти бары и рестораны слева. А теперь перейдем к циклу
[123:03] => верно, что у нас есть вложенный цикл while, в котором общее количество итераций не будет превышать
[123:07] => и потому, что каждый стержень толкается и выскочил только один раз. И у нас есть возможность
[123:12] => таким образом, стоимость соответствует той же логике для процесса справа, и мы добавляем поиск максимальной площади.
[123:19] => Мы начинаем с временной сложности. И за ту космическую сложность, которая у нас есть, и за высоту
[123:26] => и для стека, и для слева. И для формы, правильно, мы уходим от космической сложности.
[123:35] => В этом океане, какая бы ни была гистограмма трижды, но у нас есть решение, где мы
[123:39] => пересечь это только хочет, давайте поговорим об этом. Хорошо, представьте, что у нас есть этот бар в качестве первого бара,
[123:46] => мы все еще можем расширить его справа, потому что мы не нашли того, что покороче. Следующий бар
[123:51] => это один, вы все еще можете расширить их оба, мы не нашли ничего, что их останавливало. Третий бар,
[123:57] => то же самое. Четвертый бар, то же самое, вы все еще можете расширяйте их все, потому что сердца увеличиваются.
[124:04] => И, кстати, мы помещаем их на склад. Как, например, следующий бар — это этот,
[124:10] => этому столбику понравится, если предыдущие три столбика перестанут расширяться, потому что он короче их.
[124:15] => Другими словами, все бары, которые выше его в стеке.
[124:21] => И поскольку теперь мы знаем, где заканчиваются эти полосы, мы не можем вычислить самый большой прямоугольник,
[124:26] => фактические бары на четвертом индексе, поэтому они останавливаются на индексе три. Для этого бара, вот прямоугольник для
[124:33] => следующий из стопки. Два — это прямоугольник. А для следующего — вот прямоугольник.
[124:39] => Мы перестали выскакивать, потому что верхняя часть стека короче, так что она все еще может расширяться.
[124:45] => Вы можете видеть, что то, что мы делаем, заключается в том, что мы складываем наши батончики в стопку. Затем, когда мы нашли
[124:50] => следующая более короткая полоса справа, мы знаем там, где они останавливаются, мы вычисляем их прямоугольник.
[124:57] => Теперь мы выдвигаем эту точку мы продолжаем эту планку Выше, нам нечего лопать без четкого
[125:02] => нажимай на него. Но для этого один короче. Итак, мы открываем этот и вычисляем прямоугольник. То
[125:09] => вершина все еще выше, мы нажимаем на нее, вычисляем прямоугольник, ставим вес с помощью этой планки, самой большой
[125:16] => прямоугольник, который мы можем сделать, не этот, а этот . Причина этого единственного результата заключается в том, что
[125:23] => индекс бара не обязательно для Мориса самые большие прямоугольники мыслей, на самом деле самые большие
[125:26] => прямоугольная мыслеформа, где последний выскочила панель мысленных повторений мыслей.
[125:34] => Например, для этого, помните, что у нас есть три бара, этот был последним, это означает
[125:40] => что самый большой прямоугольник начинается отсюда. Вот почему, когда мы толкаем штангу, мы сохраняем ту же высоту,
[125:45] => и в качестве индекса мы помещаем индекс там, где начинается прямоугольник последнего выскочившего бара.
[125:51] => Давайте поработаем с большим примером, с которым мы работали в этом видео,
[125:57] => мы можем добавить эти два столбика высоты минус один край, чтобы избежать пустого
[126:01] => стек. Первый стержень, стержень сверху короче, мы полностью помещаем его в стопку. Следующий бар,
[126:08] => планка на вершине стопки выше. Поэтому мы нашел конец своего прямоугольника, свое порождение Имани,
[126:14] => вершина стека уже не маленькая, кто перестал выскакивать. Но теперь, когда мы поднимаем эту планку,
[126:21] => как высокая пропускная способность для обоих в качестве индекса, мы помещаем индекс последней всплывающей панели, которая является одним из
[126:28] => продолжайте для более высокого, мы просто нажимаем с этим индексом, потому что мы ничего не выталкивали.
[126:33] => В следующем баре то же самое. В следующем баре то же самое. Следующий бар, который нам нужно открыть. И мы нашли конец
[126:40] => из этого бруска вот это прямоугольник. И когда мы ставим шесть в качестве индекса, мы ставим пять.
[126:46] => Следующий бар, который нам нужно всплыть, — это самый большой прямоугольник всплывающего окна, с которого начинается бар.
[126:52] => индекс, который мы нажали, равен и равен i минус один, мы можем вычислить прямоугольник и посмотреть, заменяет ли он
[126:58] => вершина все еще выше, мы поднимаем вершину все еще выше, мы поднимаемся наверх еще выше, мы поднимаемся,
[127:05] => вы можете видеть, что для каждой панели подсказок вы можете легко найти его самый большой прямоугольник,
[127:10] => вершина больше не выше, мы останавливаемся. И начальный индекс последнего узла pop равен единице.
[127:16] => Поэтому мы ставим индекс единицы при нажатии на фактическую планку. Причина этого в том, что слева,
[127:22] => наша планка может расширяться до указателя с дороги, которую мы еще не знаем. Следующая планка выше
[127:29] => без толчка, следующий такт, то же самое. И этот процесс продолжается таким образом до самого конца.
[127:45] => Закончив, мы нашли самый большой прямоугольник — вот этот, мы поворачиваем эту область.
[127:52] => И мы смогли решить эту проблему пройдя по гистограмме только один раз.
[127:58] => В коде мы начинаем с добавления этих полос конечностей создаст максимальную площадь,
[128:03] => мы создадим стек и начнем обходить бары. Стек изначально содержит первый бар,
[128:10] => тот, который мы добавили. И вы можете видеть это сейчас мы сохраняем как индекс, так и высоту.
[128:16] => В предыдущем решении мы украли индекс только потому, что могли рассчитать
[128:19] => сердце из массива сердец. Но на этот раз вытесненный индекс не
[128:23] => обязательно тот, где полоса находится на гистограмме. Поэтому мы храним и то, и другое. И на этот раз,
[128:29] => нам нужно пересечь перекладину правой оконечности, чтобы очистить стек для вычисления
[128:34] => прямоугольники баров, которые все еще находятся в стеке. Поэтому я начинаю с одного и продолжаю до последнего такта
[128:40] => на каждом баре мне понадобится переменная start, которая указывает на больший прямоугольник
[128:45] => бар наших мыслей. Помните, что это начальный индекс последнего бара, который мы открыли.
[128:53] => Но мы еще не начали появляться. Поэтому мы установили его к I теперь мы начинаем выскакивать, пока бар наверху
[129:00] => из стека выше или так же высоко, как планка нашего мы купили, мы ввели индекс и высоту в
[129:06] => переменные. Помните, что нам нужно рассчитать самый большой прямоугольник прокачанного стержня.
[129:11] => Это трудно — толкать высоту. Это обучающий индекс — это подталкиваемый индекс. И это индекс, который
[129:17] => наш минус один. Таким образом, его ширина равна i минус один минус верхний индекс плюс один, то есть я нахожусь на стоп-индексе.
[129:25] => Мы проверяем, заменяет ли он максимальную площадь Max площадь становится максимальной между ее фактическим значением
[129:30] => и самое высокое время роста, когда я нахожусь в его верхнем индексе.
[129:34] => И мы ищем начальный индекс последней всплывающей панели. Итак, начните получать стоп-индекс.
[129:40] => После того, как запас цикла переместит начальный индекс последнего выскочившего бара и высоту фактического
[129:45] => планка — это высота I, мы нажимаем начальную высоту AI, и после внешнего цикла мы заканчиваем с максимальной площадью.
[129:56] => что касается временной сложности, то снова внутренний цикл while будет выполнять наибольшее количество аллитераций в общей сложности,
[130:01] => поскольку каждый стержень выдвигается и выдвигается только один раз, у нас есть O из n временных сложностей,
[130:06] => и для отключения космической сложности, и из-за стека и массива высот.
[130:12] => Мы подошли к концу этого видео. В этом случае мы видели разные решения этой проблемы.
[130:16] => Я надеюсь, что вы поняли их все. И это была последняя проблема этого курса.
[130:24] => Поздравляю вас с окончанием этого курса. Я надеюсь что ты узнал из этого много нового,
[130:29] => и мы сможем применять их во всех ситуации. Чтобы узнать еще больше. Вы
[130:33] => можете проверить другие курсы, которые я сделал, например 50 популярных курсов по проблемам собеседования с кодированием,
[130:38] => проверьте ссылки ниже. Также, пожалуйста, скажите скажите, что вы думаете об этом курсе.
[130:43] => Если это хорошо, если это плохо, что следует улучшить и т.д. Увидимся в другой раз.