JavaScript | LeetCode

Задача: 541. Reverse String II Сложность: easy Дана строка s и целое число k, переверните первые k символов для каждых 2k символов, начиная с начала строки. Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть. Пример: Input: s = "abcdefg", k = 2 Output: "bacdfeg" 👨‍💻 Алгоритм: 1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее. 2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут. 3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--. 😎 Решение: class Solution { reverseStr(s, k) { let a = s.split(''); for (let start = 0; start < a.length; start += 2 * k) { let i = start, j = Math.min(start + k - 1, a.length - 1); while (i < j) { [a[i], a[j]] = [a[j], a[i]]; i++; j--; } } return a.join(''); } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 442. Find All Duplicates in an Array Сложность: medium Дан целочисленный массив nums длины n, где все целые числа nums находятся в диапазоне [1, n], и каждое число появляется один или два раза. Верните массив всех чисел, которые появляются дважды. Вы должны написать алгоритм, который работает за время O(n) и использует только постоянное дополнительное пространство. Пример: Input: nums = [4,3,2,7,8,2,3,1] Output: [2,3] 👨‍💻 Алгоритм: 1⃣Когда мы итерируемся по элементам входного массива, мы можем просто искать любое другое вхождение текущего элемента в оставшейся части массива. 2⃣Поскольку элемент может появляться только один или два раза, нам не нужно беспокоиться о получении дубликатов элементов, которые появляются дважды: Случай I: Если элемент встречается в массиве только один раз, при поиске его в остальной части массива ничего не найдется. Случай II: Если элемент встречается дважды, вы найдете второе вхождение элемента в оставшейся части массива. Когда вы наткнетесь на второе вхождение в более поздней итерации, это будет аналогично случаю I (поскольку больше вхождений этого элемента в оставшейся части массива не будет). 3⃣Таким образом, можно эффективно определить все элементы, которые встречаются дважды, и добавить их в результирующий массив, проходя по каждому элементу массива и проверяя наличие его второго вхождения в оставшейся части массива. 😎 Решение: var findDuplicates = function(nums) { let ans = []; for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[j] === nums[i]) { ans.push(nums[i]); break; } } } return ans; }; Ставь 👍 и забирай 📚 Базу знаний

🔴 Тестовое собеседование на Frontend-разработчика со старшим разработчиком ex. Сбер 13 августа(в четверг!) в 19:00 по мск приходи онлайн на открытое собеседование, чтобы посмотреть на настоящее интервью на Middle Frontend-разработчика. Как это будет: 📂 Даниил Дмитриев, старший разработчик в R-Vision, ex. Сбер, будет задавать реальные вопросы и задачи разработчику-добровольцу 📂 Даниил будет комментировать каждый ответ респондента, чтобы дать понять, чего от вас ожидает собеседующий на интервью 📂 В конце можно будет задать любой вопрос Даниилу Это бесплатно. Эфир проходит в рамках менторской программы от ШОРТКАТ для Frontend-разработчиков, которые хотят повысить свой грейд, ЗП и прокачать скиллы. Переходи в нашего бота, чтобы получить ссылку на эфир → @shortcut_front_bot Реклама. О рекламодателе.

Задача: 668. Kth Smallest Number in Multiplication Table Сложность: hard Почти каждый использовал таблицу умножения. Таблица умножения размером m x n - это целочисленная матрица mat, где mat[i][j] == i * j (индексация начинается с 1). Даны три целых числа m, n и k. Верните k-й наименьший элемент в таблице умножения размером m x n. Пример: Input: m = 3, n = 3, k = 5 Output: 3 Explanation: The 5th smallest number is 3. 👨‍💻 Алгоритм: 1⃣Установка границ поиска: Установите нижнюю границу left равной 1 и верхнюю границу right равной m * n. 2⃣Бинарный поиск: Используйте бинарный поиск, чтобы найти k-й наименьший элемент. Для каждого среднего значения mid, посчитайте количество элементов в таблице умножения, которые меньше или равны mid. 3⃣Проверка количества элементов: Если количество элементов меньше k, увеличьте нижнюю границу (left). Если количество элементов больше или равно k, уменьшите верхнюю границу (right). 😎 Решение: var findKthNumber = function(m, n, k) { let left = 1, right = m * n; while (left < right) { let mid = Math.floor((left + right) / 2); if (countLessEqual(m, n, mid) < k) { left = mid + 1; } else { right = mid; } } return left; }; function countLessEqual(m, n, x) { let count = 0; for (let i = 1; i <= m; i++) { count += Math.min(Math.floor(x / i), n); } return count; } Ставь 👍 и забирай 📚 Базу знаний

