JavaScript | LeetCode

И вы знаете Поэтому просто ещё раз обозначим, что промокод NETSIL скинет 5000 рублей при бронировании жилья на Яндекс Путешествиях. Забронировать #реклама travel.yandex.ru О рекламодателе

Задача: 846. Hand of Straights Сложность: medium У Алисы есть некоторое количество карт, и она хочет переставить карты в группы так, чтобы каждая группа была размером groupSize и состояла из groupSize последовательных карт. Дан целочисленный массив hand, где hand[i] — это значение, написанное на i-й карте, и целое число groupSize. Верните true, если она может переставить карты, или false в противном случае. Пример: Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3 Output: true Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8] 👨‍💻 Алгоритм: 1⃣Проверьте, делится ли длина массива hand на groupSize. Если нет, верните false. 2⃣Создайте карту cardCount для хранения количества каждой карты в массиве hand. 3⃣Итерируйте по массиву hand и обновляйте карту cardCount. Затем итерируйте снова для создания групп: Найдите начальную карту startCard для потенциальной последовательности, уменьшая startCard, пока не найдёте карту, которая отсутствует в карте cardCount. Попробуйте сформировать последовательность из groupSize карт, начиная с startCard. Если какая-либо карта в потенциальной последовательности отсутствует в карте cardCount, верните false. Если последовательность можно сформировать, уменьшите количество каждой карты в последовательности в карте cardCount. 😎 Решение: var isNStraightHand = function(hand, groupSize) { if (hand.length % groupSize !== 0) { return false; } const cardCount = new Map(); for (let card of hand) { cardCount.set(card, (cardCount.get(card) || 0) + 1); } hand.sort((a, b) => a - b); for (let card of hand) { if (cardCount.get(card) === 0) { continue; } for (let nextCard = card; nextCard < card + groupSize; nextCard++) { if ((cardCount.get(nextCard) || 0) === 0) { return false; } cardCount.set(nextCard, cardCount.get(nextCard) - 1); } } return true; }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 288. Unique Word Abbreviation Сложность: medium Сокращение слова — это объединение его первой буквы, количества символов между первой и последней буквой и последней буквы. Если слово состоит только из двух символов, то оно является сокращением само по себе. Например: dog --> d1g, потому что между первой буквой 'd' и последней буквой 'g' одна буква. internationalization --> i18n, потому что между первой буквой 'i' и последней буквой 'n' 18 букв. it --> it, потому что любое слово из двух символов является своим собственным сокращением. Реализуйте класс ValidWordAbbr: ValidWordAbbr(String[] dictionary) Инициализирует объект со словарем слов. boolean isUnique(string word) Возвращает true, если выполняется одно из следующих условий (в противном случае возвращает false): В словаре нет слова, сокращение которого равно сокращению слова word. Для любого слова в словаре, сокращение которого равно сокращению слова word, это слово и word одинаковы. Пример: Input ["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"] [[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]] Output [null, false, true, false, true, true] Explanation ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]); validWordAbbr.isUnique("dear"); // return false, dictionary word "deer" and word "dear" have the same abbreviation "d2r" but are not the same. validWordAbbr.isUnique("cart"); // return true, no words in the dictionary have the abbreviation "c2t". validWordAbbr.isUnique("cane"); // return false, dictionary word "cake" and word "cane" have the same abbreviation "c2e" but are not the same. validWordAbbr.isUnique("make"); // return true, no words in the dictionary have the abbreviation "m2e". validWordAbbr.isUnique("cake"); // return true, because "cake" is already in the dictionary and no other word in the dictionary has "c2e" abbreviation. 👨‍💻 Алгоритм: 1⃣Инициализация: Создайте словарь сокращений abbrDict, который будет хранить сокращения слов в виде ключей и булевы значения, указывающие, уникально ли сокращение. Создайте множество dict, содержащее все слова из словаря, чтобы быстро проверять наличие слова в словаре. 2⃣Генерация сокращений: При инициализации объекта ValidWordAbbr пройдите через каждое слово в словаре и создайте его сокращение. Если сокращение уже существует в abbrDict, установите значение в false (не уникальное). В противном случае установите значение в true (уникальное). 3⃣Проверка уникальности: Для метода isUnique создайте сокращение для входного слова и проверьте, есть ли это сокращение в abbrDict. Если сокращение отсутствует в abbrDict, возвращайте true. Если сокращение присутствует и оно уникально, проверьте, есть ли это слово в словаре. Если да, возвращайте true, в противном случае - false. 😎 Решение: class ValidWordAbbr { constructor(dictionary) { this.abbrDict = new Map(); this.dict = new Set(dictionary); for (const word of this.dict) { const abbr = this.toAbbr(word); this.abbrDict.set(abbr, !this.abbrDict.get(abbr)); } } isUnique(word) { const abbr = this.toAbbr(word); const hasAbbr = this.abbrDict.get(abbr); return hasAbbr === undefined || (hasAbbr && this.dict.has(word)); } toAbbr(word) { const n = word.length; if (n <= 2) { return word; } return `${word[0]}${n - 2}${word[n - 1]}`; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 209. Minimum Size Subarray Sum Сложность: medium Дан массив положительных целых чисел nums и положительное целое число target. Верните минимальную длину подмассива, сумма которого больше или равна target. Если такого подмассива нет, верните 0. Пример: Input: target = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: The subarray [4,3] has the minimal length under the problem constraint. 👨‍💻 Алгоритм: 1️⃣Инициализация переменных: Создайте три целочисленные переменные left, right и sumOfCurrentWindow. Переменные left и right формируют подмассив, указывая на начальные и конечные индексы текущего подмассива (или окна), а sumOfCurrentWindow хранит сумму этого окна. Инициализируйте все их значением 0. Создайте еще одну переменную res для хранения ответа на задачу. Инициализируйте ее большим целым значением. 2️⃣Итерация по массиву: Итерируйте по массиву nums с помощью right, начиная с right = 0 до nums.length - 1, увеличивая right на 1 после каждой итерации. Выполняйте следующее внутри этой итерации: Добавьте элемент с индексом right к текущему окну, увеличив sumOfCurrentWindow на nums[right]. Проверьте, если sumOfCurrentWindow >= target. Если да, у нас есть подмассив, который удовлетворяет условию. В результате, попытайтесь обновить переменную ответа res длиной этого подмассива. Выполните res = min(res, right - left + 1). Затем удалите первый элемент из этого окна, уменьшив sumOfCurrentWindow на nums[left] и увеличив left на 1. Этот шаг повторяется во внутреннем цикле, пока sumOfCurrentWindow >= target. 3️⃣Возврат результата: Текущая сумма окна теперь меньше target. Нужно добавить больше элементов в окно. В результате, увеличивается right на 1. Верните res. 😎 Решение: class Solution { minSubArrayLen(target, nums) { let left = 0, sumOfCurrentWindow = 0; let res = Number.MAX_VALUE; for (let right = 0; right < nums.length; right++) { sumOfCurrentWindow += nums[right]; while (sumOfCurrentWindow >= target) { res = Math.min(res, right - left + 1); sumOfCurrentWindow -= nums[left]; left++; } } return res === Number.MAX_VALUE ? 0 : res; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 638. Shopping Offers Сложность: medium В магазине LeetCode Store есть n предметов для продажи. Каждый товар имеет свою цену. Однако существуют специальные предложения, и специальное предложение состоит из одного или нескольких различных видов товаров с распродажной ценой. Вам дан целочисленный массив price, где price[i] - цена i-го товара, и целочисленный массив needs, где needs[i] - количество штук i-го товара, который вы хотите купить. Вам также дан массив special, где special[i] имеет размер n + 1, где special[i][j] - количество штук j-го товара в i-м предложении, а special[i][n] (т.е., Возвращает наименьшую цену, которую вы можете заплатить за определенный товар из заданных, где вы могли бы оптимально использовать специальные предложения. Вам не разрешается покупать больше товаров, чем вы хотите, даже если это снизит общую цену. Вы можете использовать любое из специальных предложений столько раз, сколько захотите. Пример: Input: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2] Output: 14 👨‍💻 Алгоритм: 1⃣Рекурсивное вычисление стоимости Определите функцию, которая рекурсивно вычисляет минимальную стоимость для оставшихся нужд, используя динамическое программирование для запоминания уже вычисленных значений. 2⃣Использование специальных предложений Для каждой комбинации товаров в специальных предложениях, определите, можно ли использовать это предложение без превышения нужд. Если можно, вычислите новую стоимость, учитывая это предложение. 3⃣Выбор минимальной стоимости Сравните стоимость при использовании специальных предложений и стоимость при покупке товаров по индивидуальным ценам, выбирая минимальную стоимость. 😎 Решение: var shoppingOffers = function(price, special, needs) { const memo = new Map(); const dfs = (needs) => { const key = needs.join(','); if (memo.has(key)) { return memo.get(key); } let minPrice = needs.reduce((sum, need, i) => sum + need * price[i], 0); for (let offer of special) { const newNeeds = needs.map((need, i) => need - offer[i]); if (newNeeds.every(need => need >= 0)) { minPrice = Math.min(minPrice, offer[offer.length - 1] + dfs(newNeeds)); } } memo.set(key, minPrice); return minPrice; }; return dfs(needs); }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 384. Shuffle an Array Сложность: medium Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания. Реализуйте класс Solution: Solution(int[] nums): Инициализирует объект целочисленным массивом nums. int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его. int[] shuffle(): Возвращает случайное перемешивание массива. Пример: Input: ransomNote = "a", magazine = "b" Output: false 👨‍💻 Алгоритм: 1⃣Алгоритм Фишера-Йейтса удивительно похож на решение грубой силы. На каждой итерации алгоритма мы генерируем случайное целое число между текущим индексом и последним индексом массива. 2⃣Затем мы меняем местами элементы на текущем индексе и выбранном индексе. Это симулирует выбор (и удаление) элемента из "шляпы", так как следующий диапазон, из которого мы выбираем случайный индекс, не будет включать последний обработанный элемент. 3⃣Один небольшой, но важный момент заключается в том, что возможно поменять элемент сам с собой - в противном случае некоторые перестановки массива были бы более вероятны, чем другие. 😎 Решение: class Solution { constructor(nums) { this.original = [...nums]; this.array = [...nums]; } reset() { this.array = [...this.original]; return this.array; } shuffle() { for (let i = 0; i < this.array.length; i++) { const randIndex = Math.floor(Math.random() * (this.array.length - i)) + i; [this.array[i], this.array[randIndex]] = [this.array[randIndex], this.array[i]]; } return this.array; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 646. Maximum Length of Pair Chain Сложность: medium Вам дан массив из n пар, где pairs[i] = [lefti, righti] и lefti < righti. Пара p2 = [c, d] следует за парой p1 = [a, b], если b < c. Таким образом можно построить цепочку пар. Верните самую длинную цепочку, которую можно составить. Вам не нужно использовать все заданные интервалы. Вы можете выбирать пары в любом порядке. Пример: Input: nums = [1,2,2,4] Output: [2,3] 👨‍💻 Алгоритм: 1⃣Отсортируйте пары по второму элементу каждой пары (righti). 2⃣Используйте динамическое программирование или жадный алгоритм, чтобы построить цепочку максимальной длины. 3⃣Переберите отсортированные пары и выберите пары, которые могут следовать одна за другой, увеличивая длину цепочки. 😎 Решение: function findLongestChain(pairs) { pairs.sort((a, b) => a[1] - b[1]); let currentEnd = Number.MIN_SAFE_INTEGER; let count = 0; for (const pair of pairs) { if (currentEnd < pair[0]) { currentEnd = pair[1]; count++; } } return count; } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1039. Minimum Score Triangulation of Polygon Сложность: medium У вас есть выпуклый n-сторонний многоугольник, каждая вершина которого имеет целочисленное значение. Вам дан целочисленный массив values, где values[i] - это значение i-й вершины (т.е. по часовой стрелке). Вы должны триангулировать многоугольник на n - 2 треугольника. Для каждого треугольника значение этого треугольника равно произведению значений его вершин, а общий балл триангуляции равен сумме этих значений для всех n - 2 треугольников в триангуляции. Верните наименьший возможный общий балл, который вы можете получить с помощью некоторой триангуляции многоугольника. Пример: Input: values = [1,2,3] Output: 6 👨‍💻 Алгоритм: 1⃣Инициализация: Создаем двумерный массив dp, где dp[i][j] будет хранить минимальный возможный общий балл триангуляции многоугольника, состоящего из вершин от i до j. 2⃣Основное заполнение dp: Проходим по всем возможным длинам подмногоугольников, начиная с треугольников (длина 3) до всего многоугольника (длина n). Для каждого подмногоугольника находим минимальный возможный общий балл, проверяя все возможные треугольники, которые могут быть образованы из этого подмногоугольника. Заполнение dp для каждого подмногоугольника: Для каждого подмногоугольника от i до j, и для каждой возможной вершины k между i и j, обновляем значение dp[i][j], как сумму минимальных значений триангуляций левой и правой частей подмногоугольника, а также значения текущего треугольника, образованного вершинами i, k и j. 3⃣Возврат результата: Ответ будет в dp[0][n-1], который хранит минимальный возможный общий балл триангуляции для всего многоугольника. 😎 Решение: var minScoreTriangulation = function(values) { const n = values.length; const dp = Array.from({ length: n }, () => Array(n).fill(0)); for (let length = 2; length < n; length++) { for (let i = 0; i < n - length; i++) { const j = i + length; dp[i][j] = Infinity; for (let k = i + 1; k < j; k++) { dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]); } } } return dp[0][n - 1]; }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 232. Implement Queue using Stacks Сложность: easy Реализуйте очередь (FIFO) с использованием только двух стеков. Реализованная очередь должна поддерживать все функции обычной очереди (push, peek, pop и empty). Реализуйте класс MyQueue: void push(int x) добавляет элемент x в конец очереди. int pop() удаляет элемент из начала очереди и возвращает его. int peek() возвращает элемент из начала очереди. boolean empty() возвращает true, если очередь пуста, и false в противном случае. Пример: Input ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] Output [null, null, null, 1, 1, false] Explanation MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false 👨‍💻 Алгоритм: 1⃣Добавление элемента: Для метода push(int x) переместите все элементы из стека s1 в стек s2. Добавьте элемент x в стек s2. Затем переместите все элементы обратно из стека s2 в стек s1. Если стек s1 пуст, обновите переменную front значением x. 2⃣Удаление и проверка первого элемента: Для метода pop() удалите элемент из начала очереди, извлекая верхний элемент из стека s1. Обновите переменную front на новый верхний элемент стека s1, если он не пуст. Для метода peek() верните значение переменной front, так как она всегда хранит первый элемент очереди. 3⃣Проверка на пустоту: Для метода empty() верните результат проверки, является ли стек s1 пустым. 😎 Решение: class MyQueue { constructor() { this.s1 = []; this.s2 = []; this.front = null; } push(x) { if (this.s1.length === 0) { this.front = x; } while (this.s1.length > 0) { this.s2.push(this.s1.pop()); } this.s2.push(x); while (this.s2.length > 0) { this.s1.push(this.s2.pop()); } } pop() { const res = this.s1.pop(); if (this.s1.length > 0) { this.front = this.s1[this.s1.length - 1]; } return res; } empty() { return this.s1.length === 0; } peek() { return this.front; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 283. Move Zeroes Сложность: easy Дан целочисленный массив nums. Переместите все нули в конец массива, сохраняя относительный порядок ненулевых элементов. Обратите внимание, что вы должны сделать это на месте, не создавая копию массива. Пример: Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0] 👨‍💻 Алгоритм: 1⃣Инициализация указателей: Инициализируйте два указателя: lastNonZeroFoundAt для отслеживания позиции последнего ненулевого элемента и cur для итерации по массиву. 2⃣Итерация и обмен элементами: Итерируйтесь по массиву с помощью указателя cur. Если текущий элемент ненулевой, поменяйте его местами с элементом, на который указывает lastNonZeroFoundAt, и продвиньте указатель lastNonZeroFoundAt. 3⃣Завершение итерации: Повторяйте шаг 2 до конца массива. В итоге все нули будут перемещены в конец массива, сохраняя относительный порядок ненулевых элементов. 😎 Решение: var moveZeroes = function(nums) { let lastNonZeroFoundAt = 0; for (let cur = 0; cur < nums.length; cur++) { if (nums[cur] != 0) { [nums[lastNonZeroFoundAt], nums[cur]] = [nums[cur], nums[lastNonZeroFoundAt]]; lastNonZeroFoundAt++; } } }; Ставь 👍 и забирай 📚 Базу знаний