Як обчислити найдовшу послідовність елементів в масиві за допомогою JavaScript?

No video

Як обчислити найдовшу послідовність елементів в масиві за допомогою JavaScript?

Рет қаралды 1,239

Күн бұрын

Задача: обчислити довжину безперервної послідовності нулів у масиві.
Пост про задачу на телеграм-каналі: t.me/programmi...
Посилання на repl: repl.it/@koldo...
Щоб добре вивчити JavaScript приходьте на мій унікальний менторський курс ScriptJedi42: sj42.programmi...

Пікірлер: 30

@yuriikoval2453 3 жыл бұрын

Класний розв'язок. Єдине зауваження, це те що quick sort характеризується n*log(n) або n^2 складністю, а не експотенціальною.

@programmingmentorua 3 жыл бұрын

Так, це коректне уточнення, для quicksort - Big O від логарифмічного до квадратичного

@olehm9672 3 жыл бұрын

ще можна покращити перевіркою, чи поточне значення max > кількості елементів, що залишились -> не має потреби перебирати решту. Але тоді через do while

@AnoJlJloH 3 жыл бұрын

Яка ваша думка щодо такого рішення? arr.split('1').map(item => item.length).reduce((accum, cur) => Math.max(accum, cur)) або отакий Math.max(...arr.join('').split('1').map(item => item.length))

@programmingmentorua 3 жыл бұрын

Дуже гарно, мені подобається

@ostrojen 3 жыл бұрын

Було б цікаво ще подивитись на бенчмарки якісь. А взагалі типовий приклад коли якась рішення працює і рахується корректним незважаючи на його неоптимальність

@programmingmentorua 3 жыл бұрын

Ну там замість бенчмарку достатньо порахувати кількість викликів функції-компаратора в sort() і побачити значне зростання зі збільшенням кількості елементів

@utilmind 3 жыл бұрын

Та вже доведено, що для швидкості краще тільки for {}, без всяких map, filter, reduce, forEach та ін.

@ostrojen 3 жыл бұрын

@@utilmind угу, але редюс тут більше підходить по сенсу. Треба з масиву отримати одне значення, поправте якщо помиляюсь

@chapaisnoopi 3 жыл бұрын

Як не мане, то проста перевірка і лічильник легко читати і також в один прохід: const longest = arr => { let [res, count] = [0, 0]; arr.forEach( el => el === '0' ? count++ : [res, count] = [Math.max(res, count), 0] ); return Math.max(res, count); }

@utilmind 3 жыл бұрын

1. Це пошук ноликів Integer-типу, а не найдовшої послідовності елементів. 2. Це не працює, якщо масив закінчується найбільшою послідовністю: 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] //

@chapaisnoopi 3 жыл бұрын

@@utilmind Дякую за уважність, трохи підправив.

@chapaisnoopi 3 жыл бұрын

@@utilmind щодо першого: Задача: обчислити довжину безперервної послідовності нулів у масиві.

@utilmind 3 жыл бұрын

@@chapaisnoopi Ні! Будь ласка прочитайте заголовок під відео. Про нулі немає мови. Точна задача: «Як обчислити найдовшу послідовність елементів в масиві за допомогою JavaScript?»

@bohdanostrovskyi2051 3 жыл бұрын

Мне кажется возможен более простой вариант поиска (как для меня) const Foo = arr => { let res = []; let tempRes = []; arr.forEach(el => { if (el === 0) { tempRes.push(el) if (res.length < tempRes.length) res = tempRes } else { tempRes = []; } }) return res.length; } console.log(Foo(arr))

@programmingmentorua 3 жыл бұрын

Недолік такого рішення в тому, що в ньому є мутації, а загалом норм

@utilmind 3 жыл бұрын

Недолік такого рішення що воно не вирішую задачу «Обчислення найдовшої послідовності елементів в масиві за допомогою JavaScript». Здається воно рахує тільки нулі, та й ті тільки типу Integer.

@utilmind 3 жыл бұрын

@@programmingmentorua До речі, це смішно, але рішення на відео також не вирішує поставлену задачу :))) На відео демонструється пошук ноликів, а не послідовності елементів :))

@bohdanostrovskyi2051 3 жыл бұрын

@@utilmind собственно не сложно было бы переделать но да вы правы - я хотел сделать что то , что можно было сравнивать с видео

@utilmind 3 жыл бұрын

@@bohdanostrovskyi2051 я на американских тестовых заданиях и не такие уловки видал. Там нужно почти юристом быть, чтобы результат СОВЕРШЕННО ТОЧНО, БУКВАЛЬНО соответствовал поставленной задаче.

@romanyasinsky7468 3 жыл бұрын

const badLongestSeq = (seg) => { let prevCount = 0; let currentCount = 0; let longest; for (let i = 0; i prevCount ? currentCount : prevCount; prevCount = longest; currentCount = 0; } } return longest; };

@utilmind 3 жыл бұрын

Хто може дати швидше рішення? const seq = [ 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, ]; let maxCount = 0, curCount = 0, curItem, prevItem, l = seq.length+2, // +1+1 to finish last sequence and compare undefined with previous i = 0; for (; i < l; ++i) { curItem = seq[i]; if (curItem === prevItem) ++curCount; else { if (curCount > maxCount) maxCount = curCount; curCount = 1; prevItem = curItem; } } console.log("Result is " + maxCount);

@utilmind 3 жыл бұрын

На або в обертці: let longestSeq = () => { let maxCount = 0, curCount = 0, curItem, prevItem, l = seq.length+2, // +1+1 to finish last sequence and compare undefined with previous i = 0; for (; i < l; ++i) { curItem = seq[i]; if (curItem === prevItem) ++curCount; else { if (curCount > maxCount) maxCount = curCount; curCount = 1; prevItem = curItem; } } return maxCount }

@Arustokrat812 3 жыл бұрын

А як щодо такого рішення? const longestZeroSeq = (sequence) => { let finalCounter = 0; let currentCounter = 0; sequence.forEach(digit => { if (digit === '0') { currentCounter += 1; } else { if (currentCounter > finalCounter) { finalCounter = currentCounter; } currentCounter = 0; } }) return finalCounter; } Недоліком цього рішення хіба буде вкладений if у if. Рішення із reduce було неочікуваним, хоч і сам неодноразово використовував його.)

@utilmind 3 жыл бұрын

Це пошук ноликів строкового типу, а не найдовшої послідовності елементів.

@chapaisnoopi 3 жыл бұрын

const seq = [ "0", "0", "0", "1", "1", "1", "1", "1", "1", "1", "1", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" ] ; Не працює!