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

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

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

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

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

Решение

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

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

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

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

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

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

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

TS: функция преобразования к каноническому пути

Март 15, 2023 г.

Увидел эту задачу на leetcode - https://leetcode.com/problems/simplify-path/, где не так часто встречаются задачи близкие к практиктическому программированию. Ранее уже приводил решение подобной задачи для PHP. Здесь порешаем её уже на TS. Задача ...

Читать

Вычисление заголовка столбца в Excel

Март 23, 2023 г.

Leetcode задача #168. Excel Sheet column title.Задача помечена как простая, тем не менее, не сразу понял как её решать. Дано число, это номер столбца для Excel таблицы, требуется сгенерировать его буквенное имя. Иными словами сопоставить 1 -> A, ...

Читать

Задача: подсчитать варианты размена монет

Август 11, 2023 г.

Снова классика задач на перебор вариантов - есть номиналы монет, требуется найти все варианты размена указанной суммы. Число монет каждого номинала - не ...

Читать

Задача - число островов

Март 25, 2023 г.

Разбираю задачу #200 с литкода, число островов (number of islands). Задан двумерный массив, в котором участки суши помечены как "1", а участки воды - как "0". Требуется подсчитать число получившихся островов. При этом считается, что участки суши образуют ...

Читать
 

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

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



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