Задача: 91. Decode Ways
Сложность: medium

Строка s, содержащая только цифры, закодирована по соответствию: 'A' -> "1", 'B' -> "2", ..., 'Z' -> "26".
Нужно вернуть количество способов декодирования строки, учитывая, что '0' само по себе — невалидно, но может входить в состав двухзначного кода (например, "10").

Пример: Input: s = "12" Output: 2
Пояснение: "12" можно расшифровать как "AB" (1 2) или "L" (12)

Пример:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

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

1⃣Запускаем рекурсивную функцию с позиции 0. Если дошли до конца строки — это один валидный путь (возвращаем 1). Если текущий символ '0', возвращаем 0.

2⃣Проверяем, есть ли сохранённый результат для текущего индекса в memo. Если да — возвращаем его. Иначе вычисляем количество способов: один символ (если валидный) + два символа (если ≤ 26).

3⃣Сохраняем результат для текущего индекса в memo и возвращаем общее количество способов.

😎 Решение:

class Solution {
    Map<Integer, Integer> memo = new HashMap<>();

    public int numDecodings(String s) {
        return recursiveWithMemo(0, s);
    }

    private int recursiveWithMemo(int index, String str) {
        if (memo.containsKey(index)) {
            return memo.get(index);
        }

        if (index == str.length()) {
            return 1;
        }

        if (str.charAt(index) == '0') {
            return 0;
        }

        if (index == str.length() - 1) {
            return 1;
        }

        int ans = recursiveWithMemo(index + 1, str);
        if (Integer.parseInt(str.substring(index, index + 2)) <= 26) {
            ans += recursiveWithMemo(index + 2, str);
        }

        memo.put(index, ans);

        return ans;
    }
}

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

Задача: 408. Valid Word Abbreviation
Сложность: easy

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

Например, строка "замена" может быть сокращена следующим образом (но не ограничивается этим): "s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("замена") "su3i1u2on" ("su bst i t u ti on") "substitution" (без замены подстрок) Следующие сокращения не являются допустимыми:

"s55n" ("s ubsti tutio n", заменяемые подстроки смежные) "s010n" (содержит ведущие нули) "s0ubstitution" (заменяет пустую подстроку) Если задано строковое слово и аббревиатура abbr, верните, соответствует ли строка заданной аббревиатуре.

Подстрока - это непрерывная непустая последовательность символов в строке.

Пример:

Input: word = "internationalization", abbr = "i12iz4n"
Output: true

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

1⃣Инициализируйте два указателя: один для строки word и один для аббревиатуры abbr. Начните сравнение символов строки и аббревиатуры с начала.

2⃣Если символ аббревиатуры - это цифра, вычислите полное число и переместите указатель строки word на это количество символов. Если символ аббревиатуры - это буква, убедитесь, что он совпадает с текущим символом строки.

3⃣Повторяйте шаг 2, пока оба указателя не достигнут конца строки и аббревиатуры соответственно. Если это так, верните true, иначе false.

😎 Решение:

public class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        int i = 0, j = 0;
        while (i < word.length() && j < abbr.length()) {
            if (Character.isDigit(abbr.charAt(j))) {
                if (abbr.charAt(j) == '0') {
                    return false;
                }
                int num = 0;
                while (j < abbr.length() && Character.isDigit(abbr.charAt(j))) {
                    num = num * 10 + abbr.charAt(j) - '0';
                    j++;
                }
                i += num;
            } else {
                if (word.charAt(i) != abbr.charAt(j)) {
                    return false;
                }
                i++;
                j++;
            }
        }
        return i == word.length() && j == abbr.length();
    }
}

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

Задача: 99. Recover Binary Search Tree
Сложность: medium

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

Пример:

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

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

1⃣Создайте симметричный обход дерева. Это должен быть почти отсортированный список, в котором поменяны местами только два элемента.

2⃣Определите два поменянных местами элемента x и y в почти отсортированном массиве за линейное время.

3⃣Повторно пройдите по дереву. Измените значение x на y и значение y на x.

😎 Решение:

class Solution {
    public void inorder(TreeNode root, List<Integer> nums) {
        if (root == null) return;
        inorder(root.left, nums);
        nums.add(root.val);
        inorder(root.right, nums);
    }

    public int[] findTwoSwapped(List<Integer> nums) {
        int n = nums.size();
        int x = -1, y = -1;
        boolean swapped_first_occurrence = false;

        for (int i = 0; i < n - 1; ++i) {
            if (nums.get(i + 1) < nums.get(i)) {
                y = nums.get(i + 1);
                if (!swapped_first_occurrence) {
                    x = nums.get(i);
                    swapped_first_occurrence = true;
                } else {
                    break;
                }
            }
        }
        return new int[] { x, y };
    }

