Задача: 267. Palindrome Permutation II
Сложность: medium

Дана строка s, верните все палиндромные перестановки (без дубликатов) этой строки.
Вы можете вернуть ответ в любом порядке. Если у строки s нет палиндромных перестановок, верните пустой список.

Пример:

Input: s = "aabb"
Output: ["abba","baab"]

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

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

2️⃣Генерация первой половины палиндромной строки:
Создаем строку st, которая содержит все символы строки s с количеством вхождений, уменьшенным до половины от их первоначального количества.
Если длина строки s нечетная, сохраняем символ, который встречается нечетное количество раз, отдельно.

3️⃣Генерация всех перестановок первой половины и создание палиндромов:
Генерируем все перестановки строки st.
Для каждой перестановки добавляем её обратную строку к самой себе, создавая тем самым полную палиндромную строку.
Если длина строки s нечетная, добавляем сохраненный символ в середину каждого палиндрома.
Чтобы избежать дубликатов, проверяем, равны ли элементы перед свапом. Если да, то пропускаем данную перестановку.

😎 Решение:

class Solution {
    constructor() {
        this.set = new Set();
    }

    generatePalindromes(s) {
        const map = new Array(128).fill(0);
        const st = new Array(Math.floor(s.length / 2)).fill('');
        if (!this.canPermutePalindrome(s, map)) {
            return [];
        }

        let ch = '';
        let k = 0;
        for (let i = 0; i < map.length; i++) {
            if (map[i] % 2 === 1) {
                ch = String.fromCharCode(i);
            }
            for (let j = 0; j < Math.floor(map[i] / 2); j++) {
                st[k++] = String.fromCharCode(i);
            }
        }
        this.permute(st, 0, ch);
        return Array.from(this.set);
    }

    canPermutePalindrome(s, map) {
        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;
    }

    swap(s, i, j) {
        [s[i], s[j]] = [s[j], s[i]];
    }

    permute(s, l, ch) {
        if (l === s.length) {
            this.set.add(s.join('') + (ch === '' ? '' : ch) + s.slice().reverse().join(''));
        } else {
            for (let i = l; i < s.length; i++) {
                if (s[l] !== s[i] || l === i) {
                    this.swap(s, l, i);
                    this.permute(s, l + 1, ch);
                    this.swap(s, l, i);
                }
            }
        }
    }
}

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

Задача: 541. Reverse String II
Сложность: easy

Дана строка s и целое число k, переверните первые k символов для каждых 2k символов, начиная с начала строки.
Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть.

Пример:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

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

1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее.

2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут.

3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--.

😎 Решение:

class Solution {
    reverseStr(s, k) {
        let a = s.split('');
        for (let start = 0; start < a.length; start += 2 * k) {
            let i = start, j = Math.min(start + k - 1, a.length - 1);
            while (i < j) {
                [a[i], a[j]] = [a[j], a[i]];
                i++;
                j--;
            }
        }
        return a.join('');
    }
}

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

Задача: 490. The Maze
Сложность: medium

В лабиринте есть шар, который может перемещаться по пустым пространствам (представленным как 0) и стенам (представленным как 1). Шар может катиться по пустым пространствам вверх, вниз, влево или вправо, но он не остановится до тех пор, пока не наткнется на стену. Когда шар останавливается, он может выбрать следующее направление.
Дан лабиринт размером m x n, начальная позиция шара и место назначения, где start = [startrow, startcol] и destination = [destinationrow, destinationcol]. Верните true, если шар может остановиться в месте назначения, иначе верните false.
Вы можете предположить, что границы лабиринта представляют собой стены. В приведённом ниже примере они не указаны.

Пример:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.

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

1⃣Инициализация и подготовка данных
Определите количество строк и столбцов в лабиринте (m и n). Создайте 2D массив visit для отслеживания посещённых ячеек. Запустите DFS (глубокий поиск) с начальной позиции.

2⃣DFS обход
Если текущая ячейка уже посещена, верните false. Если текущая ячейка совпадает с ячейкой назначения, верните true. Отметьте текущую ячейку как посещённую. Переберите все четыре направления движения (вверх, вправо, вниз, влево): продвигайтесь в выбранном направлении до тех пор, пока не столкнётесь со стеной или границей. После остановки вызовите DFS для новой позиции.