Задача: 334. Increasing Triplet Subsequence Сложность: medium Дан массив целых чисел nums. Верните true, если существуют такие три индекса (i, j, k), что i < j < k и nums[i] < nums[j] < nums[k]. Если таких индексов не существует, верните false. Пример: Input: nums = [2,1,5,0,4,6] Output: true Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6. 👨‍💻 Алгоритм: 1⃣Инициализация переменных: Создайте две переменные first_num и second_num и установите их значение на максимальное целое значение (Integer.MAX_VALUE или аналогичный максимум для выбранного языка программирования). Эти переменные будут хранить минимальные значения, необходимые для проверки существования возрастающей тройки. 2⃣Итерация по массиву: Пройдите по каждому элементу массива nums. Для каждого элемента выполните следующие проверки: - если текущий элемент меньше или равен first_num, обновите first_num текущим элементом. - иначе, если текущий элемент меньше или равен second_num, обновите second_num текущим элементом. - иначе, если текущий элемент больше second_num, это означает, что найдена возрастающая тройка, поэтому верните true. 3⃣Возврат результата: Если после завершения итерации по массиву не была найдена возрастающая тройка, верните false. 😎 Решение: var increasingTriplet = function(nums) { let firstNum = Infinity; let secondNum = Infinity; for (let n of nums) { if (n <= firstNum) { firstNum = n; } else if (n <= secondNum) { secondNum = n; } else { return true; } } return false; }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 1268. Search Suggestions System Сложность: medium Вам дан массив строк products и строка searchWord. Разработайте систему, которая предлагает не более трех названий продуктов после ввода каждого символа searchWord. Предлагаемые товары должны иметь общий префикс с searchWord. Если есть более трех продуктов с общим префиксом, возвращаются три лексикографически минимальных продукта. Возвращается список списков предложенных продуктов после ввода каждого символа searchWord. Пример: Input: products = ["havana"], searchWord = "havana" Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]] 👨‍💻 Алгоритм: 1⃣Отсортируйте массив продуктов. 2⃣Итерируйтесь по каждому символу в searchWord, находите все продукты, которые соответствуют текущему префиксу. 3⃣Сохраняйте не более трех лексикографически минимальных продуктов для каждого префикса. 😎 Решение: var suggestedProducts = function(products, searchWord) { products.sort(); let result = []; let prefix = ""; for (let char of searchWord) { prefix += char; let suggestions = products.filter(product => product.startsWith(prefix)).slice(0, 3); result.push(suggestions); } return result; }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 57. Insert Interval Сложность: medium Вам дан массив непересекающихся интервалов intervals, где intervals[i] = [starti, endi] представляет начало и конец i-го интервала, и массив intervals отсортирован в порядке возрастания по starti. Вам также дан интервал newInterval = [start, end], представляющий начало и конец другого интервала. Вставьте newInterval в массив intervals так, чтобы intervals оставался отсортированным в порядке возрастания по starti и в intervals не было бы перекрывающихся интервалов (при необходимости объедините перекрывающиеся интервалы). Верните массив intervals после вставки. Обратите внимание, что не обязательно модифицировать массив intervals на месте. Вы можете создать новый массив и вернуть его. Пример: Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]] 👨‍💻 Алгоритм: 1️⃣ Инициализация переменных: Инициализируются переменные n и i для хранения размера массива интервалов и текущего индекса соответственно, а также пустой массив res для хранения результата. 2️⃣Обработка случаев без перекрытия и с перекрытием: В случае отсутствия перекрытия до вставки, проходим через массив интервалов до тех пор, пока конечная точка текущего интервала меньше начальной точки нового интервала. Добавляем текущий интервал в массив res и переходим к следующему. В случае перекрытия, продолжаем обход, пока начальная точка нового интервала меньше или равна конечной точке текущего интервала. Обновляем начальные и конечные точки нового интервала, объединяя перекрывающиеся интервалы в один. 3️⃣Обработка интервалов после вставки: Проходим через оставшиеся интервалы после индекса i и добавляем их в массив res. Это включает интервалы, которые следуют после нового интервала и не перекрываются с ним. Возвращаем массив res, содержащий все интервалы с корректно вставленным новым интервалом. 😎 Решение: var insert = function (intervals, newInterval) { let n = intervals.length, i = 0, res = []; while (i < n && intervals[i][1] < newInterval[0]) { res.push(intervals[i]); i++; } while (i < n && newInterval[1] >= intervals[i][0]) { newInterval[0] = Math.min(newInterval[0], intervals[i][0]); newInterval[1] = Math.max(newInterval[1], intervals[i][1]); i++; } res.push(newInterval); while (i < n) { res.push(intervals[i]); i++; } return res; }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 40. Combination Sum II Сложность: medium Дан массив целых чисел candidates и целевое число target. Нужно найти все уникальные комбинации, где числа из candidates в сумме дают target. Каждое число можно использовать только один раз в комбинации. Результаты не должны содержать повторяющихся комбинаций. Пример: Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [[1,1,6],[1,2,5],[1,7],[2,6]] 👨‍💻 Алгоритм: 1⃣ Отсортировать массив candidates для возможности пропуска дубликатов. 2⃣. Запустить рекурсивную функцию backtrack(start, trackSum): - Если trackSum == target — сохранить копию текущей комбинации - Если trackSum > target — прекратить ветку - На каждом шаге пропускать повторяющиеся элементы (если i > start && nums[i] == nums[i - 1]) - Не переиспользовать текущий элемент — следующий вызов с i + 1 3⃣ Использовать track для текущей комбинации и trackSum для суммы 😎 Решение: var combinationSum2 = function(candidates, target) { const res = []; const track = []; let trackSum = 0; const backtrack = (nums, start) => { if (trackSum === target) { res.push([...track]); return; } if (trackSum > target) return; for (let i = start; i < nums.length; i++) { if (i > start && nums[i] === nums[i - 1]) continue; track.push(nums[i]); trackSum += nums[i]; backtrack(nums, i + 1); track.pop(); trackSum -= nums[i]; } } candidates.sort((a, b) => a - b); backtrack(candidates, 0); return res; }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 1151. Minimum Swaps to Group All 1's Together Сложность: medium Дан бинарный массив data, необходимо вернуть минимальное количество перестановок, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте массива. Пример: Input: data = [1,0,1,0,1] Output: 1 Explanation: There are 3 ways to group all 1's together: [1,1,1,0,0] using 1 swap. [0,1,1,1,0] using 2 swaps. [0,0,1,1,1] using 1 swap. The minimum is 1. 👨‍💻 Алгоритм: 1⃣Используем два указателя, left и right, чтобы поддерживать скользящее окно длиной ones и проверяем каждый фрагмент массива data, подсчитывая количество единиц в нем (cnt_one) и запоминая максимальное значение max_one. 2⃣Пока окно скользит по массиву data, поддерживаем его длину равной ones. 3⃣Обновляем количество единиц в окне, добавляя новую границу data[right] и вычитая левую границу data[left]. 😎 Решение: var minSwaps = function(data) { const ones = data.reduce((a, b) => a + b, 0); let cnt_one = 0, max_one = 0; let left = 0, right = 0; while (right < data.length) { cnt_one += data[right++]; if (right - left > ones) { cnt_one -= data[left++]; } max_one = Math.max(max_one, cnt_one); } return ones - max_one; }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 172. Factorial Trailing Zeroes Сложность: medium Дано целое число n, верните количество конечных нулей в n!. Обратите внимание, что n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1. Пример: Input: n = 3 Output: 0 Explanation: 3! = 6, no trailing zero. 👨‍💻 Алгоритм: 1️⃣Вычислите факториал n: Инициализируйте переменную nFactorial значением 1. Для каждого i от 2 до n включительно умножайте nFactorial на i. 2️⃣Подсчитайте количество конечных нулей в nFactorial: Инициализируйте переменную zeroCount значением 0. Пока nFactorial делится на 10 без остатка, делите его на 10 и увеличивайте zeroCount на 1. 3️⃣Верните значение zeroCount как количество конечных нулей в n!. 😎 Решение: var trailingZeroes = function (n) { let nFactorial = BigInt(1); for (let i = 2; i <= n; i++) { nFactorial *= BigInt(i); } let zeroCount = 0; const ten = BigInt(10); while (nFactorial % ten === BigInt(0)) { nFactorial /= ten; zeroCount++; } return zeroCount; }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 789. Escape The Ghosts Сложность: medium Вы играете в упрощенную игру PAC-MAN на бесконечной 2D-сетке. Вы начинаете в точке [0, 0], и у вас есть конечная точка target = [xtarget, ytarget], к которой вы пытаетесь добраться. На карте находятся несколько привидений, их начальные позиции заданы в виде двумерного массива ghosts, где ghosts[i] = [xi, yi] представляет начальную позицию i-го привидения. Все входные данные являются целочисленными координатами. Каждый ход вы и все привидения можете независимо выбирать перемещение на 1 единицу в любом из четырех основных направлений: север, восток, юг или запад, или оставаться на месте. Все действия происходят одновременно. Вы сможете сбежать, если и только если сможете достичь цели раньше, чем любое привидение достигнет вас. Если вы достигнете любой клетки (включая конечную точку) одновременно с привидением, это не считается побегом. Верните true, если можно сбежать независимо от того, как движутся привидения, иначе верните false. Пример: Input: ghosts = [[1,0],[0,3]], target = [0,1] Output: true Explanation: You can reach the destination (0, 1) after 1 turn, while the ghosts located at (1, 0) and (0, 3) cannot catch up with you. 👨‍💻 Алгоритм: 1⃣Проверьте, что наше таксическое расстояние до цели меньше, чем расстояние от любого привидения до цели. 2⃣Если это так, мы можем гарантированно добраться до цели раньше любого привидения. 3⃣Если привидение может добраться до цели раньше нас или одновременно с нами, побег невозможен. 😎 Решение: class Solution { escapeGhosts(ghosts, target) { const taxi = (P, Q) => Math.abs(P[0] - Q[0]) + Math.abs(P[1] - Q[1]); const playerDistance = taxi([0, 0], target); return ghosts.every(ghost => taxi(ghost, target) > playerDistance); } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1208. Get Equal Substrings Within Budget Сложность: medium Вам даны две строки s и t одинаковой длины и целое число maxCost. Вы хотите преобразовать s в t. Изменение i-го символа строки s на i-й символ строки t стоит |s[i] - t[i]| (т.е. абсолютная разница между значениями ASCII символов). Верните максимальную длину подстроки s, которую можно изменить, чтобы она соответствовала соответствующей подстроке t с затратами, не превышающими maxCost. Если нет подстроки из s, которую можно изменить на соответствующую подстроку из t, верните 0. Пример: Input: s = "abcd", t = "bcdf", maxCost = 3 Output: 3 Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3. 👨‍💻 Алгоритм: 1⃣Инициализация переменных: maxLen для хранения максимальной длины подстроки с затратами, не превышающими maxCost. start для хранения начального индекса текущей подстроки. currCost для хранения текущих затрат на преобразование подстроки s в t. 2⃣Итерация по индексам от 0 до N-1: Добавить текущие затраты на преобразование символа s[i] в t[i] к currCost. Удалять элементы с левого конца, уменьшая затраты до тех пор, пока currCost не станет меньше или равным maxCost. Обновить maxLen длиной текущей подстроки. 3⃣Возврат maxLen как результата. 😎 Решение: var equalSubstring = function(s, t, maxCost) { const N = s.length; let maxLen = 0; let start = 0; let currCost = 0; for (let i = 0; i < N; i++) { currCost += Math.abs(s.charCodeAt(i) - t.charCodeAt(i)); while (currCost > maxCost) { currCost -= Math.abs(s.charCodeAt(start) - t.charCodeAt(start)); start++; } maxLen = Math.max(maxLen, i - start + 1); } return maxLen; }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 650. 2 Keys Keyboard Сложность: medium На экране блокнота есть только один символ 'A'. Для каждого шага можно выполнить одну из двух операций над этим блокнотом: Copy All: скопировать все символы, присутствующие на экране (частичное копирование не допускается). Paste: Вы можете вставить символы, которые были скопированы в прошлый раз. Учитывая целое число n, верните минимальное количество операций, чтобы символ 'A' появился на экране ровно n раз. Пример: Input: n = 3 Output: 3 👨‍💻 Алгоритм: 1⃣Используйте динамическое программирование для отслеживания минимального количества операций, необходимых для достижения определенного количества 'A' на экране. 2⃣Итерируйтесь от 1 до n, проверяя все возможные делители текущего числа и обновляя минимальное количество операций для каждого числа. 3⃣Возвращайте значение из таблицы динамического программирования для n. 😎 Решение: var minSteps = function(n) { if (n === 1) return 0; const dp = new Array(n + 1).fill(0); for (let i = 2; i <= n; i++) { dp[i] = i; for (let j = 1; j <= i / 2; j++) { if (i % j === 0) { dp[i] = Math.min(dp[i], dp[j] + i / j); } } } return dp[n]; }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 1472. Design Browser History Сложность: medium У вас есть браузер с одной вкладкой, где вы начинаете на домашней странице и можете посетить другой URL, вернуться назад на определённое количество шагов в истории или переместиться вперёд на определённое количество шагов в истории. Реализуйте класс BrowserHistory: BrowserHistory(string homepage) Инициализирует объект с домашней страницей браузера. void visit(string url) Посещает URL с текущей страницы. Это очищает всю историю вперёд. string back(int steps) Перемещает на steps шагов назад в истории. Если вы можете вернуться только на x шагов в истории, а steps > x, вы вернётесь только на x шагов. Возвращает текущий URL после перемещения назад в истории на не более чем steps шагов. string forward(int steps) Перемещает на steps шагов вперёд в истории. Если вы можете переместиться только на x шагов вперёд в истории, а steps > x, вы переместитесь только на x шагов. Возвращает текущий URL после перемещения вперёд в истории на не более чем steps шагов. Пример: Input: ["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"] [["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]] Output: [null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"] Explanation: BrowserHistory browserHistory = new BrowserHistory("leetcode.com"); browserHistory.visit("google.com"); // You are in "leetcode.com". Visit "google.com" browserHistory.visit("facebook.com"); // You are in "google.com". Visit "facebook.com" browserHistory.visit("youtube.com"); // You are in "facebook.com". Visit "youtube.com" browserHistory.back(1); // You are in "youtube.com", move back to "facebook.com" return "facebook.com" browserHistory.back(1); // You are in "facebook.com", move back to "google.com" return "google.com" browserHistory.forward(1); // You are in "google.com", move forward to "facebook.com" return "facebook.com" browserHistory.visit("linkedin.com"); // You are in "facebook.com". Visit "linkedin.com" browserHistory.forward(2); // You are in "linkedin.com", you cannot move forward any steps. 👨‍💻 Алгоритм: 1⃣Инициализация: Создайте класс BrowserHistory с двумя стеками (history и future) и строковой переменной current для хранения текущего URL. Инициализируйте current с домашней страницей. 2⃣Посещение URL: Метод visit(url) сохраняет текущий URL в стеке history, устанавливает url как текущий и очищает стек future. 3⃣Навигация назад и вперед: Метод back(steps) перемещает текущий URL в стек future и извлекает URL из стека history, пока шаги не будут исчерпаны или стек history не станет пустым. Метод forward(steps) перемещает текущий URL в стек history и извлекает URL из стека future, пока шаги не будут исчерпаны или стек future не станет пустым. 😎 Решение: class BrowserHistory { constructor(homepage) { this.history = []; this.future = []; this.current = homepage; } visit(url) { this.history.push(this.current); this.current = url; this.future = []; } back(steps) { while (steps > 0 && this.history.length > 0) { this.future.push(this.current); this.current = this.history.pop(); steps--; } return this.current; } forward(steps) { while (steps > 0 && this.future.length > 0) { this.history.push(this.current); this.current = this.future.pop(); steps--; } return this.current; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1062. Longest Repeating Substring Сложность: medium Дана строка s. Вернуть длину самой длинной повторяющейся подстроки. Если повторяющаяся подстрока отсутствует, вернуть 0. Пример: Input: s = "abcd" Output: 0 Explanation: There is no repeating substring. 👨‍💻 Алгоритм: 1⃣Перемещайте скользящее окно длиной L по строке длиной N. 2⃣Проверьте, находится ли строка в скользящем окне в хэш-наборе уже виденных строк. Если да, то повторяющаяся подстрока находится здесь. Если нет, сохраните строку из скользящего окна в хэш-наборе. 3⃣Очевидный недостаток этого подхода — большое потребление памяти в случае длинных строк. 😎 Решение: class Solution { search(L, n, S) { const seen = new Set(); for (let start = 0; start <= n - L; ++start) { const tmp = S.substring(start, start + L); if (seen.has(tmp)) return start; seen.add(tmp); } return -1; } longestRepeatingSubstring(S) { const n = S.length; let left = 1, right = n; while (left <= right) { const L = left + Math.floor((right - left) / 2); if (this.search(L, n, S) !== -1) { left = L + 1; } else { right = L - 1; } } return left - 1; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1370. Increasing Decreasing String Сложность: easy Дана строка s. Переставьте символы строки, используя следующий алгоритм: Выберите наименьший символ из s и добавьте его к результату. Выберите наименьший символ из s, который больше последнего добавленного символа, и добавьте его. Повторяйте шаг 2, пока не сможете выбрать больше символов. Выберите наибольший символ из s и добавьте его к результату. Выберите наибольший символ из s, который меньше последнего добавленного символа, и добавьте его. Повторяйте шаг 5, пока не сможете выбрать больше символов. Повторяйте шаги с 1 по 6, пока не выберете все символы из s. На каждом этапе, если наименьший или наибольший символ появляется более одного раза, вы можете выбрать любое его вхождение и добавить его к результату. Верните результирующую строку после сортировки s с помощью этого алгоритма. Пример: Input: s = "rat" Output: "art" Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm. 👨‍💻 Алгоритм: 1⃣Инициализация и сортировка: Создайте словарь для подсчета количества каждого символа в строке s. Создайте результирующую строку result. 2⃣Перебор и добавление символов: Используйте два цикла: первый для добавления символов в возрастающем порядке, второй — в убывающем. В каждом цикле добавляйте символы к результату, обновляя их количество в словаре. 3⃣Проверка завершения: Повторяйте шаги 2 и 3, пока не будут добавлены все символы из строки s в result. 😎 Решение: var sortString = function(s) { const charCount = new Array(26).fill(0); for (const c of s) { charCount[c.charCodeAt(0) - 'a'.charCodeAt(0)]++; } let result = ''; while (result.length < s.length) { for (let c = 0; c < 26; c++) { if (charCount[c] > 0) { result += String.fromCharCode(c + 'a'.charCodeAt(0)); charCount[c]--; } } for (let c = 25; c >= 0; c--) { if (charCount[c] > 0) { result += String.fromCharCode(c + 'a'.charCodeAt(0)); charCount[c]--; } } } return result; }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 1036. Escape a Large Maze Сложность: hard Имеется сетка размером 1 миллион на 1 миллион на плоскости XY, координаты каждого квадрата сетки - (x, y). Мы начинаем с исходного квадрата = [sx, sy] и хотим достичь цели = [tx, ty]. Существует также массив заблокированных квадратов, где каждый заблокированный[i] = [xi, yi] представляет собой заблокированный квадрат с координатами (xi, yi). Каждый ход мы можем пройти один квадрат на север, восток, юг или запад, если квадрат не находится в массиве заблокированных квадратов. Нам также не разрешается выходить за пределы сетки. Возвращается true тогда и только тогда, когда можно достичь целевого квадрата из исходного квадрата с помощью последовательности правильных ходов. Пример: Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2] Output: false 👨‍💻 Алгоритм: 1⃣Обработка входных данных: Загрузите координаты исходного квадрата sx, sy, целевого квадрата tx, ty и список заблокированных квадратов blocked. 2⃣Проверка простого случая: Если список blocked пуст, верните true, так как путь не будет заблокирован. Проверка начальной или целевой клетки: Если исходная или целевая клетка заблокированы, верните false. 3⃣Поиск пути с использованием BFS или DFS: Используйте алгоритм поиска в ширину (BFS) или поиска в глубину (DFS) для поиска пути от sx, sy до tx, ty, избегая заблокированных клеток. Если обнаружен путь, верните true, в противном случае верните false. 😎 Решение: var isEscapePossible = function(blocked, source, target) { const blockedSet = new Set(blocked.map(b => `${b[0]},${b[1]}`)); const src = `${source[0]},${source[1]}`; const tgt = `${target[0]},${target[1]}`; if (blockedSet.has(src) || blockedSet.has(tgt)) return false; const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]; const maxArea = blocked.length * (blocked.length - 1) / 2; const bfs = (start, end) => { const queue = [start]; const visited = new Set([start]); while (queue.length) { if (visited.size > maxArea) return true; const [x, y] = queue.shift().split(',').map(Number); for (const [dx, dy] of directions) { const nx = x + dx, ny = y + dy; const next = `${nx},${ny}`; if (nx >= 0 && nx < 1_000_000 && ny >= 0 && ny < 1_000_000 && !visited.has(next) && !blockedSet.has(next)) { if (next === end) return true; queue.push(next); visited.add(next); } } } return false; }; return bfs(src, tgt) && bfs(tgt, src); }; Ставь 👍 и забирай 📚 Базу знаний