    public void recover(TreeNode r, int count, int x, int y) {
        if (r != null) {
            if (r.val == x || r.val == y) {
                r.val = r.val == x ? y : x;
                if (--count == 0) return;
            }
            recover(r.left, count, x, y);
            recover(r.right, count, x, y);
        }
    }

    public void recoverTree(TreeNode root) {
        List<Integer> nums = new ArrayList();
        inorder(root, nums);
        int[] swapped = findTwoSwapped(nums);
        recover(root, 2, swapped[0], swapped[1]);
    }
}

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

public int smallestCommonElement(int[][] mat) {
    int n = mat.length, m = mat[0].length;
    int pos[] = new int[n], cur_max = 0, cnt = 0;
    while (true) {
        for (int i = 0; i < n; ++i) {
            while (pos[i] < m && mat[i][pos[i]] < cur_max) {
                ++pos[i];
            }
            if (pos[i] >= m) {
                return -1;
            }
            if (mat[i][pos[i]] != cur_max) {
                cnt = 1;
                cur_max = mat[i][pos[i]];
            } else if (++cnt == n) {
                return cur_max;
            }
        }
    }
}

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

Задача: 412. Fizz Buzz
Сложность: easy

Учитывая целое число n, верните строковый массив answer (с индексом 1), где: answer[i] == "FizzBuzz", если i делится на 3 и 5. answer[i] == "Fizz", если i делится на 3. answer[i] == "Buzz", если i делится на 5. answer[i] == i (как строка), если ни одно из перечисленных условий не верно.

Пример:

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

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

1⃣Создайте пустой список для хранения результата.

2⃣Пройдите по всем числам от 1 до n и для каждого числа выполните проверку: Если число делится на 3 и на 5, добавьте "FizzBuzz". Если число делится на 3, добавьте "Fizz". Если число делится на 5, добавьте "Buzz". Если ни одно из условий не выполнено, добавьте само число как строку.

3⃣Верните полученный список.

😎 Решение:

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> answer = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0 && i % 5 == 0) {
                answer.add("FizzBuzz");
            } else if (i % 3 == 0) {
                answer.add("Fizz");
            } else if (i % 5 == 0) {
                answer.add("Buzz");
            } else {
                answer.add(String.valueOf(i));
            }
        }
        return answer;
    }
}

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

Задача: 56. Merge Intervals
Сложность: medium

Дан массив интервалов, где intervals[i] = [starti, endi]. Объедините все перекрывающиеся интервалы и верните массив неперекрывающихся интервалов, которые покрывают все интервалы во входных данных.

Пример:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

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

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

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

3⃣Объединение интервалов внутри компонент:
Наконец, мы рассматриваем каждую связную компоненту, объединяя все её интервалы, создавая новый интервал с началом, равным минимальному началу среди всех интервалов в компоненте, и концом, равным максимальному концу.

Решение:

import java.util.*;

class Solution {
    private Map<int[], List<int[]>> graph;
    private Map<Integer, List<int[]>> nodesInComp;
    private Set<int[]> visited;

    private boolean overlap(int[] a, int[] b) {
        return a[0] <= b[1] && b[0] <= a[1];
    }

    private void buildGraph(int[][] intervals) {
        graph = new HashMap<>();
        for (int[] interval : intervals) {
            graph.put(interval, new LinkedList<>());
        }

        for (int[] interval1 : intervals) {
            for (int[] interval2 : intervals) {
                if (overlap(interval1, interval2)) {
                    graph.get(interval1).add(interval2);
                    graph.get(interval2).add(interval1);
                }
            }
        }
    }

    private int[] mergeNodes(List<int[]> nodes) {
        int minStart = nodes.get(0)[0];
        for (int[] node : nodes) {
            minStart = Math.min(minStart, node[0]);
        }

        int maxEnd = nodes.get(0)[1];
        for (int[] node : nodes) {
            maxEnd = Math.max(maxEnd, node[1]);
        }

        return new int[] { minStart, maxEnd };
    }

    private void markComponentDFS(int[] start, int compNumber) {
        Stack<int[]> stack = new Stack<>();
        stack.add(start);

        while (!stack.isEmpty()) {
            int[] node = stack.pop();
            if (!visited.contains(node)) {
                visited.add(node);

                if (nodesInComp.get(compNumber) == null) {
                    nodesInComp.put(compNumber, new LinkedList<>());
                }
                nodesInComp.get(compNumber).add(node);

                for (int[] child : graph.get(node)) {
                    stack.add(child);
                }
            }
        }
    }

