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

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

Задача: 677. Map Sum Pairs
Сложность: medium

Создайте карту, которая позволяет выполнять следующие действия:
Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:
MapSum() Инициализирует объект MapSum.
void insert(String key, int val) Вставляет пару ключ-значение в карту. Если ключ уже существовал, исходная пара ключ-значение будет заменена на новую.
int sum(string prefix) Возвращает сумму всех значений пар, у которых ключ начинается с данного префикса.

Пример:

Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]

Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

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

1⃣Для каждого ключа в карте проверить, начинается ли этот ключ с данного префикса.

2⃣Если ключ начинается с префикса, добавить его значение к ответу.

3⃣Вернуть полученную сумму как результат.

😎 Решение:

class MapSum {
    constructor() {
        this.map = new Map();
    }
    insert(key, val) {
        this.map.set(key, val);
    }
    sum(prefix) {
        let ans = 0;
        for (let [key, val] of this.map) {
            if (key.startsWith(prefix)) {
                ans += val;
            }
        }
        return ans;
    }
}

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

Задача: 1496. Path Crossing
Сложность: easy

Дана строка path, где path[i] = 'N', 'S', 'E' или 'W', каждая из которых представляет движение на одну единицу на север, юг, восток или запад соответственно. Вы начинаете с точки (0, 0) на 2D плоскости и идете по пути, указанному в path.

Верните true, если путь пересекает сам себя в какой-либо точке, то есть если вы в какой-то момент окажетесь в месте, которое уже посещали ранее. В противном случае верните false.

Пример:

Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.

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

1⃣Инициализация переменных:
Создать хэш-карту moves, которая сопоставляет символы 'N', 'S', 'E', 'W' с соответствующими значениями.
Инициализировать множество visited с начальной точкой (0, 0). Установить начальные координаты x = 0 и y = 0.

2⃣Проход по строке path: Для каждого символа c в path получить значения (dx, dy) из moves[c]. Обновить координаты: добавить dx к x и dy к y. Проверить, содержится ли текущая точка (x, y) в visited. Если да, вернуть true. Добавить текущую точку (x, y) в visited.

3⃣Возврат результата:
Если ни одна точка не пересекалась, вернуть false.

😎 Решение:

var isPathCrossing = function(path) {
    const moves = {
        'N': [0, 1], 'S': [0, -1],
        'E': [1, 0], 'W': [-1, 0]
    };
    const visited = new Set(['0,0']);
    let x = 0, y = 0;

    for (const c of path) {
        const [dx, dy] = moves[c];
        x += dx;
        y += dy;
        const point = `${x},${y}`;
        if (visited.has(point)) {
            return true;
        }
        visited.add(point);
    }

    return false;
};

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

Задача: 717. 1-bit and 2-bit Characters
Сложность: easy

У нас есть два специальных символа: первый символ может быть представлен одним битом 0. Второй символ может быть представлен двумя битами (10 или 11). Если задан двоичный массив bits, который заканчивается 0, верните true, если последний символ должен быть однобитным.

Пример:

Input: bits = [1,0,0]
Output: true

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

1⃣Инициализируйте индекс для итерации по массиву.

2⃣Пройдите по массиву, увеличивая индекс на 1, если текущий бит равен 0, и на 2, если текущий бит равен 1.

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

😎 Решение:

var isOneBitCharacter = function(bits) {
    let i = 0;
    while (i < bits.length - 1) {
        i += bits[i] + 1;
    }
    return i === bits.length - 1;
};

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

Задача: 319. Bulb Switcher
Сложность: medium

Есть n лампочек, которые изначально выключены. Сначала вы включаете все лампочки, затем выключаете каждую вторую лампочку.
На третьем раунде вы переключаете каждую третью лампочку (включаете, если она выключена, или выключаете, если она включена). На i-ом раунде вы переключаете каждую i-ую лампочку. На n-ом раунде вы переключаете только последнюю лампочку.
Верните количество лампочек, которые будут включены после n раундов.

Пример:

Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off]. 
So you should return 1 because there is only one bulb is on.
Explanation: The two words can be "abcw", "xtfn".

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

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

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

3⃣Подсчет включенных лампочек
Количество лампочек, которые будут включены после n раундов.

😎 Решение:

var bulbSwitch = function(n) {
    return Math.floor(Math.sqrt(n));
};

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

Задача: 494. Target Sum
Сложность: medium

Вам дан массив целых чисел nums и целое число target.
Вы хотите создать выражение из nums, добавляя один из символов '+' или '-' перед каждым числом в nums, а затем объединяя все числа.
Например, если nums = [2, 1], вы можете добавить '+' перед 2 и '-' перед 1, а затем объединить их, чтобы получить выражение "+2-1".
Верните количество различных выражений, которые можно построить и которые оцениваются в target.

Пример:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

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

1⃣Инициализация и вызов рекурсивной функции
Создайте переменную для хранения количества решений (count). Вызовите рекурсивную функцию calculate с начальными параметрами (nums, начальный индекс 0, начальная сумма 0, и target).

2⃣Рекурсивная функция calculate
Если текущий индекс равен длине массива, проверьте, равна ли текущая сумма значению target. Если да, увеличьте счетчик решений. В противном случае, вызовите функцию рекурсивно дважды: добавляя и вычитая текущее значение из суммы.

3⃣Возврат результата
После завершения всех рекурсивных вызовов верните значение счетчика решений.

😎 Решение:

class Solution {
    constructor() {
        this.count = 0;
    }

    findTargetSumWays(nums, S) {
        this.calculate(nums, 0, 0, S);
        return this.count;
    }

    calculate(nums, i, sum, S) {
        if (i === nums.length) {
            if (sum === S) {
                this.count++;
            }
        } else {
            this.calculate(nums, i + 1, sum + nums[i], S);
            this.calculate(nums, i + 1, sum - nums[i], S);
        }
    }
}

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

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

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

Задача: 49. Group Anagrams
Сложность: medium

Дан массив строк strs. Сгруппируйте анаграммы вместе. Вы можете вернуть ответ в любом порядке.
Анаграмма — это слово или фраза, сформированная путем перестановки букв другого слова или фразы, обычно используя все исходные буквы ровно один раз.

Пример:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

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

1️⃣Поддерживайте карту ans: {String -> List}, где каждый ключ K — это отсортированная строка, а каждое значение — это список строк из исходного ввода, которые при сортировке равны K.

2️⃣В Java ключ будет храниться как строка, например, code. В Python ключ будет храниться как хешируемый кортеж, например, ('c', 'o', 'd', 'e').

3️⃣Используя эту структуру данных, можно легко сгруппировать анаграммы, сопоставляя строки после сортировки их символов с ключами в карте.

😎 Решение:

var groupAnagrams = function (strs) {
    let map = new Map();
    for (let str of strs) {
        let chars = Array.from(str);
        chars.sort();
        let key = chars.join("");
        if (!map.has(key)) map.set(key, []);
        map.get(key).push(str);
    }
    return Array.from(map.values());
};

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

Задача: 310. Minimum Height Trees
Сложность: medium

Дерево — это неориентированный граф, в котором любые две вершины соединены ровно одним путем. Другими словами, любое связное граф без простых циклов является деревом.
Дано дерево из n узлов, помеченных от 0 до n - 1, и массив из n - 1 ребер, где edges[i] = [ai, bi] указывает на наличие неориентированного ребра между узлами ai и bi в дереве. Вы можете выбрать любой узел дерева в качестве корня. Когда вы выбираете узел x в качестве корня, дерево имеет высоту h. Среди всех возможных корневых деревьев те, которые имеют минимальную высоту (то есть min(h)), называются деревьями с минимальной высотой (MHT).
Верните список всех меток корней MHT. Вы можете вернуть ответ в любом порядке.
Высота корневого дерева — это количество ребер на самом длинном нисходящем пути между корнем и листом.

Пример:

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

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

1⃣Создание списка смежности
Создайте список смежности, представляющий граф.

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

3⃣Повторение процесса
Повторяйте процесс до тех пор, пока не останется два или менее узлов. Эти узлы будут корнями деревьев с минимальной высотой (MHT).

😎 Решение:

var findMinHeightTrees = function(n, edges) {
    if (n === 1) return [0];
    
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        adj[u].push(v);
        adj[v].push(u);
    }
    
    let leaves = [];
    for (let i = 0; i < n; i++) {
        if (adj[i].length === 1) leaves.push(i);
    }
    
    let remainingNodes = n;
    while (remainingNodes > 2) {
        remainingNodes -= leaves.length;
        const newLeaves = [];
        for (const leaf of leaves) {
            const neighbor = adj[leaf][0];
            adj[neighbor] = adj[neighbor].filter(node => node !== leaf);
            if (adj[neighbor].length === 1) newLeaves.push(neighbor);
        }
        leaves = newLeaves;
    }
    
    return leaves;
};

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