1/n: Задачи leetcode JS — «Max Consecutive Ones» (Найти максимальное количество последовательных единиц)
Всем привет.
Я столкнулся с тем, что на собеседованиях в некоторые ИТ-компании на 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», но это уже опциально, данная функция проходит тест «литкод».
Спасибо за внимание, начинайте кидаться помидорами. Расскажите, как бы вы лучше решили эту задачу. А я пошел решать следующие и упаковывать в статью, если будет что рассказать.