    private void buildComponents(int[][] intervals) {
        nodesInComp = new HashMap<>();
        visited = new HashSet<>();
        int compNumber = 0;

        for (int[] interval : intervals) {
            if (!visited.contains(interval)) {
                markComponentDFS(interval, compNumber);
                compNumber++;
            }
        }
    }

    public int[][] merge(int[][] intervals) {
        buildGraph(intervals);
        buildComponents(intervals);

        List<int[]> merged = new LinkedList<>();
        for (int comp = 0; comp < nodesInComp.size(); comp++) {
            merged.add(mergeNodes(nodesInComp.get(comp)));
        }

        return merged.toArray(new int[merged.size()][]);
    }
}

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

Задача: 1315. Sum of Nodes with Even-Valued Grandparent
Сложность: medium

Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.

A grandparent of a node is the parent of its parent if it exists.

Пример:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

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

1⃣Определите метод solve(), который принимает TreeNode root, значение родителя parent и значение бабушки или дедушки gParent. Этот метод возвращает сумму значений узлов с четным значением бабушки и дедушки в поддереве узла root. Если root равен null, верните 0 как сумму.

2⃣Рекурсивно пройдите по левому и правому дочерним узлам, передавая в качестве значения parent root, а в качестве значения gParent parent. Если значение gParent четное, добавьте значение root к ответу.

3⃣Вызовите рекурсивную функцию solve() с корневым узлом и значениями -1 для parent и gParent. Верните сумму для левого и правого дочерних узлов и значение для текущего узла.

😎 Решение:

class Solution {
    int solve(TreeNode root, int parent, int gParent) {
        if (root == null) {
            return 0;
        }
        return solve(root.left, root.val, parent) + solve(root.right, root.val, parent) + (gParent % 2 != 0 ? 0 : root.val);
    }

    public int sumEvenGrandparent(TreeNode root) {
        return solve(root, -1, -1);
    }
}

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

Задача: 329. Longest Increasing Path in a Matrix
Сложность: hard

Дана матрица целых чисел размером m x n. Верните длину самого длинного возрастающего пути в матрице.

Из каждой ячейки можно перемещаться в четырех направлениях: влево, вправо, вверх или вниз. Перемещение по диагонали или выход за границы матрицы (т.е. замкнутые переходы) не допускается.

Пример:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

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

1⃣Инициализация и создание матрицы:
Инициализируйте размеры матрицы m и n. Создайте матрицу matrix с добавленными границами (нулевыми значениями) вокруг исходной матрицы, чтобы избежать выхода за пределы при обработке.
Рассчитайте количество исходящих связей (outdegrees) для каждой клетки и сохраните их в outdegree.

2⃣Поиск начальных листьев:
Найдите все клетки с нулевыми исходящими связями и добавьте их в список leaves. Эти клетки будут начальной точкой для "слоевого удаления".

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

😎 Решение:

public class Solution {
    private static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private int m, n;
    public int longestIncreasingPath(int[][] grid) {
        int m = grid.length;
        if (m == 0) return 0;
        int n = grid[0].length;
        int[][] matrix = new int[m + 2][n + 2];
        for (int i = 0; i < m; ++i)
            System.arraycopy(grid[i], 0, matrix[i + 1], 1, n);

        int[][] outdegree = new int[m + 2][n + 2];
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                for (int[] d: dir)
                    if (matrix[i][j] < matrix[i + d[0]][j + d[1]])
                        outdegree[i][j]++;

        n += 2;
        m += 2;
        List<int[]> leaves = new ArrayList<>();
        for (int i = 1; i < m - 1; ++i)
            for (int j = 1; j < n - 1; ++j)
                if (outdegree[i][j] == 0) leaves.add(new int[]{i, j});

        int height = 0;
        while (!leaves.isEmpty()) {
            height++;
            List<int[]> newLeaves = new ArrayList<>();
            for (int[] node : leaves) {
                for (int[] d:dir) {
                    int x = node[0] + d[0], y = node[1] + d[1];
                    if (matrix[node[0]][node[1]] > matrix[x][y])
                        if (--outdegree[x][y] == 0)
                            newLeaves.add(new int[]{x, y});
                }
            }
            leaves = newLeaves;
        }
        return height;
    }
}

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

Задача: 477. Total Hamming Distance
Сложность: medium

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

Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums.

Пример:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

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

1⃣Для каждой уникальной пары элементов из массива вычисляем битовое XOR, чтобы найти позиции, где биты различаются. Бит, равный 1 в результате, указывает на различие.

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

