Задача: 591. Tag Validator
Сложность: hard

Дана строка, представляющая фрагмент кода, реализуйте валидатор тегов для разбора кода и определения его корректности.
Фрагмент кода считается корректным, если соблюдаются все следующие правила:
Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен.
Закрытый тег (не обязательно корректный) имеет точно следующий формат: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Среди них <TAG_NAME> — это начальный тег, а </TAG_NAME> — конечный тег. TAG_NAME в начальном и конечном тегах должен быть одинаковым. Закрытый тег корректен, если и только если TAG_NAME и TAG_CONTENT корректны.
Корректное TAG_NAME содержит только заглавные буквы и имеет длину в диапазоне [1, 9]. В противном случае TAG_NAME некорректен.
Корректное TAG_CONTENT может содержать другие корректные закрытые теги, cdata и любые символы (см. примечание 1), КРОМЕ неподходящих <, неподходящих начальных и конечных тегов, и неподходящих или закрытых тегов с некорректным TAG_NAME. В противном случае TAG_CONTENT некорректен.
Начальный тег неподходящий, если нет конечного тега с тем же TAG_NAME, и наоборот. Однако нужно также учитывать проблему несбалансированных тегов, когда они вложены.
< неподходящий, если не удается найти последующий >. И когда вы находите < или </, все последующие символы до следующего > должны быть разобраны как TAG_NAME (не обязательно корректный).
cdata имеет следующий формат: <![CDATA[CDATA_CONTENT]]>. Диапазон CDATA_CONTENT определяется как символы между <![CDATA[ и первым последующим ]]>.
CDATA_CONTENT может содержать любые символы. Функция cdata заключается в том, чтобы запретить валидатору разбирать CDATA_CONTENT, поэтому даже если в нем есть символы, которые могут быть разобраны как тег (корректный или некорректный), вы должны рассматривать их как обычные символы.

Пример:

Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: true

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

1⃣Инициализируйте стек для отслеживания открытых тегов и флаг для определения наличия тегов. Используйте регулярное выражение для проверки корректности TAG_NAME, TAG_CONTENT и CDATA.

2⃣Пройдитесь по строке, проверяя каждый символ. Если встретите <, определите тип тега (начальный, конечный или CDATA). Обновите стек и индексы в зависимости от найденного типа.

3⃣В конце проверьте, что стек пуст (все теги корректно закрыты) и верните результат.

😎 Решение:

class Solution {
    constructor() {
        this.stack = [];
        this.containsTag = false;
    }

    isValidTagName(s, ending) {
        if (ending) {
            if (this.stack.length > 0 && this.stack[this.stack.length - 1] === s) {
                this.stack.pop();
            } else {
                return false;
            }
        } else {
            this.containsTag = true;
            this.stack.push(s);
        }
        return true;
    }

    isValid(code) {
        const regex = /<[A-Z]{0,9}>([^<]*(<((\/?[A-Z]{1,9}>)|(!\[CDATA\[.*?\]\]>)))?)*/;
        if (!regex.test(code)) {
            return false;
        }

        for (let i = 0; i < code.length; i++) {
            let ending = false;
            if (this.stack.length === 0 && this.containsTag) {
                return false;
            }
            if (code[i] === '<') {
                if (code[i + 1] === '!') {
                    i = code.indexOf("]]>", i + 1);
                    if (i === -1) {
                        return false;
                    }
                    continue;
                }
                if (code[i + 1] === '/') {
                    i++;
                    ending = true;
                }
                const closeIndex = code.indexOf('>', i + 1);
                if (closeIndex === -1 || !this.isValidTagName(code.slice(i + 1, closeIndex), ending)) {
                    return false;
                }
                i = closeIndex;
            }
        }
        return this.stack.length === 0;
    }
}

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

Задача: 336. Palindrome Pairs
Сложность: hard

Вам дан массив уникальных строк words, индексируемый с 0.
Пара палиндромов — это пара целых чисел (i, j), таких что:
0 <= i, j < words.length,
i != j, и
words[i] + words[j] (конкатенация двух строк) является палиндромом.
Верните массив всех пар палиндромов из слов.
Вы должны написать алгоритм с временной сложностью O(сумма длин всех слов в words).

Пример:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

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

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

