1/n: Задачи leetcode JS — «Max Consecutive Ones» (Найти максимальное количество последовательных единиц)

Всем привет.

Я столкнулся с тем, что на собеседованиях в некоторые ИТ-компании на Frontend JavaScript требуется решать задачи, и я решил сделать серию статей на тему, как я решил их тем или иным образом. Перед вами — первый текст из этой серии.

Для решения будем использовать язык программирования TypeScript.

На каких тестах я проверял решение?

1. Подается массив [1,1,0,1,1,1], в нем максимальное количество единиц «3».

2. В этом массиве [1,0,1,1,0,1] их всего «2»

3. В этом же массиве их [1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1] — «9».

Я далеко не профессионал в синтаксисе и, как показала практика, я далек от спортивного программирования, где надо наизусть знать синтаксис спрашиваемого языка, и время на решение задачи ограничено, но я решил набивать руку, может быть, это будет мне полезно.

Мы должны написать функцию, она принимает в себя массив number (чисел) и вернет максимальное количество единичек в нем.

Сначала мы получаем следующую заготовку, с нее и начнем:

function findMaxConsecutiveOnes(nums: number[]): number { }

Я принял решение пробежаться по нашему массиву, и если там есть «0» (ноль), то надо что‑то сделать. Для этого будем использовать цикл for‑of в JavaScript.

for (const num of nums) { }

В итоге код всей функции выглядит следующим образом:

function findMaxConsecutiveOnes(nums: number[]): number {   for (const num of nums) {   } }

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

const numsArray: number[][] = [[]];

В итоге код всей функции выглядит следующим образом:

function findMaxConsecutiveOnes(nums: number[]): number {   const numsArray: number[][] = [[]];    for (const num of nums) {   } } 

Так как у нас массив может хранить массивы с числами, в цикле надо как-то обратиться к внутреннему массиву. Для этого нам нужен в скоупе функции какой-то итератор дополнительно к итерациям, проходящим по нашему принимаемому в параметре массиву. Предлагаю сделать переменную count типа number и придать ей значение нулевого индекса.

let count: number = 0;

В итоге код такой:

function findMaxConsecutiveOnes(nums: number[]): number {   let count: number = 0;   const numsArray: number[][] = [[]];    for (const num of nums) {   } }

Теперь в нашем первом цикле, если мы нашли «0» (ноль), давайте прибавим счетчик и положим в массив еще один пустой массив, а так же пропустим текущую итерацию цикла.

Предлагаю добавить в цикл следующий код:

if (num === 0) {   count++;   numsArray.push([]);   continue; }

Цикл будет выглядеть следующим образом:

for (const num of nums) {   if (num === 0) {     count++;     numsArray.push([]);     continue;   }   // напишем другой код }

Функция целиком будет выглядеть так:

function findMaxConsecutiveOnes(nums: number[]): number {   let count: number = 0;   const numsArray: number[][] = [[]];    for (const num of nums) {     if (num === 0) {       count++;       numsArray.push([]);       continue;     }     // напишем другой код   } }

После условия, но все еще внутри цикла, где мы указали комментарий, надо обратиться к вложенному массиву и туда класть наши числа, пока они не равны «0» (нулю).

numsArray[count].push(num);

Код функции будет следующий:

function findMaxConsecutiveOnes(nums: number[]): number {   let count: number = 0;   const numsArray: number[][] = [[]];    for (const num of nums) {     if (num === 0) {       count++;       numsArray.push([]);       continue;     }      numsArray[count].push(num);   } }

Теперь, если мы запустим код, то получим примерно следующую картину:

Но вспомним задачу: нам надо вернуть самое большое количество единиц от нашего изначального одномерного массива бинарных чисел (массив «0» (нулей) и «1» (единиц)).

Предлагаю пробежаться по массиву и спросить у вложенных массивов, сколько у них элементов, и опрошенное количество положить во временную переменную внутри цикла:

for (const item of numsArray) {   const lengthItem: number = item.length; }

Код всей функции будет выглядеть следующим образом:

function findMaxConsecutiveOnes(nums: number[]): number {   let count: number = 0;   const numsArray: number[][] = [[]];    for (const num of nums) {     if (num === 0) {       count++;       numsArray.push([]);       continue;     }      numsArray[count].push(num);   }    for (const item of numsArray) {     const lengthItem: number = item.length;   } }

Но наше значение неизвестно следующей итерации, и мы не можем сравнить, в каком массиве больше чисел. Для этого сделаем переменную max типа number вне скоупа цикла и приравняем ее «0» (нулю), а внутри цикла — после того, как мы спросили размер вложенного массива на каждой итерации — сделаем условие: что больше — наш max или количество элементов вложенного массива текущей итерации.

Если количество элементов массива, вложенного в массив текущей итерации, больше, обновим наш max этим количеством:

for (const item of numsArray) {   const lengthItem: number = item.length;      if (lengthItem > max) {     max = lengthItem;   } }

Теперь покажу вам всю функцию, но сразу с return max, который вернет самый большой max из функции:

function findMaxConsecutiveOnes(nums: number[]): number {   let count: number = 0;   const numsArray: number[][] = [[]];    for (const num of nums) {     if (num === 0) {       count++;       numsArray.push([]);       continue;     }      numsArray[count].push(num);   }    let max: number = 0;    for (const item of numsArray) {     const lengthItem: number = item.length;          if (lengthItem > max) {       max = lengthItem;     }   }    return max; }

По-хорошему стоит добавить в функцию завершение при ошибке, если передано что-то кроме «0» или «1», но это уже опциально, данная функция проходит тест «литкод».

Спасибо за внимание, начинайте кидаться помидорами. Расскажите, как бы вы лучше решили эту задачу. А я пошел решать следующие и упаковывать в статью, если будет что рассказать.