Решения LeetCode в хорошем стиле

В этом документе представлен всеобъемлющий обзор LeetCode-Solutions-in-Good-Style, ресурса, предлагающего удобные для начинающих учебные пособия и видеорешения для проблем с алгоритмами и структурами данных. Он отличается структурированным подходом с понятным кодом, подробными объяснениями и фокусом на сборке. глубокое понимание фундаментальных концепций, а не соревновательного кодирования.

LeetCode-решения в хорошем стиле

Пояснение: Как и большинство моих одноклассников, я одновременно занимаюсь и подвожу итоги. Я постараюсь поделиться больше и принести вам полезные знания. Спасибо за вашу постоянную поддержку.

Привет всем, это учебник начального уровня по «Алгоритмам и структурам данных». Он подходит для студентов с нулевым уровнем знаний в области алгоритмов и студентов, которые сменили карьеру. Он не подходит для подготовки к соревнованиям по алгоритмам. Я хочу донести следующее: пишите код с четкой логикой, поэтому код, который я пишу, должен быть тщательно продуман. Формат очень стандартный, без личного стиля, и я не буду писать пустую строку или комментарий, чтобы его сократить. количество строк кода. Вот:

Вы можете называть меня Вэйвэй. Я постараюсь ответить на вопросы, которые знаю, в пределах своих возможностей и времени. Если у вас есть вопросы, на которые невозможно ответить вовремя, возможно, я не увидел уведомления на сайте. Вы можете отправить мне электронное письмо по адресу [email protected].

Видео решение, которое я записал

Я начал записывать видеорешения в сентябре 2019 года. Вначале я несколько раз записывал материал, о котором хотел рассказать. Теперь пишите дословные черновики, объясняя моменты знаний. Накопилось много видео, которые по сути представляют собой небольшой систематический курс. Теперь они размещены здесь, надеюсь, что это будет полезно всем.

0. Как начинающий пользователь алгоритмов может использовать LeetCode? 【Обмен полезной информацией】

1. Временная и пространственная сложность.

В этом видео упоминается, что временная сложность является асимптотической концепцией и ее необходимо понимать с динамической точки зрения. А строгое определение (предельная форма) временной сложности поясняется для того, чтобы каждый мог понять правила расчета временной сложности. Он также отметил: временная сложность не является временем работы программы; следует использовать «пространство для времени», и больше внимания следует уделять оптимизации «временной сложности».

2. Бинарный поиск

В этом видео показано, как написать алгоритм двоичного поиска. Хотя о двоичном поиске есть много подробностей, пока мы овладеваем правильными идеями решения проблем, больше практикуемся, усердно думаем и делаем больше обобщений, проблема двоичного поиска исчезнет. больше не будет трудностей.

В следующем видео объясняются несколько примеров вопросов бинарного поиска. Мы сосредоточимся на анализе значения вопроса и на том, как использовать условия, указанные в вопросе, для постепенного сужения диапазона поиска.

Благодаря анализу вопроса 4 «Ликоу» (нахождение медианы двух массивов положительного порядка) мы познакомили вас с этой техникой: если свойства целевого элемента, который вы ищете, более сложны, вы можете инвертировать это свойство. , а затем напишите логические утверждения, которые могут легко уменьшить диапазон проблем.

3. Проблемы, связанные с сортировкой

«Сортировка слиянием» и «быстрая сортировка» — очень важные алгоритмы сортировки. Их глубокое понимание очень полезно для понимания механизма работы «рекурсивных» функций. В то же время они также являются типичным применением подхода «разделяй и властвуй». ". «Пара обратного порядка» и «Задача голландского флага (классификация цветов)» также являются очень классическими алгоритмическими задачами.

Вычисление «пар обратного порядка» полностью основано на идее «сортировки слиянием».

В объяснении проблемы «цветовой классификации» мы познакомили всех с «инвариантами цикла». В процессе написания кода мы всегда должны соблюдать семантику используемых переменных, «до выполнения программы» и «во время выполнения». остается неизменным после «завершения выполнения». Придерживаться нашего собственного определения «инвариантов цикла» — это важный способ написать правильный код.

