algo-visual

Как играть

• Открываете любой питон-файл
• Ставьте брейкпоинт в любую точку
• Запускайте отладку «Run!»
• Появится (если раньше не был) файл
  .cache/название_питон_файла.visualization.png
  в том же каталоге
  • Откройте его в отдельной вкладке
  • Расплитте набор вкладок и перенесите его вправо, так что бы слева видеть код отладки, а справа — визуализацию. Ну или наоборот
  • Это делает ссылка «!открыть_визуализацию», которая стоит везде рядом с алгоритмами.
  • Можно зумить CTRL +/-/wheel
• Enjoy!

Как создавать свое

• См contribution.md

LeetCode-задачи

Жадные алгоритмы

Надо тут попробовать как-то придерживаться порядка — от простого к сложному. В конце сверхкраткого описания, сколько минут видео (косвенная сложность, нет линейной зависимости, но если там больше 10 мин, возможно сложное).

• jump-game — В один проход вычислить «допрыгиваемость до конца», 3м.
• bag-of-tokens — Покупаем дешево, продаем дорого, дека, 6м
• advantage-shuffle — Подбор оптимальных соперников, дека, сортировка, 5м
• boats-to-save-people — комбинируем толстых и худых для экономии лодок, сортировка, жадный, 7м.
• best-time-to-buy-and-sell-stock-with-transaction-fee — Покупка-продажа единственного актива — многие решают через динамическое программирование, но тут достаточно держать два состояния на день, и решать жадным образом, 9м.
• broken-calculator — оптимальная трансформация одного числа в другое двумя действиями, с явной оптимальностью пути (сначала «вычитание» потом «умножение»), 9м.
• can-convert-string-in-k-moves — алгоритм трансформации уже задан, по сути, надо просто найти самый проблемный символ для преобразования, 5м.
• car-pooling — нет ли переполнения вагона, если известны загрузка интервалов между остановками → перейти от интервалов в дельтам «±» загрузки в остановках, отсортировать дельты, пробежаться и посмотреть, не происходит ли переполнение, 5м.
• delete-columns-to-make-sorted-ii — добавлять или нет колонки, чтобы не испортить лексикографическую сортировку, 6м (имхо, можно короче).
• dota2-senate — реализация простой «военной игры», демонстрирующая преимущество первого удара и «sucker punch», 7м.
• gas-station — «траты и затраты по кругу» — надо посчитать «топливный интеграл потенциал по контуру», и проверить что там нет отрицательных ям, 10м
• largest-values-from-labels —
• maximum-average-pass-ratio —
• maximum-nesting-depth-of-two-valid-parentheses-strings —
• maximum-number-of-groups-entering-a-competition —
• minimum-add-to-make-parentheses-valid —
• minimum-domino-rotations-for-equal-row —
• minimum-number-of-arrows-to-burst-balloons —
• minimum-replacements-to-sort-the-array —
• minimum-swaps-to-make-strings-equal —
• monotone-increasing-digits —
• non-overlapping-intervals —
• partition-label —
• previous-permutation-with-one-swap —
• queue-reconstruction-by-height —
• reconstruct-a-2-row-binary-matrix —
• reorganize-string —
• score-after-flipping-matrix —
• string-without-aaa-or-bbb —
• task-scheduler —
• wiggle-subsequence —

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

• count-number-of-ways-to-place-houses — наверное самое простой пример ДП, очень просто — подсчитать расстановку домиков на одной стороне улицы.
• number-of-ways-to-select-buildings — подсчет подпоследовательностей чтобы чередовались 0/1
• minimum-white-tiles-after-covering-with-carpets — подсчет подпоследовательностей чтобы чередовались 0/1
• total-appeal-of-a-string.py — что-то типа формулы включений-исключений, считаем каждого символа «вклад в привлекательность», суммируя число строк, включающих этот символ.
• count-beautiful-substrings-ii — ДП с двумя таблицами мемоизации с косвенностью.
• find-the-sum-of-the-power-of-all-subsequences — простой алгоритм, но очень муторное обьяснение, надо бы переделать.

Numbers

• three-divisors — тест простоты
• insert-greatest-common-divisors-in-linked-list — НОД и односвязный список.
• simplified-fractions — НОД
• the-kth-factor-of-n — перебор делителей
• prime-pairs-with-target-sum — решето Эратосфена, но наверно можно лучше.
• minimize-length-of-array-using-operations — жадный, но можно использовать НОД
• mirror-reflection — геометрия и НОК
• count-beautiful-substrings-ii — больше про ДП, от теории вычетов только учет классов вычетов (деление по модулю)

Graphs

• shortest-path-visiting-all-nodes - Кратчайшие пути, поиск в ширину.
• cheapest-flights-within-k-stops — кратчайшие пути с допограничениями
• all-ancestors-of-a-node-in-a-directed-acyclic-graph — Поиск в ширину.
• minimize-malware-spread — минимальные связные компоненты
• get-watched-videos-by-your-friends — поиск в ширину, формирование уровней
• minimum-edge-weight-equilibrium-queries-in-a-tree — бинарный лифтинг