Задача: 1028. Recover a Tree From Preorder Traversal
Сложность: hard

Мы запускаем предварительный поиск в глубину (DFS) на корне двоичного дерева. На каждый узел в этом обходе мы выводим D тире (где D - глубина этого узла), а затем выводим значение этого узла.Если глубина узла равна D, то глубина его ближайшего потомка равна D + 1.Глубина корневого узла равна 0. Если у узла есть только один ребенок, то этот ребенок гарантированно является левым ребенком. Учитывая выходной обход этого обхода, восстановите дерево и верните его корень.

Пример:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

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

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

2⃣Создание узлов:
Создайте новые узлы на основе уровня и значения из строки. Для каждого нового узла найдите его родительский узел из стека и добавьте узел как левого или правого ребенка.

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

😎 Решение:

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

public class Solution {
    public TreeNode recoverFromPreorder(String S) {
        Stack<TreeNode> stack = new Stack<>();
        for (int i = 0; i < S.length();) {
            int level = 0;
            while (i < S.length() && S.charAt(i) == '-') {
                level++;
                i++;
            }
            
            int value = 0;
            while (i < S.length() && Character.isDigit(S.charAt(i))) {
                value = value * 10 + (S.charAt(i) - '0');
                i++;
            }
            
            TreeNode node = new TreeNode(value);
            if (level == stack.size()) {
                if (!stack.isEmpty()) {
                    stack.peek().left = node;
                }
            } else {
                while (level != stack.size()) {
                    stack.pop();
                }
                stack.peek().right = node;
            }
            stack.push(node);
        }
        
        while (stack.size() > 1) {
            stack.pop();
        }
        
        return stack.peek();
    }
}

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

Задача: 815. Bus Routes
Сложность: hard

Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно.

Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно.
Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах.

Верните наименьшее количество автобусов, которые вам нужно взять, чтобы доехать от source до target. Верните -1, если это невозможно.

Пример:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

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

1⃣Верните 0, если source и target совпадают. Инициализируйте пустую карту adjList, чтобы хранить ребра, где ключ - это автобусная остановка, а значение - список целых чисел, обозначающих индексы маршрутов, которые имеют эту остановку. Инициализируйте пустую очередь q и неупорядоченное множество vis, чтобы отслеживать посещенные маршруты. Вставьте начальные маршруты в очередь q и отметьте их посещенными в vis.

2⃣Итерация по очереди, пока она не пуста: извлеките маршрут из очереди, итерируйтесь по остановкам в маршруте. Если остановка равна target, верните busCount. В противном случае, итерируйтесь по маршрутам для этой остановки в карте adjList, добавьте непосещенные маршруты в очередь и отметьте их посещенными.

3⃣Верните -1 после завершения обхода в ширину (BFS).

😎 Решение:

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) return 0;

        Map<Integer, List<Integer>> adjList = new HashMap<>();
        for (int route = 0; route < routes.length; route++) {
            for (int stop : routes[route]) {
                adjList.computeIfAbsent(stop, k -> new ArrayList<>()).add(route);
            }
        }

        Queue<Integer> q = new LinkedList<>();
        Set<Integer> vis = new HashSet<>();
        for (int route : adjList.getOrDefault(source, Collections.emptyList())) {
            q.add(route);
            vis.add(route);
        }

        int busCount = 1;
        while (!q.isEmpty()) {
            int size = q.size();

            for (int i = 0; i < size; i++) {
                int route = q.poll();

                for (int stop : routes[route]) {
                    if (stop == target) {
                        return busCount;
                    }

                    for (int nextRoute : adjList.getOrDefault(stop, Collections.emptyList())) {
                        if (!vis.contains(nextRoute)) {
                            vis.add(nextRoute);
                            q.add(nextRoute);
                        }
                    }
                }
            }
            busCount++;
        }
        return -1;
    }

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

Задача: 540. Single Element in a Sorted Array
Сложность: medium

Дан отсортированный массив, состоящий только из целых чисел, где каждый элемент встречается ровно дважды, кроме одного элемента, который встречается ровно один раз.

Верните единственный элемент, который встречается только один раз.

Ваше решение должно работать за время O(log n) и использовать O(1) памяти.

Пример:

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

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

1⃣Начиная с первого элемента, итерируемся через каждый второй элемент, проверяя, является ли следующий элемент таким же, как текущий. Если нет, то текущий элемент — это искомый элемент.

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

3⃣Возвращаем найденный элемент.

😎 Решение:

class Solution {
    public int singleNonDuplicate(int[] nums) {
        for (int i = 0; i < nums.length - 1; i += 2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[nums.length - 1];
    }
}

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

Задача: 1356. Sort Integers by The Number of 1 Bits
Сложность: easy

Дан целочисленный массив arr. Отсортируйте целые числа в массиве по возрастанию числа единиц в их двоичном представлении, а в случае, если у двух или более чисел одинаковое количество единиц, отсортируйте их по возрастанию.

Верните массив после сортировки.

Пример:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

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

1⃣Создание функции для подсчета единиц:
Создайте функцию, которая принимает целое число и возвращает количество единиц в его двоичном представлении.

2⃣Сортировка массива:
Используйте встроенную функцию сортировки, передавая ей пользовательскую функцию сравнения, которая использует количество единиц в двоичном представлении чисел для сортировки. Если количество единиц одинаковое, используйте само число для сортировки.

3⃣Возврат отсортированного массива:
Верните отсортированный массив.

😎 Решение:

import java.util.Arrays;

public class Solution {
    public int[] sortByBits(int[] arr) {
        return Arrays.stream(arr)
            .boxed()
            .sorted((a, b) -> {
                int countA = Integer.bitCount(a);
                int countB = Integer.bitCount(b);
                return countA == countB ? a - b : countA - countB;
            })
            .mapToInt(i -> i)
            .toArray();
    }
}

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

Задача: 895. Maximum Frequency Stack
Сложность: hard

Разработайте структуру данных, похожую на стек, чтобы заталкивать элементы в стек и вытаскивать из него самый частый элемент. Реализуйте класс FreqStack: FreqStack() строит пустой стек частот. void push(int val) заталкивает целое число val на вершину стека. int pop() удаляет и возвращает самый частый элемент в стеке. Если есть равенство в выборе самого частого элемента, то удаляется и возвращается элемент, который ближе всего к вершине стека.

Пример:

Input
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
Output
[null, null, null, null, null, null, null, 5, 7, 5, 4]

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

1⃣Создать два словаря: freq для хранения частоты каждого элемента и group для хранения стека элементов для каждой частоты.

2⃣При добавлении элемента увеличивать его частоту в freq и добавлять его в стек соответствующей частоты в group.

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

😎 Решение:

import java.util.*;

class FreqStack {
    private Map<Integer, Integer> freq;
    private Map<Integer, Stack<Integer>> group;
    private int maxfreq;

    public FreqStack() {
        freq = new HashMap<>();
        group = new HashMap<>();
        maxfreq = 0;
    }

    public void push(int val) {
        int f = freq.getOrDefault(val, 0) + 1;
        freq.put(val, f);
        if (f > maxfreq) {
            maxfreq = f;
            group.put(f, new Stack<>());
        }
        group.get(f).push(val);
    }

