Базовые структуры данных
Алгоритмы и структуры данных, часть 1


Что: Семинар
Когда: Пятница, 21 октября 2016, 20:00–21:20
Где: Таймс, 4 этаж

Описание

  • Кодим

    • Дек на циклическом массиве
    • Двусвязный список с удалением
  • Динамический массив (vector): избавимся от амортизации

  • Задачи на стек

    • Несколько типов скобок. Проверить на правильность. Найти парные скобки. \(O(n)\).
    • Ближайший слева меньший, ближайший справа меньший за \(O(n)\).
    • Массив положительных чисел, ищем отрезок: \(\sum \times \min \rightarrow \max \)
    • Ищем за O(wh) подпрямоугольник из нулей максимальной площади в матрице
    • Посчитать по всем отрезкам массива сумму минимум на отрезке за \(O(n)\)
    • Найти количество подпрямоугольников из нулей в матрице
    • Несколько типов скобок. Найти max по длине подстроку, являющуюся правильной скобочной последовательностью за \(O(n)\).
  • Задача: по бесконечной прямой в одну сторону идут группы людей, скорость движения группы обратно пропорциональна количеству людей, иногда группы встречаются, тогда объединяются. Сколько в итоге групп останется?

Материалы