JavaScript | LeetCode

Задача: 67. Add Binary
Сложность: easy

Даны две двоичные строки a и b. Верните их сумму в виде двоичной строки.

Пример:

Input: a = "11", b = "1"
Output: "100"

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

1️⃣Начните с переноса carry = 0. Если в числе a наименьший бит равен 1, добавьте 1 к carry. То же самое относится к числу b: если в числе b наименьший бит равен 1, добавьте 1 к carry. В этот момент carry для наименьшего бита может быть равен 0 (00), 1 (01) или 2 (10).

2️⃣Теперь добавьте наименьший бит carry к ответу и перенесите старший бит carry на следующий порядковый бит.

3️⃣Повторяйте те же шаги снова и снова, пока не будут использованы все биты в a и b. Если остаётся ненулевой carry, добавьте его. Теперь переверните строку ответа, и задача выполнена.

😎 Решение:

var addBinary = function (a, b) {
    let n = a.length,
        m = b.length;
    if (n < m) return addBinary(b, a);

    let result = [];
    let carry = 0,
        j = m - 1;
    for (let i = n - 1; i >= 0; --i) {
        if (a[i] === "1") ++carry;
        if (j >= 0 && b[j--] === "1") ++carry;

        result.push((carry % 2).toString());
        carry = Math.floor(carry / 2);
    }
    if (carry === 1) result.push("1");
    return result.reverse().join("");
};

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

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

Дано целое число numRows. Верните первые numRows строк треугольника Паскаля.
В треугольнике Паскаля каждое число является суммой двух чисел, непосредственно расположенных над ним, как показано:

Пример:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

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

1⃣Сначала мы создаём общий список треугольника, который будет хранить каждую строку как подсписок.

2⃣Затем мы проверяем особый случай, когда число строк равно 0, так как в противном случае мы бы вернули [1].

3⃣Поскольку numRows всегда больше 0, мы можем инициализировать треугольник первой строкой [1] и продолжить заполнять строки следующим образом:

😎 Решение:

var generate = function (numRows) {
    const triangle = [];
    triangle.push([]);
    triangle[0].push(1);
    for (let rowNum = 1; rowNum < numRows; rowNum++) {
        const row = [];
        const prevRow = triangle[rowNum - 1];
        row.push(1);
        for (let j = 1; j < rowNum; j++) {
            row.push(prevRow[j - 1] + prevRow[j]);
        }
        row.push(1);
        triangle.push(row);
    }
    return triangle;
};

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

Задача: 362. Design Hit Counter
Сложность: medium

Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.
Бомба уничтожает всех врагов в той же строке и столбце от точки установки до тех пор, пока не встретит стену, так как она слишком сильна, чтобы быть разрушенной.

Пример:

Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]

Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.

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

1⃣При вызове метода hit(int timestamp), добавьте временную метку в очередь.

2⃣ При вызове метода getHits(int timestamp), удалите все временные метки из очереди, которые старше 300 секунд от текущей временной метки.

3⃣Верните размер очереди как количество попаданий за последние 5 минут.

😎 Решение:

class HitCounter {
    constructor() {
        this.hits = [];
    }

    hit(timestamp) {
        this.hits.push(timestamp);
    }

    getHits(timestamp) {
        while (this.hits.length > 0 && timestamp - this.hits[0] >= 300) {
            this.hits.shift();
        }
        return this.hits.length;
    }
}

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

Задача: 1052. Grumpy Bookstore Owner
Сложность: medium

Есть владелец книжного магазина, магазин которого открыт в течение n минут. Каждую минуту в магазин заходит некоторое количество покупателей. Вам дан целочисленный массив customers длины n, где customers[i] - это номер покупателя, который заходит в магазин в начале i-й минуты, а все покупатели выходят после окончания этой минуты. В некоторые минуты владелец книжного магазина ворчлив. Вам дан двоичный массив grumpy, в котором grumpy[i] равен 1, если владелец книжного магазина ворчлив в течение i-й минуты, и равен 0 в противном случае. Когда владелец книжного магазина ворчлив, покупатели в эту минуту не удовлетворены, в противном случае они удовлетворены. Владелец книжного магазина знает секретную технику, чтобы не ворчать в течение нескольких минут подряд, но может использовать ее только один раз. Верните максимальное количество покупателей, которое может быть удовлетворено в течение дня.

