Спасибо за интересную задачу! В собственном решении я немного заморочился с иммутабельностью, поэтому преобразовал grid в матрицу объектов. Обход всех вершин графа (ячеек острова) тоже реализовал через рекурсию, но для соблюдения принципа DRY добавил абстракцию массива векторов. Попадание координат в границы матрицы проверял выражением: map[y]?.hasOwnProperty(x), что эквивалентно двойному условию: map[y] && x in map[y]. Вот, что получилось: const numIslands = grid => { const map = Array.from(Array(grid.length), (_, y) => grid[y].map((v, x) => ({ x: x, y: y, visitable: v === '1', }))); function traversal(entrance, map) { entrance.visitable = false; const directions = [ {x: 1, y: 0}, // right {x: 0, y: 1}, // down {x: -1, y: 0}, // left {x: 0, y: -1}, // up ]; for (const vector of directions) { const x = entrance.x + vector.x; const y = entrance.y + vector.y; if (map[y]?.hasOwnProperty(x) && map[y][x].visitable) { traversal(map[y][x], map); } } } let counter = 0; for (const row of map) { for (const cell of row) { if (cell.visitable) { counter++; traversal(cell, map); } } } return counter; };
офигеть, как круто) 2 часа потратил на алгоритмы, но так и не придумал, как это правильно реализовать. Пробовал сбор индексов непустых элементов, а потом их сравнение, но вылезли нюансы. Оказалось нужно поменять исходный массив и применить рекурсию) Спасибо за опыт, это реально пригодится)
Классно что сам вначале пытался решить! Восхищаюсь твоим упорством! Менять исходный массив тут прямо обязательности нету - можно и копию сделать. Но тогда сложность по памяти вырастет.
@@frontendscience проблемы оптимизации для меня актуальны. Потому очень рад, что нашел твой канал. Спасибо тебе за труд. Хорошие алгоритмы всегда пригодятся)
А Вы более разумного применения своему времени, чем писать 100500 комментов о том, что Вы не поняли решения? Например, чтоб разобраться, почему там таки должна быть рекурсия.
@Михаил Михайлов Я считаю, что как минимум за тон. На адекватные вопросы я всегда отвечаю с охотой - и с удовольствием делюсь своим временем, чтоб помочь тому, кто реально что-то старается понять и растет. А Вы обратите внимания за Ваши комментарии и сделайте выводы.
Сергей, надеюсь увидете этот комментарий. У меня на собесе была задачка, до сих пор не могу придумать как ее решить - может быть разберете в следующих видео? У нас есть матрица неизвестного размера - это фото местности где каждое число в матрице высота над уровнем моря. Нужно найти самый эфективный путь марсоходу из верхней левой точки в правую нижнюю. Каждый шаг стоит 1 единицу топлива. Также разница между высотами это топливо на спуск или подъем. Бывают недостижимые точки они обозначаются как Х. А САМОЕ СЛОЖНОЕ - первый шаг по диагонали стоит как обычный - единицу, второй в два раза больше, третий в два раза и так далее. Без диагональных премудростей Дейкстрой все считается, все супер. Главное граф из матрицы сделать и все гуд. Но вот диагонали - не пойму как с рими разобраться.
если всю задачу решили и проблема только с учетом диагонального перемещения, то могу предложить завести под это отдельную переменную. ну или я не понял в чем у вас проблема
@@thomasgabe3588 проблема в том что граф с каждым шагом меняется, для неизменного графа существуют готовые решения, но как их скомбинировать с постоянно изменяющимся я не знаю. я ведь имею матрицу - делаю граф по правилам шагов в виде объекта - и только потом прохожусь алгоритмом по нему. а если он после первого шага изменился - тогда нет смысла пробегаться по первой версии, нужна уже вторая версия графа, на следующем шаге - снова новая версия графа - и при этом нужно учесть все возможные варианты ходов. по диагонали ведь можно пойти из каждой точки в графе. если у вас есть решение - предложите плз - буду благодарен. я совсем не секу
Привет! Это на какую должность тебе такую задачу задали 🤯? Из идей которые есть: попробуй представить диагональ как ещё одно ребро в графе. То-есть выйдет плюс несколько рёбер везде.
Жесть.. сложная фигня какая-та)) Посмотрев , пришла мысль бросить занятие фронтом.. Бо если мне бы такое попросили сделать, у меня бы 100% не вышло((( мде.. вот те и войти в ит(( . Спасибо за классный видос
брат, можно не проверять клетки слева и сверху, ибо так как мы идём начиная с первой строчки и с первого столбца, то мы клетку сверху и слева уже проверяли до этого, и если в ней была 1 то и текущую клетку мы пометили как пройденную. чутка быстрее алгоритм получится
Задача классная, но я не увидел необходимости помечать шестерками другие единицы. Мое решение заключается в том, чтобы проверять предыдущие числа по горизонтали и по вертикали. То есть, если grid[R][C] === "1" и grid[R - 1][C] === "0" и grid[R][C - 1] === "0", это означает что наша единица - начало нового острова. И тогда мы увеличиваем counter. В противном случае (если перед ней или над ней тоже единица) она является продолжением уже посчитанного острова. Вот так это выглядит: const countIslands = (matrix) => { let total = 0; if (matrix.length === 0) return 0; for (let row = 0; row < matrix.length; row += 1) { for (let index = 0; index < matrix[row].length; index += 1) { const current = matrix[row][index]; if (current === 1) { const prevRowValue = matrix[row - 1] ? matrix[row - 1][index] : 0; const prevIndexValue = matrix[row][index - 1] ? matrix[row][index - 1] : 0; if (prevRowValue === 0 && prevIndexValue === 0) { total += 1; } } } } return total; };
@@frontendscience Да. Но в любом случае, если единица является продолжением острова, то либо слева, либо сверху тоже будет единица. Даже в случае со змейкой. Именно такие случаи я и проверяю, так что мое решение отработает корректно.
@@frontendscience мы же попадаем сразу на первый элемент первой строки, и относительно этого элемента, слева нет ничего, и если будет массив [0,0,0,0,0,1] - то тут справа ничего не будет.
@@frontendscience В целом как задачи для алгоритма, я с вами частично согласен, но зайдя на leetcode и проверив 2 кейса, с копированием и без, могу сказать, что разница в 1.4% по памяти не нарушила ничего в условии задачи)
@@ihor-pidhornyi то что на литкод сами тест кейсы не всегда «большие», известный факт. Вопрос в том что тут не нужно делать копию массива. Это сендбокс, это конкретная задача, и копирование тут излишне. ПС: в продашен коде никто конечно мутировать массив не будет!
@@frontendscience Иммутабельность объектов переданных в функцию всё таки считается хорошей практикой (даже для решения задачек). Незначительное увеличение сложности алгоритма по памяти - не критично. А при больших тест-кейсах, где габариты острова будут исчислятся десятками тысяч, у нас может возникникать совершенно другая проблема: переполнение стека вызовов рекурсивной функции.
Классное видео, спасибо! Есть вопрос, сколько по времени нормально будет решать подобную задачку для мидла? Или уровнем easy. Спрашиваю потому, что недавно решала задачи на собеседовании и каждая заняла от 10 до 15 минут - и не понимаю, это было нормально или надо быстрее соображать))
Для медиум задачи 10-15 мин ок, для изи уровня стараться 5-10 мин (они тоже бывают разные по сложности). Если решать много задач на подготовке, то очень быстро на собеседовании сможешь определиться с самим алгоритмом и тогда времени на решение будет уходить в разы меньше.
Перебор массива осуществляется не из рандомной позиции, поэтому в следующих проверках markNeighbours нет необходимости: if (binaryMatrix?.[R-1]?.[C] === '1') { markNeighbours(binaryMatrix, R-1,C)} if (binaryMatrix[R][C-1] === '1') { markNeighbours(binaryMatrix, R,C-1)} Ко всему код можно было бы оптимизировать. Сейчас он проходится по тем элементам, которые были помечены "6"
Убрать эти строки нельзя! В тех простейших случаях что я показал в видео, да это бы сработало. Но вот 2 тест кейса когда без этих строк будет не верный ответ: [["1","1","1"],["0","1","0"],["1","1","1"]] //Output 2 Expected 1 [["1","0","1","1","1"],["1","0","1","0","1"],["1","1","1","0","1"]] //Output 2 Expected 1 По поводу прохода уже посещенных ячеек - эта оптимизация не даст улучшения общей сложности O(n*m). Но вот код значительно усложнит - поэтому не рекомендую оверинжинирить на собеседованиях с такими оптимизациями.
Да верно. optional changing туда стоит добавить. С другой стороны, на leetcode по условию не может быть пустого массива. Так что 39ю строку вообще можно выкинуть.
Мне кажется можно добиться более оптимального решения. Я прохожу по каждой ячейке матрицы, если она единица, то if (верхняя и левая ячейки === 0 или === undefined), то мы считаем остров. Если условие нарушается, то этот остров уже был посчитан. Это решение без доп.рекурсивной функции, поэтому мы не столкнемся с возможными проблемами переполнения стека вызова функ.
Вы уверены, что предложенный алгоритм будет работать с непрямоугольными островами, а зигзагами или вот такой формы? [["1","1","1"],["0","1","0"],["1","1","1"]]
В строчках 43 и 44 нужно было так же сделать как и в 45 и 46, потому что если мы проверяем 0вой элемент в массиве то левый сосед будет последний элемент, который может быть отдельным островом, для последнего элемента так же. Или я ошибаюсь?
Спасибо за видео! Есть вопрос, пытался прогнать код в VS, в консоли в браузере выдает Unexpected token '.', ругаясь на 43 строку binaryMatrix?.[R-1]?.[C] === '1' UPD: гуглил, понял, что это за оператор, но при всем, пока не понимаю, как устранить ошибку
Скорее всего в vscode выбрана для запуска старая версия ноды. Я не спец по vscode так что не подскажу как там поставить посвежее чтобы поддерживал этот оператор. Если что в последних версиях хрома все отлично работает. Можно там запустить
у нас один цикл проходит по всем строкам, а второй по всем столбцам вот и выходит O(n*m). Квадратичная сложность получается когда у нас оба цикла проходятся по всем элементам.
@@frontendscience но количество операций будет зависеть от размера массива как n * n, т. е. n2? Проход по столбцу подразумевает же перебор элементов столбца? Интересно узнать.
n*m - это количество всех элементов в нашей матрице. ты просто итерируемся по всем элементам матрицы. В худшем случае у нас например когда все элементы матрицы единицы. тогда на первой же итерации наших циклов мы зайдем на остров(первый элемент с 1) и еще раз пройдем все наши элементы массива в рекурсии - но сделаем это только один раз, на всех других итерациях цикла у нас уже будут помечены ячейки 6ками - и мы в рекурсивную функцию заходить не будем. так что результирующая сложность останется O(n*m)
хоть я и питонист, но разве так же с колонкой не надо делать проверку, как со строкой?) Т.к. можно стоять на 0:0 и искать в C-1 (-1). Ну а решал бы так же, но при этом я бы отправлял координаты в отдельный список, а не заменял 6ками. Так бы у меня в будущем были вариации по расширению ;)
На литкод по умолчанию есть требование решить задачу не только наиболее оптимальным способом по времени, но и по памяти. Поэтому делается мутация. Это не продакшен код. А решение задачи с заданными условиями в сендбоксе.
Атятя, мутируете матрицу, нехорошо! с: На самом деле, не обязательно смотреть соседа сверху и слева, если представить сушу в матрице в виде бинарного дерева и производить глубокий обход исходя из этого, тогда достаточно смотреть только нижний и правый элемент матрицы! По крайней мере, я так мыслил, когда решал задачу
Атятя! Условия не читаем, сразу пишем коммент. И по второму пункту - не выйдет так. Острова могут быть любой формы, не обязательно прямоугольные. В том числе змейкой.
@@frontendscience насчет условия, не совсем понял. Мутация матрицы ведь необязательна, если использовать, например, мапу или объект для хранения пройденных ячеек (доступ к элементу в таком случае будет О(1))? Если я ошибаюсь, то поправьте пожалуйста
@@DevilAlex03 Все верно, но на leetcode во всех задачах есть есть еще условие реализовать алгоритм как можно более оптимальней и по памяти. Именно поэтому без надобности никто не делаем копию массива и жертвует мутацией в угоду памяти. Это не продакшен эвайромент а именно вот такой сендбокс со своими условиями.
Оптимизировать можно. Специально этого не делал дабы не усложнять понимание кода. А на общую итоговую сложность по времени это никак не влияет. Это просто вопрос уменьшения копипаста. Во всех задачах я стараюсь делать так, чтоб люди максимально легко поняли.
Благодарю за решение. К сожалению что-то пошло не так и выдает не верный ответ на вот таком кейсе: [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]] Output 0 Expected 1
Помойму проще в процессе перебора массива сравнивать с массивом отметок все соседние элементы и если они помечены как остров то не защитовать новый остров, а если не помечены то добавлять новый остров. Сложно в разы меньше все 1 проход по массиву в сравнением с представленным вариантом
Бомба, а не видео!!! Спасибо большое. Наконец-то дошло до меня как работает этот алгоритм.
Рад что было полезно!
Мне нравится, что все очень понятно и темы интересные . Мне было интересно как подобные обходы строятся. Рекурсия в дополнительной функции очень круто
Спасибо за интересную задачу!
В собственном решении я немного заморочился с иммутабельностью, поэтому преобразовал grid в матрицу объектов. Обход всех вершин графа (ячеек острова) тоже реализовал через рекурсию, но для соблюдения принципа DRY добавил абстракцию массива векторов. Попадание координат в границы матрицы проверял выражением: map[y]?.hasOwnProperty(x), что эквивалентно двойному условию: map[y] && x in map[y].
Вот, что получилось:
const numIslands = grid => {
const map = Array.from(Array(grid.length), (_, y) => grid[y].map((v, x) => ({
x: x,
y: y,
visitable: v === '1',
})));
function traversal(entrance, map) {
entrance.visitable = false;
const directions = [
{x: 1, y: 0}, // right
{x: 0, y: 1}, // down
{x: -1, y: 0}, // left
{x: 0, y: -1}, // up
];
for (const vector of directions) {
const x = entrance.x + vector.x;
const y = entrance.y + vector.y;
if (map[y]?.hasOwnProperty(x) && map[y][x].visitable) {
traversal(map[y][x], map);
}
}
}
let counter = 0;
for (const row of map) {
for (const cell of row) {
if (cell.visitable) {
counter++;
traversal(cell, map);
}
}
}
return counter;
};
Сам не смог решить, всё пытался какие-то схемы придумать, а оказалось так просто. Спасибо за разбор!
Рад что было полезно!
Юухуууу. Вот и разбор новой задачки!!! Респект!
Довольно простая задача, особенно если можно изменять исходный массив:
function numIslands(grid) {
let counter = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === "1") {
paint(i, j);
counter++;
}
}
}
function paint(r, c) {
grid[r][c] = "2";
if (grid[r - 1]?.[c] === "1") paint(r - 1, c);
if (grid[r][c + 1] === "1") paint(r, c + 1);
if (grid[r + 1]?.[c] === "1") paint(r + 1, c);
if (grid[r][c - 1] === "1") paint(r, c - 1);
}
return counter;
}
Спасибо за контент с задачами! Очень интересно и познавательно!
Рад, что было полезно! Благодарю за поддержку!
Счастлив что нашел Ваш канал!! Js react node задачи собеседование IT full stack frontend backend
Супер! Рад это слышать! Очень вдохновляют такие комментарии! Успехов, друг!
офигеть, как круто) 2 часа потратил на алгоритмы, но так и не придумал, как это правильно реализовать. Пробовал сбор индексов непустых элементов, а потом их сравнение, но вылезли нюансы. Оказалось нужно поменять исходный массив и применить рекурсию) Спасибо за опыт, это реально пригодится)
Классно что сам вначале пытался решить! Восхищаюсь твоим упорством!
Менять исходный массив тут прямо обязательности нету - можно и копию сделать. Но тогда сложность по памяти вырастет.
@@frontendscience проблемы оптимизации для меня актуальны. Потому очень рад, что нашел твой канал. Спасибо тебе за труд. Хорошие алгоритмы всегда пригодятся)
А Вы более разумного применения своему времени, чем писать 100500 комментов о том, что Вы не поняли решения? Например, чтоб разобраться, почему там таки должна быть рекурсия.
@@frontendscience ну куда ж без хейтеров? :)
@Михаил Михайлов Я считаю, что как минимум за тон. На адекватные вопросы я всегда отвечаю с охотой - и с удовольствием делюсь своим временем, чтоб помочь тому, кто реально что-то старается понять и растет. А Вы обратите внимания за Ваши комментарии и сделайте выводы.
Благодарю!
Спасибо друг! Помог решить задачу!
Афигенно объяснение!!!❤ Спасибо
Круто: доступно и понятно.
Рад, что было полезно
В голову пришло только топить острова клетка за клеткой.. не оптимально, конечно, но прокатило! :)
Runtime: 92 ms, faster than 56.10% of JavaScript online submissions for Number of Islands.
Memory Usage: 42.7 MB, less than 34.10% of JavaScript online submissions for Number of Islands.
var numIslands = function (grid) {
const lenY = grid.length;
const lenX = grid[0].length;
var total = 0;
var y = 0;
var x = 0;
while (y < lenY) {
if (grid[y][x] == '1') {
collapseIsland(y, x);
total++;
nextTile(2);
} else {
nextTile(1);
}
}
return total;
function collapseIsland(yy, xx) {
grid[yy][xx] = '0';
if (grid[yy + 1] && grid[yy + 1][xx] == '1') {
grid[yy + 1][xx] = '0';
collapseIsland(yy + 1, xx);
}
if (grid[yy][xx + 1] && grid[yy][xx + 1] == '1') {
grid[yy][xx + 1] = '0';
collapseIsland(yy, xx + 1);
}
if (grid[yy][xx - 1] && grid[yy][xx - 1] == '1') {
grid[yy][xx - 1] = '0';
collapseIsland(yy, xx - 1);
}
if (grid[yy - 1] && grid[yy - 1][xx] == '1') {
grid[yy - 1][xx] = '0';
collapseIsland(yy - 1, xx);
}
}
function nextTile(step) {
if (x >= lenX - step) {
x = 0;
y++;
} else {
x += step;
}
}
};
Благодарю за решение!
"Все острова успешно затоплены!" :)
😁🏴☠️
Сергей, надеюсь увидете этот комментарий. У меня на собесе была задачка, до сих пор не могу придумать как ее решить - может быть разберете в следующих видео?
У нас есть матрица неизвестного размера - это фото местности где каждое число в матрице высота над уровнем моря. Нужно найти самый эфективный путь марсоходу из верхней левой точки в правую нижнюю. Каждый шаг стоит 1 единицу топлива. Также разница между высотами это топливо на спуск или подъем. Бывают недостижимые точки они обозначаются как Х. А САМОЕ СЛОЖНОЕ - первый шаг по диагонали стоит как обычный - единицу, второй в два раза больше, третий в два раза и так далее.
Без диагональных премудростей Дейкстрой все считается, все супер. Главное граф из матрицы сделать и все гуд.
Но вот диагонали - не пойму как с рими разобраться.
Пример
01
25
Из нуля в двойку - 3 единицы топлива = 1 + разница высот два минус ноль
Капец задачка, ты там не в NASA устраиваешся, чтобы марсоходами управлять?
если всю задачу решили и проблема только с учетом диагонального перемещения, то могу предложить завести под это отдельную переменную. ну или я не понял в чем у вас проблема
@@thomasgabe3588 проблема в том что граф с каждым шагом меняется, для неизменного графа существуют готовые решения, но как их скомбинировать с постоянно изменяющимся я не знаю.
я ведь имею матрицу - делаю граф по правилам шагов в виде объекта - и только потом прохожусь алгоритмом по нему. а если он после первого шага изменился - тогда нет смысла пробегаться по первой версии, нужна уже вторая версия графа, на следующем шаге - снова новая версия графа - и при этом нужно учесть все возможные варианты ходов.
по диагонали ведь можно пойти из каждой точки в графе.
если у вас есть решение - предложите плз - буду благодарен.
я совсем не секу
Привет! Это на какую должность тебе такую задачу задали 🤯?
Из идей которые есть: попробуй представить диагональ как ещё одно ребро в графе. То-есть выйдет плюс несколько рёбер везде.
Спасибо большое
Сразу лайк
Благодарю :)
Жесть.. сложная фигня какая-та)) Посмотрев , пришла мысль бросить занятие фронтом.. Бо если мне бы такое попросили сделать, у меня бы 100% не вышло((( мде.. вот те и войти в ит(( . Спасибо за классный видос
Да тебе лишь бы руки опустить. Данная задача на уровень middle/senior (и то в каком-нибудь яндексе), но точно не на начинающего или джуниора.
@@Сергей-у6и7б А ну если не на начинающего то норм.
не бросили фронт по итогу?)
@@МаксимСоловьев-с9н Нет.. Работу найти сейчас не могу но уже есть опыт и на фрилансе по немногу делаю по мелочи
здорово!)
Невнимательно прочитал задание. ПОдумал, что это питон. Подумал сколько всего интересного я еще не знаю. Увидел JS - Выдохнул... =)
брат, можно не проверять клетки слева и сверху, ибо так как мы идём начиная с первой строчки и с первого столбца, то мы клетку сверху и слева уже проверяли до этого, и если в ней была 1 то и текущую клетку мы пометили как пройденную. чутка быстрее алгоритм получится
Спасибо большое за контент
Рад, что понравилось!
можно узнать, где вы делаете картинки к видео, как на 7:40 правый нижний угол?
excalidraw.com
@@frontendscience спасибо большое
Задача классная, но я не увидел необходимости помечать шестерками другие единицы. Мое решение заключается в том, чтобы проверять предыдущие числа по горизонтали и по вертикали. То есть, если grid[R][C] === "1" и grid[R - 1][C] === "0" и grid[R][C - 1] === "0", это означает что наша единица - начало нового острова. И тогда мы увеличиваем counter. В противном случае (если перед ней или над ней тоже единица) она является продолжением уже посчитанного острова.
Вот так это выглядит:
const countIslands = (matrix) => {
let total = 0;
if (matrix.length === 0) return 0;
for (let row = 0; row < matrix.length; row += 1) {
for (let index = 0; index < matrix[row].length; index += 1) {
const current = matrix[row][index];
if (current === 1) {
const prevRowValue = matrix[row - 1] ? matrix[row - 1][index] : 0;
const prevIndexValue = matrix[row][index - 1] ? matrix[row][index - 1] : 0;
if (prevRowValue === 0 && prevIndexValue === 0) {
total += 1;
}
}
}
}
return total;
};
Дело в том что острова могут быть не только прямоугольными. Например он может быть «змейкой».
@@frontendscience Да. Но в любом случае, если единица является продолжением острова, то либо слева, либо сверху тоже будет единица. Даже в случае со змейкой. Именно такие случаи я и проверяю, так что мое решение отработает корректно.
@@ВениаминТрепачко К сожалению твой код выдает не верный ответ даже на простейших случаях: input [["1","1","1","1","0"]] output: 0, Expected: 1
@@smashno Тут проблема исключительно в том, что вы используете массив строк, а я массив чисел 🙂Но логически ведь всё верно
@@ВениаминТрепачко Логически тоже не верно (если преобразовать строки в числа):
Input [["1","1","1"],["0","1","0"],["1","1","1"]]
Output: 2
Expected: 1
а проверку на существование елемента массива слева и справа не нужно(как в случае с сверху и снизу)?
Она есть ) даже ячейки специально в анимации подсвечены когда это делали.
@@frontendscience да не, я про grid.?[R].?[C-1]==='1' - вот так делать не нужно? (.?)
@@frontendscience мы же попадаем сразу на первый элемент первой строки, и относительно этого элемента, слева нет ничего, и если будет массив [0,0,0,0,0,1] - то тут справа ничего не будет.
разобрался) избыточное условие будет, можно и не писать
А я теперь понял изначальный вопрос )
Не могу понять почему мы в случае колонок не делаем проверку и при этом не вываливаемся за границы массива?
У нас есть проверка :) внутри if если мы обращаемся к несуществующей ячейке то получаем undefined. А он внутри if приводится к false
Классное решение, но я бы добавил создание копии массива)
Это увеличит сложность алгоритма по памяти, что идет в разрез с условиями задачи.
@@frontendscience В целом как задачи для алгоритма, я с вами частично согласен, но зайдя на leetcode и проверив 2 кейса, с копированием и без, могу сказать, что разница в 1.4% по памяти не нарушила ничего в условии задачи)
@@ihor-pidhornyi то что на литкод сами тест кейсы не всегда «большие», известный факт. Вопрос в том что тут не нужно делать копию массива. Это сендбокс, это конкретная задача, и копирование тут излишне. ПС: в продашен коде никто конечно мутировать массив не будет!
@@frontendscience Воот, выражения про прод мне не хватало😅😅😅
@@frontendscience Иммутабельность объектов переданных в функцию всё таки считается хорошей практикой (даже для решения задачек). Незначительное увеличение сложности алгоритма по памяти - не критично. А при больших тест-кейсах, где габариты острова будут исчислятся десятками тысяч, у нас может возникникать совершенно другая проблема: переполнение стека вызовов рекурсивной функции.
Классное видео, спасибо! Есть вопрос, сколько по времени нормально будет решать подобную задачку для мидла? Или уровнем easy. Спрашиваю потому, что недавно решала задачи на собеседовании и каждая заняла от 10 до 15 минут - и не понимаю, это было нормально или надо быстрее соображать))
Для медиум задачи 10-15 мин ок, для изи уровня стараться 5-10 мин (они тоже бывают разные по сложности). Если решать много задач на подготовке, то очень быстро на собеседовании сможешь определиться с самим алгоритмом и тогда времени на решение будет уходить в разы меньше.
Перебор массива осуществляется не из рандомной позиции,
поэтому в следующих проверках markNeighbours нет необходимости:
if (binaryMatrix?.[R-1]?.[C] === '1') { markNeighbours(binaryMatrix, R-1,C)}
if (binaryMatrix[R][C-1] === '1') { markNeighbours(binaryMatrix, R,C-1)}
Ко всему код можно было бы оптимизировать.
Сейчас он проходится по тем элементам, которые были помечены "6"
Убрать эти строки нельзя! В тех простейших случаях что я показал в видео, да это бы сработало. Но вот 2 тест кейса когда без этих строк будет не верный ответ:
[["1","1","1"],["0","1","0"],["1","1","1"]] //Output 2 Expected 1
[["1","0","1","1","1"],["1","0","1","0","1"],["1","1","1","0","1"]] //Output 2 Expected 1
По поводу прохода уже посещенных ячеек - эта оптимизация не даст улучшения общей сложности O(n*m). Но вот код значительно усложнит - поэтому не рекомендую оверинжинирить на собеседованиях с такими оптимизациями.
@@frontendscience Ok. Не рассматривал такой кейс.
@@frontendscience тоже хотел написать насчёт этого. Спасиба за такие примеры, сходу не самые очевидные
В 38 строке надо добавить optional changing либо перенести эту строку под первый if, иначе будет ошибка в случае с пустой матрицей
Да верно. optional changing туда стоит добавить. С другой стороны, на leetcode по условию не может быть пустого массива. Так что 39ю строку вообще можно выкинуть.
2:42 а если один массив будет больше чем grid[0].length ?что тогда?
В условии нашей задачи этого быть не может - у нас прямоугольная "карта"
@@frontendscience ок :)
Мне кажется можно добиться более оптимального решения.
Я прохожу по каждой ячейке матрицы, если она единица, то if (верхняя и левая ячейки === 0 или === undefined), то мы считаем остров. Если условие нарушается, то этот остров уже был посчитан.
Это решение без доп.рекурсивной функции, поэтому мы не столкнемся с возможными проблемами переполнения стека вызова функ.
Вы уверены, что предложенный алгоритм будет работать с непрямоугольными островами, а зигзагами или вот такой формы? [["1","1","1"],["0","1","0"],["1","1","1"]]
ВОПРОС К SENIOR, вы вообще смоги решить эту задачу, если да то за сколько времени вас удалось это сделать?
Синьор такую задачу должен писать с листа минут за 5-10 это максимум.
В строчках 43 и 44 нужно было так же сделать как и в 45 и 46, потому что если мы проверяем 0вой элемент в массиве то левый сосед будет последний элемент, который может быть отдельным островом, для последнего элемента так же. Или я ошибаюсь?
А нет, в js невозможно как в питоне получать доступ типа arr[-1], возвращает undefined
если ты обращаешься к элементу "за границей" массива arr[length+1] arr[-1] то всегда будет undefined
Спасибо за видео! Есть вопрос, пытался прогнать код в VS, в консоли в браузере выдает Unexpected token '.', ругаясь на 43 строку binaryMatrix?.[R-1]?.[C] === '1'
UPD: гуглил, понял, что это за оператор, но при всем, пока не понимаю, как устранить ошибку
Скорее всего в vscode выбрана для запуска старая версия ноды. Я не спец по vscode так что не подскажу как там поставить посвежее чтобы поддерживал этот оператор. Если что в последних версиях хрома все отлично работает. Можно там запустить
@@frontendscience понял, спасибо!!
Сам не смог решить, после того как ты объяснил понял почти все, кроме того как можно передать в квадратных скобочках два индекса 0_о
относительно сложности: цикл в цикле же - квадратичная сложность. Нет? С тебя видео про это в любом случае!
у нас один цикл проходит по всем строкам, а второй по всем столбцам вот и выходит O(n*m). Квадратичная сложность получается когда у нас оба цикла проходятся по всем элементам.
@@frontendscience но количество операций будет зависеть от размера массива как n * n, т. е. n2? Проход по столбцу подразумевает же перебор элементов столбца? Интересно узнать.
n*m - это количество всех элементов в нашей матрице. ты просто итерируемся по всем элементам матрицы. В худшем случае у нас например когда все элементы матрицы единицы. тогда на первой же итерации наших циклов мы зайдем на остров(первый элемент с 1) и еще раз пройдем все наши элементы массива в рекурсии - но сделаем это только один раз, на всех других итерациях цикла у нас уже будут помечены ячейки 6ками - и мы в рекурсивную функцию заходить не будем. так что результирующая сложность останется O(n*m)
хоть я и питонист, но разве так же с колонкой не надо делать проверку, как со строкой?) Т.к. можно стоять на 0:0 и искать в C-1 (-1). Ну а решал бы так же, но при этом я бы отправлял координаты в отдельный список, а не заменял 6ками. Так бы у меня в будущем были вариации по расширению ;)
с колонкой не надо - так как в этом случае просто вернется undefined, и не будет эксепшена.
Сделай пжл отдельный канал по разбору задач или совмести их в отдельный плейлист
:) Такой плейлист у нас уже есть: ua-cam.com/play/PL0k-9Y7O1GwccXKHRzmvVj17yB7T9pjTo.html
@@frontendscience 🔥 Спасибо
Что за фильм со Скалой? :)
Путешествие 2: Таинственный остров
Подобная задача в Яндексе, при отборе на стажировку. Только там еще надо острова распределить по категориям, в зависимости от формы.
Класс! Они там четко фиксированных форм бывают что ли?
@@frontendscience Да нет, просто надо определить, какие острова занимают всю высоту матрицы, а какие только часть)
grid2: тот момент, когда между "островами" нет "воды"
единственное, что не оч понравилось, что изначальный массив будет мутироваться
На литкод по умолчанию есть требование решить задачу не только наиболее оптимальным способом по времени, но и по памяти. Поэтому делается мутация. Это не продакшен код. А решение задачи с заданными условиями в сендбоксе.
Атятя, мутируете матрицу, нехорошо! с:
На самом деле, не обязательно смотреть соседа сверху и слева, если представить сушу в матрице в виде бинарного дерева и производить глубокий обход исходя из этого, тогда достаточно смотреть только нижний и правый элемент матрицы!
По крайней мере, я так мыслил, когда решал задачу
Атятя! Условия не читаем, сразу пишем коммент. И по второму пункту - не выйдет так. Острова могут быть любой формы, не обязательно прямоугольные. В том числе змейкой.
@@frontendscience Тут я попался, верно. Поправил!
@@frontendscience насчет условия, не совсем понял. Мутация матрицы ведь необязательна, если использовать, например, мапу или объект для хранения пройденных ячеек (доступ к элементу в таком случае будет О(1))?
Если я ошибаюсь, то поправьте пожалуйста
@@DevilAlex03 Все верно, но на leetcode во всех задачах есть есть еще условие реализовать алгоритм как можно более оптимальней и по памяти. Именно поэтому без надобности никто не делаем копию массива и жертвует мутацией в угоду памяти. Это не продакшен эвайромент а именно вот такой сендбокс со своими условиями.
@@frontendscience Теперь понимаю, впервые столкнулся с этим сайтом, спасибо за разъяснение
Хорошо бы ещё обойтись без дублирования кода в обработке соседей.
Оптимизировать можно. Специально этого не делал дабы не усложнять понимание кода. А на общую итоговую сложность по времени это никак не влияет. Это просто вопрос уменьшения копипаста. Во всех задачах я стараюсь делать так, чтоб люди максимально легко поняли.
Чуть по-другому сделала, хотя с рекурсией интереснее:
let grid1 = [
[1, 1, 1, 1, 0, 0],
[1, 0, 0, 1, 0, 0],
[1, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 1],
]
let obj = {}
let checkCoord = (x, y, grid) => {
if (grid[x][y] === 1) {
if (Object.keys(obj).length) {
let ifAHalfOfIcland = -1
Object.keys(obj).forEach(key => {
obj[key].forEach(el => {
if (el.x - 1 === x && el.y === y) {
ifAHalfOfIcland = key
}
if (el.x + 1 === x && el.y === y) {
ifAHalfOfIcland = key
}
if (el.x === x && el.y + 1 === y) {
ifAHalfOfIcland = key
}
if (el.x === x && el.y - 1 === y) {
ifAHalfOfIcland = key
}
})
})
if (ifAHalfOfIcland > -1) {
obj[ifAHalfOfIcland].push({x, y})
} else {
obj[Object.keys(obj).length] = [{x, y}]
}
} else {
obj[0] = [{x, y}]
}
}
}
let numIslands = function(grid) {
grid.forEach((item, x) => {
item.forEach((row, y) => {
checkCoord(x, y, grid)
})
});
return Object.keys(obj).length
}
console.log(numIslands(grid1))
Благодарю за решение. К сожалению что-то пошло не так и выдает не верный ответ на вот таком кейсе:
[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
Output 0
Expected 1
Но вы же мутируете массив с данными...
Почитай требования к задаче...
const input1 = [
["1", "0", "1", "0", "1"],
["1", "1", "0", "1", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "0", "0", "0"],
];
const mathIsland = (arg) => {
let count = 0;
let onIsland = false;
for (let i = 0; i < arg.length; i++) {
for (let j = 0; j < arg[i].length; j++) {
if (j === 0) {
onIsland = false;
}
if (arg[i][j] === "0" && onIsland === true) {
onIsland = false;
}
if (i === 0) {
if (arg[i][j] === "1" && onIsland === false) {
count++;
onIsland = true;
}
if (arg[i][j - 1] === "0" && arg[i][j] === "1" && onIsland === false) {
count++;
onIsland = true;
}
} else {
if (arg[i][j] === "1" && onIsland === false) {
if (arg[i - 1][j] !== "1") {
count++;
}
onIsland = true;
}
if (arg[i][j - 1] === "0" && arg[i][j] === "1" && onIsland === false) {
if (arg[i - 1][j] !== "1") {
count++;
}
onIsland = true;
}
}
}
}
return count;
};
console.log(input1[0], input1[1], input1[2], input1[3]);
console.log(mathIsland(input1));
Мозги скрипят(
grid[r][c]
+++
Помойму проще в процессе перебора массива сравнивать с массивом отметок все соседние элементы и если они помечены как остров то не защитовать новый остров, а если не помечены то добавлять новый остров. Сложно в разы меньше все 1 проход по массиву в сравнением с представленным вариантом
Так присылай решение, посмотрим насколько оно проще
@@frontendscience я прислал свое, похоже на то что тут описали, посмотрите. Отдельным комментарием.
@@hsmtrue Посмотрел) Не подошло. Под решением написал почему.