" Во-вторых, я готовлю серию задач в одном ключе с постепенно возрастающей сложностью. То есть для решения последующих задач medium и hard вам понадобится понимание решения этой задачи. Поэтому не ленитесь, попытайтесь разобраться и решить ее." - очень круто что ты так структурировал плейлист, я с удовольствием его весь перерешиваю
Спасибо за видео. Как по мне, так выглядит проще: var maxDistToClosest = function(seats) { let max = 0; let count = 0; let first = true; for (let i = 0; i < seats.length; i++ ) { if (seats[i] === 1) { if(first) { max = count; } count = 0; first = false; } else { count += 1; max = Math.max(max, Math.ceil(count/2)) } } return Math.max(max, count); };
вместо верхнего ифа(по поиску мест в начале), проще инициализацию сделать как let max = input1.indexOf(1); и цикл рабочий запускать от max соответственно
мне кажется splice работает за O(n) (поправьте, если не так), поэтому сложность будет в худшем случае O(n^2). Вот моё решение: function removeDuplicates(nums: number[]): number { let j = 1; for (let i = 1; i < nums.length; i++) { if (nums[i] !== nums[i - 1]) { nums[j] = nums[i]; j++; } } return j; };
Скину и свою писанину, основная идея была такая: найти индекс начала и длину самой большой последовательности нулей. Ну и вышло как-то многовато кода, плюс немного запутанно и неоправданно сложно, у вас попроще явно, а в комментах ещё лаконичнее нашёлся код) Ну, как говорится, зато сам. И кстати в моём решении можно было б сразу выдавать индекс нужного места) const maxDistToClosest = function (seats) { const seatsLen = seats.length; let maxFreeLen = -1, maxFreeIndex = -1, maxFreeLastIndex = -1; for (let i = 0, freeLen = 0, freeIndex = 0; i < seatsLen; i++) { if (seats[i] === 0) { if (freeLen === 0) { freeIndex = i; } freeLen++; } else { if (freeLen !== 0) { if (maxFreeLen < freeLen) { maxFreeLen = freeLen; maxFreeIndex = freeIndex; } freeLen = 0; } }
Благодарю за решение! Классно что сам попробовал решить! Где-то у тебя закралась ошибка связанная с последними сидениями: Input [0,1,1,1,0,0,1,0,0] Output 1 Expected 2
У меня получилось во так. Отличие от вашего решения: для проверки идет ли отсчет свободных мест с начала ряда создал переменную isStart, которая по началу true, при нахождении первой 1 менял isStart на false. А для проверки, нужно ли делить на 2, воспользовался тернарником, где проверял состояние переменной isStart и является ли arr[i] концом массива. Получилось короче, но не могу понять как тут с производительностью. Что скажите? function findMaxDistance(arr) { let max = 0; let countFree = 0; let isStart = true; for (let i = 0; i < arr.length; i++) { if(arr[i] == 1) { countFree = 0; isStart = false; } else { countFree++ max = Math.max(max, (i == arr.length - 1 || isStart) ? countFree : Math.ceil(countFree/2)) } } return max }
Благодарю за решение! Эта часть получилась короче в записи. По производительности она такая же как и в видео. Но вот чего тут нет - так это учета сидений в конце ряда. Они должны считаться также как и вначале (без деления на 2). И вот из-за этого и выходит много кода, так как мы не знаем когда наступит конец и сколько сидений перед окончанием рядя свободны.
Добрый день! Классная задача, спасибо! У меня в ходе решения вроде как удалось уйти от магической двойки. Как вам такой вариант? function maxDistToClosest(seats) { let maxDist = 0; let currentDist = 0; let sittersOnSides = 0; for (let place of seats) { if (place) { sittersOnSides++; maxDist = Math.max(Math.ceil(currentDist / sittersOnSides), maxDist); currentDist = 0; sittersOnSides = 1; } else { currentDist++; } } return Math.max(currentDist, maxDist); }
Классное решение вышло! Долго пытался понять как же оно работает. А потом как понял.... )) Магическая двойка все равно есть - но она настолько магическая что умеет превращаться в единицу по краям.
@@frontendscience Да, согласен, эта единица мозолила глаз, вроде хотелось и ее как-нибудь эдак обыграть, сохранив в осмысленно названной константе, но в итоге, видимо, не дожал)
У меня вот что получилось ``` function maxDistToClosest(seats) { let max = 0; const seatsString = seats.join(''); const re = /[0]+/g; const matches = seatsString.matchAll(re); for (let match of matches) { if (match.index === 0 || match.index + match[0].length === seatsString.length) { max = Math.max(max, match[0].length); } else { max = Math.max(max, Math.ceil(match[0].length / 2)); } } return max; } ``` matchAll - это вообще легально?
За сколько я ее решил я уже не помню. А на собеседованиях (например в FAANG) на кодинг интервью дают 45 минут: за это время необходимо разобраться с условием, задать уточняющие вопросы, продумать алгоритм, еще задать вопросов, чтобы убедиться что алгоритм будет работать, написать код, озвучивая постоянно что пишешь, проверить что эта программа будет работать как задумано (без запуска в консоли), и разобрать сложность алгоритма по времени и по памяти. Еще один момент что вы можете изначально не знать самого оптимального алгоритма решения, но важно с чего-то начать а потом успеть оптимизировать свой код. Как-то так.
while в начале функции - хорошее решения, даже не сразу понял как это должно работать (на практике такого приема не встречал). а вот дополнительный if внутри for - не очень. можно было после for написать условие if (count !== 0) {...} - решение получилось бы еще лучше
@@frontendscience лишнее условие внутри цикла - это не «дело вкуса и кодстайла», если вы хотите показать производительный код (который подразумевается на задачах подобного рода). вы по сути производите избыточные вычисления в своём примере - и этому учите. не хорошо
ну и да, решение: var maxDistToClosest = function (seats) { let count = 0; let current = seats.indexOf(1); let end = seats.lastIndexOf(1); let max = Math.max(current, seats.length - end - 1); while (current < end) { current += 1; if (!seats[current]) { count += 1; } else { max = Math.max(max, Math.ceil(count / 2)); count = 0; } } return max; }
@@LastDreamer Посмотри мои все остальные задачи на канале - они все в избыточных переменных в угоду читаемости. Эта избыточность не добавляет сложности к самому алгоритму, но зато легко понять можно что происходит. Именно это и нужно тут. В алгоритмических задачах на собеседовании не нужен продакшен реди код - нужен чистый и легко читаемый код. Как-то так! PS: В том числе и этот if :)
Спасибо большое за видео! А вы не могли бы прикреплять ссылки на задачу из самого leetcode, пожалуйста. Там есть кнопочка submit, где можно проверить решение на разных данных.
Если надо чуточку сложнее, то собственно та же задача, только учитывать весь зал, включая диагонали, сидения расположены как в кинотеатре, в шахматном порядке, ряды сужаются ближе к экрану.
Решил по другому. Ваше решение гараздо лаконичнее. Не судите строго, я учусь const maxDistToClosest = function (seats) { let max = []; let seatTaken = []; let n = seats.length - 1; for (let i = 0; i 0)) { //0....1 max.push(current); } else if ((i === k - 1) && (current !== n)) { //1....0 max.push(n - current); } else { let dist = Math.ceil((current - seatTaken[i - 1])/2); //...10001... max.push(dist); } } return Math.max(...max); } console.log(maxDistToClosest(input1));
Класс!! Идея очень прикольная вышла - собрать список занятых, а потом работать с числами(позициями занятых мест - чтобы искать промежутки свободные). Не самый оптимальный вариант по памяти вышел, но идея клёвая. 💪
Благодарю за решение! Классно, что стараешься сам до видео решать! Отлично работает когда места в середине ряда, и в конце. Но вот если ряд начинается с пустых мест то лезут баги. [ 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0] вернул 7 вместо 3.
У меня получилось такое решение: const maxDistToClosest = (seats) => { if (!seats.includes(0)) { return 0 } let currResult = 1 let result = 0 for (let i = 0; i < seats.length; i++) { let prev = seats[i - 1] let curr = seats[i] let next = seats[i + 1] if (curr === 0) { if (prev === undefined && next === 0) { currResult++ } else if (prev === 0 && next === undefined) { currResult++ } else if (prev === 0 && next === 0) { currResult++ } } else { result = Math.max(currResult, result) } } return Math.max(currResult, result) }
моё решение) function maxDistToClosest1(seats){ let max = 0 let mas = [] let count = 0 let flag = true for(let i = 0; i < seats.length; i++){ if(seats[i] === 1){ flag = false mas.push(max) max = 0 } else if (seats[i] === 0) { max += 1 } if(seats[0] === 0 && seats[i] === 0 && flag) { count += 1 } } if(max < count){ max = count } let maxNew = Math.max.apply(null, mas) return max > Math.ceil(maxNew/2) ? max : Math.ceil(maxNew/2) }
function stayAway(arr){ arr=arr.join('').match(/0*/g); arr.pop() let max=0; for (let i = 0; i < arr.length; i++){ (i===0 || i===arr.length-1) ? max=Math.max(max, arr[i].length) : max=Math.max(max, Math.ceil(arr[i].length/2)) } return max } Имеет ли право на жизнь? Дайте знать
" Во-вторых, я готовлю серию задач в одном ключе с постепенно возрастающей сложностью. То есть для решения последующих задач medium и hard вам понадобится понимание решения этой задачи. Поэтому не ленитесь, попытайтесь разобраться и решить ее." - очень круто что ты так структурировал плейлист, я с удовольствием его весь перерешиваю
Весь день сегодня пвтался решить, а оказалось все намного проще
Спасибо за видео. Как по мне, так выглядит проще:
var maxDistToClosest = function(seats) {
let max = 0;
let count = 0;
let first = true;
for (let i = 0; i < seats.length; i++ ) {
if (seats[i] === 1) {
if(first) {
max = count;
}
count = 0;
first = false;
} else {
count += 1;
max = Math.max(max, Math.ceil(count/2))
}
}
return Math.max(max, count);
};
Классный вариант! Действительно вышло очень компактно!
вместо верхнего ифа(по поиску мест в начале), проще инициализацию сделать как let max = input1.indexOf(1);
и цикл рабочий запускать от max соответственно
Интересное решение связать два цикла...👍
мне кажется splice работает за O(n) (поправьте, если не так), поэтому сложность будет в худшем случае O(n^2). Вот моё решение:
function removeDuplicates(nums: number[]): number {
let j = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] !== nums[i - 1]) {
nums[j] = nums[i];
j++;
}
}
return j;
};
За lengTh плюсую))) Сам так говорю, когда пишу)))
спасибо за Вашу работу 🔥😎
И Вам спасибо за поддержку!
Скину и свою писанину, основная идея была такая: найти индекс начала и длину самой большой последовательности нулей. Ну и вышло как-то многовато кода, плюс немного запутанно и неоправданно сложно, у вас попроще явно, а в комментах ещё лаконичнее нашёлся код) Ну, как говорится, зато сам. И кстати в моём решении можно было б сразу выдавать индекс нужного места)
const maxDistToClosest = function (seats) {
const seatsLen = seats.length;
let maxFreeLen = -1,
maxFreeIndex = -1,
maxFreeLastIndex = -1;
for (let i = 0,
freeLen = 0, freeIndex = 0; i < seatsLen; i++) {
if (seats[i] === 0) {
if (freeLen === 0) {
freeIndex = i;
}
freeLen++;
} else {
if (freeLen !== 0) {
if (maxFreeLen < freeLen) {
maxFreeLen = freeLen;
maxFreeIndex = freeIndex;
}
freeLen = 0;
}
}
if (i === seatsLen - 1) {
if (maxFreeLen < freeLen) {
maxFreeLen = freeLen;
maxFreeIndex = freeIndex;
}
}
}
maxFreeLastIndex = maxFreeIndex + maxFreeLen - 1;
if (maxFreeLen === -1) {
return -1;
} else {
if (maxFreeIndex !== 0 && maxFreeLastIndex !== seatsLen - 1) {
return Math.round(maxFreeLen/2);
} else {
return maxFreeLen;
}
}
}
Благодарю за решение! Классно что сам попробовал решить!
Где-то у тебя закралась ошибка связанная с последними сидениями:
Input [0,1,1,1,0,0,1,0,0]
Output 1
Expected 2
@@frontendscience Спасибо! Исправил) Во втором ифе в цикле во вложенном ифе вместо < надо было написать
Хмммм.... все равно что-то не то
Input [1,0,0,1,0,0,0,1,1,1,0,0,0,0,0,0,1,0,0,0,0,0]
Output 3
Expected 5
У меня получилось во так. Отличие от вашего решения: для проверки идет ли отсчет свободных мест с начала ряда создал переменную isStart, которая по началу true, при нахождении первой 1 менял isStart на false. А для проверки, нужно ли делить на 2, воспользовался тернарником, где проверял состояние переменной isStart и является ли arr[i] концом массива. Получилось короче, но не могу понять как тут с производительностью. Что скажите?
function findMaxDistance(arr) {
let max = 0;
let countFree = 0;
let isStart = true;
for (let i = 0; i < arr.length; i++) {
if(arr[i] == 1) {
countFree = 0;
isStart = false;
} else {
countFree++
max = Math.max(max, (i == arr.length - 1 || isStart) ? countFree : Math.ceil(countFree/2))
}
}
return max
}
Благодарю за решение! Эта часть получилась короче в записи. По производительности она такая же как и в видео. Но вот чего тут нет - так это учета сидений в конце ряда. Они должны считаться также как и вначале (без деления на 2). И вот из-за этого и выходит много кода, так как мы не знаем когда наступит конец и сколько сидений перед окончанием рядя свободны.
Добрый день! Классная задача, спасибо!
У меня в ходе решения вроде как удалось уйти от магической двойки. Как вам такой вариант?
function maxDistToClosest(seats) {
let maxDist = 0;
let currentDist = 0;
let sittersOnSides = 0;
for (let place of seats) {
if (place) {
sittersOnSides++;
maxDist = Math.max(Math.ceil(currentDist / sittersOnSides), maxDist);
currentDist = 0;
sittersOnSides = 1;
} else {
currentDist++;
}
}
return Math.max(currentDist, maxDist);
}
Классное решение вышло! Долго пытался понять как же оно работает. А потом как понял.... ))
Магическая двойка все равно есть - но она настолько магическая что умеет превращаться в единицу по краям.
@@frontendscience
Да, согласен, эта единица мозолила глаз, вроде хотелось и ее как-нибудь эдак обыграть, сохранив в осмысленно названной константе, но в итоге, видимо, не дожал)
Это просто идеально!
я попробовал через регулярные выражения, тож норм вроде
А решение покажешь?
Front-end Science c Сергеем Пузанковым , блин, стыдно говорить, поторопился, сейчас начал проверять, чтобы отправить - есть ошибки
Ниче, бывает. Как решишь - кидай! Сама идея интересная вообще.
У меня вот что получилось
```
function maxDistToClosest(seats) {
let max = 0;
const seatsString = seats.join('');
const re = /[0]+/g;
const matches = seatsString.matchAll(re);
for (let match of matches) {
if (match.index === 0 || match.index + match[0].length === seatsString.length) {
max = Math.max(max, match[0].length);
} else {
max = Math.max(max, Math.ceil(match[0].length / 2));
}
}
return max;
}
```
matchAll - это вообще легально?
@@gladfilm не могли бы дать комментарий к строке с условием if..??
Добрый день!
Сколько Вам потребвалось времени на её решение?
За сколько по Вашему мнению должна быть решена быть эта задача?
За сколько я ее решил я уже не помню. А на собеседованиях (например в FAANG) на кодинг интервью дают 45 минут: за это время необходимо разобраться с условием, задать уточняющие вопросы, продумать алгоритм, еще задать вопросов, чтобы убедиться что алгоритм будет работать, написать код, озвучивая постоянно что пишешь, проверить что эта программа будет работать как задумано (без запуска в консоли), и разобрать сложность алгоритма по времени и по памяти. Еще один момент что вы можете изначально не знать самого оптимального алгоритма решения, но важно с чего-то начать а потом успеть оптимизировать свой код. Как-то так.
while в начале функции - хорошее решения, даже не сразу понял как это должно работать (на практике такого приема не встречал). а вот дополнительный if внутри for - не очень. можно было после for написать условие if (count !== 0) {...} - решение получилось бы еще лучше
Дело вкуса и кодстайла
@@frontendscience лишнее условие внутри цикла - это не «дело вкуса и кодстайла», если вы хотите показать производительный код (который подразумевается на задачах подобного рода). вы по сути производите избыточные вычисления в своём примере - и этому учите. не хорошо
ну и да, решение:
var maxDistToClosest = function (seats) {
let count = 0;
let current = seats.indexOf(1);
let end = seats.lastIndexOf(1);
let max = Math.max(current, seats.length - end - 1);
while (current < end) {
current += 1;
if (!seats[current]) {
count += 1;
} else {
max = Math.max(max, Math.ceil(count / 2));
count = 0;
}
}
return max;
}
@@LastDreamer Посмотри мои все остальные задачи на канале - они все в избыточных переменных в угоду читаемости. Эта избыточность не добавляет сложности к самому алгоритму, но зато легко понять можно что происходит. Именно это и нужно тут. В алгоритмических задачах на собеседовании не нужен продакшен реди код - нужен чистый и легко читаемый код. Как-то так! PS: В том числе и этот if :)
@@LastDreamer Хорошее решение получилось.Благодарю! Хоть тут и 3 прохода по массиву - все равно сложность O(n) при этом выглядит очень лаконично!
Спасибо большое за видео! А вы не могли бы прикреплять ссылки на задачу из самого leetcode, пожалуйста. Там есть кнопочка submit, где можно проверить решение на разных данных.
решение let maxDistToClosest = (arr) => {
let maxDist = 0;
let currentDist = 0;
arr.forEach((seat, index) => {
if (seat) {
currentDist = Math.ceil(currentDist / 2);
if (maxDist < currentDist) {
maxDist = currentDist
}
currentDist = 0
} else {
currentDist += 1;
}
if(index === arr.length-1 && !seat) {
if (maxDist < currentDist) {
maxDist = currentDist
}
}
})
return maxDist;
}
прикрепил в описание leetcode.com/problems/maximize-distance-to-closest-person/
Благодарю за решение. Надо доработать: [0,0,0,0,0,1,0,0,0] - вот на таком тест кейсе падает.
Если надо чуточку сложнее, то собственно та же задача, только учитывать весь зал, включая диагонали, сидения расположены как в кинотеатре, в шахматном порядке, ряды сужаются ближе к экрану.
Отличная идея!
Решил по другому. Ваше решение гараздо лаконичнее. Не судите строго, я учусь
const maxDistToClosest = function (seats) {
let max = [];
let seatTaken = [];
let n = seats.length - 1;
for (let i = 0; i 0)) { //0....1
max.push(current);
} else if ((i === k - 1) && (current !== n)) { //1....0
max.push(n - current);
} else {
let dist = Math.ceil((current - seatTaken[i - 1])/2); //...10001...
max.push(dist);
}
}
return Math.max(...max);
}
console.log(maxDistToClosest(input1));
Класс!! Идея очень прикольная вышла - собрать список занятых, а потом работать с числами(позициями занятых мест - чтобы искать промежутки свободные). Не самый оптимальный вариант по памяти вышел, но идея клёвая. 💪
Перед просмотром видео моё решение)) Если я правильно вычисляю сложность алгоритма то тут должно быть O(n)
```js
const input = [1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0]; // 4
const maxDistToClosest = (input) => {
let farPlace = null;
let start = null;
for (let i = 0; i < input.length; i++) {
const lastIdx = input.length - 1;
if (input[i] === 0 && start === null) {
start = i;
}
if ((input[i] > 0 || i === lastIdx) && start !== null) {
if (i === lastIdx && input[lastIdx] === 0) {
const diff = input.length - start;
if (diff > farPlace) {
return diff;
}
}
if (farPlace < i / (start + 1)) {
farPlace = i / (start + 1);
start = null;
}
}
}
return farPlace;
};
console.log(maxDistToClosest(input));
```
Благодарю за решение! Классно, что стараешься сам до видео решать! Отлично работает когда места в середине ряда, и в конце. Но вот если ряд начинается с пустых мест то лезут баги.
[ 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0] вернул 7 вместо 3.
@@frontendscience да действительно я там перепутал start = null в конце надо на 1 строку вниз спустить. Вот так работает вроде норм.
```js
const maxDistToClosest = (input) => {
let farPlace = null;
let start = null;
const lastIdx = input.length - 1;
for (let i = 0; i < input.length; i++) {
if (input[i] === 0 && start === null) {
start = i;
}
if ((input[i] === 1 || i === lastIdx) && start !== null) {
if (i === lastIdx && input[lastIdx] === 0) {
const distance = input.length - start;
if (distance > farPlace) {
return distance;
}
}
const distance = i / (start + 1);
if (farPlace < distance) {
farPlace = distance;
}
start = null;
}
}
return farPlace;
};```
У меня получилось такое решение:
const maxDistToClosest = (seats) => {
if (!seats.includes(0)) {
return 0
}
let currResult = 1
let result = 0
for (let i = 0; i < seats.length; i++) {
let prev = seats[i - 1]
let curr = seats[i]
let next = seats[i + 1]
if (curr === 0) {
if (prev === undefined && next === 0) {
currResult++
} else if (prev === 0 && next === undefined) {
currResult++
} else if (prev === 0 && next === 0) {
currResult++
}
} else {
result = Math.max(currResult, result)
}
}
return Math.max(currResult, result)
}
Если в ряду все места будут пустыми (то есть все элементы массива равны 0), то получим indexOutOfBound в первом цикле while
Вы вероятно до этого писали не на js :) В js такого не будет - просто у нас вместо значения 0/1 будет undefined и while прервется
@@frontendscience а, ну тогда ок. Просто я джавист))
Const fn = arr => {
const value = arr.toString().replace(“,”,””)
if(value===“1000101”) return 2
if(value===“1000”) return 3
throw new Error(“Invalid input”)
}
🤣 искусственный интеллект прямо!
моё решение)
function maxDistToClosest1(seats){
let max = 0
let mas = []
let count = 0
let flag = true
for(let i = 0; i < seats.length; i++){
if(seats[i] === 1){
flag = false
mas.push(max)
max = 0
} else if (seats[i] === 0) {
max += 1
}
if(seats[0] === 0 && seats[i] === 0 && flag) {
count += 1
}
}
if(max < count){
max = count
}
let maxNew = Math.max.apply(null, mas)
return max > Math.ceil(maxNew/2) ? max : Math.ceil(maxNew/2)
}
function stayAway(arr){
arr=arr.join('').match(/0*/g);
arr.pop()
let max=0;
for (let i = 0; i < arr.length; i++){
(i===0 || i===arr.length-1)
? max=Math.max(max, arr[i].length)
: max=Math.max(max, Math.ceil(arr[i].length/2))
}
return max
}
Имеет ли право на жизнь? Дайте знать