Тренировки по алгоритмам 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-training Подписывайтесь на наши соц.сети: Telegram (https://t.me/Young_and_Yandex), VK (https://vk.com/young_and_yandex).
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-training Подписывайтесь на наши соц.сети: Telegram (https://t.me/Young_and_Yandex), VK (https://vk.com/young_and_yandex).