Задача: 1509. Minimum Difference Between Largest and Smallest Value in Three Moves
Сложность: medium

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

За один ход вы можете выбрать один элемент массива nums и изменить его на любое значение.

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

Пример:

Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

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

1⃣Инициализация: определите размер массива nums, если размер меньше или равен 4, верните 0. Отсортируйте массив nums и инициализируйте переменную minDiff очень большим числом.

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

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

😎 Решение:

var minDifference = function(nums) {
    const numsSize = nums.length
    
    if (numsSize <= 4) return 0
    
    nums.sort((a, b) => a - b)
    
    let minDiff = Infinity
    
    for (let left = 0; left < 4; left++) {
        const right = numsSize - 4 + left
        minDiff = Math.min(minDiff, nums[right] - nums[left])
    }
    
    return minDiff
}

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

Задача: 317. Shortest Distance from All Buildings
Сложность: hard

Дана сетка m x n, содержащая значения 0, 1 или 2, где:
каждое 0 обозначает пустую землю, по которой можно свободно проходить,
каждое 1 обозначает здание, через которое нельзя пройти,
каждое 2 обозначает препятствие, через которое нельзя пройти.
Вы хотите построить дом на пустой земле, чтобы он достиг всех зданий с минимальным суммарным расстоянием. Можно перемещаться только вверх, вниз, влево и вправо.
Верните минимальное суммарное расстояние для такого дома. Если построить такой дом невозможно согласно указанным правилам, верните -1.
Суммарное расстояние — это сумма расстояний между домами друзей и точкой встречи.

Пример:

Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7

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

1⃣Инициализация и запуск BFS
Для каждой пустой ячейки (0) в сетке grid запустите BFS, обходя все соседние ячейки в 4 направлениях, которые не заблокированы и не посещены, отслеживая расстояние от начальной ячейки.

2⃣Обработка BFS и обновление расстояний
При достижении здания (1) увеличьте счетчик достигнутых домов housesReached и суммарное расстояние distanceSum на текущее расстояние. Если housesReached равно общему количеству зданий, верните суммарное расстояние. Если BFS не может достигнуть всех домов, установите значение каждой посещенной пустой ячейки в 2, чтобы не запускать новый BFS из этих ячеек, и верните INT_MAX.

3⃣Обновление и возврат минимального расстояния
Обновите минимальное расстояние (minDistance) после каждого вызова BFS. Если возможно достигнуть все дома из любой пустой ячейки, верните найденное минимальное расстояние. В противном случае, верните -1.

😎 Решение:

class Solution {
    bfs(grid, row, col, totalHouses) {
        const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        const rows = grid.length, cols = grid[0].length;
        let distanceSum = 0, housesReached = 0, steps = 0;
        const q = [[row, col]];
        const vis = Array.from({ length: rows }, () => Array(cols).fill(false));
        vis[row][col] = true;

        while (q.length && housesReached !== totalHouses) {
            let size = q.length;
            while (size-- > 0) {
                const [r, c] = q.shift();
                if (grid[r][c] === 1) {
                    distanceSum += steps;
                    housesReached++;
                    continue;
                }
                for (const [dr, dc] of dirs) {
                    const nr = r + dr, nc = c + dc;
                    if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && !vis[nr][nc] && grid[nr][nc] !== 2) {
                        vis[nr][nc] = true;
                        q.push([nr, nc]);
                    }
                }
            }
            steps++;
        }

        if (housesReached !== totalHouses) {
            for (let r = 0; r < rows;

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

Задача: 371. Sum of Two Integers
Сложность: medium

Даны два целых числа a и b. Вернуть сумму этих двух чисел, не используя операторы + и -.

Пример:

Input: a = 1, b = 2
Output: 3

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

1⃣Упростите задачу до двух случаев: сумма или вычитание двух положительных целых чисел: x ± y, где x > y. Запомните знак результата.

2⃣Если нужно вычислить сумму:
Пока перенос не равен нулю (y != 0):
Текущий ответ без переноса равен XOR x и y: answer = x ^ y.
Текущий перенос равен сдвинутому влево AND x и y: carry = (x & y) << 1.
Подготовьтесь к следующему циклу: x = answer, y = carry.
Верните x * sign.

3⃣Если нужно вычислить разность:
Пока заимствование не равно нулю (y != 0):
Текущий ответ без заимствования равен XOR x и y: answer = x ^ y.
Текущее заимствование равно сдвинутому влево AND НЕ x и y: borrow = ((~x) & y) << 1.
Подготовьтесь к следующему циклу: x = answer, y = borrow.
Верните x * sign.

😎 Решение:

class Solution {
    getSum(a, b) {
        let x = Math.abs(a), y = Math.abs(b);
        if (x < y) return this.getSum(b, a);
        const sign = a > 0 ? 1 : -1;

        if (a * b >= 0) {
            while (y !== 0) {
                const carry = (x & y) << 1;
                x ^= y;
                y = carry;
            }
        } else {
            while (y !== 0) {
                const borrow = ((~x) & y) << 1;
                x ^= y;
                y = borrow;
            }
        }
        return x * sign;
    }
}

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

Задача: 246. Strobogrammatic Number
Сложность: easy

Дана строка num, представляющая собой целое число. Верните true, если num является стробограмматическим числом.
Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).

Пример:

Input: num = "69"
Output: true

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

1️⃣Создайте новую строку, перебирая оригинальную строку num в обратном порядке. Для каждого символа проверьте, является ли он допустимым для поворота (0, 1, 6, 8, 9). Если символ недопустим (2, 3, 4, 5, 7), немедленно верните false.

2️⃣Для каждого допустимого символа добавьте его соответствующее значение после поворота (0 ⟶ 0, 1 ⟶ 1, 6 ⟶ 9, 8 ⟶ 8, 9 ⟶ 6) в новую строку.

3️⃣Сравните полученную строку с исходной строкой num. Если они равны, верните true, в противном случае верните false.

😎 Решение:

class Solution {
    isStrobogrammatic(num) {
        let rotated = "";
        for (let i = num.length - 1; i >= 0; i--) {
            const c = num[i];
            if (c === '0' || c === '1' || c === '8') {
                rotated += c;
            } else if (c === '6') {
                rotated += '9';
            } else if (c === '9') {
                rotated += '6';
            } else {
                return false;
            }
        }
        return num === rotated;
    }
}

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

Задача: 747. Largest Number At Least Twice of Others
Сложность: easy

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

Пример:

Input: nums = [3,6,1,0]
Output: 1

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

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

2⃣Проверьте, является ли этот максимальный элемент по крайней мере в два раза больше всех остальных элементов массива.

3⃣Если условие выполняется, верните индекс максимального элемента, иначе верните -1.

😎 Решение:

var minCostClimbingStairs = function(cost) {
    let dp = cost.slice();
    for (let i = 2; i < cost.length; i++) {
        dp[i] += Math.min(dp[i - 1], dp[i - 2]);
    }
    return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
};

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

Сложность: medium
Задача: 562. Longest Line of Consecutive One in Matrix

Дана бинарная матрица размера m x n. Вернуть длину самой длинной последовательной линии из единиц в матрице.
Линия может быть горизонтальной, вертикальной, диагональной или анти-диагональной.

Пример:

Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3

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

1⃣Создайте 3 матрицы для хранения текущей длины последовательных единиц: horizontal, vertical, diagonal и anti_diagonal.

2⃣Итерируйте через каждый элемент матрицы: Если элемент равен 1, обновите соответствующие значения в матрицах horizontal, vertical, diagonal и anti_diagonal. Обновите максимальную длину последовательной линии.

3⃣Верните максимальную длину.

😎 Решение:

class Solution {
    longestLine(mat) {
        if (!mat || !mat.length || !mat[0].length) {
            return 0;
        }
        
        const m = mat.length;
        const n = mat[0].length;
        let maxLength = 0;
        
        const horizontal = Array.from({ length: m }, () => Array(n).fill(0));
        const vertical = Array.from({ length: m }, () => Array(n).fill(0));
        const diagonal = Array.from({ length: m }, () => Array(n).fill(0));
        const antiDiagonal = Array.from({ length: m }, () => Array(n).fill(0));
        
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (mat[i][j] === 1) {
                    horizontal[i][j] = (j > 0 ? horizontal[i][j-1] : 0) + 1;
                    vertical[i][j] = (i > 0 ? vertical[i-1][j] : 0) + 1;
                    diagonal[i][j] = (i > 0 && j > 0 ? diagonal[i-1][j-1] : 0) + 1;
                    antiDiagonal[i][j] = (i > 0 && j < n - 1 ? antiDiagonal[i-1][j+1] : 0) + 1;
                    
                    maxLength = Math.max(maxLength, horizontal[i][j], vertical[i][j], diagonal[i][j], antiDiagonal[i][j]);
                }
            }
        }
        
        return maxLength;
    }
}

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

Сложность: easy
Задача: 375. Guess Number Higher or Lower II

Мы играем в угадайку. Правила игры следующие:

Я загадываю число между 1 и n.
Вы угадываете число.
Если вы угадаете правильное число, вы выигрываете игру.
Если вы угадаете неправильное число, я скажу вам, загаданное число больше или меньше, и вы продолжите угадывать.
Каждый раз, когда вы угадываете неправильное число x, вы платите x долларов. Если у вас закончились деньги, вы проигрываете игру.
Дано число n. Верните минимальную сумму денег, необходимую для гарантированной победы независимо от того, какое число я загадаю.

Пример:

Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.

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

1⃣В методе "грубой силы" для чисел в диапазоне (i, j) выбираем каждое число от i до j в качестве опорного и находим максимальную стоимость из его левых и правых сегментов. Если выбрать число из диапазона (i, (i + j) / 2) как опорное, правый сегмент будет длиннее левого, что приведет к большему максимальному затратам из правого сегмента.

2⃣Наша цель - уменьшить большие затраты, приходящиеся на правый сегмент. Поэтому целесообразно выбирать опорное число из диапазона ((i + j) / 2, j). В этом случае затраты на оба сегмента будут ближе друг к другу, что минимизирует общую стоимость.

3⃣Вместо перебора от i до j, итерируем от (i + j) / 2 до j, находя минимально возможные затраты аналогично методу грубой силы.

😎 Решение:

var calculate = function(low, high) {
    if (low >= high) return 0;
    let minres = Infinity;
    for (let i = low; i <= high; i++) {
        let res = i + Math.max(calculate(i + 1, high), calculate(low, i - 1));
        minres = Math.min(res, minres);
    }
    return minres;
};

var getMoneyAmount = function(n) {
    return calculate(1, n);
};

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

Задача: 561. Array Partition
Сложность: easy

Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.

Пример:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

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

1⃣Отсортируйте массив nums в неубывающем порядке.

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

3⃣Суммируйте выбранные элементы и верните эту сумму.

😎 Решение:

class Solution {
    arrayPairSum(nums) {
        nums.sort((a, b) => a - b);
        let sum = 0;
        for (let i = 0; i < nums.length; i += 2) {
            sum += nums[i];
        }
        return sum;
    }
}

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

Задача: 919. Complete Binary Tree Inserter
Сложность: medium

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

Реализуйте класс CBTInserter: CBTInserter(TreeNode root) Инициализирует структуру данных корнем полного бинарного дерева. int insert(int v) Вставляет TreeNode в дерево со значением Node.val == val так, что дерево остается полным, и возвращает значение родителя вставленного TreeNode. TreeNode get_root() Возвращает корневой узел дерева.

Пример:

Input
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
Output
[null, 1, 2, [1, 2, 3, 4]]

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

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

2⃣Вставка: Добавление нового узла в первое доступное место слева направо.

3⃣Возвращение корня: Просто возвращает корневой узел.

😎 Решение:

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class CBTInserter {
    constructor(root) {
        this.root = root;
        this.deque = [];
        const queue = [root];
        while (queue.length > 0) {
            const node = queue.shift();
            if (!node.left || !node.right) {
                this.deque.push(node);
            }
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
        }
    }

    insert(v) {
        const node = this.deque[0];
        const newNode = new TreeNode(v);
        if (!node.left) {
            node.left = newNode;
        } else {
            node.right = newNode;
            this.deque.shift();
        }
        this.deque.push(newNode);
        return node.val;
    }

    get_root() {
        return this.root;
    }
}

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

Задача: 559. Maximum Depth of N-ary Tree
Сложность: easy

Дано n-арное дерево, найдите его максимальную глубину.
Максимальная глубина - это количество узлов вдоль самого длинного пути от корневого узла до самого дальнего листового узла.
Сериализация ввода n-арного дерева представлена в порядке уровня, каждая группа дочерних узлов разделена значением null (см. примеры).

Пример:

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

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

1⃣Интуитивный подход заключается в решении задачи с помощью рекурсии.

2⃣Здесь мы демонстрируем пример с использованием стратегии поиска в глубину (DFS - Depth First Search).

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

😎 Решение:

class Solution {
    maxDepth(root) {
        if (root === null) {
            return 0;
        } else if (root.children.length === 0) {
            return 1;
        } else {
            let heights = root.children.map(child => this.maxDepth(child));
            return Math.max(...heights) + 1;
        }
    }
}

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

Задача: 730. Count Different Palindromic Subsequences
Сложность: hard

Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi.

Пример:

Input: s = "bccb"
Output: 6

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

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

2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j.

3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок.

😎 Решение:

var countPalindromicSubsequences = function(s) {
    const MOD = 10**9 + 7;
    const n = s.length;
    const dp = Array.from({ length: n }, () => Array(n).fill(0));

    for (let i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    for (let length = 2; length <= n; length++) {
        for (let i = 0; i <= n - length; i++) {
            const j = i + length - 1;
            if (s[i] === s[j]) {
                let l = i + 1, r = j - 1;
                while (l <= r && s[l] !== s[i]) l++;
                while (l <= r && s[r] !== s[j]) r--;
                if (l > r) {
                    dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
                } else if (l === r) {
                    dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
                } else {
                    dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1];
                }
            } else {
                dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
            }
            dp[i][j] = (dp[i][j] + MOD) % MOD;
        }
    }

    return dp[0][n - 1];
};

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

Задача: 30. Substring with Concatenation of All Words
Сложность: hard

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

Пример:

Input: s = "barfoothefoobarman", words = ["foo","bar"]  
Output: [0,9]

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

1️⃣ Вычисляем:
- len — длина одного слова
- windowSize — общее число символов в одной перестановке всех слов
- Если s.length < windowSize, возвращаем []

2️⃣ Заполняем Map m, где ключ — слово из words, значение — количество его вхождений

3️⃣ Двигаемся по строке s посимвольно:
- Для каждого индекса start проверяем, является ли подстрока от start длины windowSize валидной комбинацией слов из m
- Для проверки используем isConcat()

😎 Решение:

var findSubstring = function(s, words) {
    const len = words[0].length;
    const windowSize = words.length * len;
    if (s.length < windowSize) return [];

    const m = new Map();
    const res = [];

    for (let word of words) {
        m.set(word, (m.get(word) || 0) + 1);
    }

    for (let start = 0; start <= s.length - windowSize; start++) {
        if (isConcat(s, new Map(m), len, start, start + windowSize - 1)) {
            res.push(start);
        }
    }

    return res;
};

function isConcat(s, m, len, start, end) {
    let chars = m.size;
    for (let i = start; i <= end; i += len) {
        const word = s.substring(i, i + len);
        if (!m.has(word) || m.get(word) === 0) return false;
        m.set(word, m.get(word) - 1);
        if (m.get(word) === 0) chars--;
    }
    return chars === 0;
}

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

Задача: 42. Trapping Rain Water
Сложность: hard

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

Пример:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

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

1️⃣Найдите максимальную высоту столбца с левого конца до индекса i в массиве left_max.

2️⃣Найдите максимальную высоту столбца с правого конца до индекса i в массиве right_max.

3️⃣Итерируйте по массиву высот height и обновляйте ans: добавьте min(left_max[i], right_max[i]) - height[i] к ans.

😎 Решение:

var trap = function (height) {
    if (height.length == 0) return 0;
    let ans = 0;
    let size = height.length;
    let left_max = new Array(size).fill(0),
        right_max = new Array(size).fill(0);
    left_max[0] = height[0];
    for (let i = 1; i < size; i++) {
        left_max[i] = Math.max(height[i], left_max[i - 1]);
    }
    right_max[size - 1] = height[size - 1];
    for (let i = size - 2; i >= 0; i--) {
        right_max[i] = Math.max(height[i], right_max[i + 1]);
    }
    for (let i = 1; i < size - 1; i++) {
        ans += Math.min(left_max[i], right_max[i]) - height[i];
    }
    return ans;
};

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

Задача: 314. Binary Tree Vertical Order Traversal
Сложность: medium

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

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

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

1⃣Создайте хэш-таблицу с именем columnTable для отслеживания результатов.

2⃣Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь.

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

😎 Решение:

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class Solution {
    verticalOrder(root) {
        const output = [];
        if (root === null) {
            return output;
        }

        const columnTable = new Map();
        const queue = [];
        let column = 0;
        queue.push([root, column]);

        while (queue.length > 0) {
            const [node, col] = queue.shift();

            if (node !== null) {
                if (!columnTable.has(col)) {
                    columnTable.set(col, []);
                }
                columnTable.get(col).push(node.val);

                queue.push([node.left, col - 1]);
                queue.push([node.right, col + 1]);
            }
        }

        const sortedKeys = Array.from(columnTable.keys()).sort((a, b) => a - b);
        for (const key of sortedKeys) {
            output.push(columnTable.get(key));
        }

        return output;
    }
}

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

Задача: 947. Most Stones Removed with Same Row or Column
Сложность: medium

Учитывая массив stones длины n, где stones[i] = [xi, yi] представляет местоположение i-го камня, верните наибольшее возможное количество камней, которые могут быть удалены.

Пример:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

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

1⃣Представить каждую строку и столбец как узлы в графе.

2⃣Создать связи между узлами для камней, которые находятся в той же строке или столбце.
Использовать алгоритм поиска в глубину (DFS) или объединение-поиска (Union-Find), чтобы найти компоненты связности.

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

😎 Решение:

var removeStones = function(stones) {
    const parent = {};
    
    function find(x) {
        if (!(x in parent)) parent[x] = x;
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    }
    
    function union(x, y) {
        parent[find(x)] = find(y);
    }
    
    for (const [x, y] of stones) {
        union(x, ~y);
    }
    
    const uniqueRoots = new Set(Object.keys(parent).map(find));
    return stones.length - uniqueRoots.size;
};

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

Задача: 152. Maximum Product Subarray
Сложность: medium

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

Пример:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

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

1️⃣Инициализация:
Если массив nums пуст, возвращаем 0, так как нет элементов для обработки.
Инициализируем переменную result первым элементом массива, чтобы иметь начальную точку сравнения для нахождения максимального произведения.


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

3️⃣Вычисление произведения и обновление результата:
Для каждой итерации внутреннего цикла умножаем текущий элемент nums[j] на аккумулирующую переменную accu и проверяем, не стало ли текущее произведение больше максимального найденного до этого.
Обновляем переменную result, если текущее произведение accu превышает текущее максимальное значение result.


😎 Решение:

var maxProduct = function (nums) {
    if (nums.length === 0) return 0;

    let result = nums[0];

    for (let i = 0; i < nums.length; i++) {
        let accu = 1;
        for (let j = i; j < nums.length; j++) {
            accu *= nums[j];
            result = Math.max(result, accu);
        }
    }

    return result;
};

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

Задача: 88. Merge Sorted Array
Сложность: easy

Вам даны два массива целых чисел nums1 и nums2, отсортированных в порядке неубывания, а также два целых числа m и n, представляющих количество элементов в nums1 и nums2 соответственно.
Слейте nums1 и nums2 в один массив, отсортированный в порядке неубывания.
Итоговый отсортированный массив не должен возвращаться функцией, а должен храниться внутри массива nums1. Чтобы это обеспечить, длина nums1 составляет m + n, где первые m элементов обозначают элементы, которые должны быть объединены, а последние n элементов установлены в 0 и должны быть проигнорированы. Длина nums2 составляет n.

Пример:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

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

1️⃣Самая простая реализация заключалась бы в создании копии значений в nums1, называемой nums1Copy, а затем использовании двух указателей для чтения и одного указателя для записи для чтения значений из nums1Copy и nums2 и записи их в nums1.

2️⃣Инициализируйте nums1Copy новым массивом, содержащим первые m значений nums1.
Инициализируйте указатель для чтения p1 в начале nums1Copy.
Инициализируйте указатель для чтения p2 в начале nums2.

3️⃣Инициализируйте указатель для записи p в начале nums1.
Пока p все еще находится внутри nums1:
Если nums1Copy[p1] существует и меньше или равно nums2[p2]:
Запишите nums1Copy[p1] в nums1[p], и увеличьте p1 на 1.
Иначе
Запишите nums2[p2] в nums1[p], и увеличьте p2 на 1.
Увеличьте p на 1.

😎 Решение:

var merge = function (nums1, m, nums2, n) {
    let nums1Copy = nums1.slice(0, m);
    let p1 = 0;
    let p2 = 0;
    for (let p = 0; p < m + n; p++) {
        if (p2 >= n || (p1 < m && nums1Copy[p1] < nums2[p2])) {
            nums1[p] = nums1Copy[p1++];
        } else {
            nums1[p] = nums2[p2++];
        }
    }
}

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

Задача: 110. Balanced Binary Tree
Сложность: easy

Дано бинарное дерево, определите, является ли оно
сбалансированным по высоте.

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: true

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

1️⃣Сначала мы определяем функцию height, которая для любого узла p в дереве T возвращает:
-1, если p является пустым поддеревом, т.е. null;
1 + max(height(p.left), height(p.right)) в противном случае.

2️⃣Теперь, когда у нас есть метод для определения высоты дерева, остается только сравнить высоты детей каждого узла. Дерево T с корнем r является сбалансированным тогда и только тогда, когда высоты его двух детей отличаются не более чем на 1 и поддеревья каждого ребенка также сбалансированы.

3️⃣Следовательно, мы можем сравнить высоты двух дочерних поддеревьев, а затем рекурсивно проверить каждое из них:
Если root == NULL, возвращаем true.
Если abs(height(root.left) - height(root.right)) > 1, возвращаем false.
В противном случае возвращаем isBalanced(root.left) && isBalanced(root.right).

😎 Решение:

var height = function (root) {
    if (root == null) {
        return -1;
    }
    return 1 + Math.max(height(root.left), height(root.right));
};

var isBalanced = function (root) {
    if (root == null) {
        return true;
    }
    return (
        Math.abs(height(root.left) - height(root.right)) < 2 &&
        isBalanced(root.left) &&
        isBalanced(root.right)
    );
};

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

Задача: 1372. Longest ZigZag Path in a Binary Tree
Сложность: medium

Вам дан корень бинарного дерева.

Зигзагообразный путь для бинарного дерева определяется следующим образом:

Выберите любой узел в бинарном дереве и направление (вправо или влево).
Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу.
Измените направление с вправо на влево или с влево на вправо.
Повторяйте второй и третий шаги, пока не сможете двигаться по дереву.
Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0).

Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве.

Пример:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

1⃣Рекурсивная функция DFS:
Создайте рекурсивную функцию dfs, которая будет выполнять обход дерева и отслеживать текущую длину зигзагообразного пути и направление движения (влево или вправо).

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

3⃣Рекурсивный вызов для левого и правого дочерних узлов:
Рекурсивно вызывайте функцию dfs для левого и правого дочерних узлов с обновленными параметрами длины и направления.

😎 Решение:

var longestZigZag = function(root) {
    let maxLength = 0;

    const dfs = (node, isLeft, length) => {
        if (!node) return;
        maxLength = Math.max(maxLength, length);
        if (isLeft) {
            dfs(node.left, false, length + 1);
            dfs(node.right, true, 1);
        } else {
            dfs(node.right, true, length + 1);
            dfs(node.left, false, 1);
        }
    };

    dfs(root, true, 0);
    dfs(root, false, 0);

    return maxLength;
};

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

Задача: 1663. Smallest String With A Given Numeric Value
Сложность: medium

Числовое значение строчной буквы определяется ее позицией (начиная с 1) в алфавите, поэтому числовое значение a равно 1, числовое значение b равно 2, числовое значение c равно 3 и так далее.

Числовое значение строки, состоящей из строчных букв, определяется как сумма числовых значений ее символов. Например, числовое значение строки "abe" равно 1 + 2 + 5 = 8.

Вам даны два целых числа n и k. Верните лексикографически наименьшую строку длиной n с числовым значением, равным k.

Обратите внимание, что строка x лексикографически меньше строки y, если x идет перед y в словарном порядке, то есть либо x является префиксом y, либо, если i - первая позиция, где x[i] != y[i], то x[i] идет перед y[i] в алфавитном порядке.

Пример:

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

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

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

2⃣Итерация от позиции 1 до n и заполнение символом каждой позиции:
Найти позиции, которые нужно заполнить, исключая текущую позицию, задаваемую переменной positionsLeft как n - position - 1.
Если значение k больше, чем positionsLeft * 26, зарезервировать числовое значение 26 (символ z) для всех оставшихся позиций positionsLeft. Вычислить значение текущей позиции, заданное переменной add, как k - (positionsLeft * 26). Вычесть рассчитанное значение add из k, чтобы найти оставшееся значение k после заполнения текущей позиции.
Иначе, заполнить текущую позицию символом a, имеющим числовое значение 1. Вычесть 1 из k, чтобы найти оставшееся значение k после заполнения текущей позиции.

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

😎 Решение:

class Solution {
    getSmallestString(n, k) {
        let result = Array(n).fill('a');
        
        for (let position = 0; position < n; position++) {
            let positionsLeft = (n - position - 1);
            if (k > positionsLeft * 26) {
                let add = k - (positionsLeft * 26);
                result[position] = String.fromCharCode(97 + add - 1);
                k -= add;
            } else {
                k -= 1;
            }
        }
        
        return result.join('');
    }
}

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