3⃣Результат
Если любой вызов DFS возвращает true, завершите выполнение и верните true. Если ни один путь не приводит к цели, верните false.

😎 Решение:

class Solution {
    constructor() {
        this.directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    }

    hasPath(maze, start, destination) {
        const m = maze.length, n = maze[0].length;
        const visit = Array.from({ length: m }, () => Array(n).fill(false));
        return this.dfs(m, n, maze, start, destination, visit);
    }

    dfs(m, n, maze, curr, destination, visit) {
        if (visit[curr[0]][curr[1]]) return false;
        if (curr[0] === destination[0] && curr[1] === destination[1]) return true;
        visit[curr[0]][curr[1]] = true;
        for (const [dx, dy] of this.directions) {
            let r = curr[0], c = curr[1];
            while (r >= 0 && r < m && c >= 0 && c < n && maze[r][c] === 0) {
                r += dx;
                c += dy;
            }
            if (this.dfs(m, n, maze, [r - dx, c - dy], destination, visit)) return true;
        }
        return false;
    }
}

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

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

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

Задача: 589. N-ary Tree Preorder Traversal
Сложность: easy

Дан корень N-арного дерева, верните значения его узлов в порядке предварительного (preorder) обхода.
Сериализация ввода N-арного дерева представлена в их обходе уровнями. Каждая группа детей разделена значением null (См. примеры).

Пример:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

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

1⃣Инициализация
Создайте два списка: stack для хранения узлов и output для хранения значений узлов в порядке обхода. Добавьте корневой узел в stack.

2⃣Итеративный обход
Пока stack не пуст, извлекайте узел из stack и добавляйте его значение в output. Разверните список дочерних узлов текущего узла и добавьте их в stack.

3⃣Возврат результата
Верните список output как результат.

😎 Решение:

function Node(val, children) {
    this.val = val;
    this.children = children || [];
}

var preorder = function(root) {
    if (root === null) return [];
    let stack = [root];
    let output = [];
    
    while (stack.length > 0) {
        let node = stack.pop();
        output.push(node.val);
        for (let i = node.children.length - 1; i >= 0; i--) {
            stack.push(node.children[i]);
        }
    }
    
    return output;
};

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

Задача: 208. Implement Trie (Prefix Tree)
Сложность: medium

Trie (произносится как "трай") или префиксное дерево — это древовидная структура данных, используемая для эффективного хранения и поиска ключей в наборе строк. Существует множество применений этой структуры данных, таких как автозаполнение и проверка орфографии.
Реализуйте класс Trie:
Trie() инициализирует объект trie.
void insert(String word) вставляет строку word в trie.
boolean search(String word) возвращает true, если строка word есть в trie (то есть была вставлена ранее), и false в противном случае.
boolean startsWith(String prefix) возвращает true, если есть ранее вставленная строка word, которая имеет префикс prefix, и false в противном случае.

Пример:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

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

1️⃣Инициализация и вставка в Trie:
Создайте класс Trie, который включает в себя метод insert(String word) для добавления строк в Trie.
Метод insert инициализирует текущий узел как корень и проходит по каждому символу строки. Если текущий узел не содержит символа, создайте новый узел. В конце отметьте последний узел как конец слова.

2️⃣Поиск строки в Trie:
Создайте метод search(String word), который использует вспомогательный метод searchPrefix(String word) для поиска строки или префикса в Trie.
В методе searchPrefix начните с корневого узла и для каждого символа строки перемещайтесь к следующему узлу. Если на каком-то этапе узел не содержит текущего символа, верните null. В противном случае, в конце строки верните текущий узел.

3️⃣Проверка наличия префикса в Trie:
Создайте метод startsWith(String prefix), который также использует метод searchPrefix(String prefix).
Метод startsWith вызывает searchPrefix и возвращает true, если возвращаемый узел не равен null, что указывает на наличие префикса в Trie.

😎 Решение:

class TrieNode {
    constructor() {
        this.links = new Array(26).fill(null);
        this.isEnd = false;
    }

    containsKey(ch) {
        return this.links[ch.charCodeAt(0) - 'a'.charCodeAt(0)] !== null;
    }

    get(ch) {
        return this.links[ch.charCodeAt(0) - 'a'.charCodeAt(0)];
    }

    put(ch, node) {
        this.links[ch.charCodeAt(0) - 'a'.charCodeAt(0)] = node;
    }

    setEnd() {
        this.isEnd = true;
    }

    isEndNode() {
        return this.isEnd;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;
        for (let ch of word) {
            if (!node.containsKey(ch)) {
                node.put(ch, new TrieNode());
            }
            node = node.get(ch);
        }
        node.setEnd();
    }

    searchPrefix(word) {
        let node = this.root;
        for (let ch of word) {
            if (node.containsKey(ch)) {
                node = node.get(ch);
            } else {
                return null;
            }
        }
        return node;
    }

    search(word) {
        let node = this.searchPrefix(word);
        return node !== null && node.isEndNode();
    }

    startsWith(prefix) {

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

Задача: 366. Find Leaves of Binary Tree
Сложность: medium

Дан корень бинарного дерева, соберите узлы дерева следующим образом:
Соберите все листовые узлы.
Удалите все листовые узлы.
Повторяйте, пока дерево не станет пустым.

Пример:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

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

1⃣Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -1.

2⃣Сохранить пары (высота, значение) для всех узлов и отсортировать их по высоте.

3⃣Организовать узлы по высоте и вернуть результат.

😎 Решение:

class Solution {
    constructor() {
        this.pairs = [];
    }

    getHeight(node) {
        if (!node) return -1;
        const leftHeight = this.getHeight(node.left);
        const rightHeight = this.getHeight(node.right);
        const currHeight = Math.max(leftHeight, rightHeight) + 1;
        this.pairs.push([currHeight, node.val]);
        return currHeight;
    }

    findLeaves(root) {
        this.getHeight(root);
        this.pairs.sort((a, b) => a[0] - b[0]);
        const solution = [];
        let currentHeight = -1;
        for (const [height, value] of this.pairs) {
            if (height !== currentHeight) {
                solution.push([]);
                currentHeight = height;
            }
            solution[solution.length - 1].push(value);
        }
        return solution;
    }
}

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

Задача: 211. Design Add and Search Words Data Structure
Сложность: medium

Спроектируйте структуру данных, которая поддерживает добавление новых слов и проверку, соответствует ли строка любому ранее добавленному слову.
Реализуйте класс WordDictionary:
WordDictionary() инициализирует объект.
void addWord(word) добавляет слово в структуру данных, оно может быть сопоставлено позже.
bool search(word) возвращает true, если в структуре данных есть строка, которая соответствует слову, или false в противном случае. Слово может содержать точки '.', где точки могут быть сопоставлены с любой буквой.

Пример 1:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

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

1️⃣ Инициализация и добавление слова:
Создайте класс WordDictionary с конструктором, который инициализирует корневой узел TrieNode.
Метод addWord(String word) добавляет слово в структуру данных. Инициализируйте текущий узел как корневой и пройдите по каждому символу слова. Если символ отсутствует среди дочерних узлов текущего узла, создайте новый узел. Перемещайтесь к следующему узлу. В конце отметьте текущий узел как конец слова.

2️⃣ Поиск слова в узле:
Метод searchInNode(String word, TrieNode node) ищет слово в переданном узле TrieNode. Пройдите по каждому символу слова. Если символ не найден среди дочерних узлов текущего узла, проверьте, является ли символ точкой '.'. Если да, рекурсивно выполните поиск в каждом дочернем узле текущего узла. Если символ не точка и не найден, верните false. Если символ найден, перейдите к следующему узлу. В конце проверьте, является ли текущий узел концом слова.

3️⃣ Поиск слова в структуре данных:
Метод search(String word) использует метод searchInNode() для поиска слова, начиная с корневого узла. Верните результат поиска. Если слово найдено, верните true, иначе false.

😎 Решение:

class TrieNode {
    constructor() {
        this.children = new Map();
        this.isWord = false;
    }
}

class WordDictionary {
    constructor() {
        this.trie = new TrieNode();
    }

    addWord(word) {
        let node = this.trie;
        for (let ch of word) {
            if (!node.children.has(ch)) {
                node.children.set(ch, new TrieNode());
            }
            node = node.children.get(ch);
        }
        node.isWord = true;
    }

    searchInNode(word, node) {
        for (let i = 0; i < word.length; i++) {
            let ch = word[i];
            if (!node.children.has(ch)) {
                if (ch === '.') {
                    for (let child of node.children.values()) {
                        if (this.searchInNode(word.slice(i + 1), child)) {
                            return true;
                        }
                    }
                }
                return false;
            } else {
                node = node.children.get(ch);
            }
        }
        return node.isWord;
    }

    search(word) {
        return this.searchInNode(word, this.trie);
    }
}

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

Задача: 51. N-Queens
Сложность: medium

Задача о n-ферзях заключается в размещении n ферзей на шахматной доске n на n таким образом, чтобы ни один из ферзей не атаковал друг друга.
Для заданного целого числа n верните все различные решения этой задачи. Ответ можно предоставить в любом порядке.
Каждое решение содержит уникальную конфигурацию доски с размещением ферзей, где символы 'Q' и '.' обозначают ферзя и пустое пространство соответственно.

Пример:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

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

1️⃣Создание рекурсивной функции backtrack, которая использует несколько аргументов для сохранения состояния доски. Первый параметр — это строка, на которой мы собираемся разместить следующую ферзя. Также будут использоваться три набора, которые отслеживают, в каких столбцах, диагоналях и антидиагоналях уже были размещены ферзи. Кроме того, текущее состояние доски сохраняется для включения в ответ, если найдено действительное решение. Если текущая рассматриваемая строка равна n, значит, найдено решение. Текущее состояние доски добавляется в список решений и функция завершается. Для получения корректного формата вывода используется вспомогательная функция.

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

3️⃣Если размещение ферзя возможно, ферзь добавляется на доску, и обновляются три набора данных (cols, diagonals и antiDiagonals). Затем функция вызывается снова, но с row + 1. Вызов функции в шаге 3 исследует все допустимые состояния доски с учетом размещенного ферзя на шаге 2. После завершения исследования этого пути выполняется откат: ферзь удаляется из клетки, что включает удаление значений, добавленных в наборы, и удаление "Q" с доски.

😎 Решение:

var solveNQueens = function (n) {
    const solutions = [];
    const emptyBoard = Array.from({ length: n }, () => Array(n).fill("."));
    const createBoard = (state) => {
        const board = [];
        for (let row = 0; row < n; row++) {
            board.push(state[row].join(""));
        }
        return board;
    };
    const backtrack = (row, diagonals, antiDiagonals, cols, state) => {
        if (row === n) {
            solutions.push(createBoard(state));
            return;
        }
        for (let col = 0; col < n; col++) {
            const currDiagonal = row - col;
            const currAntiDiagonal = row + col;
            if (
                cols.has(col) ||
                diagonals.has(currDiagonal) ||
                antiDiagonals.has(currAntiDiagonal)
            ) {
                continue;
            }
            cols.add(col);
            diagonals.add(currDiagonal);
            antiDiagonals.add(currAntiDiagonal);
            state[row][col] = "Q";
            backtrack(row + 1, diagonals, antiDiagonals, cols, state);
            cols.delete(col);
            diagonals.delete(currDiagonal);
            antiDiagonals.delete(currAntiDiagonal);
            state[row][col] = ".";
        }
    };
    backtrack(0, new Set(), new Set(), new Set(), emptyBoard);
    return solutions;
};

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

Задача: 856. Score of Parentheses
Сложность: medium

Дана строка s, состоящая из сбалансированных скобок, верните счёт строки.

Счёт сбалансированной строки скобок основывается на следующих правилах:

"()" имеет счёт 1.
AB имеет счёт A + B, где A и B — сбалансированные строки скобок.
(A) имеет счёт 2 * A, где A — сбалансированная строка скобок.

Пример:

Input: s = "()"
Output: 1

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

1⃣Назовём сбалансированную строку примитивной, если её нельзя разделить на две непустые сбалансированные строки.

2⃣Отслеживая баланс (количество открывающих скобок минус количество закрывающих скобок), мы можем разделить строку S на примитивные подстроки S = P_1 + P_2 + ... + P_n. Тогда, по определению, score(S) = score(P_1) + score(P_2) + ... + score(P_n).

3⃣Для каждой примитивной подстроки (S[i], S[i+1], ..., S[k]), если длина строки равна 2, то её счёт равен 1. В противном случае, счёт равен удвоенному счёту подстроки (S[i+1], S[i+2], ..., S[k-1]).

😎 Решение:

var scoreOfParentheses = function(S) {
    return F(S, 0, S.length)
}

var F = function(S, i, j) {
    let ans = 0, bal = 0

    for (let k = i; k < j; k++) {
        bal += S[k] === '(' ? 1 : -1
        if (bal === 0) {
            if (k - i === 1) ans++
            else ans += 2 * F(S, i + 1, k)
            i = k + 1
        }
    }

    return ans
}

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

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

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

Пример:

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

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

1⃣Определить вспомогательную функцию.

2⃣Создать рекрусию.

3⃣Закончить с написанием кода.

😎 Решение:

var inorderTraversal = function (root) {
    let res = [];
    helper(root, res);
    return res;
};
var helper = function (root, res) {
    if (root !== null) {
        helper(root.left, res);
        res.push(root.val);
        helper(root.right, res);
    }
};

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

Задача: 398. Random Pick Index
Сложность: medium

Из целочисленного массива nums с возможными дубликатами случайным образом выведите индекс заданного целевого числа. Можно предположить, что заданное целевое число должно существовать в массиве. Реализация класса Solution: Solution(int[] nums) Инициализирует объект с массивом nums. int pick(int target) Выбирает случайный индекс i из nums, где nums[i] == target. Если существует несколько допустимых i, то каждый индекс должен иметь равную вероятность возврата.

Пример:

Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]

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

1⃣Инициализируйте объект с массивом nums. Сохраните этот массив для дальнейшего использования.

2⃣Реализуйте метод pick(target), который выбирает случайный индекс i из массива nums, где nums[i] равен target. Если таких индексов несколько, каждый из них должен иметь равную вероятность быть выбранным.

3⃣Для реализации метода pick используйте алгоритм reservoir sampling для выбора случайного индекса.

😎 Решение:

class Solution {
    constructor(nums) {
        this.nums = nums;
    }

    pick(target) {
        let count = 0;
        let result = -1;
        for (let i = 0; i < this.nums.length; i++) {
            if (this.nums[i] === target) {
                count++;
                if (Math.floor(Math.random() * count) === count - 1) {
                    result = i;
                }
            }
        }
        return result;
    }
}

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

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

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

Пример:

Input: target = 2
Output: 3

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

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

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

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

😎 Решение:

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

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

Задача: 1429. First Unique Number
Сложность: medium

У вас есть очередь целых чисел, необходимо извлечь первый уникальный элемент из очереди.

Реализуйте класс FirstUnique:
- FirstUnique(int[] nums) Инициализирует объект числами в очереди.
- int showFirstUnique() возвращает значение первого уникального элемента в очереди и возвращает -1, если такого элемента нет.
- void add(int value) вставляет значение в очередь.

Пример:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output: 
[null,2,null,2,null,3,null,-1]
Explanation: 
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5);            // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1

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

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

2⃣Метод showFirstUnique возвращает значение первого уникального элемента в очереди, если таковой существует, или -1, если уникальных элементов нет.

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

😎 Решение:

class FirstUnique {
    constructor(nums) {
        this.isUnique = new Map();
        this.queue = new Map();
        for (let num of nums) {
            this.add(num);
        }
    }

