Java | LeetCode

Задача: 932. Beautiful Array
Сложность: medium

Массив nums длины n красив, если: nums является перестановкой целых чисел в диапазоне [1, n]. Для каждого 0 <= i < j < n не существует индекса k с i < k < j, где 2 * nums[k] == nums[i] + nums[j]. Задано целое число n, верните любой красивый массив nums длины n. Для заданного n будет хотя бы один правильный ответ.

Пример:

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

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

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

2⃣Если длина массива равна 1, вернуть массив [1].
Разделить n на четные и нечетные индексы и создать массивы для них.

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

😎 Решение:

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

class Solution {
    public int[] beautifulArray(int n) {
        List<Integer> result = construct(n);
        int[] resArray = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resArray[i] = result.get(i);
        }
        return resArray;
    }
    
    private List<Integer> construct(int n) {
        if (n == 1) {
            List<Integer> base = new ArrayList<>();
            base.add(1);
            return base;
        }
        List<Integer> odd = construct((n + 1) / 2);
        List<Integer> even = construct(n / 2);
        List<Integer> result = new ArrayList<>();
        for (int x : odd) {
            result.add(2 * x - 1);
        }
        for (int x : even) {
            result.add(2 * x);
        }
        return result;
    }
}

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

Задача: 913. Cat and Mouse
Сложность: hard

В игру на неориентированном графе играют два игрока, Мышь и Кот, которые чередуются по очереди. Граф задан следующим образом: graph[a] - это список всех вершин b, таких, что ab является ребром графа. Мышь начинает в вершине 1 и идет первой, Кот начинает в вершине 2 и идет второй, а в вершине 0 находится дыра. Во время хода каждого игрока он должен пройти по одному ребру графа, которое встречает его местоположение.Например, если Мышь находится в узле 1, она должна добраться до любого узла графа[1]. Кроме того, Кошке запрещено добираться до Дыры (узел 0). Затем игра может закончиться тремя способами: если Кошка занимает тот же узел, что и Мышь, Кошка побеждает. Если Мышь достигает Дыры, Мышь побеждает. Если позиция повторяется (т.е, игроки находятся в той же позиции, что и в предыдущий ход, и сейчас очередь того же игрока двигаться), то игра считается ничейной. Учитывая граф и предполагая, что оба игрока играют оптимально, верните 1, если в игре победила мышь, 2, если в игре победила кошка, или 0, если в игре ничья.

Пример:

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

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

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

2⃣Проверить три условия окончания игры:
Мышь достигает дырки (победа мыши).
Кот достигает мыши (победа кота).
Позиция повторяется (ничья).

3⃣Использовать BFS (поиск в ширину) для определения результатов игры, начиная с конечных состояний и работая назад.

😎 Решение:

import java.util.*;

public class Solution {
    public int catMouseGame(int[][] graph) {
        int n = graph.length;
        final int DRAW = 0, MOUSE = 1, CAT = 2;
        int[][][] dp = new int[n][n][2];
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 1; i < n; i++) {
            dp[0][i][0] = MOUSE;
            dp[0][i][1] = MOUSE;
            dp[i][i][0] = CAT;
            dp[i][i][1] = CAT;
            queue.offer(new int[]{0, i, 0, MOUSE});
            queue.offer(new int[]{0, i, 1, MOUSE});
            queue.offer(new int[]{i, i, 0, CAT});
            queue.offer(new int[]{i, i, 1, CAT});
        }

        while (!queue.isEmpty()) {
            int[] state = queue.poll();
            int mouse = state[0], cat = state[1], turn = state[2], winner = state[3];
            for (int[] parent : parents(graph, mouse, cat, turn)) {
                int m = parent[0], c = parent[1], t = parent[2];
                if (dp[m][c][t] == DRAW) {
                    if ((t == 0 && winner == MOUSE) || (t == 1 && winner == CAT)) {
                        dp[m][c][t] = winner;
                        queue.offer(new int[]{m, c, t, winner});
                    } else {
                        int degrees = 0;
                        for (int[] p : parents(graph, m, c, t)) degrees++;
                        if (degrees == 0) {
                            dp[m][c][t] = winner;
                            queue.offer(new int[]{m, c, t, winner});
                        }
                    }
                }
            }
        }

