Всем привет.
Я столкнулся с тем, что на собеседованиях в некоторые ИТ-компании на Frontend JavaScript требуется решать задачи, и я решил сделать серию статей на тему, как я решил их тем или иным образом. Перед вами — первый текст из этой серии.
Для решения будем использовать язык программирования TypeScript.
На каких тестах я проверял решение?
Подается массив [1,1,0,1,1,1], в нем максимальное количество единиц «3».
В этом массиве [1,0,1,1,0,1] их всего «2»
В этом же массиве их [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», но это уже опциально, данная функция проходит тест «литкод».
Спасибо за внимание, начинайте кидаться помидорами. Расскажите, как бы вы лучше решили эту задачу. А я пошел решать следующие и упаковывать в статью, если будет что рассказать.
