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

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

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

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

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

Решение

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

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

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

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

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

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

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

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

Март 25, 2023 г.

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

Читать

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

Август 11, 2023 г.

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

Читать

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

Март 15, 2023 г.

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

Читать

Решение задачи оптимизации в направленном графе

Апрель 9, 2023 г.

Сегодня расскажу о решении задачи №1857 с литкода, которая называется как "Largest Color Value in a Directed Graph". Суть задачи: дан направленный ...

Читать
 

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

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



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