Задача: №17. Letter Combinations of a Phone Number
Сложность: medium

Дана строка digits, содержащая цифры от 2 до 9.
Нужно вернуть все возможные комбинации букв, которые может представлять эта строка по стандартной телефонной клавиатуре.

Пример:

Input: digits = "23"  
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

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

1️⃣ Инициализируем массив ans с пустой строкой [''] и таблицу соответствия цифр буквам d[], где d[0] — это буквы для цифры 2 и т.д.

2️⃣ Для каждой цифры в строке digits, берём соответствующую строку символов s из таблицы d.

3️⃣ Для каждого уже полученного префикса a и каждой буквы b из s формируем новую комбинацию a + b и сохраняем в новом массиве. После полной итерации обновляем ans.

😎 Решение:

var letterCombinations = function (digits) {
    if (digits.length === 0) {
        return [];
    }

    const ans = [''];
    const d = ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];

    for (const i of digits) {
        const s = d[parseInt(i) - 2];
        const t = [];

        for (const a of ans) {
            for (const b of s) {
                t.push(a + b);
            }
        }

        ans.splice(0, ans.length, ...t);
    }

    return ans;
};

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

Задача: 956. Tallest Billboard
Сложность: hard

Вы устанавливаете рекламный щит и хотите, чтобы он имел наибольшую высоту. У рекламного щита будет две стальные опоры, по одной с каждой стороны. Каждая стальная опора должна быть одинаковой высоты. Вам дается набор стержней, которые можно сварить вместе. Например, если у вас есть стержни длиной 1, 2 и 3, вы можете сварить их вместе, чтобы получилась опора длиной 6. Верните наибольшую возможную высоту вашей рекламной установки. Если вы не можете установить рекламный щит, верните 0.

Пример:

Input: rods = [1,2,3,6]
Output: 6

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

1⃣Определить количество строк n и длину каждой строки m.
Создать массив delete_count длиной m, который будет отслеживать количество удаляемых столбцов.

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

3⃣Повторять процесс до тех пор, пока массив строк не станет лексикографически отсортированным.
Вернуть количество удаленных столбцов.

😎 Решение:

var minDeletionSize = function(strs) {
    const n = strs.length;
    const m = strs[0].length;
    const deleteCount = new Array(m).fill(false);
    
    const isSorted = () => {
        for (let i = 0; i < n - 1; i++) {
            for (let j = 0; j < m; j++) {
                if (deleteCount[j]) continue;
                if (strs[i][j] > strs[i + 1][j]) return false;
                if (strs[i][j] < strs[i + 1][j]) break;
            }
        }
        return true;
    };
    
    while (!isSorted()) {
        for (let j = 0; j < m; j++) {
            if (deleteCount[j]) continue;
            for (let i = 0; i < n - 1; i++) {
                if (strs[i][j] > strs[i + 1][j]) {
                    deleteCount[j] = true;
                    break;
                }
            }
            if (deleteCount[j]) break;
        }
    }
    
    return deleteCount.filter(Boolean).length;
};

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

Задача: 751. IP to CIDR
Сложность: medium

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

Пример:

Input: ip = "255.0.0.7", n = 10
Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]

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

1⃣Преобразовать начальный IP-адрес в целое число.

2⃣Пока количество оставшихся IP-адресов n больше нуля: Определить наибольший блок, который начинается с текущего IP-адреса и не превышает количество оставшихся IP-адресов. Добавить этот блок к результату. Увеличить текущий IP-адрес на размер блока. Уменьшить количество оставшихся IP-адресов n.

3⃣Преобразовать блоки обратно в формат CIDR и вернуть их.

😎 Решение:

function ipToInt(ip) {
    const parts = ip.split('.').map(Number);
    return (parts[0] << 24) + (parts[1] << 16) + (parts[2] << 8) + parts[3];
}

function intToIp(num) {
    return `${(num >> 24) & 255}.${(num >> 16) & 255}.${(num >> 8) & 255}.${num & 255}`;
}

function cidr(ip, prefixLength) {
    return `${ip}/${prefixLength}`;
}

function findCidrBlocks(startIp, n) {
    let start = ipToInt(startIp);
    const result = [];
    
    while (n > 0) {
        let maxSize = 1;
        while (maxSize <= start && maxSize <= n) {
            maxSize <<= 1;
        }
        maxSize >>= 1;
        
        while (start % maxSize !== 0) {
            maxSize >>= 1;
        }
        
        result.push(cidr(intToIp(start), 32 - Math.log2(maxSize) | 0 + 1));
        start += maxSize;
        n -= maxSize;
    }
    
    return result;
}

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

Задача: 153. Find Minimum in Rotated Sorted Array
Сложность: medium

Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,2,4,5,6,7] может стать:
[4,5,6,7,0,1,2], если он был повернут 4 раза.
[0,1,2,4,5,6,7], если он был повернут 7 раз.
Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Для данного отсортированного и повернутого массива nums с уникальными элементами верните минимальный элемент этого массива.
Вы должны написать алгоритм, который работает за время O(log n).

Пример:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

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

1️⃣Нахождение середины массива:
Определите элемент, находящийся посередине массива.

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

3️⃣Остановка поиска при нахождении точки перегиба:
Поиск прекращается, когда найдена точка перегиба, когда выполняется одно из двух условий:
nums[mid] > nums[mid + 1] – следовательно, mid+1 является наименьшим элементом.
nums[mid - 1] > nums[mid] – следовательно, mid является наименьшим элементом.


😎 Решение:

var findMin = function (nums) {
    if (nums.length == 1) {
        return nums[0];
    }
    if (nums[right] > nums[0]) {
        return nums[0];
    }
    while (right >= left) {
        let mid = left + Math.floor((right - left) / 2);
        if (nums[mid] > nums[mid + 1]) {
            return nums[mid + 1];
        }
        if (nums[mid - 1] > nums[mid]) {
            return nums[mid];
        }
        if (nums[mid] > nums[0]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return Number.MAX_VALUE;
};

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

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

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