Задача: 1182. Shortest Distance to Target Color
Сложность: medium

Дан массив colors, содержащий три цвета: 1, 2 и 3.

Также даны несколько запросов. Каждый запрос состоит из двух целых чисел i и c. Верните наименьшее расстояние между заданным индексом i и целевым цветом c. Если решения нет, верните -1.

Пример:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation: 
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).

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

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

2⃣Для каждого запроса, содержащего i и c, если c не является одним из ключей в хэш-таблице, то colors не содержит c, поэтому верните -1. Иначе, найдите позицию i в соответствующем списке индексов indexList для поддержания упорядоченного порядка.

3⃣Если i меньше всех элементов в indexList, то i - indexList[0] является кратчайшим расстоянием. Если i больше всех элементов в indexList, то indexList[indexList.size() - 1] - i является кратчайшим расстоянием. Иначе, ближайшее появление c к i либо на индексе вставки, либо перед ним, поэтому рассчитайте расстояние от i до каждого из них и верните наименьшее.

😎 Решение:

var shortestDistanceColor = function(colors, queries) {
    let queryResults = [];
    let hashmap = new Map();

    for (let i = 0; i < colors.length; i++) {
        if (!hashmap.has(colors[i])) {
            hashmap.set(colors[i], []);
        }
        hashmap.get(colors[i]).push(i);
    }

    for (let [target, color] of queries) {
        if (!hashmap.has(color)) {
            queryResults.push(-1);
            continue;
        }

        let indexList = hashmap.get(color);
        let insert = binarySearch(indexList, target);

        if (insert < 0) {
            insert = -insert - 1;
        }

        if (insert === 0) {
            queryResults.push(indexList[insert] - target);
        } else if (insert === indexList.length) {
            queryResults.push(target - indexList[insert - 1]);
        } else {
            let leftNearest = target - indexList[insert - 1];
            let rightNearest = indexList[insert] - target;
            queryResults.push(Math.min(leftNearest, rightNearest));
        }
    }

    return queryResults;
};

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -left - 1;
}

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

Задача: 1434. Number of Ways to Wear Different Hats to Each Other
Сложность: hard

Дано n человек и 40 видов шляп, пронумерованных от 1 до 40.

Дан двумерный целочисленный массив hats, где hats[i] — список всех шляп, предпочитаемых i-м человеком.

Вернуть количество способов, которыми n человек могут носить различные шляпы друг у друга.

Поскольку ответ может быть слишком большим, вернуть его по модулю 10^9 + 7.

Пример:

Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions. 
First person choose hat 3, Second person choose hat 4 and last one hat 5.

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

1⃣Инициализировать переменные: n - количество людей, done = 2^n - 1, MOD = 10^9 + 7, memo - двумерный массив размером 41 * done, заполненный -1, и hatsToPeople - отображение шляп на людей.

2⃣Заполнить hatsToPeople, сопоставив каждую шляпу людям, которые её предпочитают. Реализовать функцию dp(hat, mask), которая использует мемоизацию для вычисления количества способов распределения шляп.

3⃣Вернуть результат вызова dp(1, 0), который выполняет основное вычисление количества способов распределения шляп.

😎 Решение:

class Solution {
  constructor() {
    this.MOD = 1000000007;
    this.memo = [];
    this.done = 0;
    this.n = 0;
    this.hatsToPeople = new Map();
  }

  numberWays(hats) {
    this.n = hats.length;
    this.hatsToPeople.clear();
    hats.forEach((personHats, i) => {
      personHats.forEach(hat => {
        if (!this.hatsToPeople.has(hat)) {
          this.hatsToPeople.set(hat, []);
        }
        this.hatsToPeople.get(hat).push(i);
      });
    });

    this.done = (1 << this.n) - 1;
    this.memo = Array.from({ length: 41 }, () => Array(this.done).fill(-1));

    return this.dp(1, 0);
  }

