Подсчет кол-ва нулевых подмассивов

Разбор задачи с литкода. (2348. Number of Zero-Filled Subarrays).

Суть: есть массив чисел, нужно подсчитать кол-во подмассивов, состоящих из нулей.

Например, дан массив [0, 0, 1].

Как видим, есть последовательность из двух нулей в начале массива. Она генерирует нам три «нулевых» подмассива — [0]x2 и [0, 0]. Т.е. ответ для данного примера — 3.

Решение

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

Если попробовать разные последовательности, то быстро определяется закономерность:

Число комбинаций рекурсивно растет на n для каждого следующего шага.

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

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

Пример кода на typescript:

Написать комментарий

Мало букафф? Читайте есчо !

Задача о последнем дне переправы по льду

Июнь 30, 2023 г.

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

Читать

Поиск выхода из лабиринта

Июнь 3, 2023 г.

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

Читать

 

Комментарии к «Подсчет кол-ва нулевых подмассивов»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: