Задача: 113. Path Sum II
Сложность: medium

Дан корень бинарного дерева и целое число targetSum. Верните все пути от корня до листа, где сумма значений узлов в пути равна targetSum. Каждый путь должен быть возвращён как список значений узлов, а не ссылок на узлы.

Путь от корня до листа — это путь, начинающийся от корня и заканчивающийся на любом листовом узле. Лист — это узел без детей.

Пример:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

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

1️⃣Определение функции recurseTree: Функция принимает текущий узел (node), оставшуюся сумму (remainingSum), которая необходима для продолжения поиска вниз по дереву, и список узлов (pathNodes), который содержит все узлы, встреченные до текущего момента на данной ветке.

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

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

😎 Решение:

var pathSum = function (root, sum) {
    let pathsList = [];
    let pathNodes = [];
    let recurseTree = function (node, remainingSum, pathNodes, pathsList) {
        if (!node) {
            return;
        }
        pathNodes.push(node.val);
        if (
            remainingSum === node.val &&
            node.left === null &&
            node.right === null
        ) {
            pathsList.push(Array.from(pathNodes));
        } else {
            recurseTree(
                node.left,
                remainingSum - node.val,
                pathNodes,
                pathsList,
            );
            recurseTree(
                node.right,
                remainingSum - node.val,
                pathNodes,
                pathsList,
            );
        }
        pathNodes.pop();
    };
    recurseTree(root, sum, pathNodes, pathsList);
    return pathsList;
};

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

Задача: 460. LFU Cache
Сложность: hard

Спроектируйте и реализуйте структуру данных для кеша с наименьшим количеством использования (Least Frequently Used, LFU).
Реализуйте класс LFUCache:
LFUCache(int capacity): Инициализирует объект с указанной вместимостью структуры данных.
int get(int key): Возвращает значение ключа, если ключ существует в кеше. В противном случае возвращает -1.
void put(int key, int value): Обновляет значение ключа, если он уже присутствует, или вставляет ключ, если его еще нет. Когда кеш достигает своей вместимости, он должен аннулировать и удалить ключ, используемый наименее часто, перед вставкой нового элемента. В этой задаче, если имеется несколько ключей с одинаковой частотой использования, аннулируется наименее недавно использованный ключ.
Чтобы определить наименее часто используемый ключ, для каждого ключа в кеше поддерживается счетчик использования. Ключ с наименьшим счетчиком использования является наименее часто используемым ключом.
Когда ключ впервые вставляется в кеш, его счетчик использования устанавливается на 1 (из-за операции put). Счетчик использования для ключа в кеше увеличивается при вызове операции get или put для этого ключа.
Функции get и put должны иметь среднюю временную сложность O(1).

Пример:

Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

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

1⃣insert(int key, int frequency, int value):
Вставить пару частота-значение в cache с заданным ключом.
Получить LinkedHashSet, соответствующий данной частоте (по умолчанию пустой Set), и вставить в него ключ.

2⃣int get(int key):
Если ключа нет в кеше, вернуть -1.
Получить частоту и значение из кеша.
Удалить ключ из LinkedHashSet, связанного с частотой.
Если minf == frequency и LinkedHashSet пуст, увеличить minf на 1 и удалить запись частоты из frequencies.
Вызвать insert(key, frequency + 1, value).
Вернуть значение.

3⃣void put(int key, int value):
Если capacity <= 0, выйти.
Если ключ существует, обновить значение и вызвать get(key).
Если размер кеша равен capacity, удалить первый элемент из LinkedHashSet, связанного с minf, и из кеша.
Установить minf в 1.
Вызвать insert(key, 1, value).

😎 Решение:

class LFUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.minf = 0;
        this.cache = new Map();
        this.frequencies = new Map();
    }

    insert(key, frequency, value) {
        if (!this.frequencies.has(frequency)) {
            this.frequencies.set(frequency, new Set());
        }
        this.frequencies.get(frequency).add(key);
        this.cache.set(key, { frequency, value });
    }

    get(key) {
        if (!this.cache.has(key)) return -1;
        let { frequency, value } = this.cache.get(key);
        this.frequencies.get(frequency).delete(key);
        if (this.frequencies.get(frequency).size === 0) {
            this.frequencies.delete(frequency);
            if (this.minf === frequency) this.minf++;
        }
        this.insert(key, frequency + 1, value);
        return value;
    }

    put(key, value) {
        if (this.capacity <= 0) return;
        if (this.cache.has(key)) {
            this.cache.get(key).value = value;
            this.get(key);
            return;
        }
        if (this.cache.size === this.capacity) {
            let oldest = Array.from(this.frequencies.get(this.minf))[0];
            this.cache.delete(oldest);
            this.frequencies.get(this.minf).delete(oldest);
            if (this.frequencies.get(this.minf).size === 0) this.frequencies.delete(this.minf);
        }
        this.minf = 1;
        this.insert(key, 1, value);
    }
}

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

Задача: 43. Multiply Strings
Сложность: hard

Даны два неотрицательных целых числа num1 и num2, представленные в виде строк. Верните произведение num1 и num2, также представленное в виде строки.
Примечание: Вы не должны использовать встроенную библиотеку BigInteger или прямо преобразовывать входные данные в целые числа.

Пример:

Input: num1 = "2", num2 = "3"
Output: "6"

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

1️⃣Переверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры в secondNumber:
Инициализируйте переменную carry, первоначально равную 0.
Инициализируйте массив (currentResult), который начинается с некоторого количества нулей, основываясь на позиции цифры в secondNumber.

2️⃣Для каждой цифры в firstNumber:
Умножьте цифру из secondNumber на цифру из firstNumber и добавьте предыдущий carry к умножению.
Возьмите остаток от деления умножения на 10, чтобы получить последнюю цифру.
Добавьте последнюю цифру в массив currentResult.
Разделите умножение на 10, чтобы получить новое значение для carry.

3️⃣После итерации по каждой цифре в первом числе, если carry не равен нулю, добавьте carry в currentResult.
Добавьте currentResult к ans.
Если последняя цифра в ans равна нулю, перед тем как перевернуть ans, необходимо удалить ноль из ans. В противном случае в финальном ответе будет ведущий ноль.
Переверните ans и верните его.

😎 Решение:

let addStrings = function (num1, num2) {
    let ans = [];
    let carry = 0;

    for (let i = 0; i < num1.length || i < num2.length; ++i) {
        let digit1 = i < num1.length ? num1[i] : 0;
        let digit2 = i < num2.length ? num2[i] : 0;

        let sum = digit1 + digit2 + carry;
        carry = Math.floor(sum / 10);
        ans.push(sum % 10);
    }

    if (carry) {
        ans.push(carry);
    }
    return ans;
};

let multiplyOneDigit = function (firstNumber, secondNumberDigit, numZeros) {
    let currentResult = [];
    for (let i = 0; i < numZeros; ++i) {
        currentResult.push(0);
    }

    let carry = 0;

    for (let i = 0; i < firstNumber.length; ++i) {
        let multiplication = Number(secondNumberDigit) * Number(firstNumber[i]) + carry;
        carry = Math.floor(multiplication / 10);
        currentResult.push(multiplication % 10);
    }

    if (carry) {
        currentResult.push(carry);
    }
    return currentResult;
};

let multiply = function (num1, num2) {
    if (num1 === "0" || num2 === "0") {
        return "0";
    }

    let firstNumber = [...num1];
    let secondNumber = [...num2];

    firstNumber.reverse();
    secondNumber.reverse();

    let N = firstNumber.length + secondNumber.length;
    let ans = new Array(N).fill(0);

    for (let i = 0; i < secondNumber.length; ++i) {
        ans = addStrings(
            multiplyOneDigit(firstNumber, secondNumber[i], i),
            ans,
        );
    }

    if (ans[ans.length - 1] === 0) {
        ans.pop();
    }

    ans.reverse();
    return ans.join("");
};

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

Задача: 330. Patching Array
Сложность: hard