        return dp[1][2][0];
    }

    private List<int[]> parents(int[][] graph, int mouse, int cat, int turn) {
        List<int[]> res = new ArrayList<>();
        if (turn == 1) {
            for (int m : graph[mouse]) {
                res.add(new int[]{m, cat, 0});
            }
        } else {
            for (int c : graph[cat]) {
                if (c > 0) res.add(new int[]{mouse, c, 1});
            }
        }
        return res;
    }
}

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

Задача: 1249. Minimum Remove to Make Valid Parentheses
Сложность: medium

Дана строка s из '(' , ')' и строчных английских символов. Ваша задача - удалить минимальное количество скобок ( '(' или ')' в любых позициях), чтобы полученная строка со скобками была допустимой, и вернуть любую допустимую строку. Формально строка со скобками допустима тогда и только тогда, когда: она пустая, содержит только строчные символы, или может быть записана как AB (A, конкатенированная с B), где A и B - допустимые строки, или может быть записана как (A), где A - допустимая строка.

Пример:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"

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

1⃣Пройдите по строке s и сохраните индексы всех открывающих скобок '(' в стек. При встрече закрывающей скобки ')', удалите соответствующую открытую скобку из стека. Если в стеке нет соответствующей открывающей скобки, пометьте эту закрывающую скобку для удаления.

2⃣После первого прохода, все оставшиеся в стеке открывающие скобки пометьте для удаления.

3⃣Создайте новую строку, удалив все помеченные скобки.

😎 Решение:

public class Solution {
    public String minRemoveToMakeValid(String s) {
        StringBuilder sb = new StringBuilder(s);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < sb.length(); i++) {
            if (sb.charAt(i) == '(') {
                stack.push(i);
            } else if (sb.charAt(i) == ')') {
                if (!stack.isEmpty()) {
                    stack.pop();
                } else {
                    sb.setCharAt(i, '*');
                }
            }
        }
        while (!stack.isEmpty()) {
            sb.setCharAt(stack.pop(), '*');
        }
        return sb.toString().replaceAll("\\*", "");
    }
}

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

Задача: 867. Transpose Matrix
Сложность: easy

Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу.

Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами.

Пример:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]

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

1⃣Инициализируйте новую матрицу ans с размерами C x R, где C — количество столбцов в исходной матрице, а R — количество строк.

2⃣Скопируйте каждую запись исходной матрицы в новую матрицу так, чтобы ans[c][r] = matrix[r][c].

3⃣Верните матрицу ans.

😎 Решение:

class Solution {
    public int[][] transpose(int[][] A) {
        int R = A.length, C = A[0].length;
        int[][] ans = new int[C][R];
        for (int r = 0; r < R; ++r)
            for (int c = 0; c < C; ++c)
                ans[c][r] = A[r][c];
        return ans;
    }
}

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

Задача: 650. 2 Keys Keyboard
Сложность: medium

На экране блокнота есть только один символ 'A'. Для каждого шага можно выполнить одну из двух операций над этим блокнотом: Copy All: скопировать все символы, присутствующие на экране (частичное копирование не допускается). Paste: Вы можете вставить символы, которые были скопированы в прошлый раз. Учитывая целое число n, верните минимальное количество операций, чтобы символ 'A' появился на экране ровно n раз.

Пример:

Input: n = 3
Output: 3

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

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

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

3⃣Возвращайте значение из таблицы динамического программирования для n.

😎 Решение:

public class Solution {
    public int minSteps(int n) {
        if (n == 1) return 0;
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; j <= i / 2; j++) {
                if (i % j == 0) {
                    dp[i] = Math.min(dp[i], dp[j] + i / j);
                }
            }
        }
        return dp[n];
    }
}

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

Задача: 520. Detect Capital
Сложность: easy

Мы определяем правильное использование заглавных букв в слове, когда выполняется одно из следующих условий:

Все буквы в этом слове заглавные, как "USA".
Все буквы в этом слове строчные, как "leetcode".
Только первая буква в этом слове заглавная, как "Google".
Дана строка word. Верните true, если использование заглавных букв в ней правильное.

Пример:

Input: word = "USA"
Output: true

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

1⃣Шаблон для первого случая в регулярном выражении: [A-Z]*, где [A-Z] соответствует одной заглавной букве от 'A' до 'Z', а * означает повторение предыдущего шаблона 0 или более раз. Этот шаблон представляет "Все заглавные буквы".

2⃣Шаблон для второго случая в регулярном выражении: [a-z]*, где [a-z] соответствует одной строчной букве от 'a' до 'z'. Этот шаблон представляет "Все строчные буквы". Шаблон для третьего случая в регулярном выражении: [A-Z][a-z]*, где первая буква заглавная, а остальные строчные.