3⃣Суммируем все Хэмминговы расстояния для всех пар, чтобы получить общую сумму Хэмминговых расстояний.

😎 Решение:

public class Solution {
    public int totalHammingDistance(int[] nums) {
        int ans = 0;
        
        if (nums.length == 0) {
            return ans;
        }
        
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                ans += Integer.bitCount(nums[i] ^ nums[j]);
            }
        }
        
        return ans;
    }
}

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

Задача: 999. Available Captures for Rook
Сложность: easy

Вам дана матрица 8 x 8, изображающая шахматную доску. На ней есть ровно одна белая ладья, представленная символом "R", некоторое количество белых слонов "B" и некоторое количество черных пешек "p". Пустые клетки обозначаются символом '.'. Ладья может перемещаться на любое количество клеток по горизонтали или вертикали (вверх, вниз, влево, вправо), пока не достигнет другой фигуры или края доски. Ладья атакует пешку, если она может переместиться на ее клетку за один ход. Примечание: Ладья не может перемещаться через другие фигуры, такие как слоны или пешки. Это означает, что ладья не может атаковать пешку, если путь ей преграждает другая фигура. Верните количество пешек, которые атакует белая ладья.

Пример:

Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]

Output: 3

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

1⃣Поиск ладьи:
Найдите координаты белой ладьи "R" на шахматной доске.

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

3⃣Подсчет атакованных пешек:
Если встреченная фигура - черная пешка "p", увеличьте счетчик атакованных пешек.
Если встреченная фигура - белый слон "B" или край доски, остановитесь в этом направлении.

😎 Решение:

public class Solution {
    public int numRookCaptures(char[][] board) {
        int countPawns(int x, int y, int dx, int dy) {
            while (x >= 0 && x < 8 && y >= 0 && y < 8) {
                if (board[x][y] == 'B') break;
                if (board[x][y] == 'p') return 1;
                x += dx;
                y += dy;
            }
            return 0;
        }

        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[i][j] == 'R') {
                    return countPawns(i, j, -1, 0) + countPawns(i, j, 1, 0) +
                           countPawns(i, j, 0, -1) + countPawns(i, j, 0, 1);
                }
            }
        }
        return 0;
    }
}

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

Задача: 314. Binary Tree Vertical Order Traversal
Сложность: medium

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

Если два узла находятся в одной строке и столбце, порядок должен быть слева направо.

Пример:

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

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

1⃣Создайте хэш-таблицу с именем columnTable для отслеживания результатов.

2⃣Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь.

3⃣После завершения BFS обхода получите хэш-таблицу, содержащую значения узлов, сгруппированные по индексам столбцов. Для каждой группы значений отсортируйте их по индексам строк. Отсортируйте хэш-таблицу по ключам (индексам столбцов) в порядке возрастания и верните результаты по столбцам.

😎 Решение:

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> output = new ArrayList<>();
        if (root == null) {
            return output;
        }

        Map<Integer, ArrayList<Integer>> columnTable = new HashMap<>();
        Queue<Pair<TreeNode, Integer>> queue = new ArrayDeque<>();
        int column = 0;
        queue.offer(new Pair<>(root, column));

        while (!queue.isEmpty()) {
            Pair<TreeNode, Integer> p = queue.poll();
            root = p.getKey();
            column = p.getValue();

            if (root != null) {
                if (!columnTable.containsKey(column)) {
                    columnTable.put(column, new ArrayList<Integer>());
                }
                columnTable.get(column).add(root.val);

                queue.offer(new Pair<>(root.left, column - 1));
                queue.offer(new Pair<>(root.right, column + 1));
            }
        }

        List<Integer> sortedKeys = new ArrayList<>(columnTable.keySet());
        Collections.sort(sortedKeys);
        for (int k : sortedKeys) {
            output.add(columnTable.get(k));
        }

        return output;
    }
}

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

Задача: 173. Binary Search Tree Iterator
Сложность: medium

Реализуйте класс BSTIterator, который представляет итератор по обходу бинарного дерева поиска (BST) в порядке in-order:

BSTIterator(TreeNode root): Инициализирует объект класса BSTIterator. Корень BST передается в качестве параметра конструктора. Указатель должен быть инициализирован на несуществующее число, меньшее любого элемента в BST.
boolean hasNext(): Возвращает true, если в обходе справа от указателя существует число, иначе возвращает false.
int next(): Перемещает указатель вправо, затем возвращает число на указателе.
Обратите внимание, что при инициализации указателя на несуществующее наименьшее число, первый вызов next() вернет наименьший элемент в BST.
Можно предположить, что вызовы next() всегда будут допустимы. То есть, при вызове next() в обходе всегда будет хотя бы одно следующее число.