2⃣Итерация по всем парам слов и проверка:
Пройдите по всем парам слов в массиве words, используя два вложенных цикла.
Для каждой пары слов проверяйте, образуют ли они палиндром при конкатенации. Это делается путем объединения строк и проверки, равна ли объединенная строка своей обратной версии.

3⃣Добавление найденных пар в результат:
Если проверка на палиндром проходит, добавьте текущую пару индексов в список результатов.
Верните итоговый список всех найденных пар.

😎 Решение:

var palindromePairs = function(words) {
    let pairs = [];
    
    for (let i = 0; i < words.length; i++) {
        for (let j = 0; j < words.length; j++) {
            if (i === j) continue;
            let combined = words[i] + words[j];
            if (combined === combined.split('').reverse().join('')) {
                pairs.push([i, j]);
            }
        }
    }
    
    return pairs;
};

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

Задача: 518. Coin Change II
Сложность: medium

Вам дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег.
Верните количество комбинаций, которые составляют эту сумму. Если эту сумму нельзя составить никакой комбинацией монет, верните 0.
Предположим, что у вас есть бесконечное количество каждой монеты.
Ответ гарантированно вписывается в знаковое 32-битное целое число.

Пример:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

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

1⃣Создайте двумерный массив memo с n строками и amount + 1 столбцами. Инициализируйте значения -1, чтобы указать, что подзадача еще не решена. Реализуйте рекурсивный метод numberOfWays, который принимает два параметра: индекс i текущей рассматриваемой монеты и оставшуюся сумму, которую нужно составить. Он возвращает количество способов составить сумму, используя монеты, начиная с индекса i до последней монеты.

2⃣Если amount == 0, верните 1. Мы можем выбрать один способ, не выбирая ни одной монеты, чтобы составить сумму 0. Если i == n, у нас не осталось монет для составления суммы, верните 0. Если эта подзадача уже решена, т.е. memo[i][amount] != -1, верните memo[i][amount]. Если значение текущей монеты превышает сумму, мы не можем её использовать. Рекурсивно вызовите numberOfWays(i + 1, amount), присвойте результат memo[i][amount] и верните его.

3⃣В противном случае, добавьте общее количество способов составить сумму, как выбирая текущую монету, так и игнорируя её. Сложите значения numberOfWays(i, amount - coins[i]) и numberOfWays(i + 1, amount), сохраните результат в memo[i][amount] и верните его. Верните numberOfWays(0, amount), ответ на исходную задачу.

😎 Решение:

var change = function(amount, coins) {
    const memo = Array.from({ length: coins.length }, () => Array(amount + 1).fill(-1));

    const numberOfWays = (i, amount) => {
        if (amount === 0) return 1;
        if (i === coins.length) return 0;
        if (memo[i][amount] !== -1) return memo[i][amount];

        if (coins[i] > amount) {
            memo[i][amount] = numberOfWays(i + 1, amount);
        } else {
            memo[i][amount] = numberOfWays(i, amount - coins[i]) + numberOfWays(i + 1, amount);
        }
        return memo[i][amount];
    };

    return numberOfWays(0, amount);
};

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

Задача: 288. Unique Word Abbreviation
Сложность: medium

Сокращение слова — это объединение его первой буквы, количества символов между первой и последней буквой и последней буквы. Если слово состоит только из двух символов, то оно является сокращением само по себе.
Например:
dog --> d1g, потому что между первой буквой 'd' и последней буквой 'g' одна буква.
internationalization --> i18n, потому что между первой буквой 'i' и последней буквой 'n' 18 букв.
it --> it, потому что любое слово из двух символов является своим собственным сокращением.
Реализуйте класс ValidWordAbbr:
ValidWordAbbr(String[] dictionary) Инициализирует объект со словарем слов.
boolean isUnique(string word) Возвращает true, если выполняется одно из следующих условий (в противном случае возвращает false):
В словаре нет слова, сокращение которого равно сокращению слова word.
Для любого слова в словаре, сокращение которого равно сокращению слова word, это слово и word одинаковы.

Пример:

Input
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]]
Output
[null, false, true, false, true, true]

Explanation
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // return false, dictionary word "deer" and word "dear" have the same abbreviation "d2r" but are not the same.
validWordAbbr.isUnique("cart"); // return true, no words in the dictionary have the abbreviation "c2t".
validWordAbbr.isUnique("cane"); // return false, dictionary word "cake" and word "cane" have the same abbreviation  "c2e" but are not the same.
validWordAbbr.isUnique("make"); // return true, no words in the dictionary have the abbreviation "m2e".
validWordAbbr.isUnique("cake"); // return true, because "cake" is already in the dictionary and no other word in the dictionary has "c2e" abbreviation.

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

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

2⃣Генерация сокращений:
При инициализации объекта ValidWordAbbr пройдите через каждое слово в словаре и создайте его сокращение.
Если сокращение уже существует в abbrDict, установите значение в false (не уникальное). В противном случае установите значение в true (уникальное).

3⃣Проверка уникальности:
Для метода isUnique создайте сокращение для входного слова и проверьте, есть ли это сокращение в abbrDict.
Если сокращение отсутствует в abbrDict, возвращайте true.
Если сокращение присутствует и оно уникально, проверьте, есть ли это слово в словаре. Если да, возвращайте true, в противном случае - false.

😎 Решение:

class ValidWordAbbr {
    constructor(dictionary) {
        this.abbrDict = new Map();
        this.dict = new Set(dictionary);
        for (const word of this.dict) {
            const abbr = this.toAbbr(word);
            this.abbrDict.set(abbr, !this.abbrDict.get(abbr));
        }
    }

    isUnique(word) {
        const abbr = this.toAbbr(word);
        const hasAbbr = this.abbrDict.get(abbr);
        return hasAbbr === undefined || (hasAbbr && this.dict.has(word));
    }

    toAbbr(word) {
        const n = word.length;
        if (n <= 2) {
            return word;
        }
        return `${word[0]}${n - 2}${word[n - 1]}`;
    }
}

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

Задача: 323. Number of Connected Components in an Undirected Graph
Сложность: medium

У вас есть граф из n узлов. Вам дано целое число n и массив edges, где edges[i] = [ai, bi] указывает на наличие ребра между ai и bi в графе.
Верните количество связных компонентов в графе.

Пример:

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

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

1⃣Создание списка смежности
Создайте список смежности, такой что adj[v] содержит все смежные вершины вершины v.

2⃣Инициализация посещенных узлов
Инициализируйте хэш-карту или массив visited для отслеживания посещенных вершин.

3⃣Подсчет компонентов
Определите счетчик и инициализируйте его нулем. Итерируйте по каждой вершине в edges, и если вершина еще не была посещена, начните DFS с этой вершины. Добавляйте каждую вершину, посещенную во время DFS, в visited. Каждый раз, когда начинается новый DFS, увеличивайте счетчик на один. В конце, счетчик будет содержать количество связных компонентов в неориентированном графе.

😎 Решение:

function countComponents(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    edges.forEach(([u, v]) => {
        adj[u].push(v);
        adj[v].push(u);
    });

    const visited = new Set();
    let count = 0;

    const dfs = (node) => {
        const stack = [node];
        while (stack.length > 0) {
            const current = stack.pop();
            if (!visited.has(current)) {
                visited.add(current);
                adj[current].forEach(neighbor => {
                    if (!visited.has(neighbor)) stack.push(neighbor);
                });
            }
        }
    };

    for (let i = 0; i < n; i++) {
        if (!visited.has(i)) {
            dfs(i);
            count++;
        }
    }

    return count;
}

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

Задача: 106. Construct Binary Tree from Inorder and Postorder Traversal
Сложность: medium

Даны два массива целых чисел: inorder и postorder, где inorder — это массив обхода в глубину бинарного дерева слева направо, а postorder — это массив обхода в глубину после обработки всех потомков узла. Постройте и верните соответствующее бинарное дерево.

Пример:

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

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

1️⃣Создайте хэш-таблицу (hashmap) для хранения соответствия значений и их индексов в массиве обхода inorder.

2️⃣Определите вспомогательную функцию helper, которая принимает границы левой и правой части текущего поддерева в массиве inorder. Эти границы используются для проверки, пусто ли поддерево. Если левая граница больше правой (in_left > in_right), то поддерево пустое и функция возвращает None.

3️⃣Выберите последний элемент в массиве обхода postorder в качестве корня. Значение корня имеет индекс index в обходе inorder. Элементы от in_left до index - 1 принадлежат левому поддереву, а элементы от index + 1 до in_right — правому поддереву. Согласно логике обхода postorder, сначала рекурсивно строится правое поддерево helper(index + 1, in_right), а затем левое поддерево helper(in_left, index - 1). Возвращается корень.

😎 Решение:

var buildTree = function (inorder, postorder) {
    var idx_map = {};
    var post_idx = postorder.length - 1;
    var helper = function (in_left, in_right) {
        if (in_left > in_right) return null;
        var root_val = postorder[post_idx];
        var root = new TreeNode(root_val);
        var index = idx_map[root_val];
        post_idx--;
        root.right = helper(index + 1, in_right);
        root.left = helper(in_left, index - 1);
        return root;
    };
    for (var i = 0; i < inorder.length; i++) idx_map[inorder[i]] = i;
    return helper(0, inorder.length - 1);
};

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

Задача: 1166. Design File System
Сложность: medium

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

Формат пути - это одна или несколько конкатенированных строк в форме: /, за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" - допустимые пути, в то время как пустая строка "" и "/" не допустимы.

Реализуйте класс FileSystem:

- bool createPath(string path, int value) создает новый путь и связывает с ним значение, если это возможно, и возвращает true. Возвращает false, если путь уже существует или его родительский путь не существует.
- int get(string path) возвращает значение, связанное с путем, или возвращает -1, если путь не существует.

Пример:

Input: 
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output: 
[null,true,1]
Explanation: 
FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1

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

1⃣Инициализируйте словарь или HashMap под названием paths, который будет использовать ключ в виде пути, переданного в нашу функцию create, и значение, переданное этой функции.

2⃣Для функции create выполняем три шага. Сначала выполняем базовую проверку валидности пути. Проверяем, является ли путь пустым, "/" или если путь уже существует в нашем словаре. Если любое из этих условий выполнено, просто возвращаем false. Затем получаем родительский путь предоставленного пути и проверяем его наличие в словаре. Если родительский путь не существует, возвращаем false, иначе продолжаем.

3⃣Наконец, вставляем предоставленный путь и значение в словарь и возвращаем true. Для функции get просто возвращаем значение по умолчанию -1, если путь не существует в словаре. В противном случае возвращаем фактическое значение.

😎 Решение:

class FileSystem {
    constructor() {
        this.paths = new Map();
    }

    createPath(path, value) {
        if (!path || (path.length === 1 && path === "/") || this.paths.has(path)) {
            return false;
        }

        const delimIndex = path.lastIndexOf("/");
        const parent = path.substring(0, delimIndex);

        if (parent.length > 1 && !this.paths.has(parent)) {
            return false;
        }

        this.paths.set(path, value);
        return true;
    }

    get(path) {
        return this.paths.has(path) ? this.paths.get(path) : -1;
    }
}

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

Задача: 100. Same Tree
Сложность: easy

Даны корни двух бинарных деревьев p и q. Напишите функцию, чтобы проверить, одинаковы ли они.

Два бинарных дерева считаются одинаковыми, если они структурно идентичны, и узлы имеют одинаковые значения.

Пример:

Input: p = [1,2,3], q = [1,2,3]
Output: true

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

1⃣Использовать рекурсию.

2⃣Проверьте, не равны ли узлы p и q значению None, и равны ли их значения.

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

😎 Решение:

var isSameTree = function (p, q) {
    if (p == null && q == null) return true;
    if (q == null || p == null) return false;
    if (p.val != q.val) return false;
    return isSameTree(p.right, q.right) && isSameTree(p.left, q.left);
};

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

Задача: 145. Binary Tree Postorder Traversal
Сложность: easy

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

Пример:

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

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

1️⃣Заполнение стека по стратегии право->узел->лево:
Инициируйте стек и добавьте в него корень дерева.
Перед тем как положить узел в стек, сначала добавьте его правого потомка, затем сам узел, а после — левого потомка. Это обеспечит последовательное извлечение узлов из стека в нужном порядке для постпорядкового обхода.

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

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

😎 Решение:

var postorderTraversal = function (root) {
    let output = [];
    let stack = [];
    if (root === null) return output;
    stack.push(root);
    while (stack.length > 0) {
        root = stack.pop();
        output.push(root.val);
        if (root.left !== null) stack.push(root.left);
        if (root.right !== null) stack.push(root.right);
    }
    output.reverse();
    return output;
};

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

Задача: 462. Minimum Moves to Equal Array Elements II
Сложность: medium

Дан массив целых чисел nums размера n, вернуть минимальное количество ходов, необходимых для того, чтобы сделать все элементы массива равными.
В одном ходе вы можете увеличить или уменьшить элемент массива на 1.
Тестовые случаи составлены так, что ответ поместится в 32-битное целое число.

Пример:

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

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

1⃣Найти минимальный и максимальный элементы в массиве. Пусть k будет числом, к которому должны быть приведены все элементы массива.
2⃣Перебирать значения k в диапазоне между минимальным и максимальным элементами, вычисляя количество ходов, необходимых для каждого k.
3⃣Определить минимальное количество ходов среди всех возможных k, что и будет конечным результатом.

😎 Решение:

class Solution {
    minMoves2(nums) {
        let ans = Number.MAX_SAFE_INTEGER;
        let minval = Math.min(...nums);
        let maxval = Math.max(...nums);
        for (let i = minval; i <= maxval; i++) {
            let sum = 0;
            for (let num of nums) {
                sum += Math.abs(num - i);
            }
            ans = Math.min(ans, sum);
        }
        return ans;
    }
}

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

Задача: 491. Non-decreasing Subsequences
Сложность: medium

Дан массив целых чисел nums. Верните все возможные различные неубывающие подпоследовательности данного массива, содержащие как минимум два элемента. Вы можете вернуть ответ в любом порядке.

Пример:

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

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

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

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

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

😎 Решение:

var findSubsequences = function(nums) {
    const result = new Set();
    const sequence = [];
    backtrack(nums, 0, sequence, result);
    return Array.from(result).map(JSON.parse);
};

function backtrack(nums, index, sequence, result) {
    if (index === nums.length) {
        if (sequence.length >= 2) {
            result.add(JSON.stringify(sequence));
        }
        return;
    }
    if (sequence.length === 0 || sequence[sequence.length - 1] <= nums[index]) {
        sequence.push(nums[index]);
        backtrack(nums, index + 1, sequence, result);
        sequence.pop();
    }
    backtrack(nums, index + 1, sequence, result);
}

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

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

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

Задача: 369. Plus One Linked List
Сложность: hard

Дано неотрицательное целое число, представленное в виде связного списка цифр. Добавить к этому числу единицу.
Цифры хранятся таким образом, что самая значимая цифра находится в начале списка.

Пример:

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

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

1⃣Инициализируйте стражевой узел как ListNode(0) и установите его как новую голову списка: sentinel.next = head. Найдите крайний правый элемент, не равный девяти.

2⃣Увеличьте найденную цифру на единицу и установите все следующие девятки в ноль.

3⃣Верните sentinel, если его значение было установлено на 1, иначе верните head (sentinel.next).

😎 Решение:

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    plusOne(head) {
        let sentinel = new ListNode(0);
        sentinel.next = head;
        let notNine = sentinel;

        let current = head;
        while (current !== null) {
            if (current.val !== 9) {
                notNine = current;
            }
            current = current.next;
        }

        notNine.val += 1;
        notNine = notNine.next;

        while (notNine !== null) {
            notNine.val = 0;
            notNine = notNine.next;
        }

        return sentinel.val === 0 ? sentinel.next : sentinel;
    }
}

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

Сложность: hard
Задача: 631. Design Excel Sum Formula

Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти.

Пример:

Input
["Excel", "set", "sum", "set", "get"]
[[3, "C"], [1, "A", 2], [3, "C", ["A1", "A1:B2"]], [2, "B", 2], [3, "C"]]
Output
[null, null, 4, null, 6]

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

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

2⃣Метод установки значений
Реализуйте метод set, который будет изменять значение ячейки в матрице.

3⃣Метод вычисления суммы
Реализуйте метод sum, который будет вычислять сумму значений ячеек, указанных в списке numbers. Метод должен поддерживать как одиночные ячейки, так и диапазоны ячеек.

😎 Решение:

class Excel {
    constructor(height, width) {
        this.mat = Array.from({ length: height }, () => Array(width.charCodeAt(0) - 'A'.charCodeAt(0) + 1).fill(0));
        this.formulas = new Map();
    }

    set(row, column, val) {
        this.mat[row - 1][column.charCodeAt(0) - 'A'.charCodeAt(0)] = val;
        this.formulas.delete(`${row},${column}`);
    }

    get(row, column) {
        const key = `${row},${column}`;
        if (this.formulas.has(key)) {
            return this._evaluateFormula(key);
        }
        return this.mat[row - 1][column.charCodeAt(0) - 'A'.charCodeAt(0)];
    }

    sum(row, column, numbers) {
        const key = `${row},${column}`;
        this.formulas.set(key, numbers);
        return this._evaluateFormula(key);
    }

    _evaluateFormula(key) {
        const numbers = this.formulas.get(key);
        let total = 0;
        for (const number of numbers) {
            if (number.includes(":")) {
                const [start, end] = number.split(":");
                const startRow = parseInt(start.slice(1));
                const startCol = start.charCodeAt(0);
                const endRow = parseInt(end.slice(1));
                const endCol = end.charCodeAt(0);
                for (let r = startRow; r <= endRow; r++) {
                    for (let c = startCol; c <= endCol; c++) {
                        total += this.get(r, String.fromCharCode(c));
                    }
                }
            } else {
                const r = parseInt(number.slice(1));
                const c = number.charAt(0);
                total += this.get(r, c);
            }
        }
        return total;
    }
}

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

Задача: 92. Reverse Linked List II
Сложность: medium

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

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

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

1️⃣Определяем рекурсивную функцию, которая будет отвечать за переворачивание части односвязного списка. Назовем эту функцию recurse. Функция принимает три параметра: m, начальную точку переворота, n, конечную точку переворота, и указатель right, который начинается с узла n в связанном списке и движется назад вместе с откатом рекурсии. Если это пока не ясно, следующие диаграммы помогут.

2️⃣Также у нас есть указатель left, который начинается с узла m в связанном списке и движется вперед. В Python мы должны использовать глобальную переменную для этого, которая изменяется с каждым вызовом рекурсии. В других языках, где изменения, сделанные в вызовах функций, сохраняются, мы можем рассматривать этот указатель как дополнительную переменную для функции recurse.
В рекурсивном вызове, учитывая m, n и right, мы проверяем, равно ли n единице. Если это так, дальше двигаться не нужно.

3️⃣До тех пор, пока мы не достигнем n = 1, мы продолжаем двигать указатель right на один шаг вперед, после чего делаем рекурсивный вызов с уменьшенным на один значением n. В то же время мы продолжаем двигать указатель left вперед до тех пор, пока m не станет равным 1. Когда мы говорим, что указатель движется вперед, мы имеем в виду pointer.next.
Таким образом, мы откатываемся, как только n достигает 1. В этот момент указатель right находится на последнем узле подсписка, который мы хотим перевернуть, и left уже достиг первого узла этого подсписка. Тогда мы меняем данные и перемещаем указатель left на один шаг вперед с помощью left = left.next. Нам нужно, чтобы это изменение сохранялось в процессе отката.
Оттуда при каждом откате указатель right движется на один шаг назад. Это и есть та симуляция, о которой мы всё время говорили. Обратное движение симулируется откатом.
Мы прекращаем обмены, когда right == left, что происходит, если размер подсписка нечетный, или right.next == left, что происходит в процессе отката для четного подсписка, когда указатель right пересекает left. Мы используем глобальный булевый флаг для остановки обменов, как только эти условия выполнены.

😎 Решение:

var reverseBetween = function (head, m, n) {
    let left = head,
        stop = false;
    const recurseAndReverse = (right, m, n) => {
        if (n == 1) return;
        right = right.next;
        if (m > 1) left = left.next;
        recurseAndReverse(right, m - 1, n - 1);
        if (left == right || right.next == left) stop = true;
        if (!stop) {
            [left.val, right.val] = [right.val, left.val];
            left = left.next;
        }
    };
    recurseAndReverse(head, m, n);
    return head;
};

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

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

Дана доска Sudoku 9x9. Нужно проверить, является ли она действительной. Проверке подлежат только заполненные ячейки, по правилам:
- В каждой строке цифры от 1 до 9 не должны повторяться
- В каждом столбце цифры от 1 до 9 не должны повторяться
- В каждом из девяти блоков 3x3 цифры от 1 до 9 не должны повторяться

Пример:

Input: board = 
[["5","3",".",".","7",".",".",".","."],
 ["6",".",".","1","9","5",".",".","."],
 [".","9","8",".",".",".",".","6","."],
 ["8",".",".",".","6",".",".",".","3"],
 ["4",".",".","8",".","3",".",".","1"],
 ["7",".",".",".","2",".",".",".","6"],
 [".","6",".",".",".",".","2","8","."],
 [".",".",".","4","1","9",".",".","5"],
 [".",".",".",".","8",".",".","7","9"]]
Output: true

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

1️⃣ Создаем три структуры: rowSet, colSet, boxSet (или Map), чтобы отслеживать наличие чисел в строках, столбцах и блоках 3x3.

2️⃣ Проходим по каждой ячейке поля:
- Пропускаем, если это .
- Проверяем наличие текущей цифры в соответствующей строке, столбце и блоке
- Если она уже была — возвращаем false
- Иначе добавляем в соответствующие множества

3️⃣ Если дошли до конца, не нарушив правил — возвращаем true

😎 Решение:

var isValidSudoku = function(board) {
    const rows = new Array(9).fill(0).map(() => new Set());
    const cols = new Array(9).fill(0).map(() => new Set());
    const boxes = new Array(9).fill(0).map(() => new Set());

    for (let r = 0; r < 9; r++) {
        for (let c = 0; c < 9; c++) {
            const val = board[r][c];
            if (val === '.') continue;

            const boxIdx = Math.floor(r / 3) * 3 + Math.floor(c / 3);

            if (rows[r].has(val) || cols[c].has(val) || boxes[boxIdx].has(val)) {
                return false;
            }

            rows[r].add(val);
            cols[c].add(val);
            boxes[boxIdx].add(val);
        }
    }

    return true;
};

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

Задача: 247. Strobogrammatic Number II
Сложность: medium

Дано целое число n, верните все стробограмматические числа длины n. Ответ можно возвращать в любом порядке.
Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).

Пример:

Input: n = 2
Output: ["11","69","88","96"]

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

1️⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа.

2️⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n:
Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"].
Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns.
Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n.

3️⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums.

😎 Решение:

class Solution {
    constructor() {
        this.reversiblePairs = [
            ['0', '0'], ['1', '1'],
            ['6', '9'], ['8', '8'], ['9', '6']
        ];
    }

    generateStroboNumbers(n, finalLength) {
        if (n === 0) {
            return [""];
        }

        if (n === 1) {
            return ["0", "1", "8"];
        }

        const prevStroboNums = this.generateStroboNumbers(n - 2, finalLength);
        const currStroboNums = [];

        for (const prevStroboNum of prevStroboNums) {
            for (const pair of this.reversiblePairs) {
                if (pair[0] !== '0' || n !== finalLength) {
                    currStroboNums.push(pair[0] + prevStroboNum + pair[1]);
                }
            }
        }

        return currStroboNums;
    }

    findStrobogrammatic(n) {
        return this.generateStroboNumbers(n, n);
    }
}

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

Задача: 78. Subsets
Сложность: medium

Дан массив целых чисел nums, содержащий уникальные элементы. Верните все возможные подмножества (степенной набор).

Множество решений не должно содержать дублирующихся подмножеств. Результат может быть возвращен в любом порядке.

Пример:

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

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

1️⃣Определяем функцию обратного отслеживания под названием backtrack(first, curr), которая принимает индекс первого элемента, который нужно добавить, и текущую комбинацию в качестве аргументов.

2️⃣Если текущая комбинация завершена, мы добавляем её в итоговый вывод.

3️⃣В противном случае перебираем индексы i от first до длины всей последовательности n, добавляем элемент nums[i] в текущую комбинацию curr, продолжаем добавлять больше чисел в комбинацию: backtrack(i + 1, curr) и возвращаемся, удаляя nums[i] из curr.

😎 Решение:

var subsets = function (nums) {
    let output = [];
    let n = nums.length;
    function backtrack(first = 0, curr = [], k) {
        if (curr.length == k) {
            output.push([...curr]);
            return;
        }
        for (let i = first; i < n; i++) {
            curr.push(nums[i]);
            backtrack(i + 1, curr, k);
            curr.pop();
        }
    }
    for (let k = 0; k < n + 1; k++) {
        backtrack(0, [], k);
    }
    return output;
};

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

Задача: 946. Validate Stack Sequences
Сложность: medium

Учитывая, что два целочисленных массива pushed и popped имеют разные значения, верните true, если это могло быть результатом последовательности операций push и pop на изначально пустом стеке, или false в противном случае.

Пример:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true

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

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

2⃣Пройти по каждому элементу в массиве pushed:
Добавить элемент в стек.
Проверить верхний элемент стека:
Если он совпадает с текущим элементом в popped, удалить элемент из стека и увеличить указатель j.

3⃣В конце вернуть true, если указатель j достиг конца массива popped, иначе вернуть false.

😎 Решение:

var validateStackSequences = function(pushed, popped) {
    const stack = [];
    let j = 0;
    for (let x of pushed) {
        stack.push(x);
        while (stack.length && j < popped.length && stack[stack.length - 1] === popped[j]) {
            stack.pop();
            j++;
        }
    }
    return j === popped.length;
};

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

Задача: 958. Check Completeness of a Binary Tree
Сложность: medium

Дан корень бинарного дерева, определите, является ли оно полным бинарным деревом.

В полном бинарном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. На последнем уровне h может быть от 1 до 2^h узлов включительно.

Пример:

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

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

1⃣Если корень дерева равен null, верните true.

2⃣Инициализируйте переменную nullNodeFound как false для отслеживания того, встречался ли уже null-узел. Создайте очередь и поместите в неё корень дерева.

3⃣Пока очередь не пуста:
Извлеките первый элемент из очереди.
Если элемент равен null, установите nullNodeFound в true.
Если элемент не равен null, проверьте, встречался ли уже null-узел. Если nullNodeFound равен true, верните false. В противном случае добавьте в очередь левого и правого потомков текущего узла.

😎 Решение:

var isCompleteTree = function(root) {
    if (root === null) {
        return true;
    }

    let queue = [root];
    let nullNodeFound = false;

    while (queue.length > 0) {
        let node = queue.shift();
        
        if (node === null) {
            nullNodeFound = true;
        } else {
            if (nullNodeFound) {
                return false;
            }
            queue.push(node.left);
            queue.push(node.right);
        }
    }
    return true;
};

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

Задача: 166. Fraction to Recurring Decimal
Сложность: medium

Даны два целых числа, представляющих числитель и знаменатель дроби. Верните дробь в строковом формате.
Если дробная часть повторяется, заключите повторяющуюся часть в скобки.
Если возможны несколько ответов, верните любой из них.
Гарантируется, что длина строки ответа будет меньше 10^4 для всех предоставленных входных данных.

Пример:

Input: numerator = 1, denominator = 2
Output: "0.5"

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

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

2️⃣Обработка нулевого остатка:
Если в процессе деления остаток становится равным нулю, это означает, что дробная часть не повторяется и процесс можно завершать.

3️⃣Учет особенностей:
Будьте осторожны с крайними случаями, такими как отрицательные дроби или особо сложные случаи, например, деление −1 на −2147483648. В этих случаях следует корректно обрабатывать знаки и возможные переполнения.

😎 Решение:

var fractionToDecimal = function (numerator, denominator) {
    if (numerator === 0) {
        return "0";
    }
    var fraction = [];
    if ((numerator < 0) ^ (denominator < 0)) {
        fraction.push("-");
    }
   
    var dividend = Math.abs(numerator);
    var divisor = Math.abs(denominator);
    fraction.push(Math.floor(dividend / divisor).toString());
    var remainder = dividend % divisor;
    if (remainder === 0) {
        return fraction.join("");
    }
    fraction.push(".");
    var map = {};
    while (remainder !== 0) {
        if (remainder in map) {
            fraction.splice(map[remainder], 0, "(");
            fraction.push(")");
            break;
        }
        map[remainder] = fraction.length;
        remainder *= 10;
        fraction.push(Math.floor(remainder / divisor).toString());
        remainder %= divisor;
    }
    return fraction.join("");
};

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