3⃣Объедините эти три шаблона: [A-Z]*|[a-z]*|[A-Z][a-z]*, где | означает "или". Мы можем объединить второй и третий случай, получив . [a-z]*, где . соответствует любому символу. Итоговый шаблон: [A-Z]*|.[a-z]*.

😎 Решение:

import java.util.regex.*;

class Solution {
    public boolean detectCapitalUse(String word) {
        String pattern = "[A-Z]*|.[a-z]*";
        return Pattern.matches(pattern, word);
    }
}

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

Задача: 856. Score of Parentheses
Сложность: medium

Дана строка s, состоящая из сбалансированных скобок, верните счёт строки.

Счёт сбалансированной строки скобок основывается на следующих правилах:

"()" имеет счёт 1.
AB имеет счёт A + B, где A и B — сбалансированные строки скобок.
(A) имеет счёт 2 * A, где A — сбалансированная строка скобок.

Пример:

Input: s = "()"
Output: 1

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

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

2⃣Отслеживая баланс (количество открывающих скобок минус количество закрывающих скобок), мы можем разделить строку S на примитивные подстроки S = P_1 + P_2 + ... + P_n. Тогда, по определению, score(S) = score(P_1) + score(P_2) + ... + score(P_n).

3⃣Для каждой примитивной подстроки (S[i], S[i+1], ..., S[k]), если длина строки равна 2, то её счёт равен 1. В противном случае, счёт равен удвоенному счёту подстроки (S[i+1], S[i+2], ..., S[k-1]).

😎 Решение:

class Solution {
    public int scoreOfParentheses(String S) {
        return F(S, 0, S.length());
    }

    public int F(String S, int i, int j) {
        int ans = 0, bal = 0;

        for (int k = i; k < j; ++k) {
            bal += S.charAt(k) == '(' ? 1 : -1;
            if (bal == 0) {
                if (k - i == 1) ans++;
                else ans += 2 * F(S, i + 1, k);
                i = k + 1;
            }
        }

        return ans;
    }
}

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

Задача: 186. Reverse Words in a String II
Сложность: medium

Дан массив символов s, переверните порядок слов.

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

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

Пример:

Input: s = ["a"]
Output: ["a"]

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

1⃣Перевернуть всю строку: применить функцию reverse, которая переворачивает весь массив символов от начала до конца.

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

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

😎 Решение:

class Solution {
    public void reverse(char[] s, int left, int right) {
        while (left < right) {
            char tmp = s[left];
            s[left++] = s[right];
            s[right--] = tmp;
        }
    }

    public void reverseEachWord(char[] s) {
        int n = s.length;
        int start = 0, end = 0;

        while (start < n) {
            while (end < n && s[end] != ' ') ++end;
            reverse(s, start, end - 1);            start = end + 1;
            ++end;
        }
    }

    public void reverseWords(char[] s) {
        reverse(s, 0, s.length - 1);
        reverseEachWord(s);
    }
}

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

Задача: 1509. Minimum Difference Between Largest and Smallest Value in Three Moves
Сложность: medium

Вам дан массив целых чисел nums.

За один ход вы можете выбрать один элемент массива nums и изменить его на любое значение.

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

Пример:

Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

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

1⃣Инициализация: определите размер массива nums, если размер меньше или равен 4, верните 0. Отсортируйте массив nums и инициализируйте переменную minDiff очень большим числом.

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

3⃣Верните minDiff, которое хранит минимальную разницу между наибольшими и наименьшими значениями после удаления до трех элементов.

😎 Решение:

class Solution {
    public int minDifference(int[] nums) {
        int numsSize = nums.length;
        
        if (numsSize <= 4) return 0;
        
        Arrays.sort(nums);
        
        int minDiff = Integer.MAX_VALUE;
        
        for (int left = 0, right = numsSize - 4; left < 4; left++, right++) {
            minDiff = Math.min(minDiff, nums[right] - nums[left]);
        }
        
        return minDiff;
    }
}

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

Задача: 599. Minimum Index Sum of Two Lists
Сложность: easy

Даны два массива строк list1 и list2, необходимо найти общие строки с наименьшей суммой индексов.

Общая строка - это строка, которая появляется и в list1, и в list2.

Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк.

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

Пример:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".

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

1⃣Для каждой строки из list1, сравниваем её с каждой строкой из list2, обходя весь список list2. Используем хэш-таблицу map, которая содержит элементы в виде (сумма: список строк). Здесь сумма относится к сумме индексов совпадающих элементов, а список строк соответствует списку совпадающих строк, чья сумма индексов равна этой сумме.