    public int pop() {
        int val = group.get(maxfreq).pop();
        freq.put(val, freq.get(val) - 1);
        if (group.get(maxfreq).isEmpty()) {
            maxfreq--;
        }
        return val;
    }
}

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

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

Дан пустой двумерный бинарный массив grid размером m x n. Этот массив представляет собой карту, где 0 означает воду, а 1 — сушу. Изначально все ячейки массива — водные (т.е. все ячейки содержат 0).
Вы можете выполнить операцию "добавить землю", которая превращает воду в указанной позиции в сушу. Вам дан массив positions, где positions[i] = [ri, ci] — позиция (ri, ci), в которой следует выполнить i-ю операцию.
Верните массив целых чисел answer, где answer[i] — количество островов после превращения ячейки (ri, ci) в сушу.
Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Вы можете считать, что все четыре края сетки окружены водой.

Пример:

Input: m = 1, n = 1, positions = [[0,0]]
Output: [1]

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

1⃣Инициализация:
Создайте массивы x[] = { -1, 1, 0, 0 } и y[] = { 0, 0, -1, 1 }, которые будут использоваться для нахождения соседей ячейки.
Создайте экземпляр UnionFind, например, dsu(m * n). Инициализируйте всех родителей значением -1. Используйте объединение по рангу, инициализируйте все ранги значением 0. Наконец, инициализируйте count = 0.
Создайте список целых чисел answer, где answer[i] будет хранить количество островов, образованных после превращения ячейки positions[i] в сушу.

2⃣Обработка позиций:
Итерация по массиву positions. Для каждой позиции в positions:
Выполните линейное отображение, чтобы преобразовать двумерную позицию ячейки в landPosition = position[0] * n + position[1].
Используйте операцию addLand(landPosition), чтобы добавить landPosition как узел в граф. Эта функция также увеличит count.
Итерация по каждому соседу позиции. Соседа можно определить с помощью neighborX = position[0] + x[i] и neighborY = position[1] + y[i], где neighborX — координата X, а neighborY — координата Y соседней ячейки. Выполните линейное отображение соседней ячейки с помощью neighborPosition = neighborX * n + neighborY. Теперь, если на neighborPosition есть суша, т.е. isLand(neighborPosition) возвращает true, выполните объединение neighborPosition и landPosition. В объединении уменьшите count на 1.

3⃣Определение количества островов:
Выполните операцию numberOfIslands, которая возвращает количество островов, образованных после превращения позиции в сушу. Добавьте это значение в answer.
Верните answer.

😎 Решение

class UnionFind {
    private int[] parent, rank;
    private int count;
    public UnionFind(int size) { parent = new int[size]; rank = new int[size]; Arrays.fill(parent, -1); count = 0; }
    public void addLand(int x) { if (parent[x] >= 0) return; parent[x] = x; count++; }
    public boolean isLand(int x) { return parent[x] >= 0; }
    public int numberOfIslands() { return count; }
    public int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; }
    public void unionSet(int x, int y) { int xset = find(x), yset = find(y); if (xset == yset) return;
        if (rank[xset] < rank[yset]) parent[xset] = yset; else { parent[yset] = xset; if (rank[xset] == rank[yset]) rank[xset]++; } count--; }
}

class Solution {
    public List<Integer> numIslands2(int m, int n, List<int[]> positions) {
        UnionFind dsu = new UnionFind(m * n);
        int[] x = {-1, 1, 0, 0}, y = {0, 0, -1, 1};
        List<Integer> answer = new ArrayList<>();
        for (int[] pos : positions) {
            int land = pos[0] * n + pos[1];
            dsu.addLand(land);
            for (int i = 0; i < 4; i++) {
                int nx = pos[0] + x[i], ny = pos[1] + y[i], neighbor = nx * n + ny;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && dsu.isLand(neighbor)) { dsu.unionSet(land, neighbor); }
            }
            answer.add(dsu.numberOfIslands());
        }
        return answer;
    }
}

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

Задача: 179. Largest Number
Сложность: medium

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

Поскольку результат может быть очень большим, вам необходимо вернуть строку вместо целого числа.

Пример:

Input: nums = [10,2]
Output: "210"

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

1⃣Преобразование и сортировка: Преобразовать каждое число в строку и отсортировать массив строк с использованием специального компаратора, который для двух строк 𝑎 и b сравнивает результаты конкатенации 𝑎+𝑏 и 𝑏+𝑎.

2⃣Проверка на нули: Если после сортировки первый элемент массива равен "0", вернуть "0", так как все числа в массиве нули.

3⃣Формирование результата: Конкатенировать отсортированные строки для формирования наибольшего числа и вернуть это число в виде строки.

😎 Решение:

class Solution {
    private class LargerNumberComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            String order1 = a + b;
            String order2 = b + a;
            return order2.compareTo(order1);
        }
    }

    public String largestNumber(int[] nums) {
        String[] asStrs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            asStrs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(asStrs, new LargerNumberComparator());
        if (asStrs[0].equals("0")) {
            return "0";
        }
        String largestNumberStr = new String();
        for (String numAsStr : asStrs) {
            largestNumberStr += numAsStr;
        }

        return largestNumberStr;
    }
}

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

