Блин, я как раз в прошлом месяце искала такой видос :( И нашла только какой-то шестилетней давности :( Спасибо! Полезно! И монтаж такой клевый, каждый раз приятно удивляюсь :3
мне кажется без стека вполне можно обойтись : алгоритм простой - следующая скобка является ли закрывающей - да - вырежи их и проверь еще раз предыдущую let arr1='{}((({}{[]}{}{[[[]]]}{}{})))'; function convert(str){ switch (str) { case ')' : return '('; case ']' : return '['; case '}' : return '{'; default : return ' ' } } let test =function(arr){ if (arr.length%2 !=0) {return false}; // можно исключить for (let i=0; i
немогу врубиться ы это строку if (brackets[current] !== stack.pop()) return false . И почему нельзя обойтись без (brackets[current] перевертывание скобок ? может кто объяснит
ок объясню на примере: [()]. Мы прошли первые 2 символа с открывающимися скобочками и поместили их в стек. Сейчас он выглядит так: [( Доходим до закрывающегося символа ")". Нам надо сравнить что у нас вверху стека находится тоже круглая но открывающаяся скобочка. Для этого мы из таблицы соответствия закрывающих скобочек открывающимся достаем brackets[current]. current сейчас равен ")" значит brackets[current] вернет "(". И мы делаем операцию stack.pop(). Метод pop отрывает верхний элемент стека и возвращает его. Значит мы сравним "(" и "(" - и проверка вернет false значит конструкция return false не отработает и мы пойдем проверять следующую скобочку. Если бы у нас скобки не матчились - то мы сразу возвращаем false как результат работы программы
Спасибо за видео! Немного изменил код, кому как больше по вкусу. function isValid(s) { const stack = []; const brackets = { ')': '(', ']': '[', '}': '{', }; for (const current of s) { if (current in brackets) { if (brackets[current] !== stack.pop()) return false; } else { stack.push(current); } } return !stack.length; }
Не самое оптимальное решение, но тоже имеет право на жизнь)) function check(str) { const checkStr = '[]{}()'; const bracketsStack = []; let bracket = 0; let bracketPosition = -1; for (let i = 0; bracket = str[i]; i++) { bracketPosition = checkStr.indexOf(bracket); if (bracketPosition === -1) { continue; } if (bracketPosition % 2 === 0) { bracketsStack.push(bracketPosition + 1); } else if (bracketsStack.pop() !== bracketPosition) { return false; } } return bracketsStack.length === 0; }
пол часа потратил но по моему не плохой вариант )) const examples = { '{':'}', '[':']', '(':')'}; const stack = []; function test(str) { let result = true; [...str].forEach((item, i) => { if (examples[item]) { stack.push(item); } else if (item !== examples[stack.pop()]) { result = false; } }); return result; }
Занимаюсь недавно. Сделал без использования объектов. Не знал про понятие "стека". Использовал только for, if и function. Функция ищет соседние скобки одного вида и разного направления, если находит - вырезает их через splice, увеличивает счетчик (счетчик использую как условие выхода из цикла) и заново вызывает себя. ___________________________ function validBraces(braces) { let arr = braces.split(''); let ciclCounter = 0; const endOfCicl = arr.length; function recursDelBrasket(arr) { for (let i = 0; i < arr.length; i++) { const element = arr[i]; console.log(arr); console.log(element); if(arr.length === 0){ break; } if((element === '(') && ((i + 1) === arr.indexOf(')'))){ ciclCounter++; arr.splice(i, 2); return recursDelBrasket(arr); } if((element === '{') && ((i + 1) === arr.indexOf('}'))){ ciclCounter++; arr.splice(i, 2); return recursDelBrasket(arr); } if((element === '[') && ((i + 1) === arr.indexOf(']'))){ ciclCounter++; arr.splice(i, 2); return recursDelBrasket(arr); } if(ciclCounter >= endOfCicl){ break } } } recursDelBrasket(arr); if(arr.length === 0) { return true; } else { return false; } }
так лучше function brackets(str) { const regEx = /(\[\]|\{\}|\(\))/; let index = 0; while (index !== -1) { index = str.search(regEx); str = str.substring(0, index) + str.substring(index + 2); } return !Boolean(str); }
Решил на php за 15 мин где-то через рекурсивный проход. В самом начале сделал проверку на четность кол-ва скобочек, чтобы сразу отсеять невалид. Решение через стек элегантнее конечно, т.к. нет необходимости обрабатывать всю строку.
так просто, чтобы было, тоже свое решение оставлю) function isValidString(str){ let tempStr = str; let spliters = ['()', '[]' , '{}']; for (let i = 0 ; i < spliters.length ; i++){ if (!tempStr.length) return true; tempStr = tempStr.split(spliters[i]).join(''); } if (str.length === tempStr.length) { return false; } else { return isValidString(tempStr); } } п.с.: спасибо за качественный контент, приятно и смотреть и разбираться вместе над frontend задачами
Спасибо за видео и интересную задачу! Решение почти полностью совпало с моим (даже нейминг), только цикл в другую сторону. 🙂 const isValidBracketSequence = str => { const brackets = { ')': '(', ']': '[', '}': '{', }, stack = []; for (let i = str.length - 1; i >= 0; i--) { let char = str[i]; if (char in brackets) { stack.push(brackets[char]); } else if (char !== stack.pop()) { return false; } } return stack.length === 0; };
Раньше решал задачу через два масcива: с символами скобок начала и конца. Принцип тот же, но удобно сопоставлять по номеру вхождения в масив через indexOf. И работает шустрее) function isBalanced(string) { const arr = [] const start = ['{','[','('] const end = ['}',']',')'] for (let char of string) { if (start.includes(char)) arr.push(char) else if (end.includes(char)) if (arr[arr.length-1] === start[end.indexOf(char)]) arr.pop() else return false } return arr.length === 0 }
Интересное решение но не был рассмотрен кейс, если строка начинается с закрывающей скобки или количество закрывающих скобок превышает количество открывающих, тогда мы вызываем метод pop() из пустого стэка, что может вызывать ошибки.
Ошибки не будет. [].pop() возвращает undefined. Дальше будет сравниваться скобка с undefined что будет возвращать false так как последовательность не валидна.
@@frontendscience Я имел ввиду ошибки в других языках, забыл дописать. Я сам с JS очень поверхностно знаком, поэтому не знал как в нем будет) Спасибо за объяснение!
Где-то читал( уже не вспомню) , что в именованиях лучше не использовать прошедшее время( если только домен этого не требует). И фонетически "isClosingBracket" звучит лучше. И спасибо за видосы)
Сергей, контент отличный! Единственный вот момент который смутил: то, что внутри цикла, есть indexof. В итоге данная реализация ведь O(n*n)? Либо я чего то не понимаю…
решал похожее сделал функцию на удаление из строки () [] и тд потом проверял есть ли еще такие в строке и удалял еще раз и так по кругу в цикле -) суть проверки в том что у вас всегда будет скобки которые открываются и закрываются сразу же, поэтому если таких нет, то строка с ошибкой ну и в конце если строка стала пустой то все четко, если нет то опять же ошибка
ну че народ погнали function sc(scob){ let i = 0 scob = scob.split('') while (scob.length>0){ console.log(scob) if(scob[i] == ')'){ // вычисляет первую закрывающуюся скобку if(scob[i-1] == '(') { //рядом с ней обязательно должна быть открывающая скобка scob.splice(i-1,2) //если это так удаляем эти скобки из массива i=0 // начинаем массив с начала continue // начинаем цикл с начала } else return false // если рядом с закрываеющейся скобочкой нет открывающийся значит все пропало } else if(scob[i] == '}'){ if(scob[i-1] == '{'){ scob.splice(i-1,2) i=0 continue } else return false } else if(scob[i] == ']'){ if(scob[i-1] == '['){ scob.splice(i-1,2) i=0 continue } else return false } else i++ } if(scob.length == 0) return true }
@@frontendscience let scob = '{{}' console.log(sc(scob)) function sc(scob){ let i = 0 scob = scob.split('') if(scob.length % 2) return false while (scob.length>0){ console.log(scob) if(scob[i] == ')'){ // вы числяет первую закрывающуюся скобку if(scob[i-1] == '(') { //рядом с ней обязательно должна быть открывающая скобка scob.splice(i-1,2) //если это так удаляем эти скобки из массива i=0 // начинаем массив с начала continue // начинаем цикл с начала } else return false // если рядом сзакрываеющийся скобочкой нет открывающийся значит все пропало } else if(scob[i] == '}'){ if(scob[i-1] == '{'){ scob.splice(i-1,2) i=0 continue } else return false } else if(scob[i] == ']'){ if(scob[i-1] == '['){ scob.splice(i-1,2) i=0 continue } else return false } else i++ } if(scob.length == 0) return true }
На интервью в одну известную компанию решил без создания обратного словаря: const brackets = { '(': ')', '{': '}', '[': ']', }; /** * @param {string} s * @return {boolean} */ const isValid = (s) => { const stack = []; for (sym of s) { if (sym in brackets) { stack.push(sym); } else if (sym !== brackets[stack.pop()]) { return false; } } return !stack.length; };
А что если мы можем менять местами соседние скобки ({[ или)]}бесконечное количество раз? То есть ([) ] уже будет true так как можем поменять местами последние 2. Менять, например, ( и) не можем так как смотрят в разные стороны
Конечно! Решение задачи складывается из 2 частей - разобраться в том, каким алгоритмом ты это будешь решать, и потом все запрограммировать. Я видел очень много разработчиков, которые на собеседовании рассказывали правильно алгоритм, но не могли это запрограммировать. Так что половина работы уже есть! А определение нужного алгоритма придет с практикой ;) успехов!
На середине 5й минуты я почувствовал себя ребёнком, почти в ладоши начал хлопать, а потом вспомнил что 20минут первого, а завтра(фактически сегодня уже, блин) четверг :( з.ы. Видео класс, впрочем как и всегда.
Уже пятый день бьюсь над задачей, прохожу на Хекслет курс фронтенд разработчика и мы ещё не дошли до мап, предлагают решить задачу через две константы с открывающимися и закрывающимися скобками через indexOf Видео очень доступно обьяснило мне ход решения, мне было и так все понятно, но как сравнить скобки без обьекта до сих пор не понял, но обязательно дойду к этому. Спасибо, отлично делаете свое дело, удачи вам!
Рад что было полезно. Что касается варианта без объекта, то нужно создать 2 переменные ‘({[‘ и ‘)}]’ теперь с помощью indexOf в первой ищем текущую скобку и проверяем чтобы закрывающаяся была равна скобке с тем же индексом но во второй переменной
Лучше проверку на длину сделать в начале, если длина не является валидной (3, 5, 7, ... etc.), то делаем ретерн и все, чтобы не прогонять код и делать проверку в конце
Объясните, пожалуйста, почему этот алгоритм является рекурсивным? Насколько мне известно, рекурсия в программировании - это вызов функцией самой себя. В данном коде такого нет, так в чём же заключается рекурсия?
Алгоритм который был реализован в видео не рекурсивный. Я упомянул что мы можем решить задачу рекурсивно выкусывая все пары скобочек. до тех пор пока есть что выкусывать. В этом случае функция ищет и удаляет все рядом стоящие пары скобок. И мы будем оставшуюся строку еще раз скармливать этой функции. Будет рекурсивное решение. Вариант же предложенный в видео более эффективен - работает линейно - и за один проход определяет валидность строки.
Это тоже невалидная последовательность. Алгоритм отработает правильно и сделает проверку на первом же символе. У нас будет пустой стек и закрывающуюся скобку не с чем будет сравнивать. Поэтому алгоритм вернет false.
@@frontendscience Соглашусь, это уже мелочи! В любом случае, спасибо за твои видео, и то что ты делаешь! У тебя отличный контент и очень крутое качество монтажа и съёмки!
Решал раньше такую задачу на codewars (Valid Parentheses сложностью 5 kyu), там были только круглые скобки. Задачу из видео решил двумя способами. Первый, попроще для понимания, со сложностью O (n ^ 2), второй - O (n). По памяти оба варианта O (n). Способ 1: function isValid(s) { let match = { ")": "(", "]": "[", "}": "{", } let arr = s.split(''); for (let i = arr.length - 1; i > 0; i--) { if (match[arr[i]] === arr[i - 1]) { arr.splice(i - 1, 2); } } return arr.length === 0; } Результат на leetcode: Runtime: 72 ms, faster than 85.01%. Memory Usage less than 33.16% Способ 2: function isValid(s) { let match = { ")": "(", "]": "[", "}": "{", } let stack = []; for (let i = 0; i < s.length; i++) { if (s[i] === "(" || s[i] === "[" || s[i] === "{") { stack.push(s[i]); } else if (match[s[i]] !== stack.pop()) { return false; } } return stack.length === 0; } Результат на leetcode: Runtime: 68 ms, faster than 94.38% Memory Usage less than 76.51% Кстати, мой второй вариант и решение из видео очень похожи, но мой способ немного короче :)
function isValid(s) { let arr = s.split(''); let obj = { '[': ']', '{': '}', '(': ')', }; for (let i = 0; i < arr.length - 1; i++) { if (arr[i + 1] === obj[arr[i]]) { arr.splice(i, 2); i = Math.max(i - 2, -1); } } return arr.length === 0; } Результат на leetcode: Runtime 53ms Beats 94.63% P.S. решение через стек, конечно, лучше для больших строк
Немного мучений и вот мое решение: isValid = function(s) { let stack = []; let brackets = {'()':'','{}':'','[]':''}; for (let i = 0; i < s.length; i++) { if (s[i] + s[i + 1] in brackets) { i += 1; continue; } if (stack[stack.length - 1] + s[i] in brackets) { stack.pop(); continue; } stack.push(s[i]); } return !stack.length; }
спасибо за контент =) перед решением случайно на глаза попал самый верхний комментарий, где что-то писали про стек и это стало хорошим спойлером решения) время O(n), память O(n) const isValidBrackets1 = (str) => { const brackets = str.split(''); const BRACKETS_WITH_RIGHT_AS_KEY = new Map([[')', '('], [']', '['], ['}', '{']]); const stack = []; for (let bracket of brackets) { const isLeftBracket = [...BRACKETS_WITH_RIGHT_AS_KEY.values()].includes(bracket); if (isLeftBracket) { stack.push(bracket); } else if (stack.at(-1) === BRACKETS_WITH_RIGHT_AS_KEY.get(bracket)) { stack.pop(); } else { return false; } } return stack.length === 0; }
У Вас очень интересные задачки и решения!) Мне друг недавно дал задачку написать функцию, которая принимает в качестве параметра неограниченное количество целых чисел, и возвращает их среднее арифмитическое(сумма делить на количество). Example: sumArgs(3,24,35,16,7) => 17 Которую решила так: function sumArgs() { return [...arguments].reduce((n, s) => n + s) / arguments.length; } Интересно Ваше мнение, может есть ещё какой-то интересный вариант😀
Лучше использовать rest-парамерты, чтобы "собрать" неограниченное число аргументов: developer.mozilla.org/ru/docs/Web/JavaScript/Reference/Functions/rest_parameters Так рекомендуют на MDN, если вы пишите код для поддерживающих ES6+ браузеров или окружений: developer.mozilla.org/ru/docs/Web/JavaScript/Reference/Functions/arguments#description Позвольте также дать вам несколько рекомендаций: 1. Функция вычисляет среднее арифметическое, так и называйте ее - average. 2. Входные данные можно проверять: вдруг в функцию передали не тот тип аргументов или вызвали без них? На заметку: reduce принимает два аргумента - функцию и начальное значение-аккумулятор. Если второе опускается, то им становится значение первого элемента массива. Без проверки входящих данных выглядит близко к вашему варианту: function average1(...nums) { return nums.reduce((n, s) => n + s, 0) / nums.length; } Можно использовать стрелочную функцию: const average2 = (...nums) => (nums.reduce((n, s) => n + s, 0) / nums.length); Интересным вариантом будет разбить функции на несколько, но тогда, чтобы добиться желаемого вами результата, придется их композировать. Зато это позволить переиспользовать каждую в отдельности, а так же композировать их с другими, не имеющими дела к вашей текущей задаче функциями. Пример ручной композиции: const sum = nums => nums.reduce((s, n) => s += n, 0); const length = items => items.length; const average = (...nums) => (sum(nums) / length(nums)); Добра-удачи.