    showFirstUnique() {
        for (let [key, value] of this.queue) {
            if (this.isUnique.get(key)) {
                return key;
            }
        }
        return -1;
    }

    add(value) {
        if (!this.isUnique.has(value)) {
            this.isUnique.set(value, true);
            this.queue.set(value, null);
        } else if (this.isUnique.get(value)) {
            this.isUnique.set(value, false);
            this.queue.delete(value);
        }
    }
}

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

Задача: 844. Backspace String Compare
Сложность: easy

Даны две строки s и t, верните true, если они равны после ввода в пустые текстовые редакторы. Символ '#' означает клавишу backspace.

Обратите внимание, что после нажатия backspace на пустом тексте, текст останется пустым.

Пример:

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

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

1⃣Пройдите по строкам s и t с конца, учитывая символы '#' как backspace и пропуская соответствующие символы.

2⃣Сравнивайте текущие символы из обеих строк, пропуская символы, которые должны быть удалены.

3⃣Если все соответствующие символы совпадают и строки эквивалентны после всех backspace операций, верните true; в противном случае верните false.

😎 Решение:

var backspaceCompare = function(S, T) {
    let i = S.length - 1, j = T.length - 1;
    let skipS = 0, skipT = 0;

    while (i >= 0 || j >= 0) {
        while (i >= 0) {
            if (S[i] === '#') {
                skipS++;
                i--;
            } else if (skipS > 0) {
                skipS--;
                i--;
            } else {
                break;
            }
        }
        while (j >= 0) {
            if (T[j] === '#') {
                skipT++;
                j--;
            } else if (skipT > 0) {
                skipT--;
                j--;
            } else {
                break;
            }
        }
        if (i >= 0 && j >= 0 && S[i] !== T[j]) {
            return false;
        }
        if ((i >= 0) !== (j >= 0)) {
            return false;
        }
        i--;
        j--;
    }
    return true;
};

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