Задача: 1426. Counting Elements
Сложность: easy

Дан целочисленный массив arr, посчитайте, сколько элементов x в нем есть таких, что x + 1 также находится в arr. Если в arr есть дубликаты, считайте их отдельно.

Пример:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

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

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

2⃣Итерируйте по каждому элементу массива и используйте вспомогательную функцию для проверки, содержится ли элемент x + 1 в массиве.

3⃣Увеличьте счетчик, если x + 1 найден, и верните значение счетчика.

😎 Решение:

class Solution {
    public int countElements(int[] arr) {
        int count = 0;
        for (int x : arr) {
            if (integerInArray(arr, x + 1)) {
                count++;
            }
        }
        return count;
    }

    public boolean integerInArray(int[] arr, int target) {
        for (int x : arr) {
            if (x == target) {
                return true;
            }
        }
        return false;
    }
}

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

Задача: 940. Distinct Subsequences II
Сложность: hard

Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (Например, "ace" является подпоследовательностью "abcde", а "aec" - нет.

Пример:

Input: s = "abc"
Output: 7

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

1⃣Определить матрицу DP, где dp[i][j] будет хранить количество подпоследовательностей строки s с длиной i, оканчивающихся символом j.

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

3⃣Вернуть сумму всех значений в DP по модулю 10^9 + 7.

😎 Решение:

class Solution {
    private static final int MOD = 1000000007;
    
    public int countSubsequences(String s) {
        int[] dp = new int[26];
        for (char c : s.toCharArray()) {
            int index = c - 'a';
            dp[index] = (int)(((long)sum(dp) + 1) % MOD);
        }
        return sum(dp);
    }
    
    private int sum(int[] dp) {
        int result = 0;
        for (int val : dp) {
            result = (result + val) % MOD;
        }
        return result;
    }
}

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

Задача: 1036. Escape a Large Maze
Сложность: hard

Имеется сетка размером 1 миллион на 1 миллион на плоскости XY, координаты каждого квадрата сетки - (x, y). Мы начинаем с исходного квадрата = [sx, sy] и хотим достичь цели = [tx, ty]. Существует также массив заблокированных квадратов, где каждый заблокированный[i] = [xi, yi] представляет собой заблокированный квадрат с координатами (xi, yi). Каждый ход мы можем пройти один квадрат на север, восток, юг или запад, если квадрат не находится в массиве заблокированных квадратов. Нам также не разрешается выходить за пределы сетки. Возвращается true тогда и только тогда, когда можно достичь целевого квадрата из исходного квадрата с помощью последовательности правильных ходов.

Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

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

1⃣Обработка входных данных:
Загрузите координаты исходного квадрата sx, sy, целевого квадрата tx, ty и список заблокированных квадратов blocked.

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

3⃣Поиск пути с использованием BFS или DFS:
Используйте алгоритм поиска в ширину (BFS) или поиска в глубину (DFS) для поиска пути от sx, sy до tx, ty, избегая заблокированных клеток.
Если обнаружен путь, верните true, в противном случае верните false.

😎 Решение:

import java.util.*;

public class Solution {
    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        Set<Pair<Integer, Integer>> blockedSet = new HashSet<>();
        for (int[] b : blocked) {
            blockedSet.add(new Pair<>(b[0], b[1]));
        }
        Pair<Integer, Integer> src = new Pair<>(source[0], source[1]);
        Pair<Integer, Integer> tgt = new Pair<>(target[0], target[1]);

        if (blockedSet.contains(src) || blockedSet.contains(tgt)) return false;

        List<int[]> directions = Arrays.asList(
                new int[]{0, 1}, new int[]{1, 0},
                new int[]{0, -1}, new int[]{-1, 0});
        int maxArea = blocked.length * (blocked.length - 1) / 2;

        boolean bfs(Pair<Integer, Integer> start, Pair<Integer, Integer> end) {
            Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
            queue.add(start);
            Set<Pair<Integer, Integer>> visited = new HashSet<>();
            visited.add(start);

            while (!queue.isEmpty()) {
                if (visited.size() > maxArea) return true;
                Pair<Integer, Integer> current = queue.poll();
                for (int[] dir : directions) {
                    int nx = current.getKey() + dir[0];
                    int ny = current.getValue() + dir[1];
                    Pair<Integer, Integer> next = new Pair<>(nx, ny);
                    if (nx >= 0 && nx < 1_000_000 && ny >= 0 && ny < 1_000_000 && !visited.contains(next) && !blockedSet.contains(next)) {
                        if (next.equals(end)) return true;
                        queue.add(next);
                        visited.add(next);
                    }
                }
            }
            return false;
        }

        return bfs(src, tgt) && bfs(tgt, src);
    }
}

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

