Прикольно что на литкоде есть тесты с огромными массивами. Типа решил задачу, а оказывается еще решать и решать. :) Спасибо за видео, очень крутой формат!
Решил по-другому. Всю эту гористую местность разбил на уровни снизу вверх. И на каждом уровне просчитал количество воды. А те крайние выемки для воды, которые не ограждены стеной слева и справа - вычитаем. Такое решение мне кажется проще в понимании :) 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));
Спасибо за интересную задачу! Моё решение получилось далеко не оптимальным (почему-то не учитывал, что массив 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);
Всегда смотрю как вы решаете и понимаю, что в лоб лучше не решать, а подумать о сложности ахах, но всё же может кому-то будет интересно. 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
Эту задачу уровня 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%
Спасибо, задачка супер -- проста в условиях, сложна в решении! Денёк пришлось помозговать.. теперь пойду смотреть Ваше решение, наверняка оно легче!) А мой первый сабмишн таков: 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); } };
Как идея для видео, можете запилить ролик, план развития js разработчика, ну или фронт енд, ну или что-то в этом роде, хотя думаю у вас там и так куча идей:)
Какая интересная задача, хоть и простая. Спасибо! Я почему-то про интегрирование (дискретное) сразу подумал, т.е.площадь удава, который съел слона и похож на шляпу, посчитать, а потом вычесть..
Есть ещё один способ решить эту задачу за линейное время и константную память. Нужно найти самый большой элемент и его индекс (любой наибольший эл-т если их больше одного) и пройтись циклом слева, на каждой итерации обновляя максимальную высоту слева и высчитывая объем в клетке(так как мы уже знаем максимум с обоих сторон). Потом сделать то же самое, только справа. Мне это решение показалось проще, чем с указателями let trap = function(height) { let vol = 0
Благодарю за решение! Интересно вышло! Алгоритм очень похож - но мы добавили еще один проход для поиска максимума. PS: с указателями на самом деле мы тоже одним из указателей найдем этот максимальный пик - и этот указатель на нем и останется до конца работы алгоритма.
Можно ещё так :) 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 Да, перепроверил своё решение. Во-первых сам себе трудностей создал по переводу массива в строку и обратно (хоть так тоже работает с входными данными из видео). Во-вторых, такой подход (с делением массива на два и проверке максимального числа в каждом) не пройдёт при большой длине массива. Поторопился, в общем :)
Сергей, скажите, пожалуйста, а часто ли на собеседованиях на джуна фронтендера спрашивают алгоритмы и структуры и хезмаст ли для джуна хорошо в них разбираться? Upd: спасибо за ваши старания! до вас даже не слышал о таком понятии как сложность алгоритма)
Благодарю, очень рад. Про алгоритмы и структуры данных, как уже написали, все зависит от компании. В основном джунов такое не спрашиваю, начинают примерно от миддла. Но компании по типу Google, Яндекс и пр. даже на уровне джунов требуют такие знания.
@@frontendscience Спасибо за ответ, просто недавно созрел для поиска первой работы, на первых двух собесах меня спросили про это hr, тут я и удивился и не был готов к такому, т.к. алгоритмами пользовался только на учебе в вузе на с++ несколько лет назад )
@@frontendscience спб upd: довольно странно собеситься по телефону с hr, она задавала вопросы по реакту, а я не понимал, что она хочет, как оказалось мне нужно было объяснить как из дочернего элемента изменять стейт родительского (ее формулировку я, к сожалению, не запомнил) Кстати отправил вам заявку на паблик интервью, буду надеяться, что услышимся когда-нибудь!
В вебшторме при клике на файл второй кнопкой есть команда run - это запустить выполнение этого js-файла с помощью node js. Откроется соответствующая вкладка внизу.
Здравствуйте Сергей, очень нужна ваша помощь, дело в том что я уже в комментах написал проблему, но ютуб удалил коммент.Может мне на инст прислать проблему?или какой либо другой мессенджер
я не посмотрел еще решение, но я решил просто нарезать данный массив на двухмерный и найти сумму всех нулей, расположенных между единицами :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]--;
Задача красивая, спору нет. Алгоритмы решения и реализацию сам придумал? Или немножко где-то подсмотрел, видел похожее? Как то с трудом верится, что такое решение можно найти самому, даже имея приличный опыт)
Ищем левый положительный элемент и правый положительный элемент, считаем количество нулей между ними. Потом отнимаем 1 от всех элементов и снова считаем левый и правый и нули между ними и т.д. То есть считаем замкнутые нули по слоям.
привет! ютюб удаляет все комменты со ссылками. По твоему вопросу - у тебя ошибка в коде - ты поставил return total; внутри while - получилось что на первой же итерации ты вернул ответ из функции и не пошел дальше. return total должен быть после того как while отработает
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)
Уверен что решение не очень (да и навело на меня решение другой задачи, про сушу), но на всякий случай прикреплю, интересно) 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) { 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^2). Так как есть внешний цикл for который идет по всем элементам (в худшем случае максимум будет на самом последнем элементе), а потом внутри есть еще один цикл forEach. Поэтому это решение на литкод выдает: Time Limit Exceeded. Он хочет более оптимальный вариант по времени.
Привет, решил попробовать сделать задачу по твоем первому алгоритму решения, по тестам которые в видео вроде как прошло, но хотелось бы услышать твой фидбэк)) const trap = (height) => { let sum = 0; let maxLeftArr = []; let maxRightArr = []; let maxleftNum = 0; let maxRightNum = 0; let volume = []; for (let i = 0; i < height.length; i++) { if (height[i] < height[i - 1] && height[i - 1] > maxleftNum) { maxleftNum = height[i - 1]; maxLeftArr.push(maxleftNum); } else { maxLeftArr.push(maxleftNum); } } for (let i = height.length - 1; i >= 0; i--) { if (height[i + 1] > maxRightNum) { maxRightNum = height[i + 1]; maxRightArr.push(maxRightNum); } else { maxRightArr.push(maxRightNum); } } maxRightArr.reverse(); for (let i = 0; i < maxLeftArr.length; i++) { volume.push(Math.min(maxLeftArr[i], maxRightArr[i])); } for (let i = 0; i < height.length; i++) { if (volume[i] - height[i] > 0) { sum += volume[i] - height[i]; } } return sum; }; trap(arr1);
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
Кое-что поправил и прошло. 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.
Андрей, я вижу нотификации, но самих комментариев нет и не могу посмотреть до конца даже сообщения. Ютуб удаляет все комменты сл ссылками. Но я так понимаю, что вы просто решение уже высылаете. И его я тоже не вижу. Почему-то ютуб трет эти комменты. Может, увидел большую активность, чем всегда, не знаю… попробуйте выслать номер id пользователя на кодпене и id самого пена. Без полной ссылки
Уфф, це була потна катка)) 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); // Рахуємо клітинки з водою }
о, что то новое уже на просторах ютуба, с графическим объяснениям это просто бомба!
Благодарим за поддержку! Рады, что понравилось!
Прикольно что на литкоде есть тесты с огромными массивами. Типа решил задачу, а оказывается еще решать и решать. :)
Спасибо за видео, очень крутой формат!
задача классная, ну а ваше графическое объяснение просто топ! спасибо)))
Благодарю) Рад, что понравилось!
Решил по-другому. Всю эту гористую местность разбил на уровни снизу вверх. И на каждом уровне просчитал количество воды. А те крайние выемки для воды, которые не ограждены стеной слева и справа - вычитаем. Такое решение мне кажется проще в понимании :)
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));
этот канал по всей логике уже давно должен быть миллионником, ну или скоро будет
Класс! Пусть так и будет! :)
Спасибо за интересную задачу! Моё решение получилось далеко не оптимальным (почему-то не учитывал, что массив 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;
};
Спасибо, такое интересное решение, действительно очень компактно, а я решила очень громоздко.
Годнота! Однозначно лайк и подписка!)
Благодарю за поддержку! ;) приветствую!
Однозначно подписка. Спасибо автору❤️
Благодарим! Рады Вам! :)
Всегда смотрю как вы решаете и понимаю, что в лоб лучше не решать, а подумать о сложности ахах, но всё же может кому-то будет интересно. 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
Супер, спасибо!!!!
И Вам спасибо за поддержку!
Привет, спасибо за качественный контент) Вот мой варик :
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;
}
Эту задачу уровня 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%
Спасибо, задачка супер -- проста в условиях, сложна в решении!
Денёк пришлось помозговать.. теперь пойду смотреть Ваше решение, наверняка оно легче!)
А мой первый сабмишн таков:
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);
}
};
ВОУ!!! Круто, что сам дошел до решения!!!
Очень качественный контент, спасибо, готовлюсь к собеседованию по твоим видосам😎
Рад, что полезно! Успехов!
Как идея для видео, можете запилить ролик, план развития js разработчика, ну или фронт енд, ну или что-то в этом роде, хотя думаю у вас там и так куча идей:)
Лайк, однозначно
Благодарим за поддержку!
Какая интересная задача, хоть и простая. Спасибо!
Я почему-то про интегрирование (дискретное) сразу подумал, т.е.площадь удава, который съел слона и похож на шляпу, посчитать, а потом вычесть..
Очень интересно, благодарю!
Моё решение получилось раза в 2-3 длиннее, а самое интересное, сколько разных вариантов решения предлагают люди!
Супер. Спасибо
Есть ещё один способ решить эту задачу за линейное время и константную память. Нужно найти самый большой элемент и его индекс (любой наибольший эл-т если их больше одного) и пройтись циклом слева, на каждой итерации обновляя максимальную высоту слева и высчитывая объем в клетке(так как мы уже знаем максимум с обоих сторон). Потом сделать то же самое, только справа. Мне это решение показалось проще, чем с указателями
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 а по памяти пятиконстантная как минимум)
while (left
Как раз таки эта реализация требует
Можно ещё так :)
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 Да, перепроверил своё решение. Во-первых сам себе трудностей создал по переводу массива в строку и обратно (хоть так тоже работает с входными данными из видео). Во-вторых, такой подход (с делением массива на два и проверке максимального числа в каждом) не пройдёт при большой длине массива. Поторопился, в общем :)
Сергей, скажите, пожалуйста, а часто ли на собеседованиях на джуна фронтендера спрашивают алгоритмы и структуры и хезмаст ли для джуна хорошо в них разбираться?
Upd: спасибо за ваши старания! до вас даже не слышал о таком понятии как сложность алгоритма)
Вообще нет, но в яндекс нужно знать например, у меня были задачи на stack и указатели. В faang тоже нужно
Благодарю, очень рад.
Про алгоритмы и структуры данных, как уже написали, все зависит от компании. В основном джунов такое не спрашиваю, начинают примерно от миддла. Но компании по типу Google, Яндекс и пр. даже на уровне джунов требуют такие знания.
@@frontendscience Спасибо за ответ, просто недавно созрел для поиска первой работы, на первых двух собесах меня спросили про это hr, тут я и удивился и не был готов к такому, т.к. алгоритмами пользовался только на учебе в вузе на с++ несколько лет назад )
@@Nikita-gn4bg странно что hr такое спрашивал. А что за город?
@@frontendscience спб
upd: довольно странно собеситься по телефону с hr, она задавала вопросы по реакту, а я не понимал, что она хочет, как оказалось мне нужно было объяснить как из дочернего элемента изменять стейт родительского (ее формулировку я, к сожалению, не запомнил)
Кстати отправил вам заявку на паблик интервью, буду надеяться, что услышимся когда-нибудь!
Будет видео о проектах для обучения?
Будет!
Приятного просмотра: ua-cam.com/video/0ue4Z3W0x60/v-deo.html
Как открыть терминал как у вас,внизу,что бы можна было проверять работу кода?
В вебшторме при клике на файл второй кнопкой есть команда run - это запустить выполнение этого js-файла с помощью node js. Откроется соответствующая вкладка внизу.
@@frontendscience Можна ли при помощи Vs code это зделать?
@@vasiajulia4173 уверен, что можно, но не подскажу как, т.к. с VScode не работал
@@frontendscience Спасибо , я постараюсь разобраться,пока просто пишу код как у вас и пытаюсь вникать в суть)
@@vasiajulia4173 успехов! Это хорошо, что Вы тренируетесь.
Оба варианта очень крутые, но второй все таки круче даже просто потому что он короче) JS Frontend Backend Задачи Собеседование React
Ценю твою поддержку)
Здравствуйте Сергей, очень нужна ваша помощь, дело в том что я уже в комментах написал проблему, но ютуб удалил коммент.Может мне на инст прислать проблему?или какой либо другой мессенджер
Не вопрос, конечно, пиши в инст или на почту
я не посмотрел еще решение, но я решил просто нарезать данный массив на двухмерный и найти сумму всех нулей, расположенных между единицами :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));
Что за графический редактор?
Это online сервис excalidraw
like
Дякую
Задача красивая, спору нет.
Алгоритмы решения и реализацию сам придумал? Или немножко где-то подсмотрел, видел похожее?
Как то с трудом верится, что такое решение можно найти самому, даже имея приличный опыт)
Как раз-таки опыт решает, особенно, если подобные задачи уже были решены до этого. А на этом канале они есть.
У меня только 1 вопрос почему здесь дизлайк? Всё понятно и ясно.
Кто вообще придумал спрашивать задачи с Leetcode на собеседованиях. Вопрос конечно риторический.
Ищем левый положительный элемент и правый положительный элемент, считаем количество нулей между ними. Потом отнимаем 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));
моща. спс
))))) нзчт
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 а как можно попасть на собеседование к вам?
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
}
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
}
Уверен что решение не очень (да и навело на меня решение другой задачи, про сушу), но на всякий случай прикреплю, интересно)
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 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
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)
}
Отлично вышло! Благодарю за решение
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)
Вот моё решение:
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
Благодарю за ответ.
Привет, решил попробовать сделать задачу по твоем первому алгоритму решения, по тестам которые в видео вроде как прошло, но хотелось бы услышать твой фидбэк))
const trap = (height) => {
let sum = 0;
let maxLeftArr = [];
let maxRightArr = [];
let maxleftNum = 0;
let maxRightNum = 0;
let volume = [];
for (let i = 0; i < height.length; i++) {
if (height[i] < height[i - 1] && height[i - 1] > maxleftNum) {
maxleftNum = height[i - 1];
maxLeftArr.push(maxleftNum);
} else {
maxLeftArr.push(maxleftNum);
}
}
for (let i = height.length - 1; i >= 0; i--) {
if (height[i + 1] > maxRightNum) {
maxRightNum = height[i + 1];
maxRightArr.push(maxRightNum);
} else {
maxRightArr.push(maxRightNum);
}
}
maxRightArr.reverse();
for (let i = 0; i < maxLeftArr.length; i++) {
volume.push(Math.min(maxLeftArr[i], maxRightArr[i]));
}
for (let i = 0; i < height.length; i++) {
if (volume[i] - height[i] > 0) {
sum += volume[i] - height[i];
}
}
return sum;
};
trap(arr1);
ссылки на 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
Не могу понять откуда он эти цифры берёт.
Дааа. Вторым способом намного легче и быстрее
Потому что он знает, как рассчитывают сложность алгоритмов по BigO.)
ua-cam.com/video/Fu4BzQNN0Qs/v-deo.html
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
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])
}
Классно! Благодарю что поделился!
уж лучше собирать дождевую воду чем собираться на пенсию в 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); // Рахуємо клітинки з водою
}