2⃣Во время сравнений, когда находится совпадение строки на i-м индексе из list1 и j-м индексе из list2, создаём запись в map, соответствующую сумме i + j, если такая запись ещё не существует. Если запись с этой суммой уже существует, добавляем текущую строку в список строк, соответствующих сумме i + j.

3⃣В конце обходим ключи в map и находим список строк, соответствующих ключу с минимальной суммой.

😎 Решение:

import java.util.*;

public class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        HashMap<Integer, List<String>> map = new HashMap<>();
        for (int i = 0; i < list1.length; i++) {
            for (int j = 0; j < list2.length; j++) {
                if (list1[i].equals(list2[j])) {
                    if (!map.containsKey(i + j)) {
                        map.put(i + j, new ArrayList<>());
                    }
                    map.get(i + j).add(list1[i]);
                }
            }
        }
        int minIndexSum = Integer.MAX_VALUE;
        for (int key : map.keySet()) {
            minIndexSum = Math.min(minIndexSum, key);
        }
        return map.get(minIndexSum).toArray(new String[0]);
    }
}

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

Задача: 827. Making A Large Island
Сложность: hard

Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1.

Верните размер самого большого острова в grid после выполнения этой операции.

Остров — это группа 1, соединенных в 4 направлениях.

Пример:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

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

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

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

3⃣Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1.

😎 Решение:

class Solution {
    int[] dr = new int[]{-1, 0, 1, 0};
    int[] dc = new int[]{0, -1, 0, 1};
    int[][] grid;
    int N;

    public int largestIsland(int[][] grid) {
        this.grid = grid;
        N = grid.length;

        int index = 2;
        int[] area = new int[N*N + 2];
        for (int r = 0; r < N; ++r)
            for (int c = 0; c < N; ++c)
                if (grid[r][c] == 1)
                    area[index] = dfs(r, c, index++);

        int ans = 0;
        for (int x: area) ans = Math.max(ans, x);
        for (int r = 0; r < N; ++r)
            for (int c = 0; c < N; ++c)
                if (grid[r][c] == 0) {
                    Set<Integer> seen = new HashSet();
                    for (Integer move: neighbors(r, c))
                        if (grid[move / N][move % N] > 1)
                            seen.add(grid[move / N][move % N]);

                    int bns = 1;
                    for (int i: seen) bns += area[i];
                    ans = Math.max(ans, bns);
                }

        return ans;
    }

    public int dfs(int r, int c, int index) {
        int ans = 1;
        grid[r][c] = index;
        for (Integer move: neighbors(r, c)) {
            if (grid[move / N][move % N] == 1) {
                grid[move / N][move % N] = index;
                ans += dfs(move / N, move % N, index);
            }
        }

        return ans;
    }

    public List<Integer> neighbors(int r, int c) {
        List<Integer> ans = new ArrayList();
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            if (0 <= nr && nr < N && 0 <= nc && nc < N)
                ans.add(nr * N + nc);
        }

        return ans;
    }

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

Задача: 1382. Balance a Binary Search Tree
Сложность: medium

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

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

Пример:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

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

1⃣Инициализация. Создайте пустой список inorder для хранения значений узлов после обхода в порядке возрастания.

2⃣Выполнение обхода в порядке возрастания. Обойдите бинарное дерево поиска (BST) и заполните список inorder значениями узлов в отсортированном порядке.

3⃣Перестроение сбалансированного BST. Определите рекурсивную функцию createBalancedBST, которая принимает список inorder, начальный индекс и конечный индекс в качестве параметров. Если начальный индекс больше конечного, верните null (или эквивалент). Вычислите средний индекс как середину текущего диапазона. Создайте новый узел дерева со значением в среднем индексе. Рекурсивно создайте левое поддерево, используя левую половину текущего диапазона. Рекурсивно создайте правое поддерево, используя правую половину текущего диапазона. Верните корень вновь построенного сбалансированного BST.

😎 Решение:

class Solution {
    public TreeNode balanceBST(TreeNode root) {
        if (root == null) return null;

        TreeNode vineHead = new TreeNode(0);
        vineHead.right = root;
        TreeNode current = vineHead;

        while (current.right != null) {
            if (current.right.left != null) {
                rightRotate(current, current.right);
            } else {
                current = current.right;
            }
        }

        int nodeCount = 0;
        current = vineHead.right;
        while (current != null) {
            nodeCount++;
            current = current.right;
        }

        int m = (int) Math.pow(2, Math.floor(Math.log(nodeCount + 1) / Math.log(2))) - 1;
        makeRotations(vineHead, nodeCount - m);
        while (m > 1) {
            m /= 2;
            makeRotations(vineHead, m);
        }

        TreeNode balancedRoot = vineHead.right;
        return balancedRoot;
    }

    private void rightRotate(TreeNode parent, TreeNode node) {
        TreeNode tmp = node.left;
        node.left = tmp.right;
        tmp.right = node;
        parent.right = tmp;
    }

    private void leftRotate(TreeNode parent, TreeNode node) {
        TreeNode tmp = node.right;
        node.right = tmp.left;
        tmp.left = node;
        parent.right = tmp;
    }

    private void makeRotations(TreeNode vineHead, int count) {
        TreeNode current = vineHead;
        for (int i = 0; i < count; i++) {
            TreeNode tmp = current.right;
            leftRotate(current, tmp);
            current = current.right;
        }
    }
}

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

Задача: 1122. Relative Sort Array
Сложность: easy

Даны два массива arr1 и arr2, элементы arr2 уникальны, и все элементы arr2 также присутствуют в arr1.

Отсортируйте элементы arr1 таким образом, чтобы относительный порядок элементов в arr1 был таким же, как в arr2. Элементы, которые не встречаются в arr2, должны быть размещены в конце arr1 в порядке возрастания.

Пример:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

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

1⃣Инициализация и подсчёт:
Инициализируйте пустой массив result и массив remaining для хранения оставшихся элементов.
Создайте хеш-таблицу countMap для хранения количества вхождений каждого элемента из arr2 в arr1.

2⃣Заполнение countMap и remaining:
Пройдитесь по элементам arr1 и если элемент присутствует в countMap, увеличьте его счетчик. Если элемент не присутствует в arr2, добавьте его в remaining.

3⃣Формирование результирующего массива:
Пройдитесь по arr2 и добавьте элементы в result в соответствии с их количеством в countMap.
Отсортируйте массив remaining и добавьте его элементы в result.
Верните result в виде массива.

😎 Решение:

class Solution {

    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> countMap = new HashMap<>();
        List<Integer> remaining = new ArrayList<>();
        List<Integer> result = new ArrayList<>();

        for (int value : arr2) {
            countMap.put(value, 0);
        }

        for (int value : arr1) {
            if (countMap.containsKey(value)) {
                countMap.put(value, countMap.get(value) + 1);
            } else {
                remaining.add(value);
            }
        }

        Collections.sort(remaining);

        for (int value : arr2) {
            for (int j = 0; j < countMap.get(value); j++) {
                result.add(value);
            }
        }

        result.addAll(remaining);

        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

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

Задача: 1203. Sort Items by Groups Respecting Dependencies
Сложность: hard

Есть n предметов, каждый из которых принадлежит нулевой или одной из m групп, где group[i] — это группа, к которой принадлежит i-й предмет, и равно -1, если i-й предмет не принадлежит никакой группе. Предметы и группы имеют индексацию с нуля. Группа может не иметь ни одного предмета.

Верните отсортированный список предметов таким образом:
Предметы, принадлежащие одной группе, расположены рядом друг с другом в отсортированном списке.
Существуют некоторые отношения между этими предметами, где beforeItems[i] — это список, содержащий все предметы, которые должны быть перед i-м предметом в отсортированном массиве (слева от i-го предмета).
Верните любое решение, если существует более одного решения, и верните пустой список, если решения не существует.

Пример:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]

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

1⃣Инициализация и создание графов:
Присвоить уникальные идентификаторы группам для элементов без группы.
Создать два графа: item_graph для элементов и group_graph для групп. Также создать два массива для учета входящих рёбер для элементов и групп.

2⃣Построение графов:
Пройти по массиву beforeItems и добавить зависимости между элементами в item_graph, увеличивая счётчик входящих рёбер.
Если элементы принадлежат разным группам, добавить зависимость между группами в group_graph, увеличивая счётчик входящих рёбер.

3⃣Топологическая сортировка и создание итогового списка:
Выполнить топологическую сортировку для элементов и групп. Если есть цикл, вернуть пустой список.
Создать итоговый список, добавляя отсортированные элементы каждой группы.