«Первое пропущенное положительное число» — это классическая алгоритмическая задача. Используемая идея — «хеширование на месте», которое можно понимать как специальное применение алгоритма «сортировки ведерком»: одна морковка, одна косточка и одно ведро. Сохраните элемент. Хочу подчеркнуть, что тот факт, что вы можете это сделать, тесно связан со значением элементов входного массива.

4. Раздвижное окно

Проблема «скользящего окна» — это типичная проблема, решаемая с помощью «инвариантов цикла», которые проверяют наши способности кодирования и отладки.

5. Проблемы, связанные со стеком

Задачи, решаемые с помощью «стеков», требуют от нас использования конкретных примеров, чтобы обнаружить, что их решение совпадает с правилом «последним пришел — первым вышел»:

Освоение следующих двух вопросов неотделимо от изучения конкретных примеров и последующего обобщения общих правил.

Одним из наиболее широко используемых применений «стека» является поддержка структур данных для «рекурсии», «обхода в глубину» и «алгоритма «разделяй и властвуй».

6. Комбинированный поиск

Структура данных «Union Search Set» в настоящее время редко используется на собеседованиях. Если вы готовитесь к собеседованию по алгоритму, ее можно пропустить.

7. дерево

Многие проблемы с деревьями можно решить, используя «обход в глубину» или «обход в ширину».

8. Алгоритм возврата

«Алгоритм обратного отслеживания» на самом деле представляет собой обход «деревовидной структуры», содержащейся в вопросе, в глубину. При решении задач такого типа важно нарисовать на бумаге диаграмму древовидной структуры.

9. Динамическое программирование

10. Обход в ширину и топологическая сортировка

11. Хэш-таблица

12. Битовые операции, связанные

Мой личный сайт и заметки по изучению алгоритма

Группа WeChat и группа QQ

Если вам нужны друзья для совместной работы над вопросами, вы можете присоединиться к группе WeChat и группе QQ.

МойLeetBook

Вот рекламная акция для себя. Недавно я запустил свой собственный LeetBook на «LeetBook»: «Изучение алгоритмов с нуля» (ранее известный как «Изучение алгоритмов и структур данных с помощью «LeetCoin»)», который в основном предназначен для друзей, которые сменили карьеру и имеют нулевой фундамент Объяснить базовые знания алгоритмов и структур данных.

проиллюстрировать:

Первые две главы LeetBook (Временная сложность, Двоичный поиск) можно прочитать бесплатно. За чтение следующих глав требуется плата. Цена для нечленов составляет 99 юаней, а для участников — 69 юаней. Каталог домашней страницы, который вы сейчас просматриваете, — это. то же, что LeetBook. Только дополнительная часть, не меньше;

Названия курсов, примеры, упражнения и вспомогательный репозиторий кода LeetBook (репозиторий, который вы сейчас просматриваете) полностью общедоступны. Если вы уже освоили контент (включая упражнения), разработанный в LeetBook, не рекомендуется его приобретать;

Затраченная энергия такая же, как и при обычном написании решения, за исключением того, что LeetBook будет более подробным при создании диаграмм. Платный контент: время и энергия, затраченные на создание учебных пособий, а также участие сотрудников и экспертов «Ликоу» в производстве и обзоре, улучшат впечатления от чтения. Не исключено, что я обычно пишу больше знаний по решению проблем, чем LeetBook;

Пользователи среднего и продвинутого уровня, пожалуйста, совершайте покупки с осторожностью;

Вы можете проконсультироваться со мной по поводу содержания курса на сайте «Ликоу» или в других моих социальных аккаунтах, а можете задать вопрос на этом складе. Независимо от того, куплю я курс или нет, я постараюсь ответить на те вопросы, которые знаю (если позволяет время и в пределах моих возможностей). Спасибо всем за вашу постоянную поддержку меня. Каждый может связаться со мной, если у вас есть предложения и мнения;

Знания, которые я объясняю, содержатся в книгах, которые я всем рекомендовал, в блогах, решениях проблем и написанных мной заметках. Опубликованные решения проблем, блоги и заметки всегда будут доступны для общего доступа, и пока у меня есть время и силы, я буду делиться ими. Я продолжу делать это, делюсь информацией и отвечаю на вопросы;