Дан отсортированный массив целых чисел nums и целое число n. Добавьте/дополните элементы в массив таким образом, чтобы любое число в диапазоне [1, n] включительно могло быть сформировано как сумма некоторых элементов массива.
Верните минимальное количество дополнений, необходимых для этого.

Пример:

Input: nums = [1,3], n = 6
Output: 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

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

1️⃣ Инициализация переменных:
Создайте переменную miss, представляющую наименьшее пропущенное число, которое еще не покрыто, и установите ее значение на 1. Создайте переменную patches для подсчета необходимых дополнений и переменную i для итерации по массиву nums.

2️⃣ Основной цикл:
Используйте цикл while, который будет выполняться до тех пор, пока miss не станет больше n.
Внутри цикла проверьте, покрывает ли текущий элемент nums[i] значение miss. Если да, добавьте nums[i] к miss и увеличьте i. Если нет, добавьте значение miss к самому себе (это означает добавление нового элемента в массив) и увеличьте счетчик patches.

3️⃣ Возврат результата:
После завершения цикла верните значение patches, которое представляет минимальное количество необходимых дополнений.

😎 Решение:

var minPatches = function(nums, n) {
    let patches = 0, i = 0, miss = 1;
    while (miss <= n) {
        if (i < nums.length && nums[i] <= miss) {
            miss += nums[i++];
        } else {
            miss += miss;
            patches++;
        }
    }
    return patches;
};

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

Задача: 354. Russian Doll Envelopes
Сложность: hard

Вам дан двумерный массив целых чисел envelopes, где envelopes[i] = [wi, hi] представляет ширину и высоту конверта.

Один конверт может поместиться в другой, если и только если ширина и высота одного конверта больше ширины и высоты другого конверта.
Верните максимальное количество конвертов, которые вы можете вложить друг в друга (т.е. поместить один в другой).

Примечание: Вы не можете поворачивать конверт.

Пример:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

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

1⃣Отсортируйте массив конвертов по возрастанию по первой размерности (ширине) и по убыванию по второй размерности (высоте).

2⃣Извлеките вторую размерность (высоты) отсортированного массива.

3⃣Найдите длину наибольшей возрастающей подпоследовательности в массиве высот.

😎 Решение:

class Solution {
    lengthOfLIS(nums) {
        const dp = [];
        for (const num of nums) {
            let i = this.binarySearch(dp, num);
            if (i < 0) i = -(i + 1);
            if (i < dp.length) dp[i] = num;
            else dp.push(num);
        }
        return dp.length;
    }

    binarySearch(arr, target) {
        let left = 0, right = arr.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (arr[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left < arr.length && arr[left] === target ? left : -(left + 1);
    }

    maxEnvelopes(envelopes) {
        envelopes.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]);
        const secondDim = envelopes.map(envelope => envelope[1]);
        return this.lengthOfLIS(secondDim);
    }
}

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

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

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

Задача: 249. Group Shifted Strings
Сложность: medium

Выполните следующие операции сдвига на строке:
Правый сдвиг: замените каждую букву следующей буквой английского алфавита, где 'z' заменяется на 'a'. Например, "abc" можно сдвинуть вправо на "bcd" или "xyz" можно сдвинуть вправо на "yza".
Левый сдвиг: замените каждую букву предыдущей буквой английского алфавита, где 'a' заменяется на 'z'. Например, "bcd" можно сдвинуть влево на "abc" или "yza" можно сдвинуть влево на "xyz".
Мы можем продолжать сдвигать строку в обоих направлениях, чтобы сформировать бесконечную последовательность сдвигов.
Например, сдвиньте "abc", чтобы сформировать последовательность: ... <-> "abc" <-> "bcd" <-> ... <-> "xyz" <-> "yza" <-> .... <-> "zab" <-> "abc" <-> ...
Вам дан массив строк strings, сгруппируйте все strings[i], которые принадлежат одной и той же последовательности сдвигов. Ответ можно вернуть в любом порядке.

Пример:

Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"]

Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]

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

1️⃣Переберите строки, и для каждой строки найдите ее хэш-значение, сдвигая все символы так, чтобы строка начиналась с 'a'. Значение сдвига равно позиции первого символа строки, и каждый символ сдвигается на это значение с учетом модуля 26.