😎 Решение:

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        int groupId = m;
        for (int i = 0; i < n; i++) if (group[i] == -1) group[i] = groupId++;

        Map<Integer, List<Integer>> itemGraph = new HashMap<>();
        Map<Integer, List<Integer>> groupGraph = new HashMap<>();
        int[] itemIndegree = new int[n], groupIndegree = new int[groupId];
        for (int i = 0; i < n; i++) itemGraph.put(i, new ArrayList<>());
        for (int i = 0; i < groupId; i++) groupGraph.put(i, new ArrayList<>());

        for (int curr = 0; curr < n; curr++) {
            for (int prev : beforeItems.get(curr)) {
                itemGraph.get(prev).add(curr);
                itemIndegree[curr]++;
                if (group[curr] != group[prev]) {
                    groupGraph.get(group[prev]).add(group[curr]);
                    groupIndegree[group[curr]]++;
                }
            }
        }

        List<Integer> itemOrder = topologicalSort(itemGraph, itemIndegree);
        List<Integer> groupOrder = topologicalSort(groupGraph, groupIndegree);
        if (itemOrder.isEmpty() || groupOrder.isEmpty()) return new int[0];

        Map<Integer, List<Integer>> orderedGroups = new HashMap<>();
        for (int item : itemOrder) orderedGroups.computeIfAbsent(group[item], k -> new ArrayList<>()).add(item);

        List<Integer> answerList = new ArrayList<>();
        for (int groupIndex : groupOrder) answerList.addAll(orderedGroups.getOrDefault(groupIndex, new ArrayList<>()));

        return answerList.stream().mapToInt(Integer::intValue).toArray();
    }

    private List<Integer> topologicalSort(Map<Integer, List<Integer>> graph, int[] indegree) {
        List<Integer> visited = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        for (int key : graph.keySet()) if (indegree[key] == 0) stack.add(key);

        while (!stack.isEmpty()) {
            int curr = stack.pop();
            visited.add(curr);
            for (int next : graph.get(curr)) if (--indegree[next] == 0) stack.add(next);
        }

        return visited.size() == graph.size() ? visited : new ArrayList<>();
    }
}

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

Задача: 665. Non-decreasing Array
Сложность: medium

Дан массив nums из n целых чисел. Ваша задача - проверить, можно ли сделать его неубывающим, изменив не более одного элемента.

Мы определяем массив как неубывающий, если для каждого i (индексация с 0), такого что 0 <= i <= n - 2, выполняется условие nums[i] <= nums[i + 1].

Пример:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

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

1⃣Инициализация переменных:
Завести переменную count для подсчета числа изменений.
Проверить последовательность чисел в массиве nums.

2⃣Проверка условий:
Если nums[i] > nums[i + 1], то увеличиваем count.
Если count превышает 1, возвращаем false, так как больше одного изменения недопустимо.
Если nums[i - 1] > nums[i + 1] и nums[i] > nums[i + 2], то возвращаем false.

3⃣Возврат результата:
Если количество изменений не превышает 1, вернуть true.

😎 Решение:

public class Solution {
    public boolean checkPossibility(int[] nums) {
        int count = 0;
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                if (count > 0) {
                    return false;
                }
                count++;
                if (i == 1 || nums[i] >= nums[i - 2]) {
                    nums[i - 1] = nums[i];
                } else {
                    nums[i] = nums[i - 1];
                }
            }
        }
        
        return true;
    }
}

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

Задача: №21. Merge Two Sorted Lists
Сложность: easy

Вам даны заголовки двух отсортированных связанных списков list1 и list2.
Объедините их в один отсортированный список, сшивая существующие узлы.
Верните заголовок нового объединенного списка.

Пример:

Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]

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

1⃣Если один из списков пуст — возвращаем второй как результат.

2⃣Сравниваем значения текущих узлов списков: выбираем меньший и рекурсивно вызываем mergeTwoLists для оставшейся части.

3⃣Связываем меньший узел с результатом рекурсивного вызова и возвращаем его как текущий.

😎 Решение:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                list1.next = mergeTwoLists(list1.next, list2);
                return list1;
            } else {
                list2.next = mergeTwoLists(list1, list2.next);
                return list2;
            }
        }
        return list1 != null ? list1 : list2;
    }
}

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

Задача: 210. Course Schedule II
Сложность: medium

Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив.

Пример:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Объяснение: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0.
Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].

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

1⃣Инициализация и построение графа:
Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе.
Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма.

