LeetCode task about collecting rainwater | JavaScript interview
Вставка
- Опубліковано 2 чер 2024
- Привет, друзья! Продолжаем решать задачи про воду с LeetCode. И сегодня мы разберем задачу про сбор дождевой воды - 42. Trapping Rain Water.
Эта задача Hard уровня сложности - такие задают на собеседованиях миддлам и синьорам, поэтому, джуны, в комментах не бояться! 😉
По условиям: у нас на вход подается массив с высотой рельефа. Представим себе, что каждая "ячейка" рельефа у нас шириной 1 и высотой той, которая задана в конкретном элементе массива. Наша задача посчитать, какое количество элементов (юнитов) воды может накопиться в таком рельефе, если пройдет дождь.
Из дополнительных условий - это то, что длина массива может быть от 1 до 10 000, а значения элементов в массиве могут быть от 0 до 100 000.
Присылайте свои решения в комментариях! С интересом их посмотрим!
👍Если Вам понравился данный разбор - поддержите нас лайком и комментарием! И обязательно проверьте, нажат ли у вас колокольчик, чтоб первыми узнавать о наших новых выпусках 😉
👍🤩 Будем благодарны за поддержку нашего канала на Патреоне: / frontendscience
Таймкоды:
00:00 Интро
00:28 Условие задачи
02:01 Алгоритм решения
09:49 Алгоритм решения с константой по памяти
16:30 Пишем код
21:25 Проверяем решение
21:40 Делаем рефакторинг
24:08 Присылайте ваши решения
✅ Задача на Leetcode: leetcode.com/problems/trappin...
✅ Код из видео: codepen.io/puzankov/pen/WNOKy...
---
Если видео было для вас полезным, ставьте лайк и поделитесь им с друзьями.
Подписывайтесь на наш канал: bit.ly/fs-ytb
---
Присоединяйтесь к нам в соцсетях:
FB: / frontendscience
Instagram Сергея Пузанкова: / puzankovcom
Заходите на наш сайт: frontend-science.com/
---
Music:
Blue Wednesday "From a friend",
Blue Wednesday & Dillan Witherow - Long Walk Short Dock.
---
#ityoutubersru #фронтенд #алгоритмы #leetcode
---
о, что то новое уже на просторах ютуба, с графическим объяснениям это просто бомба!
Благодарим за поддержку! Рады, что понравилось!
Решил по-другому. Всю эту гористую местность разбил на уровни снизу вверх. И на каждом уровне просчитал количество воды. А те крайние выемки для воды, которые не ограждены стеной слева и справа - вычитаем. Такое решение мне кажется проще в понимании :)
const input1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]; // 6
const input2 = [4, 2, 0, 3, 2, 5]; // 9
function trap(height) {
const max = Math.max(...height);
let total = 0;
for (let i = 0; i < max; i++) {
let startWall = -1;
let endWall = -1;
height.forEach((el, idx) => {
if (i >= el)
total++;
if (el > i)
{
if (startWall < 0)
startWall = idx;
endWall = idx;
}
});
total -= startWall + (height.length - (endWall + 1));
}
return total;
}
console.log(trap(input1));
console.log(trap(input2));
Прикольно что на литкоде есть тесты с огромными массивами. Типа решил задачу, а оказывается еще решать и решать. :)
Спасибо за видео, очень крутой формат!
Спасибо, такое интересное решение, действительно очень компактно, а я решила очень громоздко.
Однозначно подписка. Спасибо автору❤️
Благодарим! Рады Вам! :)
Давай больше разборов задач! Очень интересно и полезно!
👍
Очень интересно, благодарю!
Моё решение получилось раза в 2-3 длиннее, а самое интересное, сколько разных вариантов решения предлагают люди!
Какая интересная задача, хоть и простая. Спасибо!
Я почему-то про интегрирование (дискретное) сразу подумал, т.е.площадь удава, который съел слона и похож на шляпу, посчитать, а потом вычесть..
этот канал по всей логике уже давно должен быть миллионником, ну или скоро будет
Класс! Пусть так и будет! :)
Эту задачу уровня hard решил быстрее, чем большинство уровня middle.
Решение методом двух указателей. Выбираю наименьший из двух краев и считаю, сколько воды поместится в близлежащий блок. Сложность O(n). По памяти O(1).
function trap(arr) {
let left = 0;
let right = arr.length - 1;
let maxLeft = arr[left];
let maxRight = arr[right];
let result = 0;
while (left + 1 < right) {
if (arr[left] < arr[right]) {
left++;
let current = arr[left];
if (current < maxLeft) {
result += maxLeft - current;
} else {
maxLeft = current;
}
} else {
right--;
let current = arr[right];
if (current < maxRight) {
result += maxRight - current;
} else {
maxRight = current;
}
}
}
return result;
}
Результат на leetcode: Runtime 49ms Beats 99.33%
Всегда смотрю как вы решаете и понимаю, что в лоб лучше не решать, а подумать о сложности ахах, но всё же может кому-то будет интересно. While + for. Я перебирал каждый уровень графика снизу вверх и смотрел "послойно" на каком уровне где сколько воды лежит.
let arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]//6
let arr1 = [4,2,0,3,2,5]//9
function trap(arr) {
let result = 0
let arrIsEmty = false;
while(!arrIsEmty){
let weDontHaveLeftNotZeroElementNow = true
let lastDontZeroElementIndex;
let countZeroElementsInRow = 0
for(let i=0; i
Спасибо за интересную задачу! Моё решение получилось далеко не оптимальным (почему-то не учитывал, что массив heigth может содержать большие числа). Оформил его через создание матрицы рельефа (земля - true, пустота - false), потом вычислил сколько воды поместится в каждой строке матрицы и суммировал. Вот, делюсь:
const trap = heigth => {
const reliefMatrix = [],
maxHeigth = Math.max(...heigth);
for (let i = 0; i < maxHeigth; i++) {
reliefMatrix[i] = heigth.map(v => i < v);
}
let water = 0;
for (let row of reliefMatrix) {
let leftSide = row.indexOf(true),
rightSide = row.lastIndexOf(true),
container = row.slice(leftSide, rightSide);
water += container.filter(v => !v).length;
}
return water;
};
P.S.:// Можно записать в одну строчку:
const trap = heigth => Array.from(Array(Math.max(...heigth)), (_, i) => heigth.map(v => i < v)).reduce((water, row) => water + row.slice(row.indexOf(true), row.lastIndexOf(true)).filter(v => !v).length, 0);
Это решение можно чуток сократить:
const trap = heigth => {
const maxHeigth = Math.max(...heigth);
let water = 0;
for (let i = 0; i < maxHeigth; i++) {
let row = heigth.map(v => i < v),
leftSide = row.indexOf(true),
rightSide = row.lastIndexOf(true),
container = row.slice(leftSide, rightSide);
water += container.filter(v => !v).length;
}
return water;
};
Очень качественный контент, спасибо, готовлюсь к собеседованию по твоим видосам😎
Рад, что полезно! Успехов!
Супер, спасибо!!!!
И Вам спасибо за поддержку!
Супер. Спасибо
Как идея для видео, можете запилить ролик, план развития js разработчика, ну или фронт енд, ну или что-то в этом роде, хотя думаю у вас там и так куча идей:)
Привет, спасибо за качественный контент) Вот мой варик :
const calcWater = (intervals) => {
let result = 0;
let highest = 0;
let currentIndex = 0;
for (let i = 0; i < intervals.length; i++) {
if ((intervals[i] >= intervals[currentIndex]) || intervals[i] === highest) {
currentIndex = i;
highest = 0;
for (let k = currentIndex + 1; k < intervals.length; k++) {
highest = Math.max(highest, intervals[k])
}
}
const min = Math.min(intervals[currentIndex], highest);
if (intervals[i] < min) {
result += min - intervals[i];
}
}
return result || 0;
}
Годнота! Однозначно лайк и подписка!)
Благодарю за поддержку! ;) приветствую!
задача классная, ну а ваше графическое объяснение просто топ! спасибо)))
Благодарю) Рад, что понравилось!
Лайк, однозначно
Благодарим за поддержку!
Есть ещё один способ решить эту задачу за линейное время и константную память. Нужно найти самый большой элемент и его индекс (любой наибольший эл-т если их больше одного) и пройтись циклом слева, на каждой итерации обновляя максимальную высоту слева и высчитывая объем в клетке(так как мы уже знаем максимум с обоих сторон). Потом сделать то же самое, только справа. Мне это решение показалось проще, чем с указателями
let trap = function(height) {
let vol = 0
const glMax = Math.max(...height)
const glMaxIndex = height.indexOf(glMax)
let leftMax = 0
for (let i = 0; i < glMaxIndex; i++) {
leftMax = Math.max(leftMax, height[i])
vol += Math.min(leftMax, glMax) - height[i]
}
let rightMax = 0
for (let i = height.length - 1; i > glMaxIndex; i--) {
rightMax = Math.max(rightMax, height[i])
vol += Math.min(rightMax, glMax) - height[i]
}
return vol
};
Благодарю за решение! Интересно вышло! Алгоритм очень похож - но мы добавили еще один проход для поиска максимума.
PS: с указателями на самом деле мы тоже одним из указателей найдем этот максимальный пик - и этот указатель на нем и останется до конца работы алгоритма.
точно, это уже не линейная сложность а двулинейная)
@@s.i.9988 а по памяти пятиконстантная как минимум)
Кто вообще придумал спрашивать задачи с Leetcode на собеседованиях. Вопрос конечно риторический.
Спасибо, задачка супер -- проста в условиях, сложна в решении!
Денёк пришлось помозговать.. теперь пойду смотреть Ваше решение, наверняка оно легче!)
А мой первый сабмишн таков:
Runtime: 84 ms, faster than 64.22% of JavaScript online submissions for Trapping Rain Water.
Memory Usage: 40.8 MB, less than 39.66% of JavaScript online submissions for Trapping Rain Water.
var trap = function (height) {
// total amount of water & city length
var total = 0;
var len = height.length;
// less than 3 buildings cannot hold water
if (len < 3) return 0;
// find the first & last peaks as the preceeding/following water is discarded
var firstPeak = findEdgePeak();
var lastPeak = findEdgePeak('last');
// one peak cannot hold water
if (firstPeak == lastPeak) return 0;
// calculate trapped water based on the map obj of the highest peaks
return calcWater(mapAllPeaks());
function calcWater(map) {
// loop map regions one by one
for (let [p1, p2] of Object.entries(map)) {
// calculate water lvl for region
let waterLvl = height[p1] < height[p2] ? height[p1] : height[p2];
// coerce str prop to Number
// add to total if below water lvl
for (let i = (p1 | 0) + 1; i < p2; i++) {
if (waterLvl > height[i]) {
total += waterLvl - height[i];
}
}
}
return total;
}
// can optionally be provided with "last" flag
function findEdgePeak(position) {
var peak = position == 'last' ? len - 1 : 0;
for (let i = peak; height[next(i)] >= height[i]; i = next(i)) {
peak = next(i);
}
return peak;
function next(i) {
if (position == 'last') return i - 1;
return i + 1;
}
}
// finds the next peak index (returns the last index of flat surfaces)
function findNextPeak(start) {
var peak;
var rising = false;
var i = start | 0;
while (peak == undefined && i height[i]) {
rising = true;
}
} else if (height[i + 1] < height[i] || i == lastPeak) {
peak = i;
}
++i;
}
return peak;
}
// TCO-friendly recursive fn
// returns a map of {[peak index]: index of the largest following peak }
function mapAllPeaks() {
// pure data object to map to
var map = Object.create(null);
function mapPeaks(curPeak) {
var maxPeak;
map[curPeak] = findNextHighest(curPeak);
curPeak = map[curPeak];
if (curPeak >= lastPeak) return map;
function findNextHighest(prevPeak) {
var nextPeak = findNextPeak(prevPeak);
if (height[nextPeak] >= height[curPeak]) return nextPeak;
if (!maxPeak || height[maxPeak] < height[nextPeak]) {
maxPeak = nextPeak;
}
if (nextPeak >= lastPeak) return maxPeak;
return findNextHighest(nextPeak);
}
return mapPeaks(curPeak);
}
return mapPeaks(firstPeak);
}
};
ВОУ!!! Круто, что сам дошел до решения!!!
while (left
Как раз таки эта реализация требует
Сергей, скажите, пожалуйста, а часто ли на собеседованиях на джуна фронтендера спрашивают алгоритмы и структуры и хезмаст ли для джуна хорошо в них разбираться?
Upd: спасибо за ваши старания! до вас даже не слышал о таком понятии как сложность алгоритма)
Вообще нет, но в яндекс нужно знать например, у меня были задачи на stack и указатели. В faang тоже нужно
Благодарю, очень рад.
Про алгоритмы и структуры данных, как уже написали, все зависит от компании. В основном джунов такое не спрашиваю, начинают примерно от миддла. Но компании по типу Google, Яндекс и пр. даже на уровне джунов требуют такие знания.
@@frontendscience Спасибо за ответ, просто недавно созрел для поиска первой работы, на первых двух собесах меня спросили про это hr, тут я и удивился и не был готов к такому, т.к. алгоритмами пользовался только на учебе в вузе на с++ несколько лет назад )
@@Nikita-gn4bg странно что hr такое спрашивал. А что за город?
@@frontendscience спб
upd: довольно странно собеситься по телефону с hr, она задавала вопросы по реакту, а я не понимал, что она хочет, как оказалось мне нужно было объяснить как из дочернего элемента изменять стейт родительского (ее формулировку я, к сожалению, не запомнил)
Кстати отправил вам заявку на паблик интервью, буду надеяться, что услышимся когда-нибудь!
Можно ещё так :)
function trap (arr) {
let sum = 0
const str = arr.join('')
for( i = 0; i < arr.length+1; i++ ){
const left = Math.max.apply(null, str.substring( 0, i ).split('') )
const right = Math.max.apply(null, str.substring( i ).split('') )
const res = Math.min( left, right ) - arr[i]
if ( res > 0 ) sum += res
}
return sum
}
Благодарю за решение! на литкод несколько тест кейсов не проходит - надо задебажить
@@frontendscience Да, перепроверил своё решение. Во-первых сам себе трудностей создал по переводу массива в строку и обратно (хоть так тоже работает с входными данными из видео). Во-вторых, такой подход (с делением массива на два и проверке максимального числа в каждом) не пройдёт при большой длине массива. Поторопился, в общем :)
моща. спс
))))) нзчт
У меня только 1 вопрос почему здесь дизлайк? Всё понятно и ясно.
я не посмотрел еще решение, но я решил просто нарезать данный массив на двухмерный и найти сумму всех нулей, расположенных между единицами :D
arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
function trap(height){
arrFloors = [];
maxValue = 0;
sum = 0;
height.forEach(item => {
(item > maxValue) ? maxValue = item: false;
});
for(i = 0; i < maxValue; i++){
arrFloors.push([]);
for(j = 0; j < height.length; j++){
if(height[j] > 0){
arrFloors[i].push(1);
height[j]--;
}else{
arrFloors[i].push(0);
}
}
}
arrFloors.forEach(item => {
for(i = item.indexOf(1); i < item.lastIndexOf(1); i++){
(item[i] == 0) ? sum++ : false;
}
})
return sum;
}
console.log(trap(arr));
Задача красивая, спору нет.
Алгоритмы решения и реализацию сам придумал? Или немножко где-то подсмотрел, видел похожее?
Как то с трудом верится, что такое решение можно найти самому, даже имея приличный опыт)
Как раз-таки опыт решает, особенно, если подобные задачи уже были решены до этого. А на этом канале они есть.
like
Дякую
Оба варианта очень крутые, но второй все таки круче даже просто потому что он короче) JS Frontend Backend Задачи Собеседование React
Ценю твою поддержку)
const trap =(mount)=>{
if (mount.length === 1) {
return 0
}
let openCarier = false;
let result = 0;
for (let position of mount2) {
if (position > 0){
openCarier = !openCarier
} else {
if (openCarier) {
result += 1;
}
}
}
return result + trap(mount.filter(pos=>pos > 0).map(pos=>pos-1))
}
сразу об этом решение подумал и сложность равна O(n)
Осмелюсь выложить не оптимальное, но всё же МОЁ решение, как обычно... в лоб ))
function trap(height) {
var maxLine = Math.max.apply(null, height)
var waterBlockCount = 0
for (let i = 1; i < maxLine + 1; i++) {
entireUnit: for (let j = 1; j < height.length - 1; j++) {
var nominal = height[j]
if (nominal >= i) continue entireUnit
else nominal = i - 1
leftUnit: for (let k = j - 1; k > -1; k--) {
var leftValue = height[k]
var countLeft = 0
if (leftValue > nominal) {
countLeft = j - k
break leftUnit
}
}
if (countLeft === 0) continue entireUnit
RightUnit: for (let l = j + 1; l < height.length + 1; l++) {
var rightValue = height[l]
var countRight = 0
if (rightValue > nominal) {
countRight = l - j
j = l - 1
break RightUnit
}
}
if (countRight === 0) continue entireUnit
waterBlockCount += countLeft + countRight - 1
}
}
return waterBlockCount
}
Будет видео о проектах для обучения?
Будет!
Приятного просмотра: ua-cam.com/video/0ue4Z3W0x60/v-deo.html
Здравствуйте Сергей, очень нужна ваша помощь, дело в том что я уже в комментах написал проблему, но ютуб удалил коммент.Может мне на инст прислать проблему?или какой либо другой мессенджер
Не вопрос, конечно, пиши в инст или на почту
const trap = (heights) => {
let result = 0;
for(let i = 1; i < heights.length - 2; i++) {
let maxLeft = Math.max(...heights.slice(0,i))
let maxRight = Math.max(...heights.slice(i + 1))
let minHeight = Math.min(maxLeft,maxRight)
let quantity = minHeight - heights[i];
if(quantity > 0){
result += quantity
}
}
return result
}
Как открыть терминал как у вас,внизу,что бы можна было проверять работу кода?
В вебшторме при клике на файл второй кнопкой есть команда run - это запустить выполнение этого js-файла с помощью node js. Откроется соответствующая вкладка внизу.
@@frontendscience Можна ли при помощи Vs code это зделать?
@@vasiajulia4173 уверен, что можно, но не подскажу как, т.к. с VScode не работал
@@frontendscience Спасибо , я постараюсь разобраться,пока просто пишу код как у вас и пытаюсь вникать в суть)
@@vasiajulia4173 успехов! Это хорошо, что Вы тренируетесь.
Что за графический редактор?
Это online сервис excalidraw
Ищем левый положительный элемент и правый положительный элемент, считаем количество нулей между ними. Потом отнимаем 1 от всех элементов и снова считаем левый и правый и нули между ними и т.д. То есть считаем замкнутые нули по слоям.
Присылайте решение!
@@frontendscience
const input1 = [0,1,0,2,1,0,1,3,2,1,2,1];
const input2 = [4,2,0,3,2,5];
function trap(input){
let waterCount = 0;
for ( let i = 0; i < Math.max( ...input ); i++ ){
waterCount = waterCount + rowCount( input.map( item => { return (item - i > 0) ? 1 : 0 }) );
}
function rowCount(row){
let result = 0;
let minLeft = row.indexOf(1);
let maxRight = row.lastIndexOf(1);
for ( let i = minLeft; i < maxRight; i++ ){
if ( row[i] == 0 ) result ++;
}
return result;
}
return waterCount;
}
console.log(trap(input1));
console.log(trap(input2));
Уверен что решение не очень (да и навело на меня решение другой задачи, про сушу), но на всякий случай прикреплю, интересно)
const input1 = [0,1,0,2,1,0,1,3,2,1,2,1]; //6
const input2 = [4,2,0,3,2,5]; //9
function trap(height){
let rows = Math.max(...height);
let cols = height.length;
let counter = 0;
if(rows === 0){
return 0;
}
let matrix = [];
let positiveIndexesArray = [];
for(let r = 0; r < rows;r++){
matrix.push([]);
positiveIndexesArray.push([]);
for(let c = 0; c < cols;c++){
if(height[c] > 0){
positiveIndexesArray[r].push(c);
matrix[r][c] = 1;
height[c] = height[c]-1;
}else{
matrix[r][c] = 0 ;
}
}
}
for(let r = 0; r < matrix.length;r++){
for(let c = 0; c < cols;c++){
if(matrix[r][c] === 0 && c > Math.min(...positiveIndexesArray[r]) && c < Math.max(...positiveIndexesArray[r])){
counter ++;
}
}
}
return counter
}
console.log(trap(input1));
console.log(trap(input2));
function trap(height) {
let result = 0;
let left = 0;
let right = height.length - 1;
const max = Math.max(...height);
const maxIndex = height.indexOf(max);
let currentMax = 0;
while (left < maxIndex) {
currentMax = Math.max(currentMax, height[left]);
result += currentMax - height[left];
left++;
}
currentMax = 0;
while (right > maxIndex) {
currentMax = Math.max(currentMax, height[right]);
result += currentMax - height[right];
right--;
}
return result;
}
const input1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]; // 6
const input2 = [4, 2, 0, 3, 2, 5]; // 9
function trap(height) {
let result = 0;
for (let i = 1; i < height.length-1; i++) {
const maxLeft = Math.max(...height.slice(0, i))
const maxRight = Math.max(...height.slice(i, height.length))
const water = Math.min(maxLeft, maxRight)
result += water > height[i] ? water - height[i] : 0
}
return result
}
console.log(trap(input1))
console.log(trap(input2))
Я только до такого додумался
function trap(height) {
while(height[1] >= height[0]) {
height.shift()
}
while(height[height.length - 2] >= height[height.length - 1]) {
height.pop()
}
if(height[0] < height[height.length - 1]) height.reverse()
let total = 0
let max = height.pop()
while(height[height.length-1] < max) {
let value = height.pop()
total = total + (max - value)
}
if(height.length < 3) return total
return total + trap(height)
}
Отлично вышло! Благодарю за решение
function collectWater(integers: number[]) {
let volume = 0;
let currentMax = 0;
let currentVolume = 0;
integers.forEach(integer => {
if (integer > currentMax) {
currentMax = integer;
volume += currentVolume;
}
if (currentMax > integer) {
currentVolume += currentMax - integer;
}
});
return volume;
}
console.log(collectWater([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6
console.log(collectWater([4, 2, 0, 3, 2, 5])); // 9
Не могу понять откуда он эти цифры берёт.
Дааа. Вторым способом намного легче и быстрее
Потому что он знает, как рассчитывают сложность алгоритмов по BigO.)
ua-cam.com/video/Fu4BzQNN0Qs/v-deo.html
let input1 = [0,1,0,2,1,0,1,3,2,1,2,1] // 6
let input2 = [4,2,0,3,2,5] // 9
let input3 = [1,0,0,1,2,3,2,1,0] // 2
function getWaterAmount (arrayOfNumbers){
let height = Math.max(...arrayOfNumbers)
let valuesPerRow = {}
let result = 0
for (let row = 1; row= row){
valuesPerRow[row].push(1)
}else{
valuesPerRow[row].push(0)
}
}
}
Object.values(valuesPerRow).forEach((arr)=>{
result += calculateBlocks(arr)
})
console.log(result)
}
function calculateBlocks(arr){
let count = []
let startCounting = false
let previousWasZero = false
let result = 0
for (const elem of arr) {
if(elem === 0 && startCounting){
count.push(1)
previousWasZero=true
}
if(elem === 1){
startCounting = true
}
if(elem ===1 && startCounting && previousWasZero){
result = count.length
}
}
return result
}
// getWaterAmount(input2)
ссылки на jsfiddle режет
я решил посчитать рядами
let input = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]; // 6
let input2 = [4, 2, 0, 3, 2, 5]; // 9
let map = [];
/**
* переводим в карту
*
* 0 | 0 1 0 0 0
* 1 | 1 1 0 0 1
* 2 | 1 1 0 1 1
* 3 | 1 1 1 1 1
*
* для наглядности * - есть кирпич, . - нет кирпича
*
* 0 | . * . . .
* 1 | * * . . *
* 2 | * * . * *
* 3 | * * * * *
*/
for (let i = 0; i < Math.max(...input); i++) {
let tmp = [];
for (let j = 0; j < input.length; j++) {
let isFill = input[j] > i && input[j] !== 0 ? 1 : 0;
tmp.push(isFill);
}
map[i] = tmp;
}
const calculateRow = (array) => {
let out = array.join(""); // джойним массив (ряд) в строку
out = out.replace(/0/g, " ").trim(); // заменяем нули на пробелы и обрезаем крайние пробелы (пустые места куда вода не наберется)
return out.split(" ").length - 1; // осталось посчитать количество пробелов (пустых мест для воды)
}
// сумма
let sum = map.reduce((acc, row) => {
return acc + calculateRow(row);
}, 0)
Благодарю за решение! Необычный подход, такого еще не видел.
ЗЫ: К сожалению на литкод он не прошел по времени: Time Limit Exceeded
Вот моё решение:
function trap(height) {
const max = Math.max(...height);
let result = 0;
for (let i = 0; i < max; i++) {
let container = {
width: 0, // количество нулей
leftBorder: 0, // позиция не нулевого элемента
rightBorder: 0 // позиция не нулевого элемента
}
height.forEach((el, i, arr) => {
if (!container.leftBorder) {
if (el > 0) {
container.leftBorder = 1;
}
}
if (container.leftBorder) {
if (el 0) {
container.rightBorder = 1;
result += container.width
container = {
width: 0, // количество нулей
leftBorder: 0, // позиция не нулевого элемента
rightBorder: 0 // позиция не нулевого элемента
}
container.leftBorder = 1
}
}
arr[i] = el - 1; // убираем нижний уровень (как в тетрисе)
})
}
return result;
}
И подскажите пожалуйста, правильно ли я посчитал сложность по скорости?
У меня получилось O(n) = n * m + n; где m - максимальная высота столбца
Благодарю за решение. Сложность вышла квадратичная O(n^2). Так как есть внешний цикл for который идет по всем элементам (в худшем случае максимум будет на самом последнем элементе), а потом внутри есть еще один цикл forEach. Поэтому это решение на литкод выдает: Time Limit Exceeded. Он хочет более оптимальный вариант по времени.
@@frontendscience
Благодарю за ответ.
320 / 320 test cases passed, but took too long. Пичаль.
Кое-что поправил и прошло. Runtime: 316 ms, faster than 5.05% of JavaScript online submissions for Trapping Rain Water.
Memory Usage: 41.3 MB, less than 14.56% of JavaScript online submissions for Trapping Rain Water.
@@user-bro прикольно! Присылай решение!
@@frontendscience
var trap = function(height) {
if (!Array.isArray(height) || height.length < 3) return 0
const secondHeight = (height.map(i => i).sort((a, b) => b-a))[1]
const tempArray = Array(...height)
let maxLeft = 0;
for (let k = 1; k < height.length-1; k++){
maxLeft = maxLeft < height[k-1] ? height[k-1] : maxLeft;
tempArray[k] = getHeight(k, height, secondHeight, maxLeft)
}
let a = height.reduce((prev, curent) => prev + curent)
let b = tempArray.reduce((prev, curent) => prev + curent)
return b-a;
};
const getHeight = (index, array, heightLimit, maxLeft) => {
let leftWallHeight = maxLeft;
let rightWallHeight = 0;
for (let r = index+1; r < array.length ; r++) {
if (array[r] > rightWallHeight) rightWallHeight = array[r];
if (rightWallHeight >= heightLimit) break;
}
return Math.max(Math.min(leftWallHeight, rightWallHeight), array[index])
}
Классно! Благодарю что поделился!
1, 5 дня трудов
let rain = [0, 1, 0, 3, 1, 0, 2, 0, 4]
let resultate = {}
console.log(edel(rain))
function edel(arr){
const max = Math.max(...arr)
colb(max, arr)
push (resultate)
let res = counter(resultate)
return res
}
function colb (max, arr) {
let j=0
while (j !== max){
j++
resultate[j] = []
for (i=0; i
23:55
получаю почему-то 0 и 2
гугл вырезает коммент, не могу скинуть в codepen
const input1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]; // 6
const input2 = [4, 2, 0, 3, 2, 5]; // 9
function trap(height) {
let maxLeft = height[0];
let maxRight = height[height.length - 1];
let left = 1;
let right = height.length - 2;
let total = 0;
while (left
привет! ютюб удаляет все комменты со ссылками.
По твоему вопросу - у тебя ошибка в коде - ты поставил return total; внутри while - получилось что на первой же итерации ты вернул ответ из функции и не пошел дальше. return total должен быть после того как while отработает
@@frontendscience большое спасибо за разъяснение, прошу извинить за невнимательность)
Приятно видеть оперативный ответ, на codepene тоже увидел ответ.
@@frontendscience а как можно попасть на собеседование к вам?
уж лучше собирать дождевую воду чем собираться на пенсию в 20
Куда исчезают мои комментарии? Модерация какая-то или что?
Андрей, я вижу нотификации, но самих комментариев нет и не могу посмотреть до конца даже сообщения. Ютуб удаляет все комменты сл ссылками. Но я так понимаю, что вы просто решение уже высылаете. И его я тоже не вижу. Почему-то ютуб трет эти комменты. Может, увидел большую активность, чем всегда, не знаю… попробуйте выслать номер id пользователя на кодпене и id самого пена. Без полной ссылки
@@frontendscience В прошлый раз мое решение в комментариях нормально прошло. Странно. Ладно, попробуем другим путем.
Уфф, це була потна катка))
const getSumRain = (isArray) => {
const input = [...isArray]
const maxLeftArray = [...isArray];
const maxRightArray = [...isArray];
// Створюю пусті масиви для комфортної роботи в подальшому
let sumFirstArray = [],
maxLeft = [],
sumSecondArray = [],
maxRight = [],
minLR = [],
isValueRain = []
maxLeftArray.map((element, index) => { // сортуємо масив із ліва направо (maxLeft)
sumFirstArray.push(maxLeftArray[index])
maxLeft.push(Math.max(...sumFirstArray))
return maxLeft
})
maxLeft.pop() // Вирівнюємо лівий край скали першого масива
maxLeft.unshift(0) // Вирівнюємо правий край скали першого масива
maxRightArray.reverse().map((element, index) => { // Створюємо такий самий масив тільки з права наліво (maxRight) за допомогою reverse()
sumSecondArray.push(maxRightArray[index])
maxRight.push(Math.max(...sumSecondArray))
return maxRight
})
maxRight.unshift(0) // Вирівнюємо лівий край скали другого масива
maxRight.reverse() // Розвертаємо, щоб коретно пройшли наступні операціїї
for (let i = 0; i < maxLeft.length; i++) { // Рахуємо мінімум в який може набратися вода
minLR.push(Math.min(maxLeft[i], maxRight[i]));
}
for (let i = 0; i < input.length; i++) { // Знаходимо заповнені водою клітинки
if (minLR[i] >= input[i]) {
const result = minLR[i] - input[i]
isValueRain.push(result)
}
}
return isValueRain.reduce((accumulator, total) => accumulator + total, 0); // Рахуємо клітинки з водою
}