2️⃣Сопоставьте оригинальную строку с найденным хэш-значением в карте mapHashToList, добавляя оригинальную строку в список, соответствующий ее хэш-значению.

3️⃣Переберите mapHashToList и сохраните список для каждого ключа в карте в массив ответа groups.

😎 Решение:

class Solution {
    shiftLetter(letter, shift) {
        return String.fromCharCode((letter.charCodeAt(0) - shift + 26) % 26 + 'a'.charCodeAt(0));
    }

    getHash(s) {
        const shift = s.charCodeAt(0);
        return Array.from(s, letter => this.shiftLetter(letter, shift)).join('');
    }

    groupStrings(strings) {
        const mapHashToList = new Map();

        for (const str of strings) {
            const hashKey = this.getHash(str);
            if (!mapHashToList.has(hashKey)) {
                mapHashToList.set(hashKey, []);
            }
            mapHashToList.get(hashKey).push(str);
        }

        return Array.from(mapHashToList.values());
    }
}

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

Задача: 999. Available Captures for Rook
Сложность: easy

Вам дана матрица 8 x 8, изображающая шахматную доску. На ней есть ровно одна белая ладья, представленная символом "R", некоторое количество белых слонов "B" и некоторое количество черных пешек "p". Пустые клетки обозначаются символом '.'. Ладья может перемещаться на любое количество клеток по горизонтали или вертикали (вверх, вниз, влево, вправо), пока не достигнет другой фигуры или края доски. Ладья атакует пешку, если она может переместиться на ее клетку за один ход. Примечание: Ладья не может перемещаться через другие фигуры, такие как слоны или пешки. Это означает, что ладья не может атаковать пешку, если путь ей преграждает другая фигура. Верните количество пешек, которые атакует белая ладья.

Пример:

Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]

Output: 3

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

1⃣Поиск ладьи:
Найдите координаты белой ладьи "R" на шахматной доске.

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

3⃣Подсчет атакованных пешек:
Если встреченная фигура - черная пешка "p", увеличьте счетчик атакованных пешек.
Если встреченная фигура - белый слон "B" или край доски, остановитесь в этом направлении.

😎 Решение:

class Solution {
    numRookCaptures(board) {
        const countPawns = (x, y, dx, dy) => {
            while (x >= 0 && x < 8 && y >= 0 && y < 8) {
                if (board[x][y] === 'B') break;
                if (board[x][y] === 'p') return 1;
                x += dx;
                y += dy;
            }
            return 0;
        };

        for (let i = 0; i < 8; i++) {
            for (let j = 0; j < 8; j++) {
                if (board[i][j] === 'R') {
                    return countPawns(i, j, -1, 0) + countPawns(i, j, 1, 0) +
                           countPawns(i, j, 0, -1) + countPawns(i, j, 0, 1);
                }
            }
        }
        return 0;
    }
}

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

Задача: 1029. Two City Scheduling
Сложность: medium

Компания планирует провести интервью с 2n людьми. Учитывая массив costs, где costs[i] = [aCosti, bCosti], стоимость перелета i-го человека в город a равна aCosti, а стоимость перелета i-го человека в город b равна bCosti. Выведите минимальную стоимость перелета каждого человека в город, чтобы в каждый город прибыло ровно n человек.

Пример:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

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

1⃣Вычислить разницу стоимости:
Для каждого человека вычислите разницу в стоимости между перелетом в город A и город B.

2⃣Сортировать по разнице:
Отсортируйте людей по разнице в стоимости перелета в город A и B. Это поможет минимизировать общую стоимость, так как мы сначала будем отправлять тех, для кого разница минимальна.

3⃣Назначить города:
Первые n человек из отсортированного списка отправьте в город A.
Оставшихся n человек отправьте в город B.

😎 Решение:

var twoCitySchedCost = function(costs) {
    costs.sort((a, b) => (a[0] - a[1]) - (b[0] - b[1]));
    let totalCost = 0;
    const n = costs.length / 2;
    for (let i = 0; i < n; i++) {
        totalCost += costs[i][0];
        totalCost += costs[i + n][1];
    }
    return totalCost;
};

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