Я очень благодарен «Ликоу» за предоставленную возможность пройти курсы и помочь исполнить маленькое желание.

Каталог классификации и решения проблем "Lekou" (организован в соответствии с главами LeetBook, глава 16 и далее - это главы, которые в настоящее время не включены в LeetBook)

Примечание. Категории вопросов соответствуют главам моего LeetBook.

Глава 1. Временная сложность

В этой части представлена ​​концепция временной сложности. Вы можете посмотреть [Видеообъяснение], которое совершенно бесплатно. В этой главе нет упражнений.

Глава 2. Бинарный поиск

Тип вопроса 1: Найдите индексы в двух точках.

проиллюстрировать:

упражняться:

Тип вопроса 2: Определите целое число с диапазоном в два балла (ответ в два балла)

Алгоритмическое мышление: уменьшай и властвуй. Если вопрос требует от нас найти целое число, и это целое число имеет определенный диапазон, мы можем постепенно сузить диапазон с помощью двоичного поиска и, наконец, приблизить его к числу.

Тип вопроса 3: Комплексная дискриминантная функция (задача максимизации)

Примечание. По сути, этот тип вопроса представляет собой «вопрос типа 2» (ответ из двух пунктов), но при первом его изучении он может показаться немного запутанным. Вопросы этого типа задаются таким же образом. Ключевые слова: «непрерывный» и «положительное целое число». Обратите внимание на то, чтобы в вопросе была указана такая ключевая информация.

Глава 3. Основные алгоритмы сортировки

Эта часть содержит четыре основных алгоритма сортировки: сортировка выбором, сортировка вставками, сортировка Хилла и пузырьковая сортировка.

Вопрос «Ликоу» 912: Решение отсортированного массива: здесь обобщены некоторые ключевые моменты и учебные материалы для задач сортировки. Вы можете начать изучение алгоритмов с задач сортировки.

Задачи о массивах можно использовать как «область для новичков» в алгоритмах, поскольку эти задачи можно решить, только овладев базовыми знаниями языков программирования. Легко придумать решения следующих проблем, даже если вы не изучили соответствующие структуры данных и знания алгоритмов.

Знание: инварианты цикла

Глава 4. Расширенные алгоритмы сортировки (важно)

В этой части необходимо сосредоточиться на освоении трех продвинутых алгоритмов сортировки: сортировки слиянием, быстрой сортировки и сортировки кучей.

проиллюстрировать:

Глава 5. Несравнительная сортировка (необязательно)

Эта часть содержит три типа сортировки без сравнения: сортировку по подсчету, поразрядную сортировку и сортировку по сегментам. Решение этих проблем требует понимания концепции хеширования на месте.

Глава 6. Скользящее окно и двойные указатели

1. Раздвижное окно

Метод написания справки для скользящего окна (не шаблон, пожалуйста, не копируйте его как есть, он предназначен только для справки, важнее понять идею построения алгоритма):

Дружеское напоминание: вопросы 3 и 76 — это базовые вопросы, которые вы должны уметь решать. Если вы хорошо разобрались в приведенных выше вопросах, вам будет легче ответить на следующие вопросы.

Ключевые вопросы:

проиллюстрировать:

упражняться:

проиллюстрировать:

Вопрос 209. Основная информация, содержащаяся в вопросе: все элементы массива являются целыми положительными числами. Всего существует 3 следующих метода.

Метод 1: Насильственное решение

Способ 2: Раздвижное окно (проанализируйте причины, по которым можно использовать раздвижные окна)

Способ 3. Создайте префикс и массив, а затем используйте двоичный поиск.

Вопрос 438: То же, что и вопрос 76;

Вопрос 567: То же, что и вопрос 76, за исключением того, что набор уточненных предложений отличается.

2. Двойные указатели

Проблема «двойного указателя» на самом деле является оптимизацией наивного алгоритма. Многие решения, не соответствующие смыслу задачи, отбираются сразу. То же самое справедливо и для метода «скользящего окна». Еще важнее проанализировать, почему можно использовать двойные указатели.