2⃣Запуск поиска в глубину (DFS):
Для каждого узла в нашем графе выполните поиск в глубину (DFS), если этот узел еще не был посещен во время DFS другого узла.
Предположим, что мы выполняем поиск в глубину для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны.

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

😎 Решение:

class Solution {
    static int WHITE = 1;
    static int GRAY = 2;
    static int BLACK = 3;

    boolean isPossible;
    Map<Integer, Integer> color;
    Map<Integer, List<Integer>> adjList;
    List<Integer> topologicalOrder;

    private void init(int numCourses) {
        this.isPossible = true;
        this.color = new HashMap<>();
        this.adjList = new HashMap<>();
        this.topologicalOrder = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            this.color.put(i, WHITE);
        }
    }

    private void dfs(int node) {
        if (!this.isPossible) return;
        this.color.put(node, GRAY);
        for (Integer neighbor : this.adjList.getOrDefault(node, new ArrayList<>())) {
            if (this.color.get(neighbor) == WHITE) {
                this.dfs(neighbor);
            } else if (this.color.get(neighbor) == GRAY) {
                this.isPossible = false;
            }
        }
        this.color.put(node, BLACK);
        this.topologicalOrder.add(node);
    }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        this.init(numCourses);
        for (int i = 0; i < prerequisites.length; i++) {
            int dest = prerequisites[i][0];
            int src = prerequisites[i][1];
            List<Integer> lst = adjList.getOrDefault(src, new ArrayList<>());
            lst.add(dest);
            adjList.put(src, lst);
        }
        for (int i = 0; i < numCourses; i++) {
            if (this.color.get(i) == WHITE) {
                this.dfs(i);
            }
        }
        if (this.isPossible) {
            int[] order = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                order[i] = this.topologicalOrder.get(numCourses - i - 1);
            }
            return order;
        } else {
            return new int[0];
        }
    }
}

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

Задача: 926. Flip String to Monotone Increasing
Сложность: medium

Двоичная строка является монотонно возрастающей, если она состоит из некоторого количества 0 (возможно, ни одного), за которым следует некоторое количество 1 (также возможно, ни одного). Вам дана двоичная строка s. Вы можете перевернуть s[i], изменив ее значение с 0 на 1 или с 1 на 0.

Пример:

Input: s = "00110"
Output: 1

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

1⃣Создать массив left для подсчета количества операций, чтобы сделать подстроку до текущего индекса монотонной (только 0).

2⃣Создать массив right для подсчета количества операций, чтобы сделать подстроку после текущего индекса монотонной (только 1).
Пройти по строке и заполнить массивы left и right.

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

😎 Решение:

class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        int[] left = new int[n + 1];
        int[] right = new int[n + 1];
        
        for (int i = 0; i < n; i++) {
            left[i + 1] = left[i] + (s.charAt(i) == '1' ? 1 : 0);
        }
        
        for (int i = n - 1; i >= 0; i--) {
            right[i] = right[i + 1] + (s.charAt(i) == '0' ? 1 : 0);
        }
        
        int result = Integer.MAX_VALUE;
        for (int i = 0; i <= n; i++) {
            result = Math.min(result, left[i] + right[i]);
        }
        return result;
    }
}

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

Задача: 786. K-th Smallest Prime Fraction
Сложность: medium

Вам дан отсортированный массив целых чисел arr, содержащий 1 и простые числа, где все элементы массива arr уникальны. Также дано целое число k.

Для каждого i и j, где 0 <= i < j < arr.length, мы рассматриваем дробь arr[i] / arr[j].

Верните k-ую наименьшую дробь из рассмотренных. Верните ответ в виде массива из двух целых чисел размера 2, где answer[0] == arr[i] и answer[1] == arr[j].

Пример:

Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.

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

1⃣Инициализируйте пустую приоритетную очередь pq для хранения пар дробей и соответствующих им индексов. Итеративно пройдите по входному массиву arr, используя переменную цикла i. Для каждого элемента arr[i] вычислите дробь, образованную делением его на наибольший элемент в массиве (arr[arr.size() - 1]). Поместите пару, состоящую из отрицательного значения дроби (-1.0 * arr[i] / arr[arr.size() - 1]) и соответствующих индексов (i для числителя и arr.size() - 1 для знаменателя), в приоритетную очередь pq. Приоритетная очередь pq теперь содержит все дроби, образованные делением каждого элемента на наибольший элемент в массиве, отсортированные в порядке возрастания значений дробей.