Задача: 1122. Relative Sort Array
Сложность: easy

Даны два массива arr1 и arr2, элементы arr2 уникальны, и все элементы arr2 также присутствуют в arr1.

Отсортируйте элементы arr1 таким образом, чтобы относительный порядок элементов в arr1 был таким же, как в arr2. Элементы, которые не встречаются в arr2, должны быть размещены в конце arr1 в порядке возрастания.

Пример:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

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

1⃣Инициализация и подсчёт:
Инициализируйте пустой массив result и массив remaining для хранения оставшихся элементов.
Создайте хеш-таблицу countMap для хранения количества вхождений каждого элемента из arr2 в arr1.

2⃣Заполнение countMap и remaining:
Пройдитесь по элементам arr1 и если элемент присутствует в countMap, увеличьте его счетчик. Если элемент не присутствует в arr2, добавьте его в remaining.

3⃣Формирование результирующего массива:
Пройдитесь по arr2 и добавьте элементы в result в соответствии с их количеством в countMap.
Отсортируйте массив remaining и добавьте его элементы в result.
Верните result в виде массива.

😎 Решение:

var relativeSortArray = function(arr1, arr2) {
    let countMap = new Map();
    let remaining = [];
    let result = [];

    for (let value of arr2) {
        countMap.set(value, 0);
    }

    for (let value of arr1) {
        if (countMap.has(value)) {
            countMap.set(value, countMap.get(value) + 1);
        } else {
            remaining.push(value);
        }
    }

    remaining.sort((a, b) => a - b);

    for (let value of arr2) {
        let count = countMap.get(value);
        for (let i = 0; i < count; i++) {
            result.push(value);
        }
    }

    return result.concat(remaining);
};

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

Задача: 415. Add Strings
Сложность: easy

Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.

Пример:

Input: num1 = "11", num2 = "123"
Output: "134"

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

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

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

3⃣Верните третье максимальное число, если оно существует, иначе верните первое максимальное число.

😎 Решение:

function thirdMax(nums) {
    let first = null;
    let second = null;
    let third = null;
    
    for (const num of nums) {
        if (num === first || num === second || num === third) {
            continue;
        }
        if (first === null || num > first) {
            third = second;
            second = first;
            first = num;
        } else if (second === null || num > second) {
            third = second;
            second = num;
        } else if (third === null || num > third) {
            third = num;
        }
    }
    
    return third !== null ? third : first;
}

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

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

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