Задача: 1436. Destination City
Сложность: easy

Дан массив paths, где paths[i] = [cityAi, cityBi] означает, что существует прямой путь из cityAi в cityBi. Вернуть конечный город, то есть город, из которого нет пути в другой город.

Гарантируется, что граф путей образует линию без циклов, поэтому будет ровно один конечный город.

Пример:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo" 
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

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

1⃣Для каждого города cityBi в paths проверьте, является ли он кандидатом на конечный город.

2⃣Для каждого кандидата проверьте, нет ли пути, ведущего из него (cityAi == candidate).

3⃣Верните город, который не имеет исходящих путей.

😎 Решение:

class Solution {
    fun destCity(paths: List<List<String>>): String {
        for (path in paths) {
            val candidate = path[1]
            var good = true
            for (p in paths) {
                if (p[0] == candidate) {
                    good = false
                    break
                }
            }
            if (good) {
                return candidate
            }
        }
        return ""
    }
}

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

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

Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,4,4,5,6,7] может стать:

[4,5,6,7,0,1,4], если он был повернут 4 раза.
[0,1,4,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, который может содержать дубликаты, верните минимальный элемент этого массива.

Необходимо максимально уменьшить количество операций.

Пример:

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

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

1⃣Сравнение с правой границей:
В классическом бинарном поиске мы бы сравнивали элемент в середине (nums[mid]) с искомым значением. В нашем случае мы сравниваем его с элементом, на который указывает правый указатель (nums[high]).

2⃣Обновление указателей:
Если элемент в середине находится в той же половине массива, что и элемент на правой границе (nums[mid] > nums[high]), минимальный элемент должен находиться в левой половине от mid. Следовательно, сдвигаем правый указатель на позицию mid.
Если nums[mid] < nums[high], это указывает, что минимальный элемент находится в правой половине или равен mid. Сдвигаем правый указатель на mid.
Если nums[mid] == nums[high], мы не можем быть уверены, в какой половине находится минимальный элемент из-за наличия дубликатов. В этом случае безопасно сдвинуть правый указатель на один шаг влево (high = high - 1), чтобы сузить область поиска без пропуска возможного минимального элемента.

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

😎 Решение:

class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;

        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) high = pivot;
            else if (nums[pivot] > nums[high]) low = pivot + 1;
            else high -= 1;
        }
        return nums[low];
    }
}

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

Задача: 556. Next Greater Element III
Сложность: medium

Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм:

Дано положительное целое число n. Найдите наименьшее целое число, которое имеет точно такие же цифры, как и число n, и больше самого числа n по значению. Если такого положительного целого числа не существует, верните -1.

Учтите, что возвращенное число должно помещаться в 32-битное целое число. Если существует допустимый ответ, но он не помещается в 32-битное целое число, верните -1.

Пример:

Input: n = 12
Output: 21

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

1⃣Нахождение и перестановка цифр
Преобразуйте число n в массив цифр. Найдите первую цифру, которая нарушает убывающий порядок (с конца массива). Назовем её индексом i. Найдите первую цифру, которая больше digits[i-1] (с конца массива). Назовем её индексом j. Поменяйте местами цифры на позициях i-1 и j.

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

3⃣Проверка результата и преобразование обратно в число
Преобразуйте массив цифр обратно в число. Если число превышает 32-битный предел, верните -1. В противном случае верните полученное число.

😎 Решение:

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
    public String swap(String s, int i0, int i1) {
        if (i0 == i1)
            return s;
        String s1 = s.substring(0, i0);
        String s2 = s.substring(i0 + 1, i1);
        String s3 = s.substring(i1 + 1);
        return s1 + s.charAt(i1) + s2 + s.charAt(i0) + s3;
    }

    ArrayList<String> list = new ArrayList<>();

    void permute(String a, int l, int r) {
        int i;
        if (l == r)
            list.add(a);
        else {
            for (i = l; i <= r; i++) {
                a = swap(a, l, i);
                permute(a, l + 1, r);
                a = swap(a, l, i);
            }
        }
    }

    public int nextGreaterElement(int n) {
        String s = "" + n;
        permute(s, 0, s.length() - 1);
        Collections.sort(list);
        int i;
        for (i = list.size() - 1; i >= 0; i--) {
            if (list.get(i).equals("" + n))
                break;
        }
        return i == list.size() - 1 ? -1 : Integer.parseInt(list.get(i + 1));
    }
}

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

Задача: 389. Find the Difference
Сложность: easy

Даны две строки s и t.

Строка t генерируется путем случайного перемешивания строки s с добавлением еще одной буквы в случайную позицию.

Верните букву, которая была добавлена в t.

Пример:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

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

1⃣Отсортируйте строки s и t.

2⃣Итерируйте по длине строк и сравнивайте их посимвольно. Это позволяет проверить, присутствует ли текущий символ строки t в строке s.

3⃣Как только встретится символ, который есть в строке t, но отсутствует в строке s, мы найдем лишний символ, который скрывала строка t все это время.

😎 Решение:

class Solution {
    public char findTheDifference(String s, String t) {
        char[] sortedS = s.toCharArray();
        char[] sortedT = t.toCharArray();
        Arrays.sort(sortedS);
        Arrays.sort(sortedT);

        int i = 0;
        while (i < s.length()) {
            if (sortedS[i] != sortedT[i]) {
                return sortedT[i];
            }
            i += 1;
        }

        return sortedT[i];
    }
}

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

Задача: 209. Minimum Size Subarray Sum
Сложность: medium

Дан массив положительных целых чисел nums и положительное целое число target. Верните минимальную длину подмассива, сумма которого больше или равна target. Если такого подмассива нет, верните 0.

Пример:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

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

1⃣Инициализация переменных:
Создайте три целочисленные переменные left, right и sumOfCurrentWindow. Переменные left и right формируют подмассив, указывая на начальные и конечные индексы текущего подмассива (или окна), а sumOfCurrentWindow хранит сумму этого окна. Инициализируйте все их значением 0.
Создайте еще одну переменную res для хранения ответа на задачу. Инициализируйте ее большим целым значением.

2⃣Итерация по массиву:
Итерируйте по массиву nums с помощью right, начиная с right = 0 до nums.length - 1, увеличивая right на 1 после каждой итерации. Выполняйте следующее внутри этой итерации:
Добавьте элемент с индексом right к текущему окну, увеличив sumOfCurrentWindow на nums[right].
Проверьте, если sumOfCurrentWindow >= target. Если да, у нас есть подмассив, который удовлетворяет условию. В результате, попытайтесь обновить переменную ответа res длиной этого подмассива. Выполните res = min(res, right - left + 1). Затем удалите первый элемент из этого окна, уменьшив sumOfCurrentWindow на nums[left] и увеличив left на 1. Этот шаг повторяется во внутреннем цикле, пока sumOfCurrentWindow >= target.

3⃣Возврат результата:
Текущая сумма окна теперь меньше target. Нужно добавить больше элементов в окно. В результате, увеличивается right на 1.
Верните res.

😎 Решение:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0, sumOfCurrentWindow = 0;
        int res = Integer.MAX_VALUE;

        for(right = 0; right < nums.length; right++) {
            sumOfCurrentWindow += nums[right];

            while (sumOfCurrentWindow >= target) {
                res = Math.min(res, right - left + 1);
                sumOfCurrentWindow -= nums[left++];
            }
        }

        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

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

Задача: 912. Sort an Array
Сложность: medium

Задав массив целых чисел nums, отсортируйте массив по возрастанию и верните его. Вы должны решить задачу без использования встроенных функций за время O(nlog(n)) и с минимально возможной пространственной сложностью.

Пример:

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

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

1⃣Используем алгоритм "Сортировка слиянием" (Merge Sort), который обеспечивает время выполнения O(n log n) и минимально возможную пространственную сложность для стабильного сортировочного алгоритма.

2⃣Разделить массив на две половины.
Рекурсивно отсортировать каждую половину.

3⃣Слить две отсортированные половины.

😎 Решение:

import java.util.Arrays;

public class Main {
    public static void mergeSort(int[] nums) {
        if (nums.length > 1) {
            int mid = nums.length / 2;
            int[] left_half = Arrays.copyOfRange(nums, 0, mid);
            int[] right_half = Arrays.copyOfRange(nums, mid, nums.length);

            mergeSort(left_half);
            mergeSort(right_half);

            int i = 0, j = 0, k = 0;
            while (i < left_half.length && j < right_half.length) {
                if (left_half[i] < right_half[j]) {
                    nums[k++] = left_half[i++];
                } else {
                    nums[k++] = right_half[j++];
                }
            }

            while (i < left_half.length) {
                nums[k++] = left_half[i++];
            }

            while (j < right_half.length) {
                nums[k++] = right_half[j++];
            }
        }
    }
}

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

Задача: 1057. Campus Bikes
Сложность: medium

В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Пример:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]

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

1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список.

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

3⃣Заполни и верни массив назначений.

😎 Решение:

import java.util.*;

public class Solution {
    public int[] assignBikes(int[][] workers, int[][] bikes) {
        List<int[]> pairs = new ArrayList<>();
        
        for (int i = 0; i < workers.length; i++) {
            for (int j = 0; j < bikes.length; j++) {
                int distance = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]);
                pairs.add(new int[]{distance, i, j});
            }
        }
        
        pairs.sort((a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            if (a[1] != b[1]) return a[1] - b[1];
            return a[2] - b[2];
        });
        
        int[] result = new int[workers.length];
        boolean[] bikeTaken = new boolean[bikes.length];
        boolean[] workerAssigned = new boolean[workers.length];
        
        Arrays.fill(result, -1);
        
        for (int[] pair : pairs) {
            int workerIdx = pair[1];
            int bikeIdx = pair[2];
            if (!workerAssigned[workerIdx] && !bikeTaken[bikeIdx]) {
                result[workerIdx] = bikeIdx;
                bikeTaken[bikeIdx] = true;
                workerAssigned[workerIdx] = true;
            }
        }
        
        return result;
    }
}

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

Задача: 274. H-Index
Сложность: medium

Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.

Пример:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

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

1⃣Отсортировать массив цитирований по убыванию:
Отсортировать массив citations в порядке убывания, чтобы наибольшее количество цитирований было в начале массива.

2⃣Найти наибольшее значение i, для которого citations[i] > i:
Пройтись по отсортированному массиву и найти наибольшее значение i, для которого выполняется условие citations[i] > i.
Это значение будет индексом, при котором количество цитирований статьи больше индекса.

3⃣Рассчитать h-индекс:
h-индекс будет равен i + 1, где i - наибольшее значение, найденное на предыдущем шаге.

😎 Решение:

public class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] papers = new int[n + 1];
        for (int c : citations)
            papers[Math.min(n, c)]++;
        int k = n;
        for (int s = papers[n]; k > s; s += papers[k])
            k--;
        return k;
    }
}

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

Задача: 507. Perfect Number
Сложность: easy

Совершенное число — это положительное целое число, которое равно сумме своих положительных делителей, исключая само число. Делитель целого числа x — это целое число, которое может делить x нацело.

Дано целое число n, верните true, если n является совершенным числом, в противном случае верните false.

Пример:

Input: num = 28
Output: true
Explanation: 28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, and 14 are all divisors of 28.

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

1⃣Инициализация
Если число num меньше или равно 0, вернуть false. Инициализируйте переменную sum значением 0.