Пример:

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // return 3
bSTIterator.next();    // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 20
bSTIterator.hasNext(); // return False

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

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

2⃣Мы обходим бинарное дерево поиска в порядке in-order и для каждого узла, который обрабатываем, добавляем его в наш массив узлов. Обратите внимание, что перед обработкой узла сначала нужно обработать (или рекурсивно вызвать) его левое поддерево, а после обработки узла — его правое поддерево.

3⃣Когда у нас будут все узлы в массиве, нам просто нужен укзатель или индекс в этом массиве для реализации двух функций next и hasNext. Всякий раз, когда вызывается hasNext, мы просто проверяем, достиг ли индекс конца массива или нет. При вызове функции next мы просто возвращаем элемент, на который указывает индекс. Также, после вызова функции next, мы должны переместить индекс на один шаг вперед, чтобы имитировать прогресс нашего итератора.

😎 Решение:

class BSTIterator {
    ArrayList<Integer> nodesSorted;
    int index;

    public BSTIterator(TreeNode root) {
        this.nodesSorted = new ArrayList<Integer>();
        this.index = -1;
        this._inorder(root);
    }

    private void _inorder(TreeNode root) {
        if (root == null) {
            return;
        }

        this._inorder(root.left);
        this.nodesSorted.add(root.val);
        this._inorder(root.right);
    }

    public int next() {
        return this.nodesSorted.get(++this.index);
    }

    public boolean hasNext() {
        return this.index + 1 < this.nodesSorted.size();
    }
}

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

Задача: 1240. Tiling a Rectangle with the Fewest Squares
Сложность: hard

Если задан прямоугольник размером n x m, верните минимальное количество квадратов с целочисленными сторонами, которые покрывают этот прямоугольник.

Пример:

Input: n = 2, m = 3
Output: 3

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

1⃣Инициализация рекурсивной функции:
Функция принимает размеры прямоугольника n x m.

2⃣Базовый случай:
Если n = 0 или m = 0, возвращаем 0, так как не осталось пространства для покрытия.

3⃣Рекурсивный случай:
Находим наибольший возможный квадрат, который может быть размещен в текущем прямоугольнике. Это квадрат со стороной min(n, m).
Размещаем этот квадрат в левом верхнем углу и рекурсивно покрываем оставшиеся три части:
Прямоугольник слева от квадрата.
Прямоугольник сверху от квадрата.
Прямоугольник справа и снизу от квадрата.

😎 Решение:

public class Solution {
    public int tilingRectangle(int n, int m) {
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }

        for (int i = 1; i <= Math.min(n, m); ++i) {
            dp[i][i] = 1;
        }

        for (int h = 1; h <= n; ++h) {
            for (int w = 1; w <= m; ++w) {
                if (h == w) continue;
                for (int i = 1; i <= h / 2; ++i) {
                    dp[h][w] = Math.min(dp[h][w], dp[i][w] + dp[h - i][w]);
                }
                for (int j = 1; j <= w / 2; ++j) {
                    dp[h][w] = Math.min(dp[h][w], dp[h][j] + dp[h][w - j]);
                }
            }
        }
        return dp[n][m];
    }
}

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

Задача: 286. Walls and Gates
Сложность: medium

Вам дана сетка размером m x n, представляющая комнаты, инициализированные следующими значениями:
-1: Стена или препятствие.
0: Ворота.
INF: Бесконечность, обозначающая пустую комнату. Мы используем значение 2^31 - 1 = 2147483647 для представления INF, так как можно предположить, что расстояние до ворот меньше 2147483647.
Заполните каждую пустую комнату расстоянием до ближайших ворот. Если невозможно добраться до ворот, комната должна быть заполнена значением INF.

Пример:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

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

1⃣Обход всех комнат:
Пройдите через каждую клетку сетки, инициализируя очередь для BFS. Если клетка содержит ворота (0), добавьте её в очередь.

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

3⃣Проверка всех направлений:
Для каждой клетки проверьте все возможные направления (вверх, вниз, влево, вправо) и добавляйте в очередь те, которые являются пустыми комнатами.

😎 Решение:

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    private static final int INF = 2147483647;
    private static final int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public void wallsAndGates(int[][] rooms) {
        int m = rooms.length;
        if (m == 0) return;
        int n = rooms[0].length;
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    queue.add(new int[]{i, j});
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] point = queue.poll();
            int x = point[0], y = point[1];
            for (int[] direction : directions) {
                int nx = x + direction[0];
                int ny = y + direction[1];
                if (nx >= 0 && ny >= 0 && nx < m && ny < n && rooms[nx][ny] == INF) {
                    rooms[nx][ny] = rooms[x][y] + 1;
                    queue.add(new int[]{nx, ny});
                }
            }
        }
    }
}

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

Задача: 847. Shortest Path Visiting All Nodes
Сложность: hard

У вас есть неориентированный связный граф из n узлов, пронумерованных от 0 до n - 1. Вам дан массив graph, где graph[i] — это список всех узлов, соединенных с узлом i ребром.

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

Пример:

Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

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

1⃣Если граф содержит только один узел, верните 0, так как мы можем начать и закончить в этом узле, не делая никаких шагов.

2⃣Инициализируйте необходимые переменные: количество узлов n, маску окончания endingMask, структуру данных seen для предотвращения циклов, очередь для выполнения BFS и счетчик шагов steps.

3⃣Заполните очередь и seen начальными состояниями (начало в каждом узле с маской, указывающей, что посещен только данный узел), затем выполните BFS для поиска кратчайшего пути, который посещает все узлы. Если найден путь, возвращайте количество шагов.

😎 Решение:

class Solution {
    public int shortestPathLength(int[][] graph) {
        if (graph.length == 1) {
            return 0;
        }
        
        int n = graph.length;
        int endingMask = (1 << n) - 1;
        boolean[][] seen = new boolean[n][endingMask];
        ArrayList<int[]> queue = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            queue.add(new int[] {i, 1 << i});
            seen[i][1 << i] = true;
        }
        
        int steps = 0;
        while (!queue.isEmpty()) {
            ArrayList<int[]> nextQueue = new ArrayList<>();
            for (int i = 0; i < queue.size(); i++) {
                int[] currentPair = queue.get(i);
                int node = currentPair[0];
                int mask = currentPair[1];
                for (int neighbor : graph[node]) {
                    int nextMask = mask | (1 << neighbor);
                    if (nextMask == endingMask) {
                        return 1 + steps;
                    }
                    
                    if (!seen[neighbor][nextMask]) {
                        seen[neighbor][nextMask] = true;
                        nextQueue.add(new int[] {neighbor, nextMask});
                    }
                }
            }
            steps++;
            queue = nextQueue;
        }
        
        return -1;
    }
}

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

Задача: 711. Number of Distinct Islands II
Сложность: hard

Вам дана двоичная матричная сетка m x n. Остров - это группа 1 (представляющая сушу), соединенных в четырех направлениях (горизонтальном или вертикальном). Можно предположить, что все четыре края сетки окружены водой. Остров считается одинаковым с другим, если они имеют одинаковую форму, или имеют одинаковую форму после поворота (только на 90, 180 или 270 градусов) или отражения (влево/вправо или вверх/вниз). Верните количество разных островов.

Пример:

Input: grid = [[1,1,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,1,1]]
Output: 1

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

1⃣Пройдите по каждому элементу матрицы, если найдена земля (1), выполните DFS для обнаружения всех связанных с этим островом земель и сохраните форму острова.

2⃣Нормализуйте форму острова, применив все возможные повороты и отражения, чтобы найти каноническую форму.

3⃣Используйте множество для хранения всех уникальных канонических форм и верните размер этого множества.

😎 Решение:

import java.util.*;

