Тренировки по алгоритмам 6.0 Лекция 2: Префиксные суммы и два указателя
00:00:00 Начало трансляции
05:17:00 Начало лекции
06:07:00 Префиксные суммы
06:56:00 Построение массива префиксных сумм
09:08:00 Проблемы переполнения
11:25:00 Решение задачи с суммой на отрезке
14:29:00 Реализация массива префиксных сумм
15:28:00 Подсчет количества нулей
16:59:00 Пример построения массива префиксных нулей
18:46:00 Проблема с запросами на полуинтервале
20:51:00 Решение задачи подсчета нулей
21:44:00 Задача подсчета отрезков с нулевой суммой
28:42:00 Реализация подсчета отрезков
31:22:00 Применение подхода к другим задачам
32:29:00 Введение в два указателя
33:21:00 Решение задачи с перебором пар
34:30:00 Оптимизация решения
36:16:00 Идея метода двух указателей
37:58:00 Реализация метода двух указателей
38:53:00 Пример кода
41:29:00 Применение метода двух указателей в другой задаче
43:12:00 Оптимизация команды
46:08:00 Левый и правый указатели
46:58:00 Добавление и вычитание игроков
47:44:00 Реализация алгоритма
48:31:00 Условия для команды
51:03:00 Пример с сортировкой слиянием
57:07:00 Задача с подстрокой
59:00:00 Оптимизация алгоритма
01:04:45 Реализация алгоритма
01:07:48 Альтернативные подходы
01:12:26 Эффективность создания списка нулей
01:13:26 Различие между скользящим окном и двумя указателями
01:14:45 Решение задач через префиксные суммы и два указателя
01:15:31 Улучшение симптоматики при хранении позиций
01:16:56 Плохое решение за O n^3
01:17:56 Сложность добавления элементов в словари
01:18:55 Создание нулевого элемента в решении пятой задачи
Будем делать из двух вложенных циклов один и научимся решать задачи на самую популярную тему на собеседованиях
Подробнее о тренировках по ссылке: https://yandex.ru/yaintern/algorithm-...
Подписывайтесь на наши соц.сети:
Telegram (https://t.me/Young_and_Yandex),
VK (https://vk.com/young_and_yandex).