  dp(hat, mask) {
    if (mask === this.done) {
      return 1;
    }

    if (hat > 40) {
      return 0;
    }

    if (this.memo[hat][mask] !== -1) {
      return this.memo[hat][mask];
    }

    let ans = this.dp(hat + 1, mask);

    if (this.hatsToPeople.has(hat)) {
      for (const person of this.hatsToPeople.get(hat)) {
        if ((mask & (1 << person)) === 0) {
          ans = (ans + this.dp(hat + 1, mask | (1 << person))) % this.MOD;
        }
      }
    }

    this.memo[hat][mask] = ans;
    return ans;
  }
}

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

Задача: 383. Ransom Note
Сложность: easy

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

Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

1⃣Поскольку строки являются неизменяемым типом, их нельзя изменять, поэтому у них нет операций "вставки" и "удаления".

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

3⃣Повторяйте этот процесс, пока не будут удалены все необходимые символы.

😎 Решение:

function canConstruct(ransomNote, magazine) {
  for (let char of ransomNote) {
    let index = magazine.indexOf(char);
    if (index === -1) {
      return false;
    }
    magazine = magazine.slice(0, index) + magazine.slice(index + 1);
  }
  return true;
}

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

Задача: 279. Perfect Squares
Сложность: medium

Дано целое число n, верните наименьшее количество чисел, являющихся совершенными квадратами, сумма которых равна n.
Совершенный квадрат — это целое число, являющееся квадратом целого числа; другими словами, это произведение некоторого целого числа на самого себя. Например, 1, 4, 9 и 16 являются совершенными квадратами, тогда как 3 и 11 не являются.

Пример:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

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

1⃣Инициализация:
Создайте массив dp размером n + 1 и заполните его значениями Integer.MAX_VALUE, кроме dp[0], которое установите в 0.
Предварительно вычислите все совершенные квадраты, которые меньше или равны n, и сохраните их в массиве square_nums.

2⃣Заполнение массива dp:
Для каждого числа i от 1 до n:
Для каждого совершенного квадрата s из массива square_nums:
Если i меньше текущего совершенного квадрата s, прервите внутренний цикл.
Обновите dp[i], чтобы он содержал минимальное количество чисел, сумма которых равна i.

3⃣Возврат результата:
Верните значение dp[n], которое будет содержать наименьшее количество совершенных квадратов, сумма которых равна n.

😎 Решение:

var numSquares = function(n) {
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    
    const maxSquareIndex = Math.floor(Math.sqrt(n)) + 1;
    const squareNums = new Array(maxSquareIndex).fill(0).map((_, i) => i * i);
    
    for (let i = 1; i <= n; i++) {
        for (let s = 1; s < maxSquareIndex; s++) {
            if (i < squareNums[s]) break;
            dp[i] = Math.min(dp[i], dp[i - squareNums[s]] + 1);
        }
    }
    
    return dp[n];
};

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

Задача: 606. Construct String from Binary Tree
Сложность: medium

Дано корневой узел бинарного дерева, ваша задача — создать строковое представление дерева, следуя определенным правилам форматирования. Представление должно быть основано на прямом обходе бинарного дерева и должно соответствовать следующим требованиям:
Представление узлов: Каждый узел в дереве должен быть представлен его целочисленным значением.
Скобки для дочерних узлов: Если у узла есть хотя бы один дочерний узел (левый или правый), его дочерние узлы должны быть представлены в скобках. Конкретно:
- Если у узла есть левый дочерний узел, значение левого дочернего узла должно быть заключено в скобки сразу после значения узла.
- Если у узла есть правый дочерний узел, значение правого дочернего узла также должно быть заключено в скобки. Скобки для правого дочернего узла должны следовать за скобками для левого дочернего узла.
Пропуск пустых скобок: Любые пустые пары скобок (т.е. ()) должны быть опущены в окончательном строковом представлении дерева, за одним исключением: когда у узла есть правый дочерний узел, но нет левого дочернего узла. В таких случаях вы должны включить пустую пару скобок, чтобы указать на отсутствие левого дочернего узла. Это гарантирует, что однозначное соответствие между строковым представлением и исходной структурой бинарного дерева сохраняется.
В итоге, пустые пары скобок должны быть опущены, когда у узла есть только левый дочерний узел или нет дочерних узлов. Однако, когда у узла есть правый дочерний узел, но нет левого дочернего узла, пустая пара скобок должна предшествовать представлению правого дочернего узла, чтобы точно отразить структуру дерева.