public class Solution {
    public int numDistinctIslands2(int[][] grid) {
        Set<String> uniqueIslands = new HashSet<>();
        
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    List<int[]> shape = new ArrayList<>();
                    dfs(grid, i, j, i, j, shape);
                    uniqueIslands.add(normalize(shape));
                }
            }
        }
        
        return uniqueIslands.size();
    }
    
    private void dfs(int[][] grid, int i, int j, int baseI, int baseJ, List<int[]> shape) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
            return;
        }
        grid[i][j] = 0;
        shape.add(new int[] {i - baseI, j - baseJ});
        dfs(grid, i + 1, j, baseI, baseJ, shape);
        dfs(grid, i - 1, j, baseI, baseJ, shape);
        dfs(grid, i, j + 1, baseI, baseJ, shape);
        dfs(grid, i, j - 1, baseI, baseJ, shape);
    }
    
    private String normalize(List<int[]> shape) {
        List<List<int[]>> shapes = new ArrayList<>();
        for (int i = 0; i < 8; i++) {
            shapes.add(new ArrayList<>());
        }
        for (int[] point : shape) {
            int x = point[0], y = point[1];
            shapes.get(0).add(new int[] {x, y});
            shapes.get(1).add(new int[] {x, -y});
            shapes.get(2).add(new int[] {-x, y});
            shapes.get(3).add(new int[] {-x, -y});
            shapes.get(4).add(new int[] {y, x});
            shapes.get(5).add(new int[] {y, -x});
            shapes.get(6).add(new int[] {-y, x});
            shapes.get(7).add(new int[] {-y, -x});
        }
        for (List<int[]> s : shapes) {
            s.sort((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        }
        String[] shapesStr = new String[8];
        for (int i = 0; i < 8; i++) {
            shapesStr[i] = shapes.get(i).toString();
        }
        Arrays.sort(shapesStr);
        return shapesStr[0];
    }
}

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

Задача: 771. Jewels and Stones
Сложность: medium

Вам даны строки jewels, представляющие типы камней, которые являются драгоценностями, и stones, представляющие камни, которые у вас есть. Каждый символ в stones является типом камня, который у вас есть. Вы хотите узнать, сколько из камней, которые у вас есть, также являются драгоценностями.

Буквы чувствительны к регистру, поэтому "a" считается другим типом камня, чем "A".

Пример:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

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

1⃣Создайте множество из строки jewels для быстрой проверки, является ли камень драгоценностью. Это позволит эффективно проверять принадлежность каждого камня к драгоценностям.

2⃣Инициализируйте счетчик для подсчета количества камней, которые являются драгоценностями. Пройдите по каждому символу в строке stones и проверьте, содержится ли этот символ в множестве jewels.

3⃣Если символ содержится в множестве, увеличьте счетчик. В конце верните значение счетчика, которое будет количеством камней, являющихся драгоценностями.

😎 Решение:

class Solution {
    public int numJewelsInStones(String J, String S) {
        int ans = 0;
        for (char s : S.toCharArray())
            for (char j : J.toCharArray())
                if (j == s) {
                    ans++;
                    break;
                }
        return ans;
    }
}

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

Задача: 689. Maximum Sum of 3 Non-Overlapping Subarrays
Сложность: hard

Дан целочисленный массив nums и целое число k. Найдите три непересекающихся подмассива длины k с максимальной суммой и верните их.

Верните результат в виде списка индексов, представляющих начальную позицию каждого интервала (нумерация с 0). Если существует несколько ответов, верните лексикографически наименьший.

Пример:

Input: nums = [1,2,1,2,6,7,5,1], k = 2
Output: [0,3,5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

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

1⃣Предположим, что фиксирован j. Нам нужно узнать на интервалах i∈[0,j−k] и l∈[j+k,len(W)−1], где наибольшее значение W[i] (и соответственно W[l]) встречается первым (то есть, с наименьшим индексом).

2⃣Мы можем решить эту задачу с помощью динамического программирования. Например, если мы знаем, что i - это место, где наибольшее значение W[i] встречается первым на [0,5], то на [0,6] первое появление наибольшего W[i] должно быть либо i, либо 6. Если, скажем, 6 лучше, тогда мы устанавливаем best = 6. В конце left[z] будет первым вхождением наибольшего значения W[i] на интервале i∈[0,z], а right[z] будет таким же, но на интервале i∈[z,len(W)−1].

3⃣Это означает, что для некоторого выбора j, кандидат на ответ должен быть (left[j - k], j, right[j + k]). Мы выбираем кандидата, который дает максимальное значение W[i] + W[j] + W[l].

😎 Решение:

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] W = new int[nums.length - k + 1];
        int currSum = 0;
        for (int i = 0; i < nums.length; i++) {
            currSum += nums[i];
            if (i >= k) {
                currSum -= nums[i - k];
            }
            if (i >= k - 1) {
                W[i - k + 1] = currSum;
            }
        }

        int[] left = new int[W.length];
        int best = 0;
        for (int i = 0; i < W.length; i++) {
            if (W[i] > W[best]) best = i;
            left[i] = best;
        }

        int[] right = new int[W.length];
        best = W.length - 1;
        for (int i = W.length - 1; i >= 0; i--) {
            if (W[i] >= W[best]) {
                best = i;
            }
            right[i] = best;
        }
        
        int[] ans = new int[]{-1, -1, -1};
        for (int j = k; j < W.length - k; j++) {
            int i = left[j - k], l = right[j + k];
            if (ans[0] == -1 || W[i] + W[j] + W[l] > W[ans[0]] + W[ans[1]] + W[ans[2]]) {
                ans[0] = i;
                ans[1] = j;
                ans[2] = l;
            }
        }
        return ans;
    }
}

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

Задача: 774. Minimize Max Distance to Gas Station
Сложность: hard

Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k.

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

Определим penalty() как максимальное расстояние между соседними автозаправочными станциями после добавления k новых станций.