2⃣Поиск делителей и вычисление суммы
Переберите числа от 1 до квадратного корня num. Если число является делителем num, добавьте его к sum. Если делитель не равен квадратному корню num, добавьте к sum также результат деления num на делитель.

3⃣Проверка на совершенное число
Вычтите num из sum. Если результат равен num, вернуть true, иначе вернуть false.

😎 Решение:

    public boolean checkPerfectNumber(int num) {
        if (num <= 0) {
            return false;
        }
        int sum = 0;
        for (int i = 1; i * i <= num; i++) {
            if (num % i == 0) {
                sum += i;
                if (i * i != num) {
                    sum += num / i;
                }

            }
        }
        return sum - num == num;
    }
}

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

Задача: 1135. Connecting Cities With Minimum Cost
Сложность: medium

Есть n городов, пронумерованных от 1 до n. Вам даны целое число n и массив connections, где connections[i] = [xi, yi, costi] указывает, что стоимость соединения города xi и города yi (двунаправленное соединение) равна costi.

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

Стоимость - это сумма использованных стоимостей соединений.

Пример:

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.

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

1⃣Сортировка рёбер:
Отсортируйте все соединения (рёбра) в графе по их весам (стоимости) в порядке возрастания.

2⃣Итерация по рёбрам и объединение:
Используйте структуру данных Disjoint Set (Union-Find) для проверки циклов и объединения поддеревьев. Для каждого ребра проверьте, принадлежат ли его концы разным поддеревьям, и если да, объедините их, добавив ребро в минимальное остовное дерево (MST).

3⃣Проверка соединённости:
Подсчитайте количество рёбер в MST. Если оно меньше n-1, верните -1, так как соединить все города невозможно. Иначе верните суммарную стоимость рёбер в MST.

😎 Решение:

class DisjointSet {
    private int[] parents;

    public void Union(int a, int b) {
        int rootA = Find(a);
        int rootB = Find(b);
        if (rootA == rootB) return;
        this.parents[rootB] = rootA;
    }

    public int Find(int a) {
        while (a != this.parents[a]) {
            a = this.parents[a];
        }
        return a;
    }

    public boolean isInSameGroup(int a, int b) {
        return Find(a) == Find(b);
    }

    public DisjointSet(int N) {
        this.parents = new int[N + 1];
        for (int i = 1; i <= N; ++i) {
            this.parents[i] = i;
        }
    }
}

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

Задача: 291. Word Pattern II
Сложность: medium

Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.

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

Пример:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

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

1⃣Инициализация структур данных и определение рекурсивной функции:
Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.
Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.
Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.

2⃣Рекурсивная проверка соответствия:
Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.
Получите символ из шаблона по индексу pIndex.
Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.

3⃣Отображение новых подстрок:
Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.
Для каждой новой подстроки проверьте, существует ли она уже в `

😎 Решение:

import java.util.HashMap;
import java.util.HashSet;

public class Solution {
    public boolean wordPatternMatch(String pattern, String s) {
        HashMap<Character, String> symbolMap = new HashMap<>();
        HashSet<String> wordSet = new HashSet<>();
        return isMatch(s, 0, pattern, 0, symbolMap, wordSet);
    }

    private boolean isMatch(String s, int sIndex, String pattern, int pIndex,
                            HashMap<Character, String> symbolMap, HashSet<String> wordSet) {
        if (pIndex == pattern.length()) {
            return sIndex == s.length();
        }
        char symbol = pattern.charAt(pIndex);
        if (symbolMap.containsKey(symbol)) {
            String word = symbolMap.get(symbol);
            if (!s.startsWith(word, sIndex)) {
                return false;
            }
            return isMatch(s, sIndex + word.length(), pattern, pIndex + 1, symbolMap, wordSet);
        }
        for (int k = sIndex + 1; k <= s.length(); k++) {
            String newWord = s.substring(sIndex, k);
            if (wordSet.contains(newWord)) {
                continue;
            }
            symbolMap.put(symbol, newWord);
            wordSet.add(newWord);
            if (isMatch(s, k, pattern, pIndex + 1, symbolMap, wordSet)) {
                return true;
            }
            symbolMap.remove(symbol);
            wordSet.remove(newWord);
        }
        return false;
    }
}

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