Задача: 743. Network Delay Time
Сложность: medium

Дана сеть из узлов, помеченных от 1 до n. Также дано times - список времен прохождения сигнала в виде направленных ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время прохождения сигнала от источника до цели. Мы пошлем сигнал из заданного узла k. Верните минимальное время, которое потребуется всем узлам, чтобы получить сигнал. Если все узлы не могут получить сигнал, верните -1.

Пример:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

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

1⃣Представьте граф в виде списка смежности.

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

3⃣Найдите максимальное значение среди кратчайших путей к узлам. Если какой-либо узел недостижим, верните -1.

😎 Решение:

var networkDelayTime = function(times, n, k) {
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [u, v, w] of times) {
        graph[u].push([v, w]);
    }

    const minHeap = [[0, k]];
    const minTime = Array(n + 1).fill(Infinity);
    minTime[k] = 0;

    while (minHeap.length) {
        minHeap.sort((a, b) => a[0] - b[0]);
        const [time, node] = minHeap.shift();
        for (const [neighbor, t] of graph[node]) {
            const newTime = time + t;
            if (newTime < minTime[neighbor]) {
                minTime[neighbor] = newTime;
                minHeap.push([newTime, neighbor]);
            }
        }
    }

    const maxTime = Math.max(...minTime.slice(1));
    return maxTime === Infinity ? -1 : maxTime;
};

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

Задача: 1036. Escape a Large Maze
Сложность: hard

Имеется сетка размером 1 миллион на 1 миллион на плоскости XY, координаты каждого квадрата сетки - (x, y). Мы начинаем с исходного квадрата = [sx, sy] и хотим достичь цели = [tx, ty]. Существует также массив заблокированных квадратов, где каждый заблокированный[i] = [xi, yi] представляет собой заблокированный квадрат с координатами (xi, yi). Каждый ход мы можем пройти один квадрат на север, восток, юг или запад, если квадрат не находится в массиве заблокированных квадратов. Нам также не разрешается выходить за пределы сетки. Возвращается true тогда и только тогда, когда можно достичь целевого квадрата из исходного квадрата с помощью последовательности правильных ходов.

Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

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

1⃣Обработка входных данных:
Загрузите координаты исходного квадрата sx, sy, целевого квадрата tx, ty и список заблокированных квадратов blocked.

2⃣Проверка простого случая:
Если список blocked пуст, верните true, так как путь не будет заблокирован.
Проверка начальной или целевой клетки:
Если исходная или целевая клетка заблокированы, верните false.

3⃣Поиск пути с использованием BFS или DFS:
Используйте алгоритм поиска в ширину (BFS) или поиска в глубину (DFS) для поиска пути от sx, sy до tx, ty, избегая заблокированных клеток.
Если обнаружен путь, верните true, в противном случае верните false.

😎 Решение:

var isEscapePossible = function(blocked, source, target) {
    const blockedSet = new Set(blocked.map(b => `${b[0]},${b[1]}`));
    const src = `${source[0]},${source[1]}`;
    const tgt = `${target[0]},${target[1]}`;
    
    if (blockedSet.has(src) || blockedSet.has(tgt)) return false;
    
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    const maxArea = blocked.length * (blocked.length - 1) / 2;
    
    const bfs = (start, end) => {
        const queue = [start];
        const visited = new Set([start]);
        
        while (queue.length) {
            if (visited.size > maxArea) return true;
            const [x, y] = queue.shift().split(',').map(Number);
            for (const [dx, dy] of directions) {
                const nx = x + dx, ny = y + dy;
                const next = `${nx},${ny}`;
                if (nx >= 0 && nx < 1_000_000 && ny >= 0 && ny < 1_000_000 && !visited.has(next) && !blockedSet.has(next)) {
                    if (next === end) return true;
                    queue.push(next);
                    visited.add(next);
                }
            }
        }
        return false;
    };
    
    return bfs(src, tgt) && bfs(tgt, src);
};

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

Задача: 995. Minimum Number of K Consecutive Bit Flips
Сложность: hard

Дан бинарный массив nums и целое число k.

Операция переворота k-бит заключается в выборе подмассива длиной k из nums и одновременном изменении каждого 0 в подмассиве на 1 и каждого 1 в подмассиве на 0.

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

Подмассив - это непрерывная часть массива.

Пример:

Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip nums[0], then flip nums[2].

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

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

2⃣Перебор элементов массива:
Для каждого элемента определите, необходимо ли его переворачивать, учитывая текущее количество переворотов и значение в массиве.
Если нужно перевернуть, увеличьте счетчик переворотов и обновите массив flip.

3⃣Проверка возможности выполнения задачи:
Если количество переворотов больше длины массива, верните -1.

😎 Решение:

var minKBitFlips = function(nums, k) {
    let n = nums.length;
    let flip = 0;
    let flips = 0;
    let flipQueue = new Array(n).fill(0);
    
    for (let i = 0; i < n; i++) {
        if (i >= k) {
            flip ^= flipQueue[i - k];
        }
        if (nums[i] == flip) {
            if (i + k > n) return -1;
            flips++;
            flip ^= 1;
            flipQueue[i] = 1;
        }
    }
    return flips;
};

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

Задача: 583. Delete Operation for Two Strings
Сложность: medium

Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми.
На одном шаге можно удалить ровно один символ в любой строке.

Пример:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

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

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

2⃣ Заполнение массива:
Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки.

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

😎 Решение:

var minDistance = function(word1, word2) {
    let m = word1.length, n = word2.length;
    let dp = new Array(n + 1).fill(0);

    for (let i = 0; i <= m; i++) {
        let temp = new Array(n + 1).fill(0);
        for (let j = 0; j <= n; j++) {
            if (i === 0 || j === 0) {
                temp[j] = i + j;
            } else if (word1[i - 1] === word2[j - 1]) {
                temp[j] = dp[j - 1];
            } else {
                temp[j] = 1 + Math.min(dp[j], temp[j - 1]);
            }
        }
        dp = temp;
    }

    return dp[n];
};

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

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

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

Задача: 722. Remove Comments
Сложность: medium

Дана программа на C++, удалите из нее комментарии. Исходный текст программы представляет собой массив строк source, где source[i] - это i-я строка исходного кода. Это результат разбиения исходной строки исходного кода символом новой строки '\n'. В C++ существует два типа комментариев: строчные и блочные. Строка "//" обозначает строчный комментарий, который означает, что он и остальные символы справа от него в той же строке должны игнорироваться. Строка "/*" обозначает блочный комментарий, который означает, что все символы до следующего (не перекрывающегося) вхождения "*/" должны игнорироваться. (Здесь вхождения происходят в порядке чтения: строка за строкой слева направо.) Чтобы было понятно, строка "/*/" еще не завершает блочный комментарий, так как окончание будет перекрывать начало. Первый эффективный комментарий имеет приоритет над остальными.
Например, если строка "//" встречается в блочном комментарии, она игнорируется. Аналогично, если строка "/*" встречается в строчном или блочном комментарии, она также игнорируется. Если после удаления комментариев определенная строка кода оказывается пустой, вы не должны выводить эту строку: каждая строка в списке ответов будет непустой.

Пример:

Input: source = ["/*Test program */", "int main()", "{ ", "  // variable declaration ", "int a, b, c;", "/* This is a test", "   multiline  ", "   comment for ", "   testing */", "a = b + c;", "}"]
Output: ["int main()","{ ","  ","int a, b, c;","a = b + c;","}"]

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

1⃣Создайте строку buffer для хранения текущей строки кода без комментариев и флаг inBlock для отслеживания, находимся ли мы внутри блочного комментария.

2⃣Пройдите по каждой строке source и по каждому символу в этой строке, обрабатывая комментарии: Если встречен блочный комментарий /*, установите флаг inBlock и пропустите символы до */. Если встречен строчный комментарий //, прекратите обработку текущей строки. Если не находимся внутри комментария, добавьте символ в buffer.

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

😎 Решение:

var removeComments = function(source) {
    let inBlock = false;
    let buffer = [];
    let result = [];
    
    for (let line of source) {
        let i = 0;
        if (!inBlock) buffer = [];
        while (i < line.length) {
            if (!inBlock && i + 1 < line.length && line[i] === '/' && line[i + 1] === '*') {
                inBlock = true;
                i += 1;
            } else if (inBlock && i + 1 < line.length && line[i] === '*' && line[i + 1] === '/') {
                inBlock = false;
                i += 1;
            } else if (!inBlock && i + 1 < line.length && line[i] === '/' && line[i + 1] === '/') {
                break;
            } else if (!inBlock) {
                buffer.push(line[i]);
            }
            i += 1;
        }
        if (buffer.length && !inBlock) {
            result.push(buffer.join(''));
        }
    }
    return result;
};

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

Задача: 669. Trim a Binary Search Tree
Сложность: medium

Дано корневое дерево двоичного поиска и нижняя и верхняя границы как low и high. Обрежьте дерево так, чтобы все его элементы лежали в диапазоне [low, high]. Обрезка дерева не должна изменять относительную структуру элементов, которые останутся в дереве (то есть любой потомок узла должен оставаться потомком). Можно доказать, что существует единственный ответ.
Верните корень обрезанного дерева двоичного поиска. Обратите внимание, что корень может измениться в зависимости от заданных границ.

Пример:

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

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

1⃣Если node.val > high, то обрезанное двоичное дерево должно находиться слева от узла.

2⃣Если node.val < low, то обрезанное двоичное дерево должно находиться справа от узла.

3⃣В противном случае обрезаем обе стороны дерева.

😎 Решение:

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

var trimBST = function(root, low, high) {
    if (root === null) return null
    if (root.val > high) return trimBST(root.left, low, high)
    if (root.val < low) return trimBST(root.right, low, high)
    root.left = trimBST(root.left, low, high)
    root.right = trimBST(root.right, low, high)
    return root
}

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

Задача: 418. Sentence Screen Fitting
Сложность: medium

Если задан экран rows x cols и предложение, представленное в виде списка строк, верните количество раз, которое данное предложение может быть помещено на экран. Порядок слов в предложении должен оставаться неизменным, и слово не может быть разбито на две строки. Два последовательных слова в строке должны разделяться одним пробелом.

Пример:

Input: sentence = ["hello","world"], rows = 2, cols = 8
Output: 1

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

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

2⃣Инициализируйте переменную для отслеживания текущей позиции в строке предложения. Для каждой строки экрана добавляйте количество символов, равное числу столбцов.

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

😎 Решение:

function wordsTyping(sentence, rows, cols) {
    const sentenceStr = sentence.join(" ") + " ";
    const length = sentenceStr.length;
    let count = 0;
    
    for (let i = 0; i < rows; i++) {
        count += cols;
        if (sentenceStr[count % length] === " ") {
            count++;
        } else {
            while (count > 0 && sentenceStr[(count - 1) % length] !== " ") {
                count--;
            }
        }
    }
    
    return Math.floor(count / length);
}

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

Задача: 1074. Number of Submatrices That Sum to Target
Сложность: hard

Дана матрица и целевое значение. Верните количество непустых подматриц, сумма элементов которых равна целевому значению.

Подматрица x1, y1, x2, y2 — это набор всех ячеек matrix[x][y] с x1 <= x <= x2 и y1 <= y <= y2.

Две подматрицы (x1, y1, x2, y2) и (x1', y1', x2', y2') различны, если у них есть какая-то различающаяся координата: например, если x1 != x1'.

Пример:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

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

1⃣Инициализируйте результат: count = 0. Вычислите количество строк: r = len(matrix) и количество столбцов: c = len(matrix[0]). Вычислите двумерную префиксную сумму ps, выделив еще одну строку и еще один столбец для нулевых значений.

2⃣Итерируйте по строкам: r1 от 1 до r и r2 от r1 до r. Внутри этого двойного цикла фиксируйте левые и правые границы строк и инициализируйте хэш-таблицу для хранения префиксных сумм. Итерируйте по столбцам от 1 до c + 1, вычислите текущую префиксную сумму 1D curr_sum и увеличьте count на количество матриц, сумма которых равна target.

3⃣Добавьте текущую префиксную сумму 1D в хэш-таблицу. Когда все итерации завершены, верните count.

😎 Решение:

var numSubmatrixSumTarget = function(matrix, target) {
    const r = matrix.length, c = matrix[0].length;
    const ps = Array.from({ length: r + 1 }, () => Array(c + 1).fill(0));
    
    for (let i = 1; i <= r; i++) {
        for (let j = 1; j <= c; j++) {
            ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + matrix[i - 1][j];
        }
    }
    
    let count = 0;
    
    for (let r1 = 1; r1 <= r; r1++) {
        for (let r2 = r1; r2 <= r; r2++) {
            const h = {0: 1};
            for (let col = 1; col <= c; col++) {
                const currSum = ps[r2][col] - ps[r1 - 1][col];
                if (h[currSum - target]) {
                    count += h[currSum - target];
                }
                h[currSum] = (h[currSum] || 0) + 1;
            }
        }
    }
    
    return count;
};

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

Задача: 605. Can Place Flowers
Сложность: easy

У вас есть длинная клумба, на которой некоторые участки засажены, а некоторые нет. Однако цветы нельзя сажать на соседних участках.
Дан целочисленный массив flowerbed, содержащий 0 и 1, где 0 означает пустой участок, а 1 — занятый участок, и целое число n. Верните true, если n новых цветов можно посадить на клумбе, не нарушая правила о соседних цветах, и false в противном случае.

Пример:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

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

1⃣Решение очень простое. Мы можем определить максимальное количество дополнительных цветов, count, которые можно посадить для данного расположения клумбы. Для этого мы проходим по всем элементам массива flowerbed и находим те элементы, которые равны 0 (означает пустую позицию).

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

3⃣Если полученное количество count больше или равно n, требуемому количеству цветов для посадки, мы можем посадить n цветов на пустые места, иначе - нет.

😎 Решение:

var canPlaceFlowers = function(flowerbed, n) {
    let count = 0;
    for (let i = 0; i < flowerbed.length; i++) {
        if (flowerbed[i] === 0) {
            let emptyLeft = i === 0 || flowerbed[i - 1] === 0;
            let emptyRight = i === flowerbed.length - 1 || flowerbed[i + 1] === 0;
            if (emptyLeft && emptyRight) {
                flowerbed[i] = 1;
                count++;
            }
        }
    }
    return count >= n;
};

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

Задача: 61. Rotate List
Сложность: medium

Дан указатель на начало связного списка, поверните список вправо на k позиций.

Пример:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

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

1️⃣Найдите старый хвост и соедините его с головой (old_tail.next = head), чтобы замкнуть кольцо. Одновременно вычислите длину списка n.

2️⃣Найдите новый хвост, который находится на позиции (n - k % n - 1) от головы, и новую голову, которая находится на позиции (n - k % n).

3️⃣Разорвите кольцо (new_tail.next = None) и верните new_head.

😎 Решение:

var rotateRight = function (head, k) {
    if (head == null) return null;
    if (head.next == null) return head;

    let old_tail = head;
    let n;
    for (n = 1; old_tail.next != null; n++) old_tail = old_tail.next;
    old_tail.next = head;

    let new_tail = head;
    for (let i = 0; i < n - (k % n) - 1; i++) new_tail = new_tail.next;
    let new_head = new_tail.next;

    new_tail.next = null;
    return new_head;
};

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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