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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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