Пример:

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
Output: 16

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

1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.

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

3⃣Найди максимальное количество дополнительных удовлетворенных покупателей, которые можно получить, используя технику на k минут подряд.

😎 Решение:

public class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int totalSatisfied = 0;
        int additionalSatisfied = 0;
        int maxAdditionalSatisfied = 0;
        
        for (int i = 0; i < customers.length; i++) {
            if (grumpy[i] == 0) {
                totalSatisfied += customers[i];
            } else {
                additionalSatisfied += customers[i];
            }
            
            if (i >= minutes) {
                if (grumpy[i - minutes] == 1) {
                    additionalSatisfied -= customers[i - minutes];
                }
            }
            
            maxAdditionalSatisfied = Math.max(maxAdditionalSatisfied, additionalSatisfied);
        }
        
        return totalSatisfied + maxAdditionalSatisfied;
    }
}

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

Задача: 329. Longest Increasing Path in a Matrix
Сложность: hard

Дана матрица целых чисел размером m x n. Верните длину самого длинного возрастающего пути в матрице.
Из каждой ячейки можно перемещаться в четырех направлениях: влево, вправо, вверх или вниз. Перемещение по диагонали или выход за границы матрицы (т.е. замкнутые переходы) не допускается.

Пример:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

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

1⃣Инициализация и создание матрицы:
Инициализируйте размеры матрицы m и n. Создайте матрицу matrix с добавленными границами (нулевыми значениями) вокруг исходной матрицы, чтобы избежать выхода за пределы при обработке.
Рассчитайте количество исходящих связей (outdegrees) для каждой клетки и сохраните их в outdegree.

2⃣Поиск начальных листьев:
Найдите все клетки с нулевыми исходящими связями и добавьте их в список leaves. Эти клетки будут начальной точкой для "слоевого удаления".

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

😎 Решение:

var longestIncreasingPath = function(matrix) {
    if (!matrix.length) return 0;
    const m = matrix.length, n = matrix[0].length;
    const outdegree = Array.from({ length: m + 2 }, () => Array(n + 2).fill(0));
    const newMatrix = Array.from({ length: m + 2 }, () => Array(n + 2).fill(0));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            newMatrix[i + 1][j + 1] = matrix[i][j];
        }
    }

    const dir = [[0, 1], [1, 0], [0, -1], [-1, 0]];

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            for (const [dx, dy] of dir) {
                if (newMatrix[i][j] < newMatrix[i + dx][j + dy]) {
                    outdegree[i][j]++;
                }
            }
        }
    }

    const leaves = [];
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (outdegree[i][j] === 0) leaves.push([i, j]);
        }
    }

    let height = 0;
    while (leaves.length) {
        height++;
        const newLeaves = [];
        for (const [i, j] of leaves) {
            for (const [dx, dy] of dir) {
                const x = i + dx, y = j + dy;
                if (newMatrix[i][j] > newMatrix[x][y]) {
                    outdegree[x][y]--;
                    if (outdegree[x][y] === 0) newLeaves.push([x, y]);
                }
            }
        }
        leaves.length = 0;
        leaves.push(...newLeaves);
    }

    return height;
};

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

Задача: 611. Valid Triangle Number
Сложность: medium

Если задан целочисленный массив nums, верните количество выбранных из массива троек, которые могут образовывать треугольники, если принять их за длины сторон треугольника.

Пример:

Input: nums = [2,2,3,4]
Output: 3

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

1⃣Отсортируйте массив nums.

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

3⃣Увеличивайте счетчик на количество подходящих пар для каждого третьего элемента.

😎 Решение:

function triangleNumber(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let count = 0;
    
    for (let k = n - 1; k >= 2; k--) {
        let i = 0;
        let j = k - 1;
        while (i < j) {
            if (nums[i] + nums[j] > nums[k]) {
                count += j - i;
                j--;
            } else {
                i++;
            }
        }
    }
    
    return count;
}

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

Задача: 521. Longest Uncommon Subsequence I
Сложность: easy

Даны две строки a и b. Верните длину самой длинной несообщей подпоследовательности между a и b. Если такой несообщей подпоследовательности не существует, верните -1.
Несообщая подпоследовательность между двумя строками — это строка, которая является подпоследовательностью только одной из них.

Пример:

