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

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

Задача: 814. Binary Tree Pruning
Сложность: medium

Дан корень бинарного дерева. Верните то же дерево, в котором удалены все поддеревья (данного дерева), не содержащие 1.

Поддерево узла node - это сам узел node и все узлы, являющиеся потомками node.

Пример:

Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

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

1⃣Используем функцию containsOne(node), которая сообщает, содержит ли поддерево в данном узле единицу, и обрезает все поддеревья, не содержащие единицу.

2⃣Например, если поддерево node.left не содержит единицу, то мы должны обрезать его через node.left = null.

3⃣Также нужно проверить родительский узел. Например, если дерево состоит из одного узла 0, то ответом будет пустое дерево.

😎 Решение:

var pruneTree = function(root) {
    if (containsOne(root)) {
        return root;
    }
    return null;
};

var containsOne = function(node) {
    if (!node) return false;

    let leftContainsOne = containsOne(node.left);
    let rightContainsOne = containsOne(node.right);

    if (!leftContainsOne) node.left = null;
    if (!rightContainsOne) node.right = null;

    return node.val === 1 || le

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

Задача: 281. Zigzag Iterator
Сложность: medium

Даны два вектора целых чисел v1 и v2, реализуйте итератор, который возвращает их элементы поочередно.
Реализуйте класс ZigzagIterator:
ZigzagIterator(List<int> v1, List<int> v2) инициализирует объект с двумя векторами v1 и v2.
boolean hasNext() возвращает true, если в итераторе еще есть элементы, и false в противном случае.
int next() возвращает текущий элемент итератора и перемещает итератор к следующему элементу.

Пример:

Input: v1 = [1,2], v2 = [3,4,5,6]
Output: [1,3,2,4,5,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].

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

1⃣Инициализация объекта:
Создайте класс ZigzagIterator с двумя списками v1 и v2. Сохраните эти списки в структуре vectors.
Инициализируйте очередь queue, содержащую пары индексов: индекс списка и индекс элемента в этом списке, если список не пуст.

2⃣Метод next:
Удалите первую пару индексов из очереди.
Извлеките элемент из соответствующего списка по указанным индексам.
Если в текущем списке есть еще элементы, добавьте новую пару индексов (тот же список, следующий элемент) в конец очереди.
Верните извлеченный элемент.

3⃣Метод hasNext:
Проверьте, пуста ли очередь.
Верните true, если в очереди есть элементы, и false в противном случае.

😎 Решение:

class ZigzagIterator {
    constructor(v1, v2) {
        this.vectors = [v1, v2];
        this.queue = [];
        this.vectors.forEach((vec, index) => {
            if (vec.length > 0) {
                this.queue.push([index, 0]);
            }
        });
    }

    next() {
        const [vecIndex, elemIndex] = this.queue.shift();
        const nextElemIndex = elemIndex + 1;
        if (nextElemIndex < this.vectors[vecIndex].length) {
            this.queue.push([vecIndex, nextElemIndex]);
        }
        return this.vectors[vecIndex][elemIndex];
    }

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

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

Задача: 593. Valid Square
Сложность: medium

Даны координаты четырех точек в 2D-пространстве p1, p2, p3 и p4. Верните true, если эти четыре точки образуют квадрат.
Координата точки pi представлена как [xi, yi]. Ввод не дан в каком-либо определенном порядке.
Корректный квадрат имеет четыре равные стороны с положительной длиной и четыре равных угла (по 90 градусов).

Пример:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: true

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

1⃣Определите функцию для вычисления расстояния между двумя точками.

2⃣Проверьте, равны ли все стороны и диагонали для трех уникальных случаев перестановки точек.

3⃣Верните true, если хотя бы одна из проверок проходит.

😎 Решение:

var dist = function(p1, p2) {
    return (p2[1] - p1[1]) ** 2 + (p2[0] - p1[0]) ** 2;
};

var check = function(p1, p2, p3, p4) {
    return dist(p1, p2) > 0 &&
           dist(p1, p2) === dist(p2, p3) &&
           dist(p2, p3) === dist(p3, p4) &&
           dist(p3, p4) === dist(p4, p1) &&
           dist(p1, p3) === dist(p2, p4);
};

var validSquare = function(p1, p2, p3, p4) {
    return check(p1, p2, p3, p4) ||
           check(p1, p3, p2, p4) ||
           check(p1, p2, p4, p3);
};

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

Задача: 291. Word Pattern II
Сложность: medium

Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.
Строка s соответствует шаблону, если существует биективное отображение отдельных символов на непустые строки так, что если каждый символ в шаблоне заменить на строку, которой он отображается, то результирующая строка будет равна s. Биективное отображение означает, что ни два символа не отображаются на одну и ту же строку, и ни один символ не отображается на две разные строки.

Пример:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

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

1⃣Инициализация структур данных и определение рекурсивной функции:
Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.
Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.
Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.

2⃣Рекурсивная проверка соответствия:
Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.
Получите символ из шаблона по индексу pIndex.
Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.

3⃣Отображение новых подстрок:
Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.
Для каждой новой подстроки проверьте, существует ли она уже в `

😎 Решение:

class Solution {
    wordPatternMatch(pattern, s) {
        const symbolMap = new Map();
        const wordSet = new Set();
        return this.isMatch(s, 0, pattern, 0, symbolMap, wordSet);
    }

    isMatch(s, sIndex, pattern, pIndex, symbolMap, wordSet) {
        if (pIndex
        if (pIndex === pattern.length) {
            return sIndex === s.length;
        }
        const symbol = pattern[pIndex];
        if (symbolMap.has(symbol)) {
            const word = symbolMap.get(symbol);
            if (!s.startsWith(word, sIndex)) {
                return false;
            }
            return this.isMatch(s, sIndex + word.length, pattern, pIndex + 1, symbolMap, wordSet);
        }
        for (let k = sIndex + 1; k <= s.length; k++) {
            const newWord = s.substring(sIndex, k);
            if (wordSet.has(newWord)) {
                continue;
            }
            symbolMap.set(symbol, newWord);
            wordSet.add(newWord);
            if (this.isMatch(s, k, pattern, pIndex + 1, symbolMap, wordSet)) {
                return true;
            }
            symbolMap.delete(symbol);
            wordSet.delete(newWord);
        }
        return false;
    }
}

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

Задача: 293. Flip Game
Сложность: easy

Вы играете в игру Flip со своим другом.
Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда один из игроков больше не может сделать ход, и, следовательно, другой игрок становится победителем.
Верните все возможные состояния строки currentState после одного допустимого хода. Вы можете вернуть ответы в любом порядке. Если допустимых ходов нет, верните пустой список [].

Пример:

Input: currentState = "++++"
Output: ["--++","+--+","++--"]

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

1⃣Создайте пустой массив nextPossibleStates для хранения всех возможных следующих состояний после одного хода.

2⃣Запустите цикл от index = 0 до currentState.size() - 1. Для каждого индекса:
Если символы на позициях index и index + 1 равны '+':
Создайте новую строку nextState, заменив две последовательные '+' на '--'.
Используйте конкатенацию строк для создания nextState из подстроки до первого '+', "--" и подстроки после второго '+' до конца.
Сохраните созданное nextState в массив nextPossibleStates.

3⃣После цикла верните массив nextPossibleStates, содержащий все возможные следующие состояния.

😎 Решение:

class Solution {
    generatePossibleNextMoves(currentState) {
        const nextPossibleStates = [];

        for (let i = 0; i < currentState.length - 1; i++) {
            if (currentState[i] === '+' && currentState[i + 1] === '+') {
                const nextState = currentState.slice(0, i) + "--" + currentState.slice(i + 2);
                nextPossibleStates.push(nextState);
            }
        }

        return nextPossibleStates;
    }
}

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

Задача: 1178. Number of Valid Words for Each PuzzleHardTopicsHint
Сложность: hard

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

Слово содержит первую букву головоломки.
Каждая буква в слове присутствует в головоломке.
Например, если головоломка "abcdefg", то допустимыми словами являются "faced", "cabbage" и "baggage", а недопустимыми словами являются "beefed" (не включает 'a') и "based" (включает 's', которой нет в головоломке).

Верните массив answer, где answer[i] - это количество слов в данном списке слов words, которые допустимы относительно головоломки puzzles[i].

Пример:

Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0,1,3,2,0]

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

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

2⃣Подсчитайте количество допустимых слов для каждой головоломки. Для каждой головоломки в списке puzzles:
Преобразуйте ее в битовую маску ее символов. Итерируйте по каждой возможной подмаске, содержащей первую букву головоломки (puzzle[i][0]). Слово является допустимым для головоломки, если его битовая маска совпадает с одной из подмасок головоломки.

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

😎 Решение:

var bitmask = function(word) {
    let mask = 0;
    for (let letter of word) {
        mask |= 1 << (letter.charCodeAt(0) - 'a'.charCodeAt(0));
    }
    return mask;
};

var findNumOfValidWords = function(words, puzzles) {
    let wordCount = new Map();
    for (let word of words) {
        let mask = bitmask(word);
        wordCount.set(mask, (wordCount.get(mask) || 0) + 1);
    }

    let result = [];
    for (let puzzle of puzzles) {
        let first = 1 << (puzzle[0].charCodeAt(0) - 'a'.charCodeAt(0));
        let count = wordCount.get(first) || 0;
        let mask = bitmask(puzzle.slice(1));
        for (let submask = mask; submask > 0; submask = (submask - 1) & mask) {
            count += wordCount.get(submask | first) || 0;
        }
        result.push(count);
    }
    return result;
};

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

Задача: 1669. Merge In Between Linked Lists
Сложность: medium

Вам даны два связанных списка: list1 и list2 размером n и m соответственно.

Удалите узлы list1 с ath узла по bth узел и вставьте на их место list2.

Синие ребра и узлы на рисунке в вверху поста указывают на результат:

Пример:

Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

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

1⃣Инициализация и добавление узлов из list1 до узла a в массив:
Инициализировать переменную index равную 0 и current1 равную list1.
Пока index меньше a, добавлять current1.val в массив mergeArray, перемещаться к следующему узлу current1.next и увеличивать index.

2⃣Добавление узлов из list2 в массив:
Инициализировать current2 равную list2.
Пока current2 не равен null, добавлять current2.val в mergeArray и перемещаться к следующему узлу current2.next.

3⃣Добавление узлов из list1 от узла b + 1 до конца в массив и создание нового связанного списка:
Найти узел на позиции b + 1, перемещая current1 и увеличивая index, пока index меньше b + 1.
Добавлять узлы из current1 в массив, пока current1 не станет null.
Создать новый связанный список из значений в mergeArray, добавляя узлы в начало списка и возвращая его.

😎 Решение:

class Solution {
    mergeInBetween(list1, a, b, list2) {
        let mergeArray = [];
        let index = 0;
        let current1 = list1;
        
        while (index < a) {
            mergeArray.push(current1.val);
            current1 = current1.next;
            index++;
        }
        
        let current2 = list2;
        while (current2 !== null) {
            mergeArray.push(current2.val);
            current2 = current2.next;
        }
        
        while (index < b + 1) {
            current1 = current1.next;
            index++;
        }
        
        while (current1 !== null) {
            mergeArray.push(current1.val);
            current1 = current1.next;
        }
        
        let resultList = null;
        for (let i = mergeArray.length - 1; i >= 0; i--) {
            resultList = new ListNode(mergeArray[i], resultList);
        }
        
        return resultList;
    }
}

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

Задача: 168. Excel Sheet Column Title
Сложность: easy

Дано целое число columnNumber, верните соответствующий заголовок столбца, как он отображается в таблице Excel.
Например:
A -> 1
B -> 2
C -> 3
Z -> 26
AA -> 27
AB -> 28

Пример:

Input: columnNumber = 1
Output: "A"

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

1️⃣Инициализация пустой строки ans:
Создайте пустую строку ans, которая будет хранить заголовок столбца.

2️⃣Циклическое преобразование числа в буквы:
Пока columnNumber больше 0, выполняйте следующие действия:
Вычтите 1 из columnNumber для корректировки индекса (Excel использует 1-индексацию).
Найдите символ, соответствующий остатку от деления columnNumber на 26, и добавьте его в начало строки ans.
Присвойте columnNumber значение от деления columnNumber на 26

3️⃣Переворот и возврат результата:
Так как символы добавляются в начало строки, то по завершению цикла строка ans содержит заголовок столбца в обратном порядке. Переверните строку ans, чтобы представить её в правильном порядке.
Верните полученный заголовок столбца.

😎 Решение:

var convertToTitle = function (columnNumber) {
    let ans = "";

    while (columnNumber > 0) {
        columnNumber--;
        ans =
            String.fromCharCode((columnNumber % 26) + "A".charCodeAt(0)) + ans;
        columnNumber = Math.floor(columnNumber / 26);
    }

    return ans;
};

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

Задача: 1198. Find Smallest Common Element in All Rows
Сложность: medium

Дана матрица mat размером m x n, где каждая строка отсортирована в строго возрастающем порядке. Верните наименьший общий элемент во всех строках.

Если общего элемента нет, верните -1.

Пример:

Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
Output: 5

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

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

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

3⃣Проверка счетчика:
Если счетчик равен количеству строк, возвращайте текущий максимум.
Повторите шаг 2.

😎 Решение:

class Solution {
    smallestCommonElement(mat) {
        const n = mat.length;
        const m = mat[0].length;
        const pos = new Array(n).fill(0);
        let cur_max = 0;
        let cnt = 0;
        
        while (true) {
            for (let i = 0; i < n; ++i) {
                while (pos[i] < m && mat[i][pos[i]] < cur_max) {
                    ++pos[i];
                }
                if (pos[i] >= m) {
                    return -1;
                }
                if (mat[i][pos[i]] !== cur_max) {
                    cnt = 1;
                    cur_max = mat[i][pos[i]];
                } else if (++cnt === n) {
                    return cur_max;
                }
            }
        }
    }
}

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

Задача: №21. Merge Two Sorted Lists
Сложность: easy

Даны два отсортированных связанных списка list1 и list2.
Нужно объединить их в один отсортированный связный список, сшивая узлы, и вернуть его голову.

Пример:

Input: list1 = [1,2,4], list2 = [1,3,4]  
Output: [1,1,2,3,4,4]

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

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

2️⃣ Сравниваем значения головных узлов list1 и list2.
- Если list1.val <= list2.val, связываем list1.next с результатом mergeTwoLists(list1.next, list2)
- Иначе — делаем то же самое для list2

3️⃣ Возвращаем голову текущего минимального узла как новый корень объединённого списка.

😎 Решение:

var mergeTwoLists = function (list1, list2) {
    if (!list1 || !list2) {
        return list1 || list2;
    }

    if (list1.val <= list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
};

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

Задача: 266. Palindrome Permutation
Сложность: easy

Дана строка s, вернуть true, если перестановка строки может образовать палиндром, и false в противном случае.

Пример:

Input: s = "code"
Output: false

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

1️⃣Вместо использования встроенной хеш-таблицы, используем массив в качестве хеш-таблицы. Для этого создаем массив длиной 128, где каждый индекс соответствует одному из 128 возможных ASCII-символов.

2️⃣Проходим по строке s и записываем количество вхождений каждого символа в этот массив.

3️⃣Затем определяем количество символов с нечетным числом вхождений, чтобы определить, возможна ли палиндромная перестановка строки s.

😎 Решение:

class Solution {
    canPermutePalindrome(s) {
        const map = new Array(128).fill(0);
        let count = 0;
        for (const char of s) {
            const index = char.charCodeAt(0);
            map[index]++;
            if (map[index] % 2 === 0) {
                count--;
            } else {
                count++;
            }
        }
        return count <= 1;
    }
}

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