Задача: 1506. Find Root of N-Ary Tree
Сложность: medium

Вам даны все узлы N-арного дерева в виде массива объектов Node, где каждый узел имеет уникальное значение.

Верните корень N-арного дерева.

Пример:

Input: tree = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]
Explanation: The tree from the input data is shown above.
The driver code creates the tree and gives findRoot the Node objects in an arbitrary order.
For example, the passed array could be [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)] or [Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)].
The findRoot function should return the root Node(1), and the driver code will serialize it and compare with the input data.
The input data and serialized Node(1) are the same, so the test passes.

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

1⃣Используйте хэшсет (named as seen) для отслеживания всех посещенных дочерних узлов. В конечном итоге корневой узел не будет в этом множестве.

2⃣Выполняйте первую итерацию, проходя по элементам входного списка. Для каждого элемента добавляйте его дочерние узлы в хэшсет seen. Поскольку значение каждого узла уникально, можно добавлять либо сам узел, либо просто его значение в хэшсет.

3⃣Посетите список еще раз. На этот раз у нас будут все дочерние узлы в хэшсете. Как только вы наткнетесь на узел, который не находится в хэшсете, это и будет корневой узел, который мы ищем.

😎 Решение:

var findRoot = function(tree) {
    const seen = new Set();

    for (const node of tree) {
        for (const child of node.children) {
            seen.add(child.val);
        }
    }

    for (const node of tree) {
        if (!seen.has(node.val)) {
            return node;
        }
    }
};

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

Задача: 505. The Maze II
Сложность: medium

В лабиринте есть мячик с пустыми пространствами (обозначенными как 0) и стенами (обозначенными как 1). Мячик может перемещаться через пустые пространства, катясь вверх, вниз, влево или вправо, но он не остановится, пока не столкнется со стеной. Когда мячик останавливается, он может выбрать следующее направление.
Дан лабиринт размером m x n, начальная позиция мяча и пункт назначения, где start = [startrow, startcol] и destination = [destinationrow, destinationcol]. Верните кратчайшее расстояние, на которое мячик должен остановиться в пункте назначения. Если мячик не может остановиться в пункте назначения, верните -1.
Расстояние — это количество пройденных пустых пространств мячиком от начальной позиции (исключительно) до пункта назначения (включительно).
Предположим, что границы лабиринта — это стены. В примере ниже они не указаны.

Пример:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: 12
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

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

1⃣Инициализация
Создайте массив distance для хранения минимальных расстояний до каждой позиции, инициализируйте его большими значениями. Установите начальную позицию start на нулевое расстояние и добавьте её в очередь.

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

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

😎 Решение:

var shortestDistance = function(maze, start, destination) {
    const m = maze.length, n = maze[0].length;
    const distance = Array.from({ length: m }, () => Array(n).fill(Infinity));
    distance[start[0]][start[1]] = 0;
    const directions = [[0, 1], [0, -1], [-1, 0], [1, 0]];
    const queue = [start];
    
    while (queue.length) {
        const [sx, sy] = queue.shift();
        for (const [dx, dy] of directions) {
            let x = sx + dx, y = sy + dy, count = 0;
            while (x >= 0 && y >= 0 && x < m && y < n && maze[x][y] === 0) {
                x += dx;
                y += dy;
                count++;
            }
            x -= dx;
            y -= dy;
            if (distance[sx][sy] + count < distance[x][y]) {
                distance[x][y] = distance[sx][sy] + count;
                queue.push([x, y]);
            }
        }
    }
    
    const res = distance[destination[0]][destination[1]];
    return res === Infinity ? -1 : res;
};

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

Задача: 737. Sentence Similarity II
Сложность: medium

Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].
Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c похожи.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
Output: true

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

1⃣Проверить, одинаковой ли длины предложения sentence1 и sentence2. Если нет, вернуть false.

2⃣Построить граф схожести слов с использованием словаря.

3⃣Использовать поиск в глубину (DFS) для проверки транзитивной схожести слов в предложениях.

😎 Решение:

var areSentencesSimilar = function(sentence1, sentence2, similarPairs) {
    if (sentence1.length !== sentence2.length) {
        return false;
    }

    const graph = {};
    for (const [x, y] of similarPairs) {
        if (!graph[x]) graph[x] = [];
        if (!graph[y]) graph[y] = [];
        graph[x].push(y);
        graph[y].push(x);
    }

    const dfs = (word1, word2, visited) => {
        if (word1 === word2) return true;
        visited.add(word1);
        for (const neighbor of graph[word1] || []) {
            if (!visited.has(neighbor) && dfs(neighbor, word2, visited)) {
                return true;
            }
        }
        return false;
    };

    for (let i = 0; i < sentence1.length; i++) {
        const w1 = sentence1[i], w2 = sentence2[i];
        if (w1 !== w2) {
            if (!dfs(w1, w2, new Set())) {
                return false;
            }
        }
    }

    return true;
};

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

Задача: 739. Daily Temperatures
Сложность: medium

Задав массив целых чисел temperature, представляющих дневные температуры, верните массив answer, такой, что answer[i] - это количество дней, которые нужно подождать после i-го дня, чтобы температура стала теплее. Если в будущем не существует дня, для которого это возможно, сохраните answer[i] == 0.

Пример:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

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

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

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

3⃣Возвращайте массив ответов.

😎 Решение:

var dailyTemperatures = function(T) {
    const answer = Array(T.length).fill(0);
    const stack = [];
    
    for (let i = 0; i < T.length; i++) {
        while (stack.length && T[i] > T[stack[stack.length - 1]]) {
            const j = stack.pop();
            answer[j] = i - j;
        }
        stack.push(i);
    }
    
    return answer;

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

Задача: 389. Find the Difference
Сложность: easy

Даны две строки s и t.
Строка t генерируется путем случайного перемешивания строки s с добавлением еще одной буквы в случайную позицию.
Верните букву, которая была добавлена в t.

Пример:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

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

1⃣Отсортируйте строки s и t.

2⃣Итерируйте по длине строк и сравнивайте их посимвольно. Это позволяет проверить, присутствует ли текущий символ строки t в строке s.

3⃣Как только встретится символ, который есть в строке t, но отсутствует в строке s, мы найдем лишний символ, который скрывала строка t все это время.

😎 Решение:

var findTheDifference = function(s, t) {
    let sortedS = s.split('').sort();
    let sortedT = t.split('').sort();

    for (let i = 0; i < sortedS.length; i++) {
        if (sortedS[i] !== sortedT[i]) {
            return sortedT[i];
        }
    }

    return sortedT[sortedS.length];
};

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

Задача: 1033. Moving Stones Until Consecutive
Сложность: medium

На оси X расположены три камня в разных позициях. Вам даны три целых числа a, b и c - позиции камней. За одно движение вы берете камень в конечной точке (т. е. либо в самой низкой, либо в самой высокой позиции камня) и перемещаете его в незанятую позицию между этими конечными точками. Формально, допустим, камни в данный момент находятся в позициях x, y и z, причем x < y < z. Вы берете камень в позиции x или z и перемещаете его в целочисленную позицию k, причем x < k < z и k != y. Игра заканчивается, когда вы больше не можете сделать ни одного хода (то есть камни находятся в трех последовательных позициях). Возвращается целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сыграть, а answer[1] - максимальное количество ходов, которое вы можете сыграть.

Пример:

Input: a = 3, b = 5, c = 1
Output: [1,2]

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

1⃣Сортировка позиций:
Убедитесь, что позиции камней отсортированы в порядке возрастания. Обозначим отсортированные позиции как x, y и z.

2⃣Вычисление минимальных ходов:
Если камни уже находятся в последовательных позициях (то есть y - x == 1 и z - y == 1), минимальное количество ходов равно 0.
Если два камня находятся в соседних позициях, а третий камень на расстоянии более чем одна позиция, минимальное количество ходов равно 1.
В остальных случаях минимальное количество ходов равно 2.

3⃣Вычисление максимальных ходов:
Максимальное количество ходов равно сумме расстояний между соседними камнями минус 2, то есть (y - x - 1) + (z - y - 1).

😎 Решение:

var numMovesStones = function(a, b, c) {
    const stones = [a, b, c].sort((x, y) => x - y);
    const [x, y, z] = stones;
    const minMoves = (y - x <= 2 || z - y <= 2) ? ((y - x === 1 && z - y === 1) ? 0 : 1) : 2;
    const maxMoves = (y - x - 1) + (z - y - 1);
    return [minMoves, maxMoves];
};

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

Задача: 1049. Last Stone Weight II
Сложность: medium

Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два любых камня и разбиваем их вместе. Предположим, что камни имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y приобретает новый вес y - x. В конце игры остается не более одного камня. Верните наименьший возможный вес оставшегося камня. Если камней не осталось, верните 0.

Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

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

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

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

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

😎 Решение:

function lastStoneWeightII(stones) {
    const totalSum = stones.reduce((a, b) => a + b, 0);
    const halfSum = Math.floor(totalSum / 2);
    const dp = Array(halfSum + 1).fill(0);

    for (let stone of stones) {
        for (let j = halfSum; j >= stone; j--) {
            dp[j] = Math.max(dp[j], dp[j - stone] + stone);
        }
    }

    return totalSum - 2 * dp[halfSum];
}

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

Задача: 80. Remove Duplicates from Sorted Array II
Сложность: medium

Дан массив целых чисел nums, отсортированный в неубывающем порядке. Удалите из него некоторые дубликаты на месте так, чтобы каждый уникальный элемент встречался не более двух раз. Относительный порядок элементов должен быть сохранён.
Поскольку в некоторых языках программирования невозможно изменить длину массива, результат следует разместить в первой части массива nums. Более формально, если после удаления дубликатов остаётся k элементов, то первые k элементов массива nums должны содержать итоговый результат. Не важно, что остаётся за пределами первых k элементов.
Верните k после размещения итогового результата в первые k слотов массива nums.
Не выделяйте дополнительное пространство для другого массива. Вы должны сделать это, изменяя исходный массив на месте с использованием дополнительной памяти O(1).

Пример:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

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

1️⃣Инициализация переменных: Используйте две переменные: i, которая указывает на текущий индекс в массиве, и count, которая отслеживает количество каждого элемента. Начните обработку массива с первого элемента (индекс 1), предполагая, что первый элемент всегда имеет count равный 1.

2️⃣Обработка элементов массива: Для каждого элемента в массиве:

3️⃣Если текущий элемент такой же, как предыдущий (nums[i] == nums[i - 1]), увеличьте count.
Если count больше 2, это означает, что текущий элемент встречается более двух раз. В этом случае удалите этот элемент из массива с помощью операции удаления, поддерживаемой вашим языком программирования (например, del, pop, remove), и уменьшите индекс i на 1, чтобы корректно обработать следующий элемент.
Если текущий элемент отличается от предыдущего (nums[i] != nums[i - 1]), это означает начало новой последовательности, поэтому сбросьте count к 1.
Возвращение результата: После обработки всех элементов в массиве, все ненужные дубликаты удалены, и в массиве остаются только допустимые элементы. Верните длину обработанного массива, так как это количество элементов, которые теперь соответствуют условиям задачи.

😎 Решение:

var removeDuplicates = function (nums) {
    let j = 0;
    for (let i = 0; i < nums.length; i++) {
        if (j < 2 || nums[i] > nums[j - 2]) {
            nums[j++] = nums[i];
        }
    }
    return j;
};

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

Задача: 723. Candy Crush
Сложность: medium

Этот вопрос касается реализации базового алгоритма исключения для Candy Crush. Дан целочисленный массив board размером m x n, представляющий сетку конфет, где board[i][j] представляет тип конфеты. Значение board[i][j] == 0 означает, что ячейка пуста. Данная доска представляет собой состояние игры после хода игрока. Теперь необходимо вернуть доску в стабильное состояние, раздавив конфеты по следующим правилам: если три или более конфет одного типа находятся рядом по вертикали или горизонтали, раздавите их все одновременно - эти позиции станут пустыми. После одновременного раздавливания всех конфет, если на пустом месте доски есть конфеты, расположенные сверху, то эти конфеты будут падать, пока не ударятся о конфету или дно одновременно. Новые конфеты не будут падать за верхнюю границу. После выполнения описанных выше действий может остаться больше конфет, которые можно раздавить. Если конфет, которые можно раздавить, больше не существует (т. е. доска стабильна), верните текущую доску. Выполняйте описанные выше правила, пока доска не станет стабильной, затем верните стабильную доску.

Пример:

Input: board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]
Output: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]

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

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

2⃣Удалите отмеченные конфеты, установив их значение в 0.

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

😎 Решение:

var candyCrush = function(board) {
    let m = board.length;
    let n = board[0].length;
    let stable = false;

    while (!stable) {
        stable = true;
        let crush = Array.from({ length: m }, () => Array(n).fill(false));

        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n - 2; j++) {
                let v = Math.abs(board[i][j]);
                if (v !== 0 && v === Math.abs(board[i][j + 1]) && v === Math.abs(board[i][j + 2])) {
                    stable = false;
                    crush[i][j] = crush[i][j + 1] = crush[i][j + 2] = true;
                }
            }
        }

        for (let i = 0; i < m - 2; i++) {
            for (let j = 0; j < n; j++) {
                let v = Math.abs(board[i][j]);
                if (v !== 0 && v === Math.abs(board[i + 1][j]) && v === Math.abs(board[i + 2][j])) {
                    stable = false;
                    crush[i][j] = crush[i + 1][j] = crush[i + 2][j] = true;
                }
            }
        }

        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (crush[i][j]) {
                    board[i][j] = 0;
                }
            }
        }

        for (let j = 0; j < n; j++) {
            let idx = m - 1;
            for (let i = m - 1; i >= 0; i--) {
                if (board[i][j] !== 0) {
                    board[idx][j] = board[i][j];
                    idx--;
                }
            }
            for (let i = idx; i >= 0; i--) {
                board[i][j] = 0;
            }
        }
    }

    return board;
};

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

Задача: 420. Strong Password Checker
Сложность: hard

Пароль считается надежным, если выполняются следующие условия: в нем не менее 6 и не более 20 символов. он содержит не менее одной строчной буквы, не менее одной заглавной буквы и не менее одной цифры. он не содержит трех повторяющихся символов подряд (например, "Baaabb0" - слабый, а "Baaba0" - сильный). Учитывая строку пароля, верните минимальное количество шагов, необходимых для того, чтобы сделать пароль сильным. Если пароль уже сильный, верните 0. За один шаг можно: вставить один символ в пароль, удалить один символ из пароля или заменить один символ пароля другим символом.

Пример:

Input: password = "a"
Output: 5

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

1⃣Определите количество недостающих символов до минимума и превышающих символов для ограничения длины пароля. Также определите наличие строчных, заглавных букв и цифр.

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

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

😎 Решение:

function strongPasswordChecker(s) {
    const n = s.length;
    const hasLower = /[a-z]/.test(s);
    const hasUpper = /[A-Z]/.test(s);
    const hasDigit = /\d/.test(s);
    let repeatCount = 0;
    
    for (let i = 0; i < n;) {
        const start = i;
        while (i < n && s[i] === s[start]) {
            i++;
        }
        repeatCount += Math.floor((i - start) / 3);
    }
    
    const missingTypes = 3 - [hasLower, hasUpper, hasDigit].filter(Boolean).length;
    
    if (n < 6) {
        return Math.max(missingTypes, 6 - n);
    } else if (n <= 20) {
        return Math.max(missingTypes, repeatCount);
    } else {
        let excessChars = n - 20;
        let overLenReduction = 0;
        for (let i = 2; i < n && excessChars > 0; i++) {
            if (i % 3 === 2 && s[i] === s[i - 1] && s[i] === s[i - 2]) {
                overLenReduction++;
                excessChars--;
            }
        }
        repeatCount -= overLenReduction;
        return (n - 20) + Math.max(missingTypes, repeatCount);
    }
}

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