Пример:

Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".

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

1⃣Инициализация и рекурсия
Начинаем с корневого узла бинарного дерева и выполняем прямой обход (preorder traversal) с использованием рекурсии. Для каждого узла добавляем его значение к строке результата.

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

3⃣Объединение результатов
Собираем результаты для каждого узла, учитывая все упомянутые случаи, чтобы получить строковое представление дерева.

😎 Решение:

var tree2str = function(t) {
    const dfs = (t) => {
        if (!t) return "";
        let res = `${t.val}`;
        if (!t.left && !t.right) return res;
        res += `(${dfs(t.left)})`;
        if (t.right) {
            res += `(${dfs(t.right)})`;
        }
        return res;
    }
    return dfs(t);
};

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

Задача: 1110. Delete Nodes And Return Forest
Сложность: medium

Дан корень бинарного дерева, каждый узел в дереве имеет уникальное значение.
После удаления всех узлов со значением из to_delete, остаётся лес (несвязное объединение деревьев).

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

Пример:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

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

1⃣Инициализация:
Преобразуйте массив to_delete в множество toDeleteSet для эффективного поиска.
Создайте пустой список forest для хранения корней деревьев в результирующем лесу.

2⃣Рекурсивный обход:
Выполните обход дерева в порядке пост-ордера, чтобы сначала обработать все дочерние узлы перед текущим узлом (node):
- рекурсивно вызовите processNode для левого и правого дочерних узлов node и обновите левого и правого дочернего узла с возвращаемым значением.

3⃣Оценка узла:
Проверьте, нужно ли удалить текущий узел, проверив, существует ли его значение в toDeleteSet. Если узел нужно удалить:
- если у узла есть левый или правый дочерний узел, добавьте их в forest.
- верните null для его родителя, чтобы эффективно удалить текущий узел, не подключая его обратно к родительскому узлу.
Если узел не нужно удалять, верните сам узел.

😎 Решение:

var delNodes = function(root, to_delete) {
    const toDeleteSet = new Set(to_delete);
    const forest = [];

    const processNode = (node) => {
        if (!node) return null;

        node.left = processNode(node.left);
        node.right = processNode(node.right);

        if (toDeleteSet.has(node.val)) {
            if (node.left) forest.push(node.left);
            if (node.right) forest.push(node.right);
            return null;
        }
        return node;
    };

    root = processNode(root);
    if (root) {
        forest.push(root);
    }

    return forest;
};

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

Задача: 257. Binary Tree Paths
Сложность: easy

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

Пример:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

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

1️⃣Если текущий узел не является null, добавьте его значение к текущему пути.
Если текущий узел является листом (не имеет дочерних узлов), добавьте текущий путь в список путей.
Если текущий узел не является листом, добавьте "->" к текущему пути и рекурсивно вызовите функцию для левого и правого дочерних узлов.

2️⃣Начните с корневого узла, пустого пути и пустого списка путей.

3️⃣Верните список всех путей от корня до листа.

😎 Решение:

class Solution {
    constructPaths(root, path, paths) {
        if (root !== null) {
            path += root.val
            if (root.left === null && root.right === null) {
                paths.push(path)
            } else {
                path += "->"
                this.constructPaths(root.left, path, paths)
                this.constructPaths(root.right, path, paths)
            }
        }
    }

    binaryTreePaths(root) {
        const paths = []
        this.constructPaths(root, "", paths)
        return paths
    }
}

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

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

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