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

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

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

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

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

Решение

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

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

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

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

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

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

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

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

Август 11, 2023 г.

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

Читать

Задача о наибольшей сумме монет

Апрель 15, 2023 г.

Решаем задачу № 2218 с leetcode - Maximum Value of K Coins From Piles. В названии фигурирует слова монеты и стопки. Если представить себе, что монеты могут быть произвольного номинала, то да - суть именно такая. У нас есть стопки монет, и дано число ...

Читать

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

Апрель 9, 2023 г.

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

Читать

87. Scramble string - задача о перетасованных строках

Март 30, 2023 г.

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

Читать
 

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

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



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