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

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

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

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

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

Решение

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

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

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

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

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

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

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

Задача о поиске всех подходящих под-сум

Июль 1, 2023 г.

№560 leetcode Subarray Sum Equals K. Есть массив чисел, и дано значение k. Надо найти все последовательные под-массивы сумма которых равна k. В условиях также сказано, что числа в массиве могут быть как положительные, так и отрицательные. Если ...

Читать

Задача о неперекрывающихся интервалах

Июнь 7, 2023 г.

Задачи об интервалах легко решаются перебором. Но если элементов много, то нужно сообразить в каком порядке их лучше перебирать, чтобы избежать лишних вычислений. Формулируется задача так: дан массив интервалов, каждый из которых определен двумя числами ...

Читать

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

Апрель 9, 2023 г.

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

Читать

GreyCode генератор

Май 3, 2023 г.

Задачи с бинарными последовательностями мне очень нравятся из-за их "эвристичности". Решение часто скрывается в двух шагах, но додуматься не просто. Следующая задача описывается так - нужно сгенерировать n-разрядный "серый код". Если вы не ...

Читать
 

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

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



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