Input: a = "aba", b = "cdc"
Output: 3
Explanation: One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc".
Note that "cdc" is also a longest uncommon subsequence.

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

1⃣Если строка a равна строке b, верните -1, так как не существует несообщей подпоследовательности.

2⃣В противном случае: Вычислите длины строк a и b. Верните длину более длинной строки.

😎 Решение:

var findLUSlength = function(a, b) {
    if (a === b) {
        return -1;
    } else {
        return Math.max(a.length, b.length);
    }
};

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

Задача: 1498. Number of Subsequences That Satisfy the Given Sum Condition
Сложность: medium

Вам дан массив целых чисел nums и целое число target.

Верните количество непустых подпоследовательностей массива nums, таких что сумма минимального и максимального элемента в них меньше или равна target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

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

1⃣Инициализация и подготовка:
Инициализируйте переменные answer равным 0 и n как длину массива nums.
Отсортируйте массив nums.
Подготовьте массив power для хранения степеней двойки до n по модулю 10^9+7.

2⃣Итерация и бинарный поиск:
Для каждого индекса left от 0 до n - 1 выполните бинарный поиск, чтобы найти самый правый индекс right, где nums[right] <= target - nums[left].
Если left <= right, добавьте количество допустимых подпоследовательностей к answer.

3⃣Возврат результата:
Верните answer по модулю 10^9+7.

😎 Решение:

var numSubseq = function(nums, target) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const mod = 1_000_000_007;
    
    const power = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        power[i] = (power[i - 1] * 2) % mod;
    }
    
    let answer = 0;
    let left = 0, right = n - 1;
    
    while (left <= right) {
        if (nums[left] + nums[right] <= target) {
            answer = (answer + power[right - left]) % mod;
            left++;
        } else {
            right--;
        }
    }
    
    return answer;
};

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

Задача: 326. Power of Three
Сложность: easy

Дано целое число n. Верните true, если оно является степенью тройки, иначе верните false.
Целое число n является степенью тройки, если существует целое число x такое, что n == 3^x.

Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

1⃣Проверка начального значения
Если n меньше или равно нулю, вернуть false, так как степени тройки всегда положительны.

2⃣Цикл деления на 3
Пока n делится на 3 без остатка, делите n на 3. Повторяйте этот процесс до тех пор, пока n делится на 3.

3⃣Проверка конечного значения
Если после всех делений значение n стало равно 1, значит исходное число является степенью тройки, вернуть true. В противном случае вернуть false.

😎 Решение:

var isPowerOfThree = function(n) {
    if (n <= 0) return false;
    while (n % 3 === 0) {
        n = Math.floor(n / 3);
    }
    return n === 1;
};

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

Задача: 543. Diameter of Binary Tree
Сложность: easy

Учитывая корень бинарного дерева, вернуть длину диаметра дерева.
Диаметр бинарного дерева — это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень.
Длина пути между двумя узлами представлена числом ребер между ними.

Пример:

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

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

1⃣Инициализируйте целочисленную переменную diameter для отслеживания самого длинного пути, найденного с помощью DFS.

2⃣Реализуйте рекурсивную функцию longestPath, которая принимает TreeNode в качестве входных данных и рекурсивно исследует дерево: Если узел равен None, вернуть 0. Рекурсивно исследовать левые и правые дочерние узлы, возвращая длины путей leftPath и rightPath. Если сумма leftPath и rightPath больше текущего diameter, обновить diameter. Вернуть большее из leftPath и rightPath плюс 1.

3⃣Вызвать longestPath с root.

😎 Решение:

class Solution {
    constructor() {
        this.diameter = 0;
    }
    
    diameterOfBinaryTree(root) {
        this.diameter = 0;
        this.longestPath(root);
        return this.diameter;
    }
    
    longestPath(node) {
        if (node === null) return 0;
        
        let leftPath = this.longestPath(node.left);
        let rightPath = this.longestPath(node.right);
        
        this.diameter = Math.max(this.diameter, leftPath + rightPath);
        
        return Math.max(leftPath, rightPath) + 1;
    }
}

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

Задача: №16. 3Sum Closest
Сложность: medium

Дан массив nums и целое число target.
Найти такие три числа из nums, сумма которых максимально близка к target.
Вернуть именно сумму этих трёх чисел. Гарантируется, что решение единственное.

Пример:

Input: nums = [-1,2,1,-4], target = 1  
Output: 2  
Explanation: Сумма -1 + 2 + 1 = 2 наиболее близка к 1

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

1️⃣ Отсортировать массив nums, чтобы использовать двухуказательный подход.

2️⃣ Перебрать все возможные значения nums[i] в цикле от 0 до n - 3.
Для каждой позиции использовать два указателя j (i + 1) и k (n - 1) для поиска остальных двух чисел.

3️⃣ Для каждой тройки вычислить сумму и:
- Если она равна target — сразу вернуть.
- Иначе обновить текущий лучший ответ ans, если новая сумма ближе к target.
- Смещать указатели в зависимости от того, больше ли сумма или меньше target.

😎 Решение:

var threeSumClosest = function (nums, target) {
    nums.sort((a, b) => a - b);
    let ans = 1 << 30;
    const n = nums.length;

    for (let i = 0; i < n; ++i) {
        let j = i + 1;
        let k = n - 1;

        while (j < k) {
            const t = nums[i] + nums[j] + nums[k];

            if (t === target) {
                return t;
            }

            if (Math.abs(t - target) < Math.abs(ans - target)) {
                ans = t;
            }

            if (t > target) {
                k--;
            } else {
                j++;
            }
        }
    }

    return ans;
};

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

Задача: №22. Generate Parentheses
Сложность: medium

Дано число n.
Нужно сгенерировать все возможные комбинации n пар правильных скобок.

Пример:

Input: n = 3  
Output: ["((()))","(()())","(())()","()(())","()()()"]

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

1️⃣ Используем DFS с тремя параметрами:
- l — количество открывающих скобок
- r — количество закрывающих
- t — текущая строка

2️⃣ Прерываем рекурсию, если:
- l > n, r > n или l < r — комбинация недопустима

