JavaScript | LeetCode

Задача: 328. Odd Even Linked List
Сложность: medium

Дан заголовок односвязного списка. Сгруппируйте все узлы с нечетными индексами вместе, а затем узлы с четными индексами, и верните упорядоченный список.
Первый узел считается нечетным, второй узел — четным и так далее.
Учтите, что относительный порядок внутри обеих групп (четной и нечетной) должен оставаться таким же, как в исходном списке.
Вы должны решить задачу с дополнительной сложностью по памяти O(1) и временной сложностью O(n).

Пример:

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

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

1⃣Инициализация указателей:
Создайте указатели odd и even для работы с нечетными и четными узлами, соответственно. Инициализируйте odd началом списка head, а even — следующим узлом head.next. Также создайте указатель evenHead для сохранения начала четного списка.

2⃣Разделение списка:
Используйте цикл для прохождения списка, перенаправляя нечетные узлы в oddList, а четные узлы в evenList. Обновляйте указатели odd и even в процессе итерации.

3⃣Соединение списков:

После окончания цикла соедините конец нечетного списка с началом четного списка, используя указатель evenHead.

😎 Решение:

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

var oddEvenList = function(head) {
    if (!head) return null;
    let odd = head, even = head.next, evenHead = even;
    
    while (even && even.next) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }
    odd.next = evenHead;
    return head;
};

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

Задача: 412. Fizz Buzz
Сложность: easy

Учитывая целое число n, верните строковый массив answer (с индексом 1), где: answer[i] == "FizzBuzz", если i делится на 3 и 5. answer[i] == "Fizz", если i делится на 3. answer[i] == "Buzz", если i делится на 5. answer[i] == i (как строка), если ни одно из перечисленных условий не верно.

Пример:

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

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

1⃣Создайте пустой список для хранения результата.

2⃣Пройдите по всем числам от 1 до n и для каждого числа выполните проверку: Если число делится на 3 и на 5, добавьте "FizzBuzz". Если число делится на 3, добавьте "Fizz". Если число делится на 5, добавьте "Buzz". Если ни одно из условий не выполнено, добавьте само число как строку.

3⃣Верните полученный список.

😎 Решение:

function fizzBuzz(n) {
    const answer = [];
    for (let i = 1; i <= n; i++) {
        if (i % 3 === 0 && i % 5 === 0) {
            answer.push("FizzBuzz");
        } else if (i % 3 === 0) {
            answer.push("Fizz");
        } else if (i % 5 === 0) {
            answer.push("Buzz");
        } else {
            answer.push(i.toString());
        }
    }
    return answer;
}

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

Задача: 104. Maximum Depth of Binary Tree
Сложность: easy

Дан корень бинарного дерева, верните его максимальную глубину.

Максимальная глубина бинарного дерева — это количество узлов вдоль самого длинного пути от корневого узла до самого удалённого листового узла.

Пример:

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

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

1️⃣Можно обойти дерево, используя стратегию поиска в глубину (DFS) или поиска в ширину (BFS).

2️⃣Для данной задачи подойдет несколько способов.

3️⃣Здесь мы демонстрируем решение, реализованное с использованием стратегии DFS и рекурсии.

😎 Решение:

var maxDepth = function (root) {
    if (root === null) {
        return 0;
    }
    const left_height = maxDepth(root.left);
    const right_height = maxDepth(root.right);
    return 1 + Math.max(left_height, right_height);
};

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

Задача: 623. Add One Row to Tree
Сложность: medium

Учитывая корень бинарного дерева и два целых числа val и depth, добавьте ряд узлов со значением val на заданную глубину depth. Обратите внимание, что корневой узел находится на глубине 1. Правило добавления таково: учитывая целое число depth, для каждого ненулевого узла дерева cur на глубине depth - 1 создайте два узла дерева со значением val в качестве левого поддерева корня cur и правого поддерева корня.
Оригинальное левое поддерево cur должно быть левым поддеревом нового корня левого поддерева. Оригинальное правое поддерево cur должно быть правым поддеревом нового корня правого поддерева. Если глубина == 1, то есть глубина - 1 вообще не существует, создайте узел дерева со значением val как новый корень всего оригинального дерева, а оригинальное дерево - левое поддерево нового корня.

Пример:

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

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

1⃣Если depth равна 1, создайте новый корень со значением val и сделайте текущий корень левым поддеревом нового корня.

2⃣Используйте обход в ширину (BFS) для поиска всех узлов на глубине depth - 1.

3⃣Для каждого узла на глубине depth - 1, вставьте новые узлы со значением val в качестве левого и правого поддеревьев, сохраняя исходные поддеревья.

😎 Решение:

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

function addOneRow(root, val, depth) {
    if (depth === 1) {
        return new TreeNode(val, root, null);
    }
    
    const queue = [root];
    let currentDepth = 1;
    
    while (queue.length > 0) {
        if (currentDepth === depth - 1) {
            for (const node of queue) {
                node.left = new TreeNode(val, node.left, null);
                node.right = new TreeNode(val, null, node.right);
            }
            break;
        }
        currentDepth++;
        const nextQueue = [];
        for (const node of queue) {
            if (node.left !== null) {
                nextQueue.push(node.left);
            }
            if (node.right !== null) {
                nextQueue.push(node.right);
            }
        }
        queue.length = 0;
        queue.push(...nextQueue);
    }
    
    return root;
}

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

Задача: 553. Optimal Division
Сложность: medium

Дано целочисленный массив nums. Соседние целые числа в nums будут выполнять деление с плавающей запятой.
Например, для nums = [2,3,4] мы будем вычислять выражение "2/3/4".
Однако, вы можете добавить любое количество скобок в любое место, чтобы изменить приоритет операций. Вы хотите добавить эти скобки так, чтобы значение выражения после вычисления было максимальным.
Верните соответствующее выражение, которое имеет максимальное значение в строковом формате.

Пример:

Input: nums = [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation: 1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant since they do not influence the operation priority.
So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

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

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

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

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

😎 Решение:

class Solution {
    addStrings(num1, num2) {
        let ans = [];
        let carry = 0;
        const n1 = num1.length;
        const n2 = num2.length;

        for (let i = 0; i < Math.max(n1, n2) || carry; i++) {
            const digit1 = i < n1 ? num1[i] : 0;
            const digit2 = i < n2 ? num2[i] : 0;
            const sum = digit1 + digit2 + carry;
            carry = Math.floor(sum / 10);
            ans.push(sum % 10);
        }
        return ans;
    }

    multiplyOneDigit(firstNumber, secondNumberDigit, numZeros) {
        const currentResult = new Array(numZeros).fill(0);
        let carry = 0;

        for (const digit of firstNumber) {
            const multiplication = (secondNumberDigit * digit) + carry;
            carry = Math.floor(multiplication / 10);
            currentResult.push(multiplication % 10);
        }
        if (carry !== 0) {
            currentResult.push(carry);
        }
        return currentResult;
    }

    multiply(firstNumber, secondNumber) {
        if (firstNumber === "0" || secondNumber === "0") {
            return "0";
        }

        firstNumber = firstNumber.split('').reverse().join('');
        secondNumber = secondNumber.split('').reverse().join('');

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

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

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

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

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

Задача: 56. Merge Intervals
Сложность: medium

Дан массив интервалов, где intervals[i] = [starti, endi]. Объедините все перекрывающиеся интервалы и верните массив неперекрывающихся интервалов, которые покрывают все интервалы во входных данных.

Пример:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

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

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

2️⃣Определение компонент связности:
Для определения, в какой компоненте связности находится каждый узел, мы выполняем обходы графа от произвольных непосещенных узлов до тех пор, пока все узлы не будут посещены. Для эффективности мы храним посещенные узлы в множестве (Set), что позволяет проводить проверки на принадлежность и вставку за константное время.

3️⃣Объединение интервалов внутри компонент:
Наконец, мы рассматриваем каждую связную компоненту, объединяя все её интервалы, создавая новый интервал с началом, равным минимальному началу среди всех интервалов в компоненте, и концом, равным максимальному концу.

Решение:

var overlap = function (a, b) {
    return a[0] <= b[1] && b[0] <= a[1];
};
var buildGraph = function (intervals) {
    var graph = new Map();
    for (var i = 0; i < intervals.length; i++) {
        for (var j = i + 1; j < intervals.length; j++) {
            if (overlap(intervals[i], intervals[j])) {
                if (graph.has(intervals[i])) {
                    graph.get(intervals[i]).push(intervals[j]);
                } else {
                    graph.set(intervals[i], [intervals[j]]);
                }
                if (graph.has(intervals[j])) {
                    graph.get(intervals[j]).push(intervals[i]);
                } else {
                    graph.set(intervals[j], [intervals[i]]);
                }
            }
        }
    }
    return graph;
};
var mergeNodes = function (nodes) {
    var minStart = Infinity;
    var maxEnd = -Infinity;
    for (var node of nodes) {
        minStart = Math.min(minStart, node[0]);
        maxEnd = Math.max(maxEnd, node[1]);
    }
    return [minStart, maxEnd];
};
var markComponentDFS = function (
    start,
    graph,
    nodesInComp,
    compNumber,
    visited,
) {
    var stack = [start];
    while (stack.length) {
        var node = stack.pop();
        if (!visited.has(node)) {
            visited.add(node);
            if (nodesInComp[compNumber]) {
                nodesInComp[compNumber].push(node);
            } else {
                nodesInComp[compNumber] = [node];
            }
            if (graph.has(node)) {
                for (var child of graph.get(node)) {
                    stack.push(child);
                }
            }
        }
    }
};
var merge = function (intervals) {
    var graph = buildGraph(intervals);
    var nodesInComp = {};
    var visited = new Set();
    var compNumber = 0;
    for (var interval of intervals) {
        if (!visited.has(interval)) {
            markComponentDFS(interval, graph, nodesInComp, compNumber, visited);
            compNumber++;
        }
    }
    var merged = [];
    for (var comp = 0; comp < compNumber; comp++) {
        merged.push(mergeNodes(nodesInComp[comp]));
    }
    return merged;
};

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

Задача: 1286. Iterator for Combination
Сложность: medium

Создайте класс CombinationIterator:

CombinationIterator(string characters, int combinationLength) Инициализирует объект строкой characters, содержащей отсортированные различные строчные буквы английского алфавита, и числом combinationLength в качестве аргументов.
next() Возвращает следующую комбинацию длины combinationLength в лексикографическом порядке.
hasNext() Возвращает true, если и только если существует следующая комбинация.

Пример:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

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

1⃣Сгенерируйте все возможные бинарные битовые маски длины n: от 0 до 2^n - 1.

2⃣Используйте битовые маски с k установленными битами для генерации комбинаций из k элементов. Если n - 1 - j-й бит установлен в битовой маске, это указывает на присутствие символа characters[j] в комбинации и наоборот.

3⃣Теперь у вас есть все заранее вычисленные комбинации. Извлекайте их одну за другой по каждому запросу.

😎 Решение:

class CombinationIterator {
    constructor(characters, combinationLength) {
        this.combinations = [];
        let n = characters.length;
        let k = combinationLength;
        for (let bitmask = 0; bitmask < (1 << n); bitmask++) {
            if (bitmask.toString(2).split('1').length - 1 === k) {
                let curr = [];
                for (let j = 0; j < n; j++) {
                    if (bitmask & (1 << (n - j - 1))) {
                        curr.push(characters[j]);
                    }
                }
                this.combinations.push(curr.join(''));
            }
        }
    }

    next() {
        return this.combinations.pop();
    }

    hasNext() {
        return this.combinations.length > 0;
    }
}

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

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

Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.

Верните пересечение этих двух списков интервалов.

Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.

Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].

Пример:

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

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

1⃣Инициализация указателей:
Создать словарь для хранения узлов по их координатам (col, row).
Создать очередь для обхода в ширину (BFS), содержащую начальную пару (root, (0, 0)).

2⃣Поиск пересечений:
Выполнить BFS обход дерева. Для каждого узла сохранить его значение в словаре по ключу (col, row).
Добавить левый потомок в очередь с координатами (row + 1, col - 1).
Добавить правый потомок в очередь с координатами (row + 1, col + 1).

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

😎 Решение:

var verticalTraversal = function(root) {
    const colTable = new Map();
    const queue = [[root, 0, 0]];

    while (queue.length > 0) {
        const [node, row, col] = queue.shift();
        if (node) {
            if (!colTable.has(col)) {
                colTable.set(col, []);
            }
            colTable.get(col).push([row, node.val]);
            queue.push([node.left, row + 1, col - 1]);
            queue.push([node.right, row + 1, col + 1]);
        }
    }

    const sortedCols = Array.from(colTable.keys()).sort((a, b) => a - b);
    const result = [];

    for (const col of sortedCols) {
        colTable.get(col).sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
        result.push(colTable.get(col).map(pair => pair[1]));
    }

    return result;
};

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

Задача: 402. Remove K Digits
Сложность: medium

Если задана строка num, представляющая неотрицательное целое число num, и целое число k, верните наименьшее возможное целое число после удаления k цифр из num.

Пример:

Input: num = "1432219", k = 3
Output: "1219"

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

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

2⃣Обработка каждой цифры
Перебирайте каждую цифру в строке num. Если текущая цифра меньше верхней цифры в стеке и у вас есть еще возможность удалить цифры (k > 0), удалите верхнюю цифру из стека. Добавьте текущую цифру в стек. Удаление оставшихся цифр: Если после прохождения всей строки k еще больше нуля, удалите оставшиеся цифры из конца стека.

3⃣Формирование результата
Постройте итоговое число из цифр в стеке и удалите ведущие нули.

😎 Решение:

class Solution {
    removeKdigits(num, k) {
        const stack = [];
        for (const digit of num) {
            while (k > 0 && stack.length > 0 && stack[stack.length - 1] > digit) {
                stack.pop();
                k--;
            }
            stack.push(digit);
        }
        stack.splice(stack.length - k, k);
        let result = stack.join('');
        while (result.length > 1 && result[0] === '0') {
            result = result.slice(1);
        }
        return result === '' ? '0' : result;
    }
}

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

Задача: 1014. Best Sightseeing Pair
Сложность: medium

Вам дан целочисленный массив values, в котором values[i] представляет собой значение i-й достопримечательности. Две достопримечательности i и j имеют расстояние j - i между собой. Оценка пары (i < j) достопримечательностей равна values[i] + values[j] + i - j: сумма значений достопримечательностей минус расстояние между ними. Возвращается максимальная оценка пары достопримечательностей.

Пример:

Input: values = [8,1,5,2,6]
Output: 11

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

1⃣Инициализация переменных:
Инициализируйте переменную max_score для хранения максимальной оценки пары.
Инициализируйте переменную max_i_plus_value для хранения максимального значения выражения values[i] + i при проходе по массиву.

2⃣Проход по массиву:
Пройдитесь по массиву начиная с первого элемента и для каждого элемента values[j] вычислите текущую оценку пары как values[j] - j + max_i_plus_value.
Обновите значение max_score, если текущая оценка больше.
Обновите значение max_i_plus_value, если текущий элемент values[j] + j больше предыдущего max_i_plus_value.

3⃣Возврат результата:
Верните значение max_score как максимальную оценку пары достопримечательностей.

😎 Решение:

class Solution {
    maxScoreSightseeingPair(values) {
        let maxScore = 0;
        let maxIPlusValue = values[0];
        
        for (let j = 1; j < values.length; j++) {
            maxScore = Math.max(maxScore, maxIPlusValue + values[j] - j);
            maxIPlusValue = Math.max(maxIPlusValue, values[j] + j);
        }
        
        return maxScore;
    }
}

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

Задача: 89. Gray Code
Сложность: medium

Последовательность Грея с n-битами — это последовательность из 2^n целых чисел, где:
1. Каждое число находится в включающем диапазоне от 0 до 2^n - 1,
2. Первое число равно 0,
3. Каждое число встречается в последовательности не более одного раза,
4. Двоичное представление каждой пары соседних чисел отличается ровно на один бит,
5. Двоичное представление первого и последнего чисел отличается ровно на один бит.
Для заданного числа n возвращается любая допустимая последовательность Грея с n-битами.

Пример:

Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit

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

1️⃣Инициализируйте список результатов для хранения последовательности решений. Добавьте 0 в список перед вызовом вспомогательного метода, так как все последовательности Грея начинаются с 0.

2️⃣Инициализируйте множество visited. Это позволяет отслеживать числа, присутствующие в текущей последовательности, чтобы избежать повторения.
Начните с числа 0.
В функции grayCodeHelper() используйте цикл for, чтобы найти каждое возможное число (next), которое может быть сгенерировано путем изменения одного бита последнего числа в списке результатов (current). Делайте это, переключая i-ый бит на каждой итерации. Поскольку максимально возможное количество битов в любом числе последовательности равно n, необходимо переключить n битов.

3️⃣Если next не присутствует в множестве использованных чисел (isPresent), добавьте его в список результатов и множество isPresent.
Продолжайте поиск с next.
Если grayCodeHelper(next) возвращает true, это означает, что допустимая последовательность найдена. Дальнейший поиск не требуется (ранняя остановка). Это раннее завершение улучшает время выполнения.
Если с next не найдена допустимая последовательность, удаляем его из списка результатов и множества isPresent и продолжаем поиск.
При достижении базового условия, когда длина текущей последовательности равна 2^n, возвращаем true.
Выход из цикла for означает, что с current в качестве последнего числа не найдена допустимая последовательность кода Грея. Поэтому возвращаем false.

😎 Решение:

var grayCode = function (n) {
    const res = [0];
    const seen = new Set(res);
    const helper = (n, res, seen) => {
        if (res.length === Math.pow(2, n)) {
            return true;
        }
        const curr = res[res.length - 1];
        for (let i = 0; i < n; i++) {
            const next = curr ^ (1 << i);
            if (!seen.has(next)) {
                seen.add(next);
                res.push(next);
                if (helper(n, res, seen)) return true;
                seen.delete(next);
                res.pop();
            }
        }
        return false;
    };
    helper(n, res, seen);
    return res;
};

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

Задача: 230. Kth Smallest Element in a BST
Сложность: medium

Дан корень бинарного дерева поиска и целое число k. Верните k-ое по величине значение (нумерация с 1) среди всех значений узлов в дереве.

Пример:

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

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

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

2⃣Извлечение узлов и проверка: Когда достигнете самого левого узла, извлеките узел из стека и уменьшите значение k на 1. Если k становится равным нулю, верните значение текущего узла, так как это и есть k-ое по величине значение.

3⃣Переход к правому поддереву: Если k не равен нулю, переместитесь к правому поддереву текущего узла и продолжайте обход, повторяя шаги 1 и 2, пока не найдете k-ое по величине значение.

😎 Решение:

class Solution {
    kthSmallest(root, k) {
        let stack = []
        
        while (true) {
            while (root !== null) {
                stack.push(root)
                root = root.left
            }
            root = stack.pop()
            if (--k === 0) return root.val
            root = root.right
        }
    }
}

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

Задача: 353. Design Snake Game
Сложность: medium

Разработайте игру "Змейка", которая играется на устройстве с экраном размером height x width. Поиграйте в игру онлайн, если вы не знакомы с ней.
Змейка изначально находится в верхнем левом углу (0, 0) с длиной в 1 единицу.
Вам дан массив food, где food[i] = (ri, ci) представляет собой строку и столбец позиции пищи, которую змейка может съесть. Когда змейка съедает кусочек пищи, ее длина и очки игры увеличиваются на 1.
Каждый кусочек пищи появляется по очереди на экране, то есть второй кусочек пищи не появится, пока змейка не съест первый кусочек пищи.
Когда кусочек пищи появляется на экране, гарантируется, что он не появится на блоке, занятом змейкой.
Игра заканчивается, если змейка выходит за пределы экрана (врезается в стену) или если ее голова занимает пространство, которое занимает ее тело после движения (например, змейка длиной 4 не может врезаться в себя).

Реализуйте класс SnakeGame:
SnakeGame(int width, int height, int[][] food) Инициализирует объект с экраном размером height x width и позициями пищи.
int move(String direction) Возвращает счет игры после применения одного движения змейки в направлении. Если игра окончена, верните -1.

Пример:

Input
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
Output
[null, 0, 0, 1, 1, 2, -1]

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

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

2⃣Реализуйте функцию для вычисления нового положения головы змейки на основе направления движения.

3⃣Обновите положение змейки и проверьте условия завершения игры. Верните текущий счет или -1, если игра закончена.

😎 Решение:

class SnakeGame {
    constructor(width, height, food) {
        this.width = width;
        this.height = height;
        this.food = food;
        this.score = 0;
        this.snake = [[0, 0]];
        this.snakeSet = new Set(["0,0"]);
        this.foodIndex = 0;
    }

    move(direction) {
        let head = this.snake[0].slice();
        switch (direction) {
            case "U":
                head[0]--;
                break;
            case "D":
                head[0]++;
                break;
            case "L":
                head[1]--;
                break;
            case "R":
                head[1]++;
                break;
        }

        if (head[0] < 0 || head[0] >= this.height || head[1] < 0 || head[1] >= this.width) {
            return -1;
        }

        let newHeadStr = head.toString();
        if (this.snakeSet.has(newHeadStr) && newHeadStr !== this.snake[this.snake.length - 1].toString()) {
            return -1;
        }

        if (this.foodIndex < this.food.length && head[0] === this.food[this.foodIndex][0] && head[1] === this.food[this.foodIndex][1]) {
            this.foodIndex++;
        } else {
            let tail = this.snake.pop();
            this.snakeSet.delete(tail.toString());
        }

        this.snake.unshift(head);
        this.snakeSet.add(newHeadStr);

        return this.snake.length - 1;
    }
}

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

Задача: №24. Swap Nodes in Pairs
Сложность: medium

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

Пример:

Input: head = [1,2,3,4]  
Output: [2,1,4,3]

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

1️⃣ Базовый случай: если head пуст или в списке только один узел — возвращаем head как есть.

2️⃣ Рекурсивно вызываем swapPairs от head.next.next, чтобы поменять местами последующие пары.

3️⃣ Меняем местами текущую пару:
- Пусть p = head.next
- p.next = head — связываем второй узел с первым
- head.next = t — первый узел указывает на результат рекурсивного вызова
- Возвращаем p — он становится новым «головой» текущей пары

😎 Решение:

var swapPairs = function (head) {
    if (!head || !head.next) {
        return head;
    }

    const t = swapPairs(head.next.next);
    const p = head.next;
    p.next = head;
    head.next = t;
    return p;
};

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

Задача: 970. Powerful Integers
Сложность: medium

Даны три целых числа x, y и bound. Верните список всех мощных чисел, которые имеют значение меньше или равное bound.

Целое число является мощным, если оно может быть представлено как x^i + y^j для некоторых целых чисел i >= 0 и j >= 0.

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

Пример:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation:
2 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32

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

1⃣Вычислите степени a и b как логарифмы bound по основаниям x и y соответственно. Создайте множество powerfulIntegers для хранения результатов.

2⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.

3⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.

😎 Решение:

var powerfulIntegers = function(x, y, bound) {
    const a = x === 1 ? bound : Math.floor(Math.log(bound) / Math.log(x));
    const b = y === 1 ? bound : Math.floor(Math.log(bound) / Math.log(y));
    const powerfulIntegers = new Set();

    for (let i = 0; i <= a; i++) {
        for (let j = 0; j <= b; j++) {
            const value = Math.pow(x, i) + Math.pow(y, j);
            if (value <= bound) {
                powerfulIntegers.add(value);
            }
            if (y === 1) break;
        }
        if (x === 1) break;
    }

    return Array.from(powerfulIntegers);
};

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

Задача: 510. Inorder Successor in BST II
Сложность: medium

Дан узел в двоичном дереве поиска, верните его последующего (in-order successor) в этом дереве. Если у узла нет последующего, верните null.

Последующий узла — это узел с наименьшим ключом, большим, чем node.val.

Вы будете иметь прямой доступ к узлу, но не к корню дерева. Каждый узел будет иметь ссылку на своего родителя. Ниже приведено определение для Node:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

Пример:

Input: tree = [5,3,6,2,4,null,null,1], node = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

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

1⃣Проверка правого поддерева
Если у узла есть правый потомок, перейдите к правому узлу, затем спускайтесь влево до самого нижнего узла. Этот узел будет следующим узлом в порядке in-order.

2⃣Поиск предка
Если у узла нет правого потомка, поднимайтесь по дереву до тех пор, пока узел не станет левым потомком своего родителя. Родитель этого узла будет следующим узлом в порядке in-order.

3⃣Возвращение результата
Верните найденный узел или null, если следующий узел не найден.

😎 Решение:

class Node {
    constructor(val, left = null, right = null, parent = null) {
        this.val = val;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }
}

var inorderSuccessor = function(x) {
    if (x.right) {
        x = x.right;
        while (x.left) {
            x = x.left;
        }
        return x;
    }

    while (x.parent && x === x.parent.right) {
        x = x.parent;
    }
    return x.parent;
};

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

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

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

Пример:

Input: candidates = [2,3,6,7], target = 7  
Output: [[2,2,3],[7]]

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

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

2⃣На каждом шаге:
- добавляем candidates[i] в текущую комбинацию
- если сумма меньше target, продолжаем поиск
- если сумма равна target, сохраняем копию комбинации
- затем откатываем шаг (pop и вычитаем)

3⃣Повторное использование чисел реализуется тем, что при рекурсивном вызове мы снова передаём i, а не i + 1.

😎Решение:

var combinationSum = function(candidates, target) {
    let sols = [];

    let sum_rec = (curr_trial, curr_sum, start_idx) => {
        for (let i = start_idx; i < candidates.length; i++) {
            const c = candidates[i];
            curr_sum += c;
            curr_trial.push(c);

            if (curr_sum < target) {
                sum_rec(curr_trial, curr_sum, i);
            } else if (curr_sum === target) {
                sols.push([...curr_trial]);
            }

            curr_sum -= c;
            curr_trial.pop();
        }
    };

    sum_rec([], 0, 0);
    return sols;
};

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

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

Алиса и Боб продолжают свои игры с кучами камней. Есть несколько куч, расположенных в ряд, и в каждой куче положительное количество камней piles[i]. Цель игры - закончить с наибольшим количеством камней.
Алиса и Боб ходят по очереди, начиная с Алисы. Изначально M = 1.
В свой ход каждый игрок может взять все камни из первых X оставшихся куч, где 1 <= X <= 2M. Затем, мы устанавливаем M = max(M, X).
Игра продолжается до тех пор, пока все камни не будут взяты.
Предполагая, что Алиса и Боб играют оптимально, верните максимальное количество камней, которые может получить Алиса.

Пример:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. 
Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. 
In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

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

1⃣Создать рекурсивную функцию f, которая принимает три параметра: p (игрок), i (индекс текущей кучи),
и m (максимальное количество куч, которые можно взять за ход).
Если i равен длине массива кучи, вернуть 0 (базовый случай рекурсии). Если значение уже вычислено ранее (dp[p][i][m] != -1), вернуть его.

2⃣Инициализировать переменную s как количество камней, взятых текущим игроком за ход, и переменную res для хранения результата текущего состояния.
Если ход Боба, инициализировать res большим числом, так как Боб хочет минимизировать результат.
Если ход Алисы, инициализировать res маленьким числом, так как Алиса хочет максимизировать результат.

3⃣Итеративно обновлять значение res в зависимости от того, чей ход, и обновлять значения в dp[p][i][m]. В конце вернуть res.

😎 Решение:

var stoneGameII = function(piles) {
    const dp = Array.from({ length: 2 }, () => 
        Array.from({ length: piles.length + 1 }, () => 
            Array(piles.length + 1).fill(-1)
        )
    );

    const f = (p, i, m) => {
        if (i === piles.length) return 0;
        if (dp[p][i][m] !== -1) return dp[p][i][m];
        let res = p === 1 ? 1000000 : -1, s = 0;
        for (let x = 1; x <= Math.min(2 * m, piles.length - i); x++) {
            s += piles[i + x - 1];
            if (p === 0) {
                res = Math.max(res, s + f(1, i + x, Math.max(m, x)));
            } else {
                res = Math.min(res, f(0, i + x, Math.max(m, x)));
            }
        }
        dp[p][i][m] = res;
        return res;
    };

    return f(0, 0, 1);
};

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

Задача: 920. Number of Music Playlists
Сложность: hard

В вашем плеере есть n разных песен. Во время путешествия вы хотите прослушать goal песен (не обязательно разных). Чтобы избежать скуки, вы создадите плейлист таким образом, чтобы: каждая песня играла хотя бы один раз. Песня может быть проиграна снова только в том случае, если было проиграно k других песен. Учитывая n, цель и k, верните количество возможных плейлистов, которые вы можете создать. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: n = 3, goal = 3, k = 1
Output: 6

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

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

2⃣Инициализировать dp[0][0] = 1, что означает, что существует один способ создать плейлист длины 0 с 0 песнями.
Заполнить массив dp, используя два случая:
Добавление новой песни, которая не была проиграна раньше: dp[i][j] += dp[i-1][j-1] * (n - j + 1)
Повторное проигрывание песни, если было проиграно k других песен: dp[i][j] += dp[i-1][j] * max(j - k, 0)

3⃣Ответ находится в dp[goal][n].

😎 Решение:

var numMusicPlaylists = function(n, goal, k) {
    const MOD = 10**9 + 7;
    let dp = Array.from({ length: goal + 1 }, () => Array(n + 1).fill(0));
    dp[0][0] = 1;

    for (let i = 1; i <= goal; i++) {
        for (let j = 1; j <= n; j++) {
            dp[i][j] = dp[i-1][j-1] * (n - j + 1) % MOD;
            if (j > k) {
                dp[i][j] = (dp[i][j] + dp[i-1][j] * (j - k) % MOD) % MOD;
            }
        }
    }

    return dp[goal][n];
};

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

Задача: 994. Rotting Oranges
Сложность: medium

Дан m x n сетка, где каждая ячейка может иметь одно из трех значений:

0, представляющее пустую ячейку,
1, представляющее свежий апельсин,
2, представляющее гнилой апельсин.
Каждую минуту любой свежий апельсин, который находится в 4-х направленно смежной ячейке с гнилым апельсином, становится гнилым.

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

Пример:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

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

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

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

3⃣Проверка оставшихся свежих апельсинов:
Если после завершения BFS все еще остаются свежие апельсины, верните -1.

😎 Решение:

var orangesRotting = function(grid) {
    let queue = [];
    let freshCount = 0;
    let minutes = 0;
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === 2) {
                queue.push([i, j]);
            } else if (grid[i][j] === 1) {
                freshCount++;
            }
        }
    }
    
    if (freshCount === 0) return 0;
    
    while (queue.length > 0) {
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const [x, y] = queue.shift();
            for (const [dx, dy] of directions) {
                const nx = x + dx;
                const ny = y + dy;
                if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && grid[nx][ny] === 1) {
                    grid[nx][ny] = 2;
                    freshCount--;
                    queue.push([nx, ny]);
                }
            }
        }
        if (queue.length > 0) {
            minutes++;
        }
    }
    
    return freshCount === 0 ? minutes : -1;
};

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