Задача: 764. Largest Plus Sign
Сложность: medium

Вам дано целое число n. У вас есть бинарная сетка размером n x n, в которой все значения изначально равны 1, за исключением некоторых индексов, указанных в массиве mines. Элемент массива mines с индексом i определяется как mines[i] = [xi, yi], где grid[xi][yi] == 0.

Верните порядок самого большого крестообразного знака из 1, выровненного по осям, который содержится в сетке. Если такого знака нет, верните 0.

Крестообразный знак из 1 порядка k имеет некоторый центр grid[r][c] == 1, а также четыре луча длиной k - 1, идущих вверх, вниз, влево и вправо, состоящие из 1. Обратите внимание, что за пределами лучей креста могут быть 0 или 1, проверяется только соответствующая область крестообразного знака на наличие 1.

Пример:

Input: n = 5, mines = [[4,2]]
Output: 2
Explanation: In the above grid, the largest plus sign can only be of order 2. One of them is shown.

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

1⃣Создайте сетку размером n x n, заполненную единицами. Затем используйте массив mines, чтобы установить значения нулей в соответствующих ячейках сетки.

2⃣Для каждой ячейки в сетке создайте четыре дополнительных сетки: left, right, up и down, которые будут хранить длину непрерывных единиц, простирающихся в соответствующем направлении от каждой ячейки.

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

😎 Решение:

class Solution {
    public int orderOfLargestPlusSign(int N, int[][] mines) {
        Set<Integer> banned = new HashSet<>();
        for (int[] mine : mines)
            banned.add(mine[0] * N + mine[1]);
            
        int ans = 0;
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                int k = 0;
                while (k <= r && r < N - k && k <= c && c < N - k &&
                        !banned.contains((r - k) * N + c) &&
                        !banned.contains((r + k) * N + c) &&
                        !banned.contains(r * N + c - k) &&
                        !banned.contains(r * N + c + k)) {
                    k++;
                }
                ans = Math.max(ans, k);
            }
        }
        return ans;
    }
}

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

Задача: 38. Count and Say
сложность: medium

Последовательность "считай и скажи" — это последовательность строк цифр, определяемая с помощью рекурсивной формулы:

countAndSay(1) = "1"
countAndSay(n) — это кодирование длин серий из countAndSay(n - 1).
Кодирование длин серий (RLE) — это метод сжатия строк, который работает путём замены последовательных идентичных символов (повторяющихся 2 или более раз) на конкатенацию символа и числа, обозначающего количество символов (длину серии). Например, чтобы сжать строку "3322251", мы заменяем "33" на "23", "222" на "32", "5" на "15" и "1" на "11". Таким образом, сжатая строка становится "23321511".

Для заданного положительного целого числа n верните n-й элемент последовательности "считай и скажи".

Пример:

Input: n = 4

Output: "1211"

Explanation:

countAndSay(1) = "1"
countAndSay(2) = RLE of "1" = "11"
countAndSay(3) = RLE of "11" = "21"
countAndSay(4) = RLE of "21" = "1211"

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

1⃣Мы хотим использовать шаблон, который соответствует строкам из одинаковых символов, таких как "4", "7777", "2222222".
Если у вас есть опыт работы с регулярными выражениями, вы можете обнаружить, что шаблон (.)\1* работает.

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

3⃣*: этот квалификатор, следующий за ссылкой на группу \1, указывает, что мы хотели бы видеть повторение группы ноль или более раз.
Таким образом, шаблон соответствует строкам, которые состоят из некоторого символа, а затем ноль или более повторений этого символа после его первого появления. Это то, что нам нужно.
Мы находим все совпадения с регулярным выражением, а затем конкатенируем результаты.

😎 Решение:

import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Solution {
    public String countAndSay(int n) {
        String currentString = "1";
        Pattern pattern = Pattern.compile("(.)\\1*");
        for (int i = 1; i < n; ++i) {
            Matcher m = pattern.matcher(currentString);
            StringBuffer nextString = new StringBuffer();
            while (m.find()) {
                nextString.append(
                    m.group().length() + String.valueOf(m.group().charAt(0))
                );
            }
            currentString = nextString.toString();
        }
        return currentString;
    }
}

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

Задача: 1437. Check If All 1's Are at Least Length K Places Away
Сложность: easy

Дан бинарный массив nums и целое число k. Вернуть true, если все единицы находятся на расстоянии не менее k позиций друг от друга, в противном случае вернуть false.

Пример:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

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

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

2⃣Итерировать по массиву nums, проверяя, если текущий элемент равен 1. Если число нулей между единицами меньше k, вернуть false; иначе сбросить счетчик нулей на 0.

3⃣Если текущий элемент равен 0, увеличить счетчик нулей. В конце итерации вернуть true.

😎 Решение:

class Solution {
    public boolean kLengthApart(int[] nums, int k) {
        int count = k;
        for (int num : nums) {
            if (num == 1) {
                if (count < k) {
                    return false;
                }
                count = 0;
            } else {
                count++;
            }
        }
        return true;
    }
}

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

Задача: 486. Predict the Winner
Сложность: medium

Дан целочисленный массив nums. Два игрока играют в игру с этим массивом: игрок 1 и игрок 2.

Игрок 1 и игрок 2 ходят по очереди, начиная с игрока 1. Оба игрока начинают игру с нулевым счетом. В каждый ход игрок берет одно из чисел с любого конца массива (то есть nums[0] или nums[nums.length - 1]), что уменьшает размер массива на 1. Игрок добавляет выбранное число к своему счету. Игра заканчивается, когда в массиве не останется элементов.

Верните true, если игрок 1 может выиграть игру. Если счета обоих игроков равны, игрок 1 все равно считается победителем, и вы также должны вернуть true. Вы можете считать, что оба игрока играют оптимально.

Пример:

Input: nums = [1,5,2]
Output: false
Explanation: Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return 

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

1⃣Определите maxDiff(left, right) как максимальную разницу в счете, которую текущий игрок может достичь. Если left = right, верните nums[left].

2⃣В противном случае текущий игрок может выбрать nums[left] или nums[right]. Максимальная разница в счете, которую он может получить, равна большему из значений nums[left] - maxDiff(left + 1, right) и nums[right] - maxDiff(left, right - 1).

3⃣Верните true, если maxDiff(0, n - 1) >= 0. Этот вызов сделан с точки зрения первого игрока, и первый игрок является победителем, если у игроков одинаковый счет (разница 0).

😎 Решение:

class Solution {
    private int maxDiff(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }

        int scoreByLeft = nums[left] - maxDiff(nums, left + 1, right);
        int scoreByRight = nums[right] - maxDiff(nums, left, right - 1);

        return Math.max(scoreByLeft, scoreByRight);
    }

    public boolean predictTheWinner(int[] nums) {
        int n = nums.length;
        return maxDiff(nums, 0, n - 1) >= 0;
    }
}

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

Задача: 1091. Shortest Path in Binary Matrix
Сложность: medium

Дан бинарный матричный массив grid размером n x n. Верните длину самого короткого чистого пути в матрице. Если чистого пути не существует, верните -1.

Чистый путь в бинарной матрице — это путь из верхнего левого угла (т.е. (0, 0)) в нижний правый угол (т.е. (n - 1, n - 1)), такой что:

Все посещенные клетки пути равны 0.
Все соседние клетки пути соединены по 8 направлениям (т.е. они различны и имеют общую сторону или угол).
Длина чистого пути — это количество посещенных клеток этого пути.

Пример:

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

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

1⃣Проверить, что начальная и конечная клетки открыты (равны 0). Если нет, вернуть -1.

2⃣Выполнить поиск в ширину (BFS) из начальной клетки, добавляя в очередь соседние клетки, если они открыты и еще не посещены. Обновлять длину пути для каждой клетки.

3⃣Если достигнута конечная клетка, вернуть длину пути. Если очередь пуста и конечная клетка не достигнута, вернуть -1.

😎 Решение:

import java.util.*;

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

    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] != 0 || grid[grid.length - 1][grid[0].length - 1] != 0) {
            return -1;
        }

        Queue<int[]> queue = new ArrayDeque<>();
        grid[0][0] = 1;
        queue.add(new int[]{0, 0});

        while (!queue.isEmpty()) {
            int[] cell = queue.remove();
            int row = cell[0], col = cell[1], distance = grid[row][col];
            if (row == grid.length - 1 && col == grid[0].length - 1) {
                return distance;
            }
            for (int[] direction : directions) {
                int newRow = row + direction[0];
                int newCol = col + direction[1];
                if (newRow >= 0 && newCol >= 0 && newRow < grid.length && newCol < grid[0].length && grid[newRow][newCol] == 0) {
                    queue.add(new int[]{newRow, newCol});
                    grid[newRow][newCol] = distance + 1;
                }
            }
        }
        return -1;
    }
}

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

Задача: 784. Letter Case Permutation
Сложность: medium

Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве.

Пример:

Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

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

1⃣Если следующий символ c является буквой, то мы удвоим все слова в нашем текущем ответе, и добавим lowercase(c) к каждому слову в первой половине, и uppercase(c) к каждому слову во второй половине.

2⃣Если c является цифрой, мы добавим его к каждому слову.

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

😎 Решение:

class Solution {
    public List<String> letterCasePermutation(String S) {
        List<List<Character>> ans = new ArrayList<>();
        ans.add(new ArrayList<>());

        for (char c : S.toCharArray()) {
            int n = ans.size();
            if (Character.isLetter(c)) {
                for (int i = 0; i < n; i++) {
                    List<Character> current = new ArrayList<>(ans.get(i));
                    ans.add(current);
                    ans.get(i).add(Character.toLowerCase(c));
                    ans.get(n + i).add(Character.toUpperCase(c));
                }
            } else {
                for (int i = 0; i < n; i++) {
                    ans.get(i).add(c);
                }
            }
        }

        List<String> result = new ArrayList<>();
        for (List<Character> list : ans) {
            StringBuilder sb = new StringBuilder();
            for (char c : list) {
                sb.append(c);
            }
            result.add(sb.toString());
        }
        return result;
    }
}

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

Задача: 233. Number of Digit One
Сложность: hard

Дано целое число n, посчитайте общее количество единиц, встречающихся во всех неотрицательных числах, меньших или равных n.

Пример:

Input: n = 13
Output: 6

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

1⃣Итерация по степеням 10: Итеративно увеличивайте значение i от 1 до n, увеличивая i в 10 раз на каждом шаге. Это позволяет анализировать каждую цифру числа n.

2⃣Подсчет групповых единиц: Для каждой итерации добавляйте (n / (i * 10)) * i к счетчику countr, что представляет собой количество единиц, встречающихся в группах размера i после каждого интервала (i * 10).

3⃣Добавление дополнительных единиц: Для каждой итерации добавляйте min(max((n % (i * 10)) - i + 1, 0), i) к счетчику countr, что представляет собой дополнительные единицы, зависящие от цифры на позиции i.

😎 Решение:

public class Solution {
    public int countDigitOne(int n) {
        int countr = 0;
        for (long i = 1; i <= n; i *= 10) {
            long divider = i * 10;
            countr += (n / divider) * i + Math.min(Math.max(n % divider - i + 1, 0), i);
        }
        return countr;
    }
}

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

Задача: 560. Subarray Sum Equals K
Сложность: medium

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

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

Пример:

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

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

1⃣Самый простой метод - рассмотреть каждый возможный подмассив данного массива nums.

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

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

😎 Решение:

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int start = 0; start < nums.length; start++) {
            for (int end = start + 1; end <= nums.length; end++) {
                int sum = 0;
                for (int i = start; i < end; i++) {
                    sum += nums[i];
                }
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

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

Задача: 1253. Reconstruct a 2-Row Binary Matrix
Сложность: medium

Даны следующие сведения о матрице с n столбцами и 2 строками: Матрица является двоичной, то есть каждый элемент матрицы может быть 0 или 1. Сумма элементов 0-й (верхней) строки задана как upper. Сумма элементов 1-й (нижней) строки задана как lower.
Сумма элементов i-го столбца (индексированного 0) - colsum[i], где colsum - целочисленный массив длины n. Ваша задача - восстановить матрицу с upper, lower и colsum. Вернуть ее в виде двумерного целочисленного массива. Если существует более одного правильного решения, будет принято любое из них. Если правильного решения не существует, верните пустой двумерный массив.

Пример:

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]

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

1⃣Инициализируйте две строки матрицы длины n с нулями.

2⃣Пройдите по массиву colsum и распределите значения 2 по обеим строкам, уменьшая upper и lower.
Пройдите по массиву colsum и распределите значения 1 по строкам, уменьшая соответствующие upper или lower.

3⃣Проверьте, что остатки upper и lower равны нулю.
Если все шаги выполнены успешно, верните восстановленную матрицу, иначе верните пустую матрицу.

😎 Решение:

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

public class Solution {
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        int n = colsum.length;
        int[] top = new int[n];
        int[] bottom = new int[n];
        
        for (int i = 0; i < n; i++) {
            if (colsum[i] == 2) {
                if (upper > 0 && lower > 0) {
                    top[i] = 1;
                    bottom[i] = 1;
                    upper--;
                    lower--;
                } else {
                    return new ArrayList<>();
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (colsum[i] == 1) {
                if (upper > lower) {
                    if (upper > 0) {
                        top[i] = 1;
                        upper--;
                    } else {
                        return new ArrayList<>();
                    }
                } else {
                    if (lower > 0) {
                        bottom[i] = 1;
                        lower--;
                    } else {
                        return new ArrayList<>();
                    }
                }
            }
        }
        
        if (upper == 0 && lower == 0) {
            List<List<Integer>> result = new ArrayList<>();
            List<Integer> topRow = new ArrayList<>();
            List<Integer> bottomRow = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                topRow.add(top[i]);
                bottomRow.add(bottom[i]);
            }
            result.add(topRow);
            result.add(bottomRow);
            return result;
        } else {
            return new ArrayList<>();
        }
    }
}

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

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

Дано целое число num. Повторно складывайте все его цифры, пока результат не станет однозначным, и верните его.

Пример:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

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

1⃣Инициализируйте переменную digital_root значением 0.

2⃣В цикле, пока num больше 0:
Добавьте к digital_root последнюю цифру num.
Уменьшите num, удалив последнюю цифру.
Если num равно 0 и digital_root больше 9, присвойте num значение digital_root и сбросьте digital_root в 0.

3⃣Верните значение digital_root.

😎 Решение:

class Solution {
    public int addDigits(int num) {
        int digital_root = 0;
        while (num > 0) {
            digital_root += num % 10;
            num /= 10;
            if (num == 0 && digital_root > 9) {
                num = digital_root;
                digital_root = 0;
            }
        }
        return digital_root;
    }
}

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

class Solution {

    List<List<Integer>> output = new ArrayList();
    int n, k;

    public void backtrack(int first, ArrayList<Integer> curr, int[] nums) {
        if (curr.size() == k) {
            output.add(new ArrayList(curr));
            return;
        }
        for (int i = first; i < n; ++i) {
            curr.add(nums[i]);
            backtrack(i + 1, curr, nums);
            curr.remove(curr.size() - 1);
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        n = nums.length;
        for (k = 0; k < n + 1; ++k) {
            backtrack(0, new ArrayList<Integer>(), nums);
        }
        return output;
    }
}

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

Задача: 1059. All Paths from Source Lead to Destination
Сложность: medium

Учитывая ребра направленного графа, где edges[i] = [ai, bi] указывает на наличие ребра между вершинами ai и bi, и две вершины source и destination этого графа, определите, все ли пути, начинающиеся из source, заканчиваются в destination, то есть: существует ли хотя бы один путь из source в destination Если существует путь из source в node без исходящих ребер, то этот node равен destination. Количество возможных путей из source в destination - конечное число. Верните true тогда и только тогда, когда все пути из source ведут в destination.

Пример:

Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
Output: false

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

1⃣Построение графа и проверка путей:
Построить граф на основе входных данных.
Использовать поиск в глубину (DFS) для проверки наличия всех путей от вершины source до вершины destination.

2⃣Проверка конечности путей:
Проверить, что из всех вершин, достижимых от source, либо исходят ребра, либо они являются вершиной destination.
Убедиться, что из любой вершины, не являющейся destination, исходят хотя бы одно ребро.

3⃣Рекурсивная проверка конечности путей:
Рекурсивно проверять, что все пути из source заканчиваются в destination, избегая циклов и проверяя конечность всех путей.

😎 Решение:

import java.util.*;

public class Solution {
    public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
        }
        
        int[] visited = new int[n];
        
        return dfs(graph, visited, source, destination);
    }
    
    private boolean dfs(Map<Integer, List<Integer>> graph, int[] visited, int node, int destination) {
        if (visited[node] != 0) {
            return visited[node] == 2;
        }
        if (!graph.containsKey(node)) {
            return node == destination;
        }
        visited[node] = 1;
        for (int neighbor : graph.get(node)) {
            if (!dfs(graph, visited, neighbor, destination)) {
                return false;
            }
        }
        visited[node] = 2;
        return true;
    }
}

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

Задача: 753. Cracking the Safe
Сложность: medium

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public String crackSafe(int n, int k) {
        Set<String> seen = new HashSet<>();
        StringBuilder result = new StringBuilder();

        String startNode = "0".repeat(n - 1);
        dfs(startNode, k, seen, result);

        result.append(startNode);
        return result.toString();
    }

    private void dfs(String node, int k, Set<String> seen, StringBuilder result) {
        for (int x = 0; x < k; x++) {
            String neighbor = node + x;
            if (!seen.contains(neighbor)) {
                seen.add(neighbor);
                dfs(neighbor.substring(1), k, seen, result);
                result.append(x);
            }
        }
    }
}

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

Задача: 1359. Count All Valid Pickup and Delivery Options
Сложность: hard

Дано n заказов, каждый из которых состоит из услуги забора и доставки.

Посчитайте все возможные допустимые последовательности забора/доставки, такие что доставка(i) всегда идет после забора(i).

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

Пример:

Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

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

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

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

3⃣Возвращение результата:
Верните результат для n заказов, применяя модуль 10^9 + 7 для предотвращения переполнения.

😎 Решение:

public class Solution {
    public int countOrders(int n) {
        int MOD = 1_000_000_007;
        long[] dp = new long[n + 1];
        dp[0] = 1;
        
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] * (2 * i - 1) * i % MOD;
        }
        
        return (int) dp[n];
    }
}

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

Задача: 1242. Web Crawler Multithreaded
Сложность: medium

Учитывая URL startUrl и интерфейс HtmlParser, реализуйте многопоточный веб-краулер, который будет просматривать все ссылки, находящиеся под тем же именем хоста, что и startUrl. Верните все URL, полученные вашим веб-краулером, в любом порядке.

Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все URL с веб-страницы данного URL. Не просматривать одну и ту же ссылку дважды. Исследовать только те ссылки, которые находятся под тем же именем хоста, что и startUrl.

Пример:

Input:
urls = [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.google.com",
  "http://news.yahoo.com/us"
]
edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl = "http://news.yahoo.com/news/topics/"
Output: [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.yahoo.com/us"
]

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

1⃣Извлечь имя хоста из startUrl.
Использовать многопоточность для обработки URL-адресов.

2⃣Хранить посещенные URL-адреса, чтобы избежать повторного посещения.

3⃣Использовать HtmlParser для получения URL-адресов с веб-страниц.

😎 Решение:

import java.net.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicBoolean;

class HtmlParser {
    public List<String> getUrls(String url) {
        return new ArrayList<>();
    }
}

public class Solution {
    public List<String> crawl(String startUrl, HtmlParser htmlParser) {
        String hostname = extractHostname(startUrl);
        Set<String> visited = ConcurrentHashMap.newKeySet();
        ExecutorService executor = Executors.newFixedThreadPool(10);
        Queue<Future<?>> futures = new ConcurrentLinkedQueue<>();

        visited.add(startUrl);
        futures.add(executor.submit(() -> visit(startUrl, htmlParser, hostname, visited, futures, executor)));

        while (!futures.isEmpty()) {
            try {
                futures.poll().get();
            } catch (InterruptedException | ExecutionException e) {
                e.printStackTrace();
            }
        }

        executor.shutdown();
        return new ArrayList<>(visited);
    }

    private void visit(String url, HtmlParser htmlParser, String hostname, Set<String> visited, Queue<Future<?>> futures, ExecutorService executor) {
        for (String nextUrl : htmlParser.getUrls(url)) {
            if (extractHostname(nextUrl).equals(hostname) && visited.add(nextUrl)) {
                futures.add(executor.submit(() -> visit(nextUrl, htmlParser, hostname, visited, futures, executor)));
            }
        }
    }

    private String extractHostname(String url) {
        try {
            URL u = new URL(url);
            return u.getHost();
        } catch (MalformedURLException e) {
            e.printStackTrace();
            return "";
        }
    }
}

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

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

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

Верните количество связных компонентов в графе.

Пример:

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

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

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

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

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

😎 Решение:

public class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        boolean[] visited = new boolean[n];
        int count = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, adj, visited);
                count++;
            }
        }

        return count;
    }

    private void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
        Stack<Integer> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            int current = stack.pop();
            if (!visited[current]) {
                visited[current] = true;
                for (int neighbor : adj.get(current)) {
                    if (!visited[neighbor]) stack.push(neighbor);
                }
            }
        }
    }
}

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

public boolean canConstruct(String ransomNote, String magazine) {
    for (char c : ransomNote.toCharArray()) {
        int index = magazine.indexOf(c);
        if (index == -1) {
            return false;
        }
        magazine = magazine.substring(0, index) + magazine.substring(index + 1);
    }
    return true;
}

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

Задача: 1675. Minimize Deviation in Array
Сложность: hard

Вам дан массив nums из n положительных целых чисел.

Вы можете выполнять два типа операций над любым элементом массива любое количество раз:
Если элемент четный, разделите его на 2.
Например, если массив [1,2,3,4], то вы можете выполнить эту операцию на последнем элементе, и массив станет [1,2,3,2].
Если элемент нечетный, умножьте его на 2.
Например, если массив [1,2,3,4], то вы можете выполнить эту операцию на первом элементе, и массив станет [2,2,3,4].
Отклонение массива — это максимальная разница между любыми двумя элементами в массиве.

Верните минимальное отклонение, которое может иметь массив после выполнения некоторого числа операций.

Пример:

Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.

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

1⃣Инициализируйте max-heap под названием evens. Если элемент массива четный, добавьте его в evens; если элемент нечетный, умножьте его на 2 и добавьте в evens. Одновременно отслеживайте минимальный элемент в evens.

2⃣Извлекайте максимальный элемент из evens, обновляйте минимальное отклонение, используя максимальный элемент и текущий минимальный элемент. Если максимальный элемент четный, делите его на 2 и снова добавляйте в evens.

3⃣Повторяйте шаг 2 до тех пор, пока максимальный элемент в evens не станет нечетным. Верните минимальное отклонение.

😎 Решение:

class Solution {
    public int minimumDeviation(int[] nums) {
        PriorityQueue<Integer> evens = new PriorityQueue<>(Collections.reverseOrder());
        int minimum = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num % 2 == 0) {
                evens.offer(num);
                minimum = Math.min(minimum, num);
            } else {
                evens.offer(num * 2);
                minimum = Math.min(minimum, num * 2);
            }
        }
        int minDeviation = Integer.MAX_VALUE;

        while (!evens.isEmpty()) {
            int currentValue = evens.poll();
            minDeviation = Math.min(minDeviation, currentValue - minimum);
            if (currentValue % 2 == 0) {
                evens.offer(currentValue / 2);
                minimum = Math.min(minimum, currentValue / 2);
            } else {
                break;
            }
        }
        return minDeviation;
    }
}

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

Задача: 663. Equal Tree Partition
Сложность: medium

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

Пример:

Input: root = [5,10,10,null,null,2,3]
Output: true

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

1⃣Вычисление общей суммы:
Напишите функцию для вычисления общей суммы всех узлов дерева.

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

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

😎 Решение:

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

class Solution {
    public boolean checkEqualTree(TreeNode root) {
        int totalSum = sumTree(root);
        if (totalSum % 2 != 0) return false;
        int target = totalSum / 2;
        return checkSubtreeSum(root, target, root);
    }

    private int sumTree(TreeNode node) {
        if (node == null) return 0;
        return node.val + sumTree(node.left) + sumTree(node.right);
    }

    private boolean checkSubtreeSum(TreeNode node, int target, TreeNode root) {
        if (node == null) return false;
        if (node != root && sumTree(node) == target) {
            return true;
        }
        return checkSubtreeSum(node.left, target, root) || checkSubtreeSum(node.right, target, root);
    }
}

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> output = new LinkedList();
        Deque<TreeNode> stack = new ArrayDeque();

        if (root == null) return output;

        stack.push(root);
        while (!stack.isEmpty()) {
            root = stack.pop();
            output.addFirst(root.val);
            if (root.left != null) stack.push(root.left);
            if (root.right != null) stack.push(root.right);
        }

        return output;
    }
}

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