3️⃣ Если l === n && r === n, добавляем строку в результат.
Иначе:
- Добавляем '(', вызываем dfs(l + 1, r, t + '(')
- Добавляем ')', вызываем dfs(l, r + 1, t + ')'

😎 Решение:

var generateParenthesis = function (n) {
    const ans = [];

    function dfs(l, r, t) {
        if (l > n || r > n || l < r) return;

        if (l === n && r === n) {
            ans.push(t);
            return;
        }

        dfs(l + 1, r, t + '(');
        dfs(l, r + 1, t + ')');
    }

    dfs(0, 0, '');
    return ans;
};

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

Задача: 532. K-diff Pairs in an Array
Сложность: medium

Дан массив целых чисел nums и целое число k. Верните количество уникальных пар с разницей k в массиве.
Пара с разницей k — это пара целых чисел (nums[i], nums[j]), для которой выполняются следующие условия:
0 <= i, j < nums.length
i != j
|nums[i] - nums[j]| == k
Обратите внимание, что |val| обозначает абсолютное значение val.

Пример:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

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

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

2⃣ Для каждого ключа в хэш-словаре проверьте, можно ли найти пару, удовлетворяющую условиям:
Если k > 0, проверьте, существует ли ключ, равный x + k.
Если k == 0, проверьте, есть ли более одного вхождения x.

3⃣ Увеличьте счётчик результатов, если условие выполняется.

😎 Решение:

var findPairs = function(nums, k) {
    let counter = new Map();
    for (let num of nums) {
        counter.set(num, (counter.get(num) || 0) + 1);
    }
    
    let result = 0;
    for (let [x, val] of counter) {
        if (k > 0 && counter.has(x + k)) {
            result++;
        } else if (k == 0 && val > 1) {
            result++;
        }
    }
    
    return result;
};

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

Задача: 928. Minimize Malware Spread II
Сложность: hard

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

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

1⃣Определить компоненты связности в графе. Для каждой компоненты связности определить количество зараженных узлов и общее количество узлов.

2⃣Для каждого узла в initial удалить его и пересчитать количество зараженных узлов.

3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если несколько узлов минимизируют количество зараженных узлов одинаково, выбрать узел с наименьшим индексом.

😎 Решение:

function minMalwareSpread(graph, initial) {
    const n = graph.length;

    function dfs(node, visited, component) {
        const stack = [node];
        while (stack.length > 0) {
            const u = stack.pop();
            component.push(u);
            for (let v = 0; v < n; v++) {
                if (graph[u][v] === 1 && !visited.has(v)) {
                    visited.add(v);
                    stack.push(v);
                }
            }
        }
    }

    const components = [];
    const visited = new Set();

    for (let i = 0; i < n; i++) {
        if (!visited.has(i)) {
            const component = [];
            visited.add(i);
            dfs(i, visited, component);
            components.push(component);
        }
    }

    const infectedInComponent = new Array(components.length).fill(0);
    const nodeToComponent = new Map();

    components.forEach((component, idx) => {
        for (const node of component) {
            nodeToComponent.set(node, idx);
        }
    });

    for (const node of initial) {
        const componentIdx = nodeToComponent.get(node);
        infectedInComponent[componentIdx]++;
    }

    initial.sort((a, b) => a - b);
    let minInfected = Infinity;
    let resultNode = initial[0];

    for (const node of initial) {
        const componentIdx = nodeToComponent.get(node);
        if (infectedInComponent[componentIdx] === 1) {
            const componentSize = components[componentIdx].length;
            if (componentSize < minInfected || (componentSize === minInfected && node < resultNode)) {
                minInfected = componentSize;
                resultNode = node;
            }
        }
    }

    return resultNode;
}

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

Задача: 45. Jump Game II
Сложность: medium

Вам дан массив целых чисел nums с индексацией с нуля и длиной n. Изначально вы находитесь в позиции nums[0].
Каждый элемент nums[i] представляет максимальную длину прыжка вперед с индекса i. Другими словами, если вы находитесь в nums[i], вы можете прыгнуть на любой nums[i + j], где:
0 <= j <= nums[i] и
i + j < n
Верните минимальное количество прыжков, чтобы достичь nums[n - 1]. Тестовые случаи сгенерированы таким образом, что вы можете достичь nums[n - 1].

Пример:

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

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

1️⃣Инициализируйте curEnd = 0, curFar = 0 и количество прыжков как answer = 0.

2️⃣Итерируйтесь по массиву nums. Для каждого индекса i наибольший индекс, до которого мы можем добраться из i, равен i + nums[i]. Обновите curFar = max(curFar, i + nums[i]).

3️⃣Если i = curEnd, это означает, что текущий прыжок завершен, и следует перейти к следующему прыжку. Увеличьте answer и установите curEnd = curFar как наибольшее расстояние, которое мы можем преодолеть следующим прыжком. Повторите с шага 2.

😎 Решение:

var jump = function (nums) {
    let answer = 0,
        n = nums.length;
    let curEnd = 0,
        curFar = 0;
    for (let i = 0; i < n - 1; ++i) {
        curFar = Math.max(curFar, i + nums[i]);
        if (i === curEnd) {
            ++answer;
            curEnd = curFar;
        }
    }
    return answer;
};

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

Задача: 1054. Distant Barcodes
Сложность: medium

На складе имеется ряд штрих-кодов, где i-й штрих-код - barcodes[i]. Переставьте штрих-коды так, чтобы два соседних штрих-кода не были одинаковыми. Вы можете вернуть любой ответ, и гарантируется, что ответ существует.

Пример:

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

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

1⃣Подсчитай частоту каждого штрих-кода.
Помести все штрих-коды в максимальную кучу на основе их частоты.

2⃣Извлекай штрих-коды из кучи, чередуя их, чтобы два соседних штрих-кода не были одинаковыми.

3⃣Если куча становится пустой, помести временно сохранённый штрих-код обратно в кучу.

😎 Решение:

function rearrangeBarcodes(barcodes) {
    const count = new Map();
    for (const barcode of barcodes) {
        count.set(barcode, (count.get(barcode) || 0) + 1);
    }

    const maxHeap = [];
    for (const [barcode, freq] of count) {
        maxHeap.push([-freq, barcode]);
    }
    maxHeap.sort((a, b) => a[0] - b[0]);

    const result = [];
    let prevFreq = 0;
    let prevBarcode = null;

    while (maxHeap.length) {
        const [freq, barcode] = maxHeap.pop();
        result.push(barcode);
        if (prevFreq < 0) {
            maxHeap.push([prevFreq, prevBarcode]);
            maxHeap.sort((a, b) => a[0] - b[0]);
        }
        prevFreq = freq + 1;
        prevBarcode = barcode;
    }

    return result;
}

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

Задача: 1250. Check If It Is a Good Array
Сложность: hard

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

Пример:

Input: nums = [12,5,7,23]
Output: true

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

1⃣Если наибольший общий делитель (НОД) всех чисел в массиве равен 1, то массив считается хорошим.

2⃣Если НОД всех чисел больше 1, то массив не считается хорошим

3⃣Получить сумму, равную 1, умножая и складывая элементы.

😎 Решение:

var isGoodArray = function(nums) {
    let gcd = nums[0];
    for (let num of nums) {
        gcd = gcdFunc(gcd, num);
        if (gcd === 1) return true;
    }
    return gcd === 1;
};

function gcdFunc(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

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

Задача: 740. Delete and Earn
Сложность: medium

Вам дан целочисленный массив nums. Вы хотите максимизировать количество очков, выполнив следующую операцию любое количество раз: Выберите любой элемент nums[i] и удалите его, чтобы заработать nums[i] очков. После этого вы должны удалить каждый элемент, равный nums[i] - 1, и каждый элемент, равный nums[i] + 1. Верните максимальное количество очков, которое вы можете заработать, применив вышеуказанную операцию некоторое количество раз.

Пример:

Input: nums = [3,4,2]
Output: 6

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

1⃣Подсчитайте количество каждого числа в массиве nums.

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

3⃣Для каждого числа num в nums, учитывайте два случая: не брать число или взять число и добавить его очки.

😎 Решение:

var deleteAndEarn = function(nums) {
    const count = {};
    nums.forEach(num => count[num] = (count[num] || 0) + 1);
    
    let prev = null;
    let avoid = 0, using = 0;
    
    Object.keys(count).sort((a, b) => a - b).forEach(num => {
        num = parseInt(num);
        if (num - 1 !== prev) {
            const newAvoid = Math.max(avoid, using);
            using = num * count[num] + Math.max(avoid, using);
            avoid = newAvoid;
        } else {
            const newAvoid = Math.max(avoid, using);
            using = num * count[num] + avoid;
            avoid = newAvoid;
        }
        prev = num;
    });
    
    return Math.max(avoid, using);
};

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

Задача: 318. Maximum Product of Word Lengths
Сложность: medium

Дан массив строк words, верните максимальное значение произведения длины word[i] на длину word[j], где два слова не имеют общих букв. Если таких двух слов не существует, верните 0.

Пример:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

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

1⃣Предварительная обработка масок и длин
Вычислите битовые маски для всех слов и сохраните их в массиве masks. Сохраните длины всех слов в массиве lens.

2⃣Сравнение слов и проверка общих букв
Сравните каждое слово с каждым последующим словом. Если два слова не имеют общих букв (проверка с использованием масок: (masks[i] & masks[j]) == 0), обновите максимальное произведение maxProd.

3⃣Возврат результата
Верните максимальное значение произведения maxProd.

😎 Решение:

var maxProduct = function(words) {
    const n = words.length;
    const masks = new Array(n).fill(0);
    const lens = new Array(n).fill(0);
    
    for (let i = 0; i < n; i++) {
        let bitmask = 0;
        for (const ch of words[i]) {
            bitmask |= 1 << (ch.charCodeAt(0) - 'a'.charCodeAt(0));
        }
        masks[i] = bitmask;
        lens[i] = words[i].length;
    }
    
    let maxVal = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if ((masks[i] & masks[j]) === 0) {
                maxVal = Math.max(maxVal, lens[i] * lens[j]);
            }
        }
    }
    return maxVal;
};

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

Задача: 652. Find Duplicate Subtrees
Сложность: medium

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

Пример:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

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

1⃣Выполните обход дерева и используйте сериализацию для представления каждого поддерева.

2⃣Храните все сериализованные представления поддеревьев в хэш-таблице и отслеживайте частоту их появления.

3⃣Найдите поддеревья, которые появляются более одного раза, и верните корневые узлы этих поддеревьев.

😎 Решение:

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var findDuplicateSubtrees = function(root) {
    const count = new Map();
    const result = [];
    
    const serialize = (node) => {
        if (!node) return "#";
        const serial = `${node.val},${serialize(node.left)},${serialize(node.right)}`;
        count.set(serial, (count.get(serial) || 0) + 1);
        if (count.get(serial) === 2) {
            result.push(node);
        }
        return serial;
    };
    
    serialize(root);
    return result;
};

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