Верните наименьшее возможное значение penalty(). Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты.

Пример:

Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000

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

1⃣Пусть i-й интервал равен deltas[i] = stations[i+1] - stations[i]. Мы хотим найти dp[n+1][k] как рекурсию. Мы можем поставить x автозаправочных станций в интервал n+1 с наилучшим расстоянием deltas[n+1] / (x+1), затем оставшиеся интервалы можно решить с ответом dp[n][k-x]. Ответ — это минимум среди всех x.

2⃣Из этой рекурсии мы можем разработать решение с использованием динамического программирования. Инициализируем двумерный массив dp, где dp[i][j] будет хранить минимальное возможное значение penalty при добавлении j автозаправочных станций на первые i интервалов.

3⃣Заполняем dp таблицу начиная с базового случая, когда нет добавленных станций. Затем для каждого интервала и количества добавленных станций вычисляем минимальное значение penalty, используя вышеописанную рекурсию. Итоговый ответ будет находиться в dp[n][k], где n — количество интервалов, а k — количество добавляемых станций.

😎 Решение:

class Solution {
    public double minmaxGasDist(int[] stations, int K) {
        int N = stations.length;
        double[] deltas = new double[N-1];
        for (int i = 0; i < N-1; ++i)
            deltas[i] = stations[i+1] - stations[i];

        double[][] dp = new double[N-1][K+1];
        for (int i = 0; i <= K; ++i)
            dp[0][i] = deltas[0] / (i+1);

        for (int p = 1; p < N-1; ++p)
            for (int k = 0; k <= K; ++k) {
                double bns = Double.MAX_VALUE;
                for (int x = 0; x <= k; ++x)
                    bns = Math.min(bns, Math.max(deltas[p] / (x+1), dp[p-1][k-x]));
                dp[p][k] = bns;
            }

        return dp[N-2][K];
    }
}

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

Задача: 790. Domino and Tromino Tiling
Сложность: medium

У вас есть два типа плиток: домино размером 2 x 1 и тромино. Вы можете вращать эти фигуры.

Дано целое число n. Верните количество способов выложить плитками доску размером 2 x n. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

При укладке каждая клетка должна быть покрыта плиткой. Две укладки считаются разными, если и только если есть две 4-направленно смежные клетки на доске, такие, что в одной укладке обе клетки заняты плиткой, а в другой - нет.

Пример:

Input: n = 3
Output: 5
Explanation: The five different ways are show above.

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

1⃣Начнем с f(n) и далее спустимся до базовых случаев, f(1), f(2) и p(2). Используйте те же определения для f и p из раздела Обзор. f(k): количество способов полностью покрыть доску шириной k. p(k): количество способов частично покрыть доску шириной k. Рекурсивные вызовы будут использовать результаты подзадач и базовых случаев, чтобы помочь нам получить окончательный результат, f(n).

2⃣Условие остановки для рекурсивных вызовов - когда k достигает базового случая (т.е. k <= 2). Значения для базовых случаев будут возвращены напрямую, вместо того чтобы делать дополнительные рекурсивные вызовы. f(1)=1, f(2)=2, p(2)=1. Чтобы избежать повторных вычислений, мы будем использовать 2 хэшмапы (f_cache и p_cache) для хранения рассчитанных значений для f и p. В Python встроенный декоратор @cache автоматически поддерживает эти хэшмапы для нас.

3⃣Если k больше 2, мы будем делать рекурсивные вызовы к f и p в соответствии с переходной функцией: f(k) = f(k−1) + f(k−2) + 2 * p(k−1), p(k) = p(k−1) + f(k−2). f(n) будет возвращено, как только все рекурсивные вызовы завершатся.

😎 Решение:

import java.util.HashMap;
import java.util.Map;

class Solution {
    private static final int MOD = 1_000_000_007;
    private Map<Integer, Integer> fCache = new HashMap<>();
    private Map<Integer, Integer> pCache = new HashMap<>();

    private int p(int n) {
        if (pCache.containsKey(n)) {
            return pCache.get(n);
        }
        if (n == 2) {
            return 1;
        }
        int result = (p(n - 1) + f(n - 2)) % MOD;
        pCache.put(n, result);
        return result;
    }

    private int f(int n) {
        if (fCache.containsKey(n)) {
            return fCache.get(n);
        }
        if (n <= 2) {
            return n;
        }
        int result = (f(n - 1) + f(n - 2) + 2 * p(n - 1)) % MOD;
        fCache.put(n, result);
        return result;
    }

    public int numTilings(int n) {
        return f(n);
    }
}

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