Разбор задачи с литкода. (2348. Number of Zero-Filled Subarrays).
Суть: есть массив чисел, нужно подсчитать кол-во подмассивов, состоящих из нулей.
Например, дан массив [0, 0, 1].
Как видим, есть последовательность из двух нулей в начале массива. Она генерирует нам три «нулевых» подмассива — [0]x2 и [0, 0]. Т.е. ответ для данного примера — 3.
Решение
Основная сложность задачи заключается в том, чтобы вывести формулу, понять как последовательность нулей перевести в число комбинаций.
Если попробовать разные последовательности, то быстро определяется закономерность:
|
1 2 3 4 5 6 |
1 [0] - 1 2 [0,0] - 3 3 [0,0,0] - 6 4 [0,0,0,0] - 10 5 [0,0,0,0,0] - 15 ... |
Число комбинаций рекурсивно растет на n для каждого следующего шага.
Если мы будем сканировать массив, то нам даже не потребуется определять полную длину последовательности нулей, т.к. на каждой итерации вдоль массива мы будем добавлять в копилку комбинаций текущую длину нулевого подмассива.
Таким образом, пройдя лишь один раз вдоль массива, мы сможем подсчитать все комбинации.
Пример кода на typescript:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
function zeroFilledSubarray(nums: number[]): number { const len = nums.length // длина текущей нулевой цепочки let curChain = 0; // копилка числа подмассивов let acc = 0; for (let i = 0; i < len; i ++) { if (nums[i] === 0) { // отлеживаем длину нулевой цепочки curChain ++; acc += curChain; } else // цепочка обрывается // обнуляем длину curChain = 0; } return acc; }; |