2⃣Повторите следующие шаги k - 1 раз: удалите верхний элемент (наименьшую дробь) из приоритетной очереди pq и сохраните его индексы в переменной cur. Уменьшите индекс знаменателя (cur[1]--). Вычислите новую дробь, образованную делением числителя в cur[0] на уменьшенный знаменатель (arr[cur[1]]). Поместите новое значение дроби (-1.0 * arr[cur[0]] / arr[cur[1]]) и соответствующие индексы (cur[0] для числителя и cur[1] для знаменателя) в приоритетную очередь pq. После k - 1 итераций верхний элемент приоритетной очереди pq будет k-й наименьшей дробью.

3⃣Извлеките индексы числителя и знаменателя из верхнего элемента приоритетной очереди и сохраните их в result. Верните массив, содержащий значения числителя (arr[result[0]]) и знаменателя (arr[result[1]]), соответствующие k-й наименьшей дроби.

😎 Решение:

import java.util.PriorityQueue;

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Double.compare((double)arr[a[0]] / arr[a[1]], (double)arr[b[0]] / arr[b[1]]));
        
        for (int i = 0; i < arr.length - 1; i++) {
            pq.offer(new int[]{i, arr.length - 1});
        }
        
        for (int i = 0; i < k - 1; i++) {
            int[] cur = pq.poll();
            if (cur[1] - 1 > cur[0]) {
                pq.offer(new int[]{cur[0], cur[1] - 1});
            }
        }
        
        int[] result = pq.poll();
        return new int[]{arr[result[0]], arr[result[1]]};
    }
}

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

Задача: 439. Ternary Expression Parser
Сложность: medium

Дана строка expression, представляющая произвольно вложенные тернарные выражения, вычислите это выражение и верните его результат.

Можно всегда считать, что данное выражение является корректным и содержит только цифры, '?', ':', 'T' и 'F', где 'T' означает истину, а 'F' - ложь. Все числа в выражении являются однозначными числами (т.е. в диапазоне от 0 до 9).

Условные выражения группируются справа налево (как обычно в большинстве языков), и результат выражения всегда будет либо цифрой, либо 'T', либо 'F'.

Пример:

Input: expression = "T?2:3"
Output: "2"
Explanation: If true, then result is 2; otherwise result is 3.

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

1⃣Определите вспомогательную функцию isValidAtomic(s), которая принимает строку s и возвращает True, если s является допустимым атомарным выражением. В противном случае функция возвращает False. Функция будет вызываться только с пятисимвольными строками. Если все следующие условия выполнены, функция возвращает True, иначе - False: s[0] является T или F. s[1] является ?. s[2] является T, F или цифрой от 0 до 9. s[3] является :. s[4] является T, F или цифрой от 0 до 9.

2⃣Определите вспомогательную функцию solveAtomic(s), которая принимает строку s и возвращает значение атомарного выражения. Значение атомарного выражения равно E1, если B - это T, иначе значение равно E2. Функция будет вызываться только с пятисимвольными строками и возвращать один символ:.

3⃣Если s[0] является T, функция возвращает s[2], иначе возвращает s[4]. В функции parseTernary(expression) уменьшайте выражение до тех пор, пока не останется односимвольная строка. Инициализируйте j как expression.size() - 1 (это будет самый правый индекс окна). Пока самое правое окно длиной 5 не является допустимым атомарным выражением, уменьшайте j на 1. Когда будет найдено самое правое допустимое атомарное выражение, решите его и уменьшите до одного символа. Замените самое правое допустимое атомарное выражение одним символом, после чего длина выражения уменьшится на 4. В итоге останется односимвольная строка, которую и верните.

😎 Решение:

class Solution {
    public String parseTernary(String expression) {
        boolean isValidAtomic(String s) {
            return s.charAt(0) == 'T' || s.charAt(0) == 'F' &&
                   s.charAt(1) == '?' &&
                   "TF0123456789".indexOf(s.charAt(2)) != -1 &&
                   s.charAt(3) == ':' &&
                   "TF0123456789".indexOf(s.charAt(4)) != -1;
        }

        char solveAtomic(String s) {
            return s.charAt(0) == 'T' ? s.charAt(2) : s.charAt(4);
        }

        while (expression.length() != 1) {
            int j = expression.length() - 1;
            while (!isValidAtomic(expression.substring(j-4, j+1))) {
                j -= 1;
            }
            expression = expression.substring(0, j-4) + solveAtomic(expression.substring(j-4, j+1)) + expression.substring(j+1);
        }

        return expression;
    }
}

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