JavaScript | LeetCode

Задача: 343. Integer Break
Сложность: medium

Дано целое число n. Верните true, если оно является степенью числа четыре. В противном случае верните false.

Целое число n является степенью числа четыре, если существует целое число x такое, что n == 4^x.

Пример:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

👨‍💻 Алгоритм:

1⃣Инициализация и базовый случай:
Создайте массив dp длиной n + 1, где dp[i] будет хранить максимальное произведение для числа i. Инициализируйте массив нулями.

2⃣Вычисление максимального произведения:
Для каждого числа i от 2 до n:
Для каждого числа j от 1 до i // 2:
Обновите dp[i] как максимальное значение между текущим dp[i], произведением j и i - j, и произведением j и dp[i - j].

3⃣Возврат результата:
Верните значение dp[n], которое будет максимальным произведением для числа n.

😎 Решение:

var integerBreak = function(n) {
    if (n <= 1) return 0;
    
    let dp = new Array(n + 1).fill(0);
    
    for (let i = 2; i <= n; i++) {
        for (let j = 1; j <= Math.floor(i / 2); j++) {
            dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
        }
    }
    
    return dp[n];
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 309. Best Time to Buy and Sell Stock with Cooldown
Сложность: medium

Дан массив prices, где prices[i] — цена данной акции в i-й день.
Найдите максимальную прибыль, которую можно получить. Вы можете совершить любое количество транзакций (т. е. купить и продать одну акцию несколько раз) с следующими ограничениями:
После продажи акции вы не можете покупать акции на следующий день (т. е. необходимо один день подождать).

Пример:

Input: prices = [1]
Output: 0

👨‍💻 Алгоритм:

1⃣Инициализация состояний
Используйте три состояния для отслеживания максимальной прибыли: hold: максимальная прибыль на данный день, если у вас есть акция. sold: максимальная прибыль на данный день, если вы продали акцию. cooldown: максимальная прибыль на данный день, если вы находитесь в периоде ожидания после продажи.

2⃣Обновление состояний
Итерируйте по каждому дню, обновляя состояния: hold: максимальная прибыль, если у вас есть акция на текущий день. sold: максимальная прибыль, если вы продаете акцию на текущий день. cooldown: максимальная прибыль, если вы находитесь в периоде ожидания на текущий день.

3⃣Определение максимальной прибыли
В конце итерации максимальная прибыль будет максимальным значением между состояниями sold и cooldown, так как hold состояние не может быть конечным состоянием для получения максимальной прибыли.

😎 Решение:

var maxProfit = function(prices) {
    if (prices.length === 0) return 0;
    
    let hold = -prices[0];
    let sold = 0;
    let cooldown = 0;
    
    for (let i = 1; i < prices.length; i++) {
        let newHold = Math.max(hold, cooldown - prices[i]);
        let newSold = hold + prices[i];
        let newCooldown = Math.max(cooldown, sold);
        
        hold = newHold;
        sold = newSold;
        cooldown = newCooldown;
    }
    
    return Math.max(sold, cooldown);
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1357. Apply Discount Every n Orders
Сложность: medium

В супермаркете, который посещает множество покупателей, товары представлены двумя параллельными массивами целых чисел products и prices, где i-й товар имеет идентификатор products[i] и цену prices[i].

Когда покупатель оплачивает товар, его счет представлен двумя параллельными массивами целых чисел product и amount, где j-й приобретенный товар имеет идентификатор product[j], а amount[j] - количество купленного товара. Их промежуточный итог рассчитывается как сумма каждого amount[j] * (цена j-го товара).

Супермаркет решил провести распродажу. Каждому n-му покупателю, оплачивающему свои покупки, будет предоставлена скидка в процентах. Сумма скидки задается параметром discount, и покупатель получит скидку в discount процентов от своего промежуточного итога. Формально, если их промежуточный итог составляет bill, то они фактически заплатят bill * ((100 - discount) / 100).

Реализуйте класс Cashier:

Cashier(int n, int discount, int[] products, int[] prices): инициализирует объект с параметрами n, discount, а также массивами товаров и их цен.
double getBill(int[] product, int[] amount): возвращает итоговую сумму счета с примененной скидкой (если применима). Ответы, отличающиеся от фактического значения не более чем на 10^-5, будут приняты.

Пример:

Input
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
Output
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]

👨‍💻 Алгоритм:

1⃣Инициализация объекта:
Создайте класс Cashier с конструктором, который принимает параметры n, discount, products и prices. В конструкторе инициализируйте необходимые переменные и создайте словарь для сопоставления идентификаторов продуктов с их ценами.

2⃣Обработка каждого счета:
Создайте метод getBill, который принимает массивы product и amount.
Вычислите промежуточный итог счета, умножая количество каждого продукта на его цену и суммируя результаты.
Увеличьте счетчик клиентов. Если клиент является n-м по счету, примените скидку к промежуточному итогу.

3⃣Верните итоговую сумму счета.

😎 Решение:

class Cashier {
    constructor(n, discount, products, prices) {
        this.n = n;
        this.discount = discount;
        this.productsPrices = new Map();
        this.customerCount = 0;
        
        for (let i = 0; i < products.length; i++) {
            this.productsPrices.set(products[i], prices[i]);
        }
    }

    getBill(product, amount) {
        this.customerCount++;
        let bill = 0.0;
        
        for (let i = 0; i < product.length; i++) {
            bill += this.productsPrices.get(product[i]) * amount[i];
        }
        
        if (this.customerCount % this.n === 0) {
            bill *= (100 - this.discount) / 100.0;
        }
        
        return bill;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 517. Super Washing Machines
Сложность: hard

У вас есть n супер стиральных машин, расположенных в одну линию. Изначально каждая стиральная машина содержит некоторое количество платьев или пуста.
За один ход вы можете выбрать любые m (1 <= m <= n) стиральные машины и одновременно передать одно платье из каждой выбранной машины в одну из её соседних стиральных машин.
Дан целочисленный массив machines, представляющий количество платьев в каждой стиральной машине слева направо по линии. Верните минимальное количество ходов, необходимых для того, чтобы во всех стиральных машинах стало одинаковое количество платьев. Если это невозможно, верните -1.

Пример:

Input: machines = [1,0,5]
Output: 3
Explanation:
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3
3rd move:    2     1 <-- 3    =>    2     2     2

👨‍💻 Алгоритм:

1⃣Проверьте, можно ли решить задачу: длина массива machines должна быть делителем суммы элементов массива machines. Если нет, верните -1. Вычислите количество платьев, которое должно быть в каждой машине: dresses_per_machine = sum(machines) / len(machines). Нормализуйте задачу, заменив количество платьев в каждой машине на количество платьев, которые нужно удалить из этой машины (может быть отрицательное значение).

2⃣Инициализируйте переменные curr_sum, max_sum и res нулем. Итеративно пройдитесь по всем машинам m в массиве machines, обновляя curr_sum и max_sum на каждом шагу: curr_sum += m, max_sum = max(max_sum, abs(curr_sum)).

3⃣Обновляйте результат res на каждом шагу: res = max(res, max_sum, m). Верните res.

😎 Решение:

var findMinMoves = function(machines) {
    const n = machines.length
    const dressTotal = machines.reduce((a, b) => a + b, 0)
    if (dressTotal % n !== 0) return -1

    const dressPerMachine = Math.floor(dressTotal / n)
    for (let i = 0; i < n; i++) {
        machines[i] -= dressPerMachine
    }

    let currSum = 0, maxSum = 0, res = 0
    for (const m of machines) {
        currSum += m
        maxSum = Math.max(maxSum, Math.abs(currSum))
        res = Math.max(res, Math.max(maxSum, m))
    }
    return res
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1167. Minimum Cost to Connect Sticks
Сложность: medium

У вас есть несколько палочек с положительными целыми длинами. Эти длины даны в виде массива sticks, где sticks[i] — длина i-й палочки.

Вы можете соединить любые две палочки длиной x и y в одну палочку, заплатив стоимость x + y. Вы должны соединить все палочки, пока не останется только одна палочка.

Верните минимальную стоимость соединения всех данных палочек в одну палочку таким образом.

Пример:

Input: sticks = [5]
Output: 0
Explanation: There is only one stick, so you don't need to do anything. The total cost is 0.

👨‍💻 Алгоритм:

1⃣Всегда выбирайте две самые маленькие палочки для соединения и продолжайте делать это, пока не останется только одна палочка. Рассмотрим 4 палочки следующих длин: sticks=[a1, a2, a3, a4]. Попробуем соединить их слева направо. После первого соединения у нас будет: sticks=[(a1 + a2), a3, a4], стоимость=(a1 + a2). После второго соединения у нас будет: sticks=[(a1 + a2 + a3), a4], стоимость=(a1 + a2)+(a1 + a2 + a3). И, наконец, последняя палочка будет выглядеть так: sticks=[(a1 + a2 + a3 + a4)], стоимость=(a1 + a2)+(a1 + a2 + a3)+(a1 + a2 + a3 + a4).

2⃣Итоговая стоимость может быть переписана следующим образом: стоимость=(3a1 + 3a2 + 2a3 + a4). Как видим, палочки, которые соединяются первыми, включаются в итоговую стоимость больше, чем те, которые выбираются позже. Следовательно, оптимально сначала выбирать меньшие палочки, чтобы получить наименьшую стоимость.

3⃣Для выполнения следующих задач будет оптимальна структура данных min heap (которая обычно реализуется как PriorityQueue в большинстве языков): получить две самые маленькие палочки (stick1 и stick2) из массива; добавить одну палочку (stick1 + stick2) обратно в массив. Эта структура данных дает сложность O(logN) для обеих операций.

😎 Решение:

var connectSticks = function(sticks) {
    const pq = new MinPriorityQueue();
    
    for (const stick of sticks) {
        pq.enqueue(stick);
    }
    
    let totalCost = 0;
    
    while (pq.size() > 1) {
        const stick1 = pq.dequeue().element;
        const stick2 = pq.dequeue().element;
        const cost = stick1 + stick2;
        totalCost += cost;
        pq.enqueue(cost);
    }
    
    return totalCost;
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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;
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 423. Reconstruct Original Digits from English
Сложность: medium

Дана строка s, содержащая неупорядоченное английское представление цифр от 0 до 9, верните цифры в порядке возрастания.

Пример:

Input: s = "owoztneoer"
Output: "012"

👨‍💻 Алгоритм:

1⃣Подсчитайте количество каждого символа в строке s с помощью хэш-таблицы или массива, чтобы определить количество каждого символа.

2⃣Используйте уникальные символы, присутствующие только в одном числе (например, 'z' для 0, 'w' для 2, 'u' для 4, 'x' для 6, 'g' для 8), чтобы определить количество этих цифр в строке. Затем определите количество остальных цифр, вычитая уже найденные цифры.

3⃣Соберите найденные цифры в строку в порядке возрастания и верните результат.

😎 Решение:

class Solution {
    originalDigits(s) {
        const count = new Array(26).fill(0);
        for (const letter of s) {
            count[letter.charCodeAt(0) - 97]++;
        }

        const out = new Array(10).fill(0);
        out[0] = count[25];
        out[2] = count[22];
        out[4] = count[20];
        out[6] = count[23];
        out[8] = count[6];
        out[3] = count[7] - out[8];
        out[5] = count[5] - out[4];
        out[7] = count[18] - out[6];
        out[9] = count[8] - out[5] - out[6] - out[8];
        out[1] = count[13] - out[7] - 2 * out[9];

        const output = [];
        for (let i = 0; i < 10; i++) {
            for (let j = 0; j < out[i]; j++) {
                output.push(i);
            }
        }
        return output.join('');
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 659. Split Array into Consecutive Subsequences
Сложность: medium

Вам дан отсортированный в неубывающем порядке массив целых чисел nums.

Определите, можно ли разделить nums на одну или несколько подпоследовательностей так, чтобы выполнялись оба следующих условия:

Каждая подпоследовательность является последовательностью последовательных возрастающих чисел (то есть каждое целое число на 1 больше предыдущего).
Все подпоследовательности имеют длину 3 или более.
Верните true, если можно разделить nums согласно вышеуказанным условиям, или false в противном случае.

Подпоследовательность массива — это новый массив, который формируется из исходного массива путем удаления некоторых (может быть, ни одного) элементов без нарушения относительных позиций оставшихся элементов. (например, [1,3,5] является подпоследовательностью [1,2,3,4,5], тогда как [1,3,2] не является).

Пример:

Input: nums = [1,2,3,3,4,5]
Output: true

👨‍💻 Алгоритм:

1⃣Подсчет частоты элементов:
Создайте хеш-таблицу для подсчета количества вхождений каждого элемента в массиве nums.

2⃣Создание подпоследовательностей:
Создайте хеш-таблицу для отслеживания количества подпоследовательностей, которые могут быть продолжены для каждого элемента.
Пройдите по каждому элементу в массиве и выполните следующие действия:
Если элемент можно добавить к существующей подпоследовательности (проверяя хеш-таблицу подпоследовательностей), добавьте его и обновите хеш-таблицу.
Если элемент нельзя добавить к существующей подпоследовательности, начните новую последовательность длиной 3 или более элементов.
Если ни одно из условий не выполнено, верните false.

3⃣Проверка результата:
Верните true, если все элементы успешно распределены по подпоследовательностям.

😎 Решение:

var isPossible = function(nums) {
    let freq = new Map();
    let need = new Map();

    for (let num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }

    for (let num of nums) {
        if (freq.get(num) === 0) {
            continue;
        }

        if (need.get(num) > 0) {
            need.set(num, need.get(num) - 1);
            need.set(num + 1, (need.get(num + 1) || 0) + 1);
        } else if (freq.get(num + 1) > 0 && freq.get(num + 2) > 0) {
            freq.set(num + 1, freq.get(num + 1) - 1);
            freq.set(num + 2, freq.get(num + 2) - 1);
            need.set(num + 3, (need.get(num + 3) || 0) + 1);
        } else {
            return false;
        }
        freq.set(num, freq.get(num) - 1);
    }

    return true;
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1376. Time Needed to Inform All Employees
Сложность: medium

В компании работает n сотрудников, каждому из которых присвоен уникальный идентификатор от 0 до n - 1. Руководитель компании имеет идентификатор headID.

У каждого сотрудника есть один непосредственный начальник, указанный в массиве manager, где manager[i] — это непосредственный начальник i-го сотрудника, manager[headID] = -1. Также гарантируется, что отношения подчинения образуют древовидную структуру.

Руководитель компании хочет сообщить всем сотрудникам компании срочную новость. Он сообщит своим непосредственным подчиненным, а они сообщат своим подчиненным и так далее, пока все сотрудники не узнают о срочной новости.

i-й сотрудник нуждается в informTime[i] минутах, чтобы сообщить всем своим непосредственным подчиненным (т.е. через informTime[i] минут все его непосредственные подчиненные могут начать распространять новость).

Верните количество минут, необходимых для того, чтобы сообщить всем сотрудникам о срочной новости.

Пример:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

👨‍💻 Алгоритм:

1⃣Создайте список смежности adjList; индекс i будет хранить смежные узлы для сотрудника с идентификатором i.

2⃣Итерируйте по сотрудникам от 0 до N - 1, и для каждого сотрудника i добавляйте ребро manager[i] -> i, если manager[i] не равен -1.

3⃣Начните выполнение DFS с узла headID и временем 0 для каждого узла как curr. Обновите максимальное время maxTime, сравнив его с текущим временем. Итерируйте по смежным узлам curr и для каждого смежного узла выполните DFS с временем time + informTime[curr]. Когда DFS завершится, верните maxTime.

😎 Решение:

class Solution {
    constructor() {
        this.maxTime = -Infinity;
    }
    
    DFS(adjList, informTime, curr, time) {
        this.maxTime = Math.max(this.maxTime, time);
        for (const adjacent of adjList[curr]) {
            this.DFS(adjList, informTime, adjacent, time + informTime[curr]);
        }
    }
    
    numOfMinutes(n, headID, manager, informTime) {
        const adjList = Array.from({ length: n }, () => []);
        for (let i = 0; i < n; i++) {
            if (manager[i] !== -1) {
                adjList[manager[i]].push(i);
            }
        }
        this.DFS(adjList, informTime, headID, 0);
        return this.maxTime;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1283. Find the Smallest Divisor Given a Threshold
Сложность: medium

Дан массив целых чисел nums и целое число threshold. Мы выберем положительный целый делитель, разделим все элементы массива на него и суммируем результат деления. Найдите наименьший делитель, такой что результат, упомянутый выше, меньше или равен threshold.

Каждый результат деления округляется до ближайшего большего целого числа. (Например: 7/3 = 3 и 10/2 = 5).

Гарантируется, что решение существует.

Пример:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2). 

👨‍💻 Алгоритм:

1⃣Найдите максимальный элемент массива nums и сохраните его в переменной maxElement.

2⃣Итерация по всем делителям от 1 до maxElement:
Инициализируйте две переменные: sumOfDivisionResults для хранения суммы результатов деления и thresholdExceeded для указания, превышен ли порог.
Итерация по всем элементам массива nums: добавьте результат деления, округленного до ближайшего большего целого числа, в переменную sumOfDivisionResults. Если сумма превышает threshold, установите thresholdExceeded в true и прекратите итерацию по массиву nums.

3⃣Проверьте, был ли превышен порог:
Если порог не был превышен, текущий делитель является наименьшим делителем, поэтому верните его.
Если не найдено возможного делителя, верните -1.

😎 Решение:

var smallestDivisor = function(nums, threshold) {
    let maxElement = Math.max(...nums);
    
    for (let divisor = 1; divisor <= maxElement; divisor++) {
        let sumOfDivisionResults = 0;
        let thresholdExceeded = true;
        
        for (let num of nums) {
            sumOfDivisionResults += Math.ceil(num / divisor);
            if (sumOfDivisionResults > threshold) {
                thresholdExceeded = false;
                break;
            }
        }
        
        if (thresholdExceeded) {
            return divisor;
        }
    }
    
    return -1;
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 190. Reverse Bits
Сложность: easy

Переверните биты заданного 32-битного беззнакового целого числа.

Пример:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:

👨‍💻 Алгоритм:

1️⃣Итерируем по байтам целого числа, используя побитовую операцию И (n & 0xff) с маской 11111111, чтобы извлечь крайний правый байт числа.

2️⃣Для каждого байта сначала переворачиваем биты внутри байта с помощью функции reverseByte(byte). Затем сдвигаем перевернутые биты на их окончательные позиции.

3️⃣В функции reverseByte(byte) используем технику мемоизации, которая сохраняет результат функции и возвращает его непосредственно при последующих вызовах с тем же входным значением. Мемоизация — это компромисс между использованием памяти и объемом вычислений.

😎 Решение:

class Solution {
    constructor() {
        this.cache = {};
    }

    reverseByte(byte) {
        if (this.cache[byte] !== undefined) {
            return this.cache[byte];
        }
        let value = (byte * 0x0202020202 & 0x010884422010) % 1023;
        this.cache[byte] = value;
        return value;
    }

    reverseBits(n) {
        let ret = 0, power = 24;
        while (n !== 0) {
            ret += this.reverseByte(n & 0xff) << power;
            n = n >>> 8;
            power -= 8;
        }
        return ret;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 741. Cherry Pickup
Сложность: hard

Вам дана сетка n x n, представляющая поле вишен. Каждая клетка - одно из трех возможных целых чисел. 0 означает, что клетка пуста, и вы можете пройти через нее, 1 означает, что клетка содержит вишню, которую вы можете сорвать и пройти через нее, или -1 означает, что клетка содержит шип, который преграждает вам путь. Верните максимальное количество вишен, которое вы можете собрать, следуя следующим правилам: Начиная с позиции (0, 0) и достигая (n - 1, n - 1) путем перемещения вправо или вниз через допустимые клетки пути (клетки со значением 0 или 1).
После достижения (n - 1, n - 1) вернитесь в (0, 0), двигаясь влево или вверх по клеткам с действительными путями. Проходя через клетку пути, содержащую вишню, вы поднимаете ее, и клетка становится пустой клеткой 0. Если между (0, 0) и (n - 1, n - 1) нет действительного пути, то вишни собрать нельзя.

Пример:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5

👨‍💻 Алгоритм:

1⃣Используйте динамическое программирование для подсчета максимального количества вишен, которые можно собрать при движении от (0, 0) до (n - 1, n - 1).

2⃣Примените еще один проход с использованием динамического программирования для движения обратно от (n - 1, n - 1) до (0, 0), чтобы учитывать вишни, собранные на обратном пути.

3⃣Объедините результаты двух проходов, чтобы найти максимальное количество вишен, которые можно собрать.

😎 Решение:

var cherryPickup = function(grid) {
    const n = grid.length;
    const dp = Array.from({ length: n }, () => Array.from({ length: n }, () => Array(2 * n - 1).fill(-Infinity)));
    dp[0][0][0] = grid[0][0];
    
    for (let k = 1; k < 2 * (n - 1) + 1; k++) {
        for (let i1 = Math.max(0, k - n + 1); i1 < Math.min(n, k + 1); i1++) {
            for (let i2 = Math.max(0, k - n + 1); i2 < Math.min(n, k + 1); i2++) {
                const j1 = k - i1, j2 = k - i2;
                if (j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1) {
                    let maxCherries = Math.max(
                        i1 > 0 && i2 > 0 ? dp[i1 - 1][i2 - 1][k - 1] : -Infinity,
                        i1 > 0 ? dp[i1 - 1][i2][k - 1] : -Infinity,
                        i2 > 0 ? dp[i1][i2 - 1][k - 1] : -Infinity,
                        dp[i1][i2][k - 1]
                    );
                    if (maxCherries != -Infinity) {
                        dp[i1][i2][k] = maxCherries + grid[i1][j1];
                        if (i1 != i2) dp[i1][i2][k] += grid[i2][j2];
                    }
                }
            }
        }
    }
    
    return Math.max(0, dp[n - 1][n - 1][2 * (n - 1)]);
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1248. Count Number of Nice Subarrays
Сложность: medium

Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.

Пример:

Input: arr = [1,2]
Output: 2

👨‍💻 Алгоритм:

1⃣Преобразуйте массив чисел nums, заменив все чётные числа на 0, а все нечётные числа на 1.

2⃣Используя технику скользящего окна (или двух указателей), найдите все подмассивы, содержащие ровно k единиц.

3⃣Подсчитайте количество таких подмассивов и верните этот результат.

😎 Решение:

var numberOfSubarrays = function(nums, k) {
    return atMost(nums, k) - atMost(nums, k - 1);
};

function atMost(nums, k) {
    let res = 0, left = 0, count = 0;
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] % 2 === 1) count++;
        while (count > k) {
            if (nums[left++] % 2 === 1) count--;
        }
        res += right - left + 1;
    }
    return res;
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 857. Minimum Cost to Hire K Workers
Сложность: hard

Есть n работников. Вам даны два целочисленных массива: quality и wage, где quality[i] — качество работы i-го работника, а wage[i] — минимальная ожидаемая заработная плата i-го работника.

Мы хотим нанять ровно k работников для формирования оплачиваемой группы. Чтобы нанять группу из k работников, мы должны оплатить их в соответствии со следующими правилами:

Каждому работнику в оплачиваемой группе должно быть выплачено как минимум его ожидаемое минимальное вознаграждение.
В группе заработная плата каждого работника должна быть прямо пропорциональна его качеству. Это означает, что если качество работы одного работника вдвое выше, чем у другого работника в группе, то ему должно быть выплачено вдвое больше.
Учитывая целое число k, верните наименьшую сумму денег, необходимую для формирования оплачиваемой группы, удовлетворяющей указанным условиям. Ответы с точностью до 10^-5 от фактического ответа будут приняты.

Пример:

Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.

👨‍💻 Алгоритм:

1⃣Инициализируйте переменные: n для размера массивов quality и wage, totalCost для минимальной стоимости (начальное значение - максимум) и currentTotalQuality для суммы качеств текущих работников. Создайте массив wageToQualityRatio для хранения отношения заработной платы к качеству и качества каждого работника. Рассчитайте и сохраните отношение заработной платы к качеству для каждого работника в wageToQualityRatio. Отсортируйте wageToQualityRatio по возрастанию.

2⃣Создайте приоритетную очередь workers (максимальная куча) для хранения выбранных работников. Итерируйте через отсортированный wageToQualityRatio: добавляйте качество текущего работника в workers и обновляйте currentTotalQuality.

3⃣Если размер workers превышает k, удалите работника с наибольшим качеством из workers и обновите currentTotalQuality. Если размер workers равен k, рассчитайте общую стоимость, умножив currentTotalQuality на отношение заработной платы к качеству текущего работника. Обновите totalCost, если рассчитанная стоимость меньше текущей. Верните totalCost.

😎 Решение:

class Solution {
    mincostToHireWorkers(quality, wage, k) {
        const n = quality.length;
        let totalCost = Infinity;
        let currentTotalQuality = 0;
        const wageToQualityRatio = quality.map((q, i) => [wage[i] / q, q]).sort((a, b) => a[0] - b[0]);
        const workers = new MaxHeap();

        for (const [ratio, q] of wageToQualityRatio) {
            workers.push(q);
            currentTotalQuality += q;

            if (workers.size() > k) {
                currentTotalQuality -= workers.pop();
            }

            if (workers.size() === k) {
                totalCost = Math.min(totalCost, currentTotalQuality * ratio);
            }
        }
        return totalCost;
    }
}

class MaxHeap {
    constructor() {
        this.heap = [];
    }

    size() {
        return this.heap.length;
    }

    push(val) {
        this.heap.push(val);
        this.heap.sort((a, b) => b - a);
    }

    pop() {
        return this.heap.shift();
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 170. Two Sum III - Data structure design
Сложность: easy

Разработайте структуру данных, которая принимает поток целых чисел и проверяет, есть ли в ней пара чисел, сумма которых равна определенному значению.
Реализуйте класс TwoSum:
- TwoSum() инициализирует объект TwoSum с изначально пустым массивом.
- void add(int number) добавляет число в структуру данных.
- boolean find(int value) возвращает true, если существует хотя бы одна пара чисел, сумма которых равна значению value, в противном случае возвращает false.

Пример:

Input
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output
[null, null, null, null, true, false]

👨‍💻 Алгоритм:

1️⃣Инициализация указателей:
Инициализируйте два указателя low и high, которые указывают на первый и последний элементы списка соответственно.

2️⃣Итерация с использованием двух указателей:
Запустите цикл для итерации по списку. Цикл завершится, когда будет найдено решение с двумя суммами или когда два указателя встретятся.
На каждом шаге цикла перемещайте один из указателей в зависимости от различных условий:
Если сумма элементов, на которые указывают текущие указатели, меньше желаемого значения, то необходимо попытаться увеличить сумму для достижения желаемого значения, то есть переместить указатель low вперёд для получения большего значения.
Если сумма элементов больше желаемого значения, то следует попытаться уменьшить сумму, перемещая указатель high в сторону указателя low.
Если сумма равна желаемому значению, можно сразу выполнить возврат из функции.

3️⃣Завершение цикла:
Если цикл завершается тем, что два указателя встречаются, то можно быть уверенным, что решения для желаемого значения не существует.

😎 Решение:

class TwoSum {
    constructor() {
        this.nums = [];
        this.is_sorted = false;
    }

    add(number) {
        this.nums.push(number);
        this.is_sorted = false;
    }

    find(value) {
        if (!this.is_sorted) {
            this.nums.sort((a, b) => a - b);
            this.is_sorted = true;
        }

        let low = 0,
            high = this.nums.length - 1;
        while (low < high) {
            let twosum = this.nums[low] + this.nums[high];
            if (twosum < value) low += 1;
            else if (twosum > value) high -= 1;
            else return true;
        }
        return false;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1531. String Compression II
Сложность: hard

Дана строка s и целое число k. Необходимо удалить не более k символов из s так, чтобы длина сжатой версии строки s с использованием RLE была минимальной.

Найдите минимальную длину сжатой версии строки s после удаления не более k символов.

Пример:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

👨‍💻 Алгоритм:

1⃣Обходим символы строки слева направо, решая для каждого символа, включать его в сжатую строку или нет. Это создает состояния (строка, оставшиеся для включения символы), которые можно представить в виде бинарного дерева, где левые потомки означают включение символов, а правые — их пропуск. Многочисленные повторяющиеся подзадачи указывают на необходимость использования динамического программирования.

2⃣Для определения состояния DP используем следующие параметры: количество пройденных символов (чтобы знать, какой символ обрабатывать следующим), последний добавленный символ в сжатую строку (чтобы определить изменение сжатия при добавлении нового символа), количество последнего символа (для правильного изменения длины сжатия при добавлении символа) и количество оставшихся символов, которые можно удалить.

3⃣Связываем состояния друг с другом: удаление нового символа увеличивает i на один и уменьшает k на один; включение нового символа оставляет длину сжатия неизменной (кроме случаев, когда частота последнего символа 1, 9 или 99) или увеличивает длину на один, если новый символ не равен последнему символу сжатия.

😎 Решение:

class Solution {
    constructor() {
        this.memo = new Map();
        this.add = new Set([1, 9, 99]);
    }

    getLengthOfOptimalCompression(s, k) {
        return this.dp(s, 0, String.fromCharCode('a'.charCodeAt(0) + 26), 0, k);
    }

    dp(s, idx, lastChar, lastCharCount, k) {
        if (k < 0) {
            return Number.MAX_SAFE_INTEGER / 2;
        }

        if (idx === s.length) {
            return 0;
        }

        const key = idx * 101 * 27 * 101 + (lastChar.charCodeAt(0) - 'a'.charCodeAt(0)) * 101 * 101 + lastCharCount * 101 + k;

        if (this.memo.has(key)) {
            return this.memo.get(key);
        }

        const deleteChar = this.dp(s, idx + 1, lastChar, lastCharCount, k - 1);
        let keepChar;
        if (s[idx] === lastChar) {
            keepChar = this.dp(s, idx + 1, lastChar, lastCharCount + 1, k) + (this.add.has(lastCharCount) ? 1 : 0);
        } else {
            keepChar = this.dp(s, idx + 1, s[idx], 1, k) + 1;
        }

        const res = Math.min(keepChar, deleteChar);
        this.memo.set(key, res);

        return res;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 852. Peak Index in a Mountain Array
Сложность: medium

Вам дан целочисленный массив горы arr длины n, где значения увеличиваются до пикового элемента, а затем уменьшаются.

Верните индекс пикового элемента.

Ваша задача — решить это с временной сложностью O(log(n)).

Пример:

Input: arr = [0,1,0]

Output: 1

👨‍💻 Алгоритм:

1⃣Создайте целочисленную переменную i и инициализируйте её значением 0.

2⃣Используя цикл while, проверьте, если текущий элемент, на который указывает i, меньше следующего элемента на индексе i + 1. Если arr[i] < arr[i + 1], увеличьте i на 1.

3⃣В противном случае, если arr[i] > arr[i + 1], верните i.

😎 Решение:

var peakIndexInMountainArray = function(arr) {
    let i = 0
    while (arr[i] < arr[i + 1]) {
        i++
    }
    return i
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1063. Number of Valid Subarrays
Сложность: hard

Дан целочисленный массив nums. Вернуть количество непустых подмассивов, в которых левый элемент не больше других элементов подмассива.

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

👨‍💻 Алгоритм:

1⃣нициализируйте переменную ans значением 0. Инициализируйте пустой стек st, который будет хранить индексы элементов в стеке.

2⃣Итерируйте по элементам массива nums для каждого индекса i: продолжайте извлекать элементы из стека st, пока стек не станет пустым или элемент nums[i] не станет больше элемента на вершине стека. Для каждого извлеченного элемента добавляйте количество подмассивов как i - st.top(). Поместите текущий индекс i в стек.

3⃣Извлеките все оставшиеся элементы из стека и для каждого рассмотрите размер nums как индекс следующего меньшего элемента. Соответственно, добавьте nums.size() - st.top() к переменной ans. Верните ans.

😎 Решение:

var validSubarrays = function(nums) {
    let ans = 0;
    let st = [];
    
    for (let i = 0; i < nums.length; i++) {
        while (st.length > 0 && nums[i] < nums[st[st.length - 1]]) {
            ans += (i - st.pop());
        }
        st.push(i);
    }
    
    while (st.length > 0) {
        ans += (nums.length - st.pop());
    }
    
    return ans;
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 119. Pascal's Triangle ll
Сложность: easy

Для данного целого числа rowIndex верните rowIndex-ю строку (с индексацией с нуля) треугольника Паскаля.

Пример:

Input: rowIndex = 3
Output: [1,3,3,1]

👨‍💻 Алгоритм:

1️⃣Давайте представим, что у нас есть функция getNum(rowIndex, colIndex), которая дает нам число с индексом colIndex в строке с индексом rowIndex. Мы могли бы просто построить k-ю строку, повторно вызывая getNum(...) для столбцов от 0 до k.

2️⃣Мы можем сформулировать нашу интуицию в следующую рекурсию:

getNum(rowIndex, colIndex) = getNum(rowIndex - 1, colIndex - 1) + getNum(rowIndex - 1, colIndex)

3️⃣Рекурсия заканчивается в некоторых известных базовых случаях:

😎 Решение:

var getNum = function (row, col) {
    if (row === 0 || col === 0 || row === col) {
        return 1;
    }
    return getNum(row - 1, col - 1) + getNum(row - 1, col);
};
var getRow = function (rowIndex) {
    let ans = [];
    for (let i = 0; i <= rowIndex; i++) {
        ans.push(getNum(rowIndex, i));
    }
    return ans;
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 316. Remove Duplicate Letters
Сложность: medium

Дана строка s, удалите повторяющиеся буквы так, чтобы каждая буква появилась один раз и только один раз. Вы должны сделать так, чтобы результат был наименьшим в лексикографическом порядке среди всех возможных результатов.

Пример:

Input: s = "bcabc"
Output: "abc"

👨‍💻 Алгоритм:

1⃣Инициализация стека
Создайте стек, который будет хранить результат, построенный по мере итерации строки.

2⃣Итерация по строке
На каждой итерации добавляйте текущий символ в стек, если он еще не был использован. Перед добавлением текущего символа удаляйте как можно больше символов из вершины стека, если это возможно и улучшает лексикографический порядок.

3⃣Удаление символов
Удаляйте символы с вершины стека при выполнении следующих условий: Символ на вершине стека больше текущего символа. Символ может быть удален, так как он встречается позже в строке. На каждом этапе итерации по строке жадно минимизируйте содержимое стека.

😎 Решение:

class Solution {
    removeDuplicateLetters(s) {
        const stack = [];
        const seen = new Set();
        const lastOccurrence = {};
        for (let i = 0; i < s.length; i++) {
            lastOccurrence[s[i]] = i;
        }

        for (let i = 0; i < s.length; i++) {
            const c = s[i];
            if (!seen.has(c)) {
                while (stack.length && c < stack[stack.length - 1] && i < lastOccurrence[stack[stack.length - 1]]) {
                    seen.delete(stack.pop());
                }
                seen.add(c);
                stack.push(c);
            }
        }
        return stack.join('');
    }
}

Ставь 👍 и забирай 📚 Базу знаний