Алгоритм двоичного поиска, используемый для поиска индексов, также можно рассматривать как решение с двойным указателем.

Глава 7. Связанный список.

Очень практичный метод решения проблем со связанными списками — это «рисование». То же самое справедливо и для анализа и объяснения других алгоритмических задач (объяснения интервьюеру).

Вы можете написать тестовые функции для связанных списков, чтобы облегчить отладку. Рекомендуемые методы реализации: ① Создать односвязный список через массив. ② Распечатать текущий узел и последующие узлы на основе текущего узла; Эти два метода могут очень удобно помочь нам в отладке программ, связанных со связанными списками.

Тип вопроса 1. Основная проблема с указателем связанного списка.

Примечание. Некоторые проблемы требуют использования «виртуальных головных узлов», чтобы избежать сложной логики обсуждения классификации для первого узла связанного списка. Мы видели эту идею в массивах, называемых «стражами».

Используйте рекурсивные функции, чтобы избежать сложных операций по изменению переменных указателя, упрощая решение проблем.

проиллюстрировать:

Тип вопроса 2: Навыки быстрого и медленного указателя

Если быть точным, лучше было бы назвать это «синхронизированным указателем».

Используя две переменные-указатели, они обе располагаются в первом узле связанного списка в начале. Одна всегда выполняет только один шаг за раз, а другая всегда выполняет только два шага за раз: один впереди и один в начале. обратно, в то же время. Таким образом, когда быстрый указатель завершит движение, медленный указатель достигнет средней позиции связанного списка.

Общей особенностью решения этих проблем является использование двух переменных-указателей для синхронного перемещения. Быстрый и медленный указатели движутся в одном направлении, и «разница» между их шагами постоянна. На основе этой уверенности можно решить некоторые проблемы в связанном списке. Использование этой идеи также может решить следующие проблемы связанных списков:

проиллюстрировать:

Тип вопроса третий: Проектирование структуры данных

Глава 8. Стек и очередь

1. Стек

Тип вопроса 1. Основные проблемы, решаемые с помощью стека.

Следующие вопросы являются очень простыми и должны быть освоены:

упражняться:

Тип вопроса 2: Монотонный стек

Монотонный стек — это обычный стек, который во время использования соответствует принципу «последним пришел — первым ушел», а элементы в стеке монотонны. Проблемы «монотонного стека» и «монотонной очереди» обычно весьма специфичны. Просто освойте примеры и некоторые упражнения.

Опыт: индексы обычно хранятся в монотонных стеках.

проиллюстрировать:

упражняться:

2. Очередь

Тип вопроса 1: Основные проблемы, решаемые с помощью очередей

Все проблемы, решаемые с использованием очередей обхода в ширину.

Тип вопроса 2: Монотонная очередь

Монотонная очередь — это обычная очередь. Эта проблема в настоящее время встречается в монотонной очереди на «Ликоу». Ключевым моментом является четкий анализ того, почему разработанный алгоритм делает очередь монотонной. Кроме того, в «Задаче о рюкзаке» есть примеры использования монотонных очередей для оптимизации, что является конкурентным знанием.

Опыт: Индексы обычно хранятся в монотонных очередях.

Глава 9. Приоритетная очередь

Примечание. Необходимо понимать реализацию «кучи» как «приоритетной очереди». Это поможет понять детали кодирования методов удаления() и замены(), чтобы вы могли более эффективно использовать кучу.

Применение: динамически выбирать элемент с наивысшим приоритетом в текущей очереди, уделяя особое внимание пониманию значения слова «динамический».

Глава 10: Комбинированный поиск

И проверьте [видеообъяснение] пунктов знаний в видеорешении вопроса 990. Основные и распространенные вопросы включают в себя:

Дополнительные вопросы:

Глава 11. Деревья (бинарные деревья и бинарные деревья поиска)

Глава 12. Алгоритм поиска с возвратом

Тип вопроса 1: Основная проблема с возвратом

С помощью этих вопросов вы можете понять идею алгоритма возврата. Точки знаний алгоритма возврата объяснены в видеорешении и текстовом решении вопроса 46 «Ликоу».

Обход с возвратом заключается в использовании обхода в глубину для поиска всех решений дерева (графа). Обход в глубину имеет очевидную рекурсивную структуру.

Советы по решению следующих проблем: ① Рисовать, рисовать, рисовать ② Понимать обход в глубину и рекурсию ③ Больше отлаживать, больше отлаживать;

Тип вопроса 2: Проблема с возвратом строк

Ключевые моменты для понимания: поскольку строка каждый раз генерирует новые символы, нет необходимости сбрасывать состояние.

Тип вопроса третий: Заливка

Тип вопроса 4: Некоторые игровые вопросы

проиллюстрировать:

Глава 13 Динамическое программирование (Часть 1)

Две важные идеи динамического программирования:

Два направления мышления в динамическом программировании:

Для решения задачи с помощью динамического программирования необходимо выполнение трех условий:

Две важные концепции динамического программирования:

Ссылка на классификацию вопросов:

Примечание. Типичные вопросы, приведенные ниже, будут добавлены (2 декабря 2020 г.).

1. Начало работы

Познакомьтесь с двумя методами динамического программирования: рекурсией памяти «сверху вниз» и рекурсией «снизу вверх».

2. Повторяющиеся подзадачи

Эта часть требует использования «принципа умножения подсчета шагов» и «принципа сложения по категориальному подсчету».

Вопрос 70: Это тот же вопрос, что и о числах Фибоначчи. В задачах подсчета будут использоваться принцип подсчета классификации и принцип подсчета шагов.

3. Оптимальная подструктура

проиллюстрировать:

Вопрос 377: Обратите внимание, что проверка не связана с рюкзаком.

4. Никаких последствий.

упражняться:

Ниже приведены некоторые классические задачи «динамического программирования». Поскольку эти вопросы настолько важны, они выделены в отдельную категорию.

5. Максимальная сумма подсегмента

упражняться:

6. Самая длинная восходящая подпоследовательность

Примечание. Вопрос 300 — это очень классическая задача динамического программирования. Решение $O(N log N)$ определяет состояние в соответствии с характеристиками самой задачи и доказывает, что массив состояний является упорядоченным массивом, что снижает временную сложность.

упражняться:

7. Самая длинная общая подстрока

8. Интервальный ДП и разделенный ДП

Интервал ДП:

Разделенный DP:

9. Дерево ДП

Глава 14 Динамическое программирование (Часть 2)

1. Проблема с рюкзаком

Девять лекций о рюкзаках: https://github.com/tianyicui/pack

(«Тип игры DP», «Сжатие состояния DP», «Цифровой DP» и т. д. будут добавлены.)

Другие вопросы

Глава 15. Жадный алгоритм

Глава 17. Хэш-таблицы

Глава 18. Суммы префиксов и хэш-таблицы

Глава 19. Обход в ширину

Некоторые проблемы с обходом деревьев в ширину и некоторые проблемы в LeetBook.

Глава 20. Алгоритм теории графов (минимальное остовное дерево)

Глава 21. Алгоритм теории графов (кратчайший путь с одним источником)

Глава 22. Алгоритм «разделяй и властвуй»

Идея «разделяй и властвуй» (разделяй и властвуй) разбивает большую проблему на несколько более мелких подзадач одного типа, а затем решает эти подзадачи рекурсивно. После завершения каждой подзадачи происходит решение. исходная проблема получена.

Алгоритм «разделяй и властвуй» может выполняться параллельно, но в области базовых алгоритмов алгоритм «разделяй и властвуй» выполняется методом обхода в глубину.

Типичные алгоритмы, применяющие идею «разделяй и властвуй»: сортировка слиянием, быстрая сортировка.

Типичные задачи мышления «разделяй и властвуй»: «Вопрос 51 о мече указывает на предложение»: «Вопрос 51 о мече указывает на предложение» 51. Пары обратного порядка в массиве (видеообъяснение).

Другие типичные вопросы (будут добавлены)

Он будет продолжать обновляться, и друзья могут оставить ценные отзывы!