JavaScript | LeetCode

Вяжете или шьёте? Зарабатывайте на мастер-классах

"Ведёте творческий блог? С VK Донатом можно зарабатывать на своём деле прямо ВКонтакте — без рекламодателей и с поддержкой тех, кому близко ваше творчество. Показывайте скетчи, открывайте ранний доступ к новым работам или общайтесь с донами в отдельном чате.

💰 Разные способы получать доход: донаты, сборы на цели, уровни подписки
✨ Доход зависит только от вас: создавайте то, что нравится вам и вашей аудитории и устанавливайте свою цену
📊 Всё на одной площадке: привлекайте аудиторию и получайте деньги без подключения сторонних сервисов

На платформе уже есть авторы, которых поддерживают тысячи донов. Подключите VK Донат в профиле или сообществе и начните зарабатывать."

Узнать больше

#реклама 16+
vk.ru
О рекламодателе

Тюльпаны оптом к 14 февраля и 8 марта 2027

В тепличном комплексе «ФЕРМА» — более 60 сортов тюльпанов класса «Экстра»: от классических до пионовидных. Крупная луковица, гарантированная высота стебля, доставка или самовывоз на следующий день после срезки.

Запросите каталог и прайс на сезон 2027:
https://ferma.ooo/tulp/

Узнать больше

#реклама
ferma.ooo
О рекламодателе

Смета мероприятия: раньше — дни, сейчас — минута

Запросить расчет, дождаться ответа, согласовать изменения — теперь для этого не нужна долгая переписка с менеджером.

С онлайн-калькулятором SMARTMICE вы сможете сделать все самостоятельно:
✅ Получить предварительную смету с разбивкой расходов за 1 минуту.
✅ Менять параметры события и сразу видеть новую стоимость.
✅ Пересчитывать бюджет без ограничений.
✅ Выгружать смету в Excel для удобной работы с командой.

Калькулятор разработало цифровое MICE-агентство SMARTMICE. Мы берем на себя организацию мероприятий, а клиентам предоставляем удобные цифровые инструменты для работы со сметами и документами.

⚡ Узнайте бюджет мероприятия прямо сейчас — без ожидания ответа менеджера.

Попробовать

#реклама 16+
smartmice.tech
О рекламодателе

Задача: 913. Cat and Mouse
Сложность: hard

В игру на неориентированном графе играют два игрока, Мышь и Кот, которые чередуются по очереди. Граф задан следующим образом: graph[a] - это список всех вершин b, таких, что ab является ребром графа. Мышь начинает в вершине 1 и идет первой, Кот начинает в вершине 2 и идет второй, а в вершине 0 находится дыра. Во время хода каждого игрока он должен пройти по одному ребру графа, которое встречает его местоположение.Например, если Мышь находится в узле 1, она должна добраться до любого узла графа[1]. Кроме того, Кошке запрещено добираться до Дыры (узел 0). Затем игра может закончиться тремя способами: если Кошка занимает тот же узел, что и Мышь, Кошка побеждает. Если Мышь достигает Дыры, Мышь побеждает. Если позиция повторяется (т.е, игроки находятся в той же позиции, что и в предыдущий ход, и сейчас очередь того же игрока двигаться), то игра считается ничейной. Учитывая граф и предполагая, что оба игрока играют оптимально, верните 1, если в игре победила мышь, 2, если в игре победила кошка, или 0, если в игре ничья.

Пример:

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0

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

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

2⃣Проверить три условия окончания игры:
Мышь достигает дырки (победа мыши).
Кот достигает мыши (победа кота).
Позиция повторяется (ничья).

3⃣Использовать BFS (поиск в ширину) для определения результатов игры, начиная с конечных состояний и работая назад.

😎 Решение:

var catMouseGame = function(graph) {
    const n = graph.length;
    const DRAW = 0, MOUSE = 1, CAT = 2;
    const dp = Array.from({ length: n }, () => Array.from({ length: n }, () => [DRAW, DRAW]));
    const queue = [];
    
    for (let i = 1; i < n; i++) {
        dp[0][i][0] = MOUSE;
        dp[0][i][1] = MOUSE;
        dp[i][i][0] = CAT;
        dp[i][i][1] = CAT;
        queue.push([0, i, 0, MOUSE]);
        queue.push([0, i, 1, MOUSE]);
        queue.push([i, i, 0, CAT]);
        queue.push([i, i, 1, CAT]);
    }
    
    function* parents(mouse, cat, turn) {
        if (turn === 1) {
            for (const m of graph[mouse]) {
                yield [m, cat, 0];
            }
        } else {
            for (const c of graph[cat]) {
                if (c > 0) yield [mouse, c, 1];
            }
        }
    }
    
    while (queue.length) {
        const [mouse, cat, turn, winner] = queue.shift();
        for (const [m, c, t] of parents(mouse, cat, turn)) {
            if (dp[m][c][t] === DRAW) {
                if ((t === 0 && winner === MOUSE) || (t === 1 && winner === CAT)) {
                    dp[m][c][t] = winner;
                    queue.push([m, c, t, winner]);
                } else {
                    let degrees = 0;
                    for (const _ of parents(m, c, t)) degrees++;
                    if (degrees === 0) {
                        dp[m][c][t] = winner;
                        queue.push([m, c, t, winner]);
                    }
                }
            }
        }
    }
    
    return dp[1][2][0];
};

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

Задача: 1161. Maximum Level Sum of a Binary Tree
Сложность: medium

Дано корневое дерево, уровень корня которого равен 1, уровень его детей равен 2 и так далее.

Верните наименьший уровень x, такой что сумма всех значений узлов на уровне x максимальна.

Пример:

Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

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

1⃣Создайте целочисленную переменную maxSum для отслеживания максимальной суммы значений узлов на любом уровне, начав с большого отрицательного значения. Создайте переменную ans для хранения ответа на задачу. Создайте переменную level для хранения текущего уровня, через который мы проходим, и инициализируйте её значением 0. Инициализируйте очередь q типа TreeNode и добавьте в неё корень.

2⃣Выполните обход в ширину (BFS) до тех пор, пока очередь не станет пустой: увеличьте level на 1 и инициализируйте sumAtCurrentLevel = 0 для вычисления суммы всех значений узлов на этом уровне. Проходите через все узлы на уровне, используя только q.size() количество узлов. Внутри этого внутреннего цикла извлекайте все узлы на текущем уровне один за другим, добавляя их значения к sumAtCurrentLevel и добавляя левых и правых детей (если они существуют) в очередь. Поймите, что после прохождения всех узлов на уровне в очереди остаются только узлы уровня +1.

3⃣После прохождения всех узлов на уровне проверьте, больше ли sumAtCurrentLevel, чем maxSum. Если maxSum < sumAtCurrentLevel, обновите переменную ответа на ans = level и установите maxSum = sumAtCurrentLevel. Верните ans.

😎 Решение:

var maxLevelSum = function(root) {
    let maxSum = -Infinity;
    let ans = 0, level = 0;
    let q = [root];
    
    while (q.length > 0) {
        level++;
        let sumAtCurrentLevel = 0;
        for (let sz = q.length; sz > 0; --sz) {
            let node = q.shift();
            sumAtCurrentLevel += node.val;
            if (node.left) {
                q.push(node.left);
            }
            if (node.right) {
                q.push(node.right);
            }
        }
        
        if (maxSum < sumAtCurrentLevel) {
            maxSum = sumAtCurrentLevel;
            ans = level;
        }
    }
    
    return ans;
};

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

Задача: 754. Reach a Number
Сложность: medium

Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения.

Пример:

Input: target = 2
Output: 3

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

1⃣Инициализируйте переменную для текущей позиции (position) и счетчик шагов (steps).

2⃣Используйте цикл, чтобы добавлять к position текущее количество шагов и увеличивать steps.

3⃣Если position достигает или превышает target и разница между position и target четная, остановите цикл и верните steps.

😎 Решение:

function reachTarget(target) {
    target = Math.abs(target);
    let position = 0;
    let steps = 0;
    while (position < target || (position - target) % 2 !== 0) {
        steps += 1;
        position += steps;
    }
    return steps;
}

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