Пример:

Input: s = "aacecaaa"
Output: "aaacecaaa"

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

1️⃣ Создание обратной строки:
Создайте обратную строку rev от исходной строки s, чтобы использовать её для сравнения.

2️⃣ Итерация для поиска наибольшего палиндрома:
Перебирайте индекс i от 0 до size(s) - 1.
Для каждой итерации проверяйте, равна ли подстрока s от начала до n - i подстроке rev от i до конца строки.
Если условие выполняется, это означает, что подстрока s от начала до n - i является палиндромом, так как rev является обратной строкой s.

3️⃣ Возврат результата:
Как только найден наибольший палиндром, возвращайте строку, состоящую из обратной подстроки rev от начала до i + исходная строка s.

😎 Решение:

class Solution {
    shortestPalindrome(s) {
        const n = s.length;
        const rev = s.split('').reverse().join('');
        for (let i = 0; i < n; i++) {
            if (s.substring(0, n - i) === rev.substring(i)) {
                return rev.substring(0, i) + s;
            }
        }
        return "";
    }
}

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

Задача: 1008. Construct Binary Search Tree from Preorder Traversal
Сложность: medium

Дается массив целых чисел preorder, который представляет собой обход BST (т.е, гарантируется, что для заданных тестовых случаев всегда можно найти дерево двоичного поиска с заданными требованиями. Дерево двоичного поиска - это двоичное дерево, в котором для каждого узла любой потомок Node.left имеет значение строго меньше, чем Node.val, а любой потомок Node.right имеет значение строго больше, чем Node.val. При обходе бинарного дерева в предварительном порядке сначала выводится значение узла, затем обход Node.left, затем обход Node.right.

Пример:

Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

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

1⃣Инициализация переменных и функций:
Создайте класс узла дерева TreeNode с атрибутами val, left и right.
Инициализируйте индекс, который будет отслеживать текущую позицию в массиве preorder.

2⃣Рекурсивная функция для построения дерева:
Создайте рекурсивную функцию constructBST с аргументами preorder, lower и upper, которые будут ограничивать значения узлов для текущей ветви дерева.
Если текущий индекс выходит за границы массива preorder, верните null.
Получите текущее значение из preorder и проверьте, находится ли оно в пределах допустимого диапазона [lower, upper]. Если нет, верните null.

3⃣Создание узла и рекурсивное построение поддеревьев:
Создайте новый узел с текущим значением и увеличьте индекс.
Рекурсивно вызовите функцию constructBST для создания левого поддерева с обновленным верхним пределом (upper равным значению текущего узла).
Рекурсивно вызовите функцию constructBST для создания правого поддерева с обновленным нижним пределом (lower равным значению текущего узла).
Верните созданный узел.

😎 Решение:

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

class Solution {
    constructor() {
        this.index = 0;
    }

    bstFromPreorder(preorder) {
        return this.constructBST(preorder, -Infinity, Infinity);
    }

    constructBST(preorder, lower, upper) {
        if (this.index === preorder.length) return null;

        let val = preorder[this.index];
        if (val < lower || val > upper) return null;

        this.index++;
        let root = new TreeNode(val);
        root.left = this.constructBST(preorder, lower, val);
        root.right = this.constructBST(preorder, val, upper);
        return root;
    }
}

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

Задача: 113. Path Sum II
Сложность: medium

Дан корень бинарного дерева и целое число targetSum. Верните все пути от корня до листа, где сумма значений узлов в пути равна targetSum. Каждый путь должен быть возвращён как список значений узлов, а не ссылок на узлы.

Путь от корня до листа — это путь, начинающийся от корня и заканчивающийся на любом листовом узле. Лист — это узел без детей.

Пример:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

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

1️⃣Определение функции recurseTree: Функция принимает текущий узел (node), оставшуюся сумму (remainingSum), которая необходима для продолжения поиска вниз по дереву, и список узлов (pathNodes), который содержит все узлы, встреченные до текущего момента на данной ветке.

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

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

😎 Решение:

var pathSum = function (root, sum) {
    let pathsList = [];
    let pathNodes = [];
    let recurseTree = function (node, remainingSum, pathNodes, pathsList) {
        if (!node) {
            return;
        }
        pathNodes.push(node.val);
        if (
            remainingSum === node.val &&
            node.left === null &&
            node.right === null
        ) {
            pathsList.push(Array.from(pathNodes));
        } else {
            recurseTree(
                node.left,
                remainingSum - node.val,
                pathNodes,
                pathsList,
            );
            recurseTree(
                node.right,
                remainingSum - node.val,
                pathNodes,
                pathsList,
            );
        }
        pathNodes.pop();
    };
    recurseTree(root, sum, pathNodes, pathsList);
    return pathsList;
};

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

Задача: 460. LFU Cache
Сложность: hard

Спроектируйте и реализуйте структуру данных для кеша с наименьшим количеством использования (Least Frequently Used, LFU).
Реализуйте класс LFUCache:
LFUCache(int capacity): Инициализирует объект с указанной вместимостью структуры данных.
int get(int key): Возвращает значение ключа, если ключ существует в кеше. В противном случае возвращает -1.
void put(int key, int value): Обновляет значение ключа, если он уже присутствует, или вставляет ключ, если его еще нет. Когда кеш достигает своей вместимости, он должен аннулировать и удалить ключ, используемый наименее часто, перед вставкой нового элемента. В этой задаче, если имеется несколько ключей с одинаковой частотой использования, аннулируется наименее недавно использованный ключ.
Чтобы определить наименее часто используемый ключ, для каждого ключа в кеше поддерживается счетчик использования. Ключ с наименьшим счетчиком использования является наименее часто используемым ключом.
Когда ключ впервые вставляется в кеш, его счетчик использования устанавливается на 1 (из-за операции put). Счетчик использования для ключа в кеше увеличивается при вызове операции get или put для этого ключа.
Функции get и put должны иметь среднюю временную сложность O(1).

Пример:

Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

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

1⃣insert(int key, int frequency, int value):
Вставить пару частота-значение в cache с заданным ключом.
Получить LinkedHashSet, соответствующий данной частоте (по умолчанию пустой Set), и вставить в него ключ.

2⃣int get(int key):
Если ключа нет в кеше, вернуть -1.
Получить частоту и значение из кеша.
Удалить ключ из LinkedHashSet, связанного с частотой.
Если minf == frequency и LinkedHashSet пуст, увеличить minf на 1 и удалить запись частоты из frequencies.
Вызвать insert(key, frequency + 1, value).
Вернуть значение.

3⃣void put(int key, int value):
Если capacity <= 0, выйти.
Если ключ существует, обновить значение и вызвать get(key).
Если размер кеша равен capacity, удалить первый элемент из LinkedHashSet, связанного с minf, и из кеша.
Установить minf в 1.
Вызвать insert(key, 1, value).

😎 Решение:

class LFUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.minf = 0;
        this.cache = new Map();
        this.frequencies = new Map();
    }

    insert(key, frequency, value) {
        if (!this.frequencies.has(frequency)) {
            this.frequencies.set(frequency, new Set());
        }
        this.frequencies.get(frequency).add(key);
        this.cache.set(key, { frequency, value });
    }

    get(key) {
        if (!this.cache.has(key)) return -1;
        let { frequency, value } = this.cache.get(key);
        this.frequencies.get(frequency).delete(key);
        if (this.frequencies.get(frequency).size === 0) {
            this.frequencies.delete(frequency);
            if (this.minf === frequency) this.minf++;
        }
        this.insert(key, frequency + 1, value);
        return value;
    }

    put(key, value) {
        if (this.capacity <= 0) return;
        if (this.cache.has(key)) {
            this.cache.get(key).value = value;
            this.get(key);
            return;
        }
        if (this.cache.size === this.capacity) {
            let oldest = Array.from(this.frequencies.get(this.minf))[0];
            this.cache.delete(oldest);
            this.frequencies.get(this.minf).delete(oldest);
            if (this.frequencies.get(this.minf).size === 0) this.frequencies.delete(this.minf);
        }
        this.minf = 1;
        this.insert(key, 1, value);
    }
}

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