Задача: 600. Non-negative Integers without Consecutive Ones
Сложность: hard

Дано положительное целое число n, верните количество чисел в диапазоне [0, n], бинарные представления которых не содержат последовательных единиц.

Пример:

Input: n = 5
Output: 5
Explanation:
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 

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

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

2⃣Чтобы проверить, существует ли 1 на позиции x (считая от младшего значащего бита), в текущем числе n, поступаем следующим образом. Сдвигаем двоичную 1 x−1 раз влево, чтобы получить число y, которое имеет 1 только на x-й позиции. Логическое И числа n и y даст результат 1 только если n содержит 1 на позиции x.

3⃣В конце подсчитываем и возвращаем количество чисел в диапазоне [0, n], не содержащих последовательных единиц.

😎 Решение:

public class Solution {
    public int findIntegers(int num) {
        int count = 0;
        for (int i = 0; i <= num; i++) {
            if (check(i)) {
                count++;
            }
        }
        return count;
    }

    public boolean check(int n) {
        int i = 31;
        while (i > 0) {
            if ((n & (1 << i)) != 0 && (n & (1 << (i - 1))) != 0) {
                return false;
            }
            i--;
        }
        return true;
    }
}

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

Задача: 1120. Maximum Average Subtree
Сложность: medium

Дан корень бинарного дерева. Верните максимальное среднее значение поддерева этого дерева. Ответы, отличающиеся от фактического ответа не более чем на 10^-5, будут приняты.

Поддерево дерева — это любой узел этого дерева плюс все его потомки.

Среднее значение дерева — это сумма его значений, деленная на количество узлов.

Пример:

Input: root = [5,6,1]
Output: 6.00000
Explanation: 
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.

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

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

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

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

😎 Решение:

class Solution {
    class State {
        int nodeCount;

        int valueSum;

        double maxAverage;

        State(int nodes, int sum, double maxAverage) {
            this.nodeCount = nodes;
            this.valueSum = sum;
            this.maxAverage = maxAverage;
        }
    }

    public double maximumAverageSubtree(TreeNode root) {
        return maxAverage(root).maxAverage;
    }

    State maxAverage(TreeNode root) {
        if (root == null) {
            return new State(0, 0, 0);
        }

        State left = maxAverage(root.left);
        State right = maxAverage(root.right);

        int nodeCount = left.nodeCount + right.nodeCount + 1;
        int sum = left.valueSum + right.valueSum + root.val;
        double maxAverage = Math.max(
                (1.0 * (sum)) / nodeCount,
                Math.max(right.maxAverage, left.maxAverage)
        );

        return new State(nodeCount, sum, maxAverage);
    }
}

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

Задача: 1002. Find Common Characters
Сложность: easy

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

Пример:

Input: words = ["bella","label","roller"]
Output: ["e","l","l"]

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

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

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

3⃣Формирование результата:
Создайте результирующий массив, добавляя каждый символ столько раз, сколько его минимальная частота.

😎 Решение:

public class Solution {
    public List<String> commonChars(String[] words) {
        int[] minFreq = new int[26];
        Arrays.fill(minFreq, Integer.MAX_VALUE);
        
        for (String word : words) {
            int[] freq = new int[26];
            for (char c : word.toCharArray()) {
                freq[c - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                minFreq[i] = Math.min(minFreq[i], freq[i]);
            }
        }
        
        List<String> result = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < minFreq[i]; j++) {
                result.add(Character.toString((char)('a' + i)));
            }
        }
        return result;
    }
}

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

Задача: 300. Longest Increasing Subsequence
Сложность: medium

Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности.

Пример:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

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

1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i.

2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1).

3⃣Верните максимальное значение из dp.

😎 Решение:

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;

        int[] dp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
        }

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int maxLength = 0;
        for (int length : dp) {
            maxLength = Math.max(maxLength, length);
        }

        return maxLength;
    }

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

Задача: 948. Bag of Tokens
Сложность: medium

Вы начинаете с начальной силой, равной power, начальным счетом 0 и мешком жетонов, представленным в виде целочисленного массива tokens, где каждый tokens[i] обозначает значение tokeni. Ваша цель - максимизировать общее количество очков, стратегически разыгрывая эти жетоны. За один ход вы можете разыграть неразыгранный жетон одним из двух способов (но не обоими для одного и того же жетона): лицом вверх: Если ваша текущая сила не меньше жетонов[i], вы можете сыграть токени, потеряв силу жетонов[i] и получив 1 очко. Лицом вниз: Если ваш текущий счет не меньше 1, вы можете сыграть токени, получив силу токенов[i] и потеряв 1 счет. Верните максимально возможный счет, который вы можете получить, сыграв любое количество токенов.

Пример:

Input: tokens = [100], power = 50

Output: 0

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

1⃣Отсортировать массив tokens.
Использовать два указателя: left и right, чтобы отслеживать начало и конец массива токенов.
Инициализировать переменные для текущей силы power, текущего счета score и максимального счета maxScore

2⃣Повторять следующие шаги, пока left не превысит right:
Если текущая сила power достаточна для разыгрывания токена tokens[left] лицом вверх, разыграть его и увеличить счет.
Если текущая сила недостаточна, но счет больше 0, разыграть токен tokens[right] лицом вниз и уменьшить счет.
Обновить максимальный счет, если текущий счет больше максимального.

3⃣Вернуть максимальный счет.

😎 Решение:

import java.util.Arrays;

class Solution {
    public int bagOfTokensScore(int[] tokens, int power) {
        Arrays.sort(tokens);
        int left = 0, right = tokens.length - 1;
        int score = 0, maxScore = 0;
        
        while (left <= right) {
            if (power >= tokens[left]) {
                power -= tokens[left];
                score++;
                left++;
                maxScore = Math.max(maxScore, score);
            } else if (score > 0) {
                power += tokens[right];
                score--;
                right--;
            } else {
                break;
            }
        }
        
        return maxScore;
    }
}

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

Задача: 100. Same Tree
Сложность: easy

Даны корни двух бинарных деревьев p и q. Напишите функцию, чтобы проверить, одинаковы ли они.

Два бинарных дерева считаются одинаковыми, если они структурно идентичны, и узлы имеют одинаковые значения.

Пример:

Input: p = [1,2,3], q = [1,2,3]
Output: true

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

1⃣Проверяем базовый случай: если оба узла p и q равны null, то они одинаковые.

2⃣Если один из узлов null, а другой нет — деревья различаются.

3⃣Если значения текущих узлов не совпадают — тоже возвращаем false. Иначе рекурсивно проверяем левое и правое поддерево.

😎 Решение:

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (q == null || p == null) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.right, q.right) && isSameTree(p.left, q.left);
    }
}

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

Задача: 299. Bulls and Cows
Сложность: medium

Вы играете в игру "Быки и коровы" со своим другом.

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

Количество "быков", то есть цифры в предположении, которые находятся на правильной позиции.
Количество "коров", то есть цифры в предположении, которые есть в вашем секретном числе, но находятся на неправильной позиции. Конкретно, это не-бычьи цифры в предположении, которые можно переставить так, чтобы они стали быками.
Дано секретное число secret и предположение вашего друга guess, верните подсказку для предположения вашего друга.

Подсказка должна быть в формате "xAyB", где x — количество быков, а y — количество коров. Обратите внимание, что и secret, и guess могут содержать повторяющиеся цифры.

Пример:

Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
  |
"7810"

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

1⃣Инициализация счетчиков:
Инициализируйте количество быков и коров значениями ноль.
Создайте хеш-таблицу для хранения символов строки secret и их частот.

2⃣Обход строки guess:
Для каждого символа ch в строке guess:
Если ch присутствует в строке secret:
Если текущий символ ch совпадает с символом на той же позиции в secret (ch == secret[idx]):
Увеличьте количество быков: bulls += 1.
Обновите количество коров, если количество текущего символа в хеш-таблице отрицательное или равно нулю (то есть этот символ уже использовался для коров): cows -= int(h[ch] <= 0).
Если текущий символ ch не совпадает с символом на той же позиции в secret (ch != secret[idx]):
Увеличьте количество коров, если количество текущего символа в хеш-таблице больше нуля: cows += int(h[ch] > 0).
Обновите хеш-таблицу, помечая текущий символ как использованный: h[ch] -= 1.

3⃣Возврат результата:
Верните количество быков и коров в формате "xAyB".

😎 Решение:

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

class Solution {
    public String getHint(String secret, String guess) {
        Map<Character, Integer> h = new HashMap<>();
        for (char ch : secret.toCharArray()) {
            h.put(ch, h.getOrDefault(ch, 0) + 1);
        }

        int bulls = 0;
        int cows = 0;
        int n = guess.length();
        char[] secretArray = secret.toCharArray();
        char[] guessArray = guess.toCharArray();

        for (int idx = 0; idx < n; idx++) {
            char ch = guessArray[idx];
            if (h.containsKey(ch)) {
                if (ch == secretArray[idx]) {
                    bulls++;
                    if (h.get(ch) <= 0) {
                        cows--;
                    }
                } else {
                    if (h.get(ch) > 0) {
                        cows++;
                    }
                }
                h.put(ch, h.get(ch) - 1);
            }
        }

        return bulls + "A" + cows + "B";
    }
}

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

Задача: 959. Regions Cut By Slashes
Сложность: medium

n x n сетка состоит из квадратов размером 1 x 1, где каждый квадрат 1 x 1 содержит '/', '', или пустое пространство ' '. Эти символы делят квадрат на смежные области.

Дана сетка grid, представленная в виде строкового массива. Верните количество областей.

Обратите внимание, что обратные слеши экранированы, поэтому '' представлен как '\'.

Пример:

Input: grid = [" /","/ "]
Output: 2

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

1⃣Создайте 4*N*N узлов для каждой ячейки сетки и соедините их в соответствии с описанием.

2⃣Используйте структуру объединения-поиска (DSU), чтобы найти количество связанных компонентов.

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

😎 Решение:

class Solution {
    public int regionsBySlashes(String[] grid) {
        int N = grid.length;
        DSU dsu = new DSU(4 * N * N);
        for (int r = 0; r < N; ++r)
            for (int c = 0; c < N; ++c) {
                int root = 4 * (r * N + c);
                char val = grid[r].charAt(c);
                if (val != '\\') {
                    dsu.union(root + 0, root + 1);
                    dsu.union(root + 2, root + 3);
                }
                if (val != '/') {
                    dsu.union(root + 0, root + 2);
                    dsu.union(root + 1, root + 3);
                }

                if (r + 1 < N)
                    dsu.union(root + 3, (root + 4 * N) + 0);
                if (r - 1 >= 0)
                    dsu.union(root + 0, (root - 4 * N) + 3);
                if (c + 1 < N)
                    dsu.union(root + 2, (root + 4) + 1);
                if (c - 1 >= 0)
                    dsu.union(root + 1, (root - 4) + 2);
            }

        int ans = 0;
        for (int x = 0; x < 4 * N * N; ++x) {
            if (dsu.find(x) == x)
                ans++;
        }

        return ans;
    }
}

class DSU {
    int[] parent;
    public DSU(int N) {
        parent = new int[N];
        for (int i = 0; i < N; ++i)
            parent[i] = i;
    }
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    public void union(int x, int y) {
        parent[find(x)] = find(y);
    }
}

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

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

Бинарное дерево является одноценным, если каждый узел в дереве имеет одинаковое значение.

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

Пример:

Input: root = [1,1,1,1,1,null,1]
Output: true

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

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

2⃣Проверьте, что все значения в списке одинаковы.

3⃣Если все значения одинаковы, верните true, иначе верните false.

😎 Решение:

class Solution {
    List<Integer> vals;
    public boolean isUnivalTree(TreeNode root) {
        vals = new ArrayList();
        dfs(root);
        for (int v: vals)
            if (v != vals.get(0))
                return false;
        return true;
    }

    public void dfs(TreeNode node) {
        if (node != null) {
            vals.add(node.val);
            dfs(node.left);
            dfs(node.right);
        }
    }
}

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

Задача: 417. Pacific Atlantic Water Flow
Сложность: medium

Имеется прямоугольный остров размером m x n, который граничит с Тихим и Атлантическим океанами. Тихий океан касается левого и верхнего краев острова, а Атлантический океан - правого и нижнего краев. Остров разбит на сетку квадратных ячеек. Вам дана целочисленная матрица heights размером m x n, где heights[r][c] - высота над уровнем моря клетки с координатами (r, c). На острове выпадает много осадков, и дождевая вода может стекать в соседние клетки прямо на север, юг, восток и запад, если высота соседней клетки меньше или равна высоте текущей клетки. Вода может течь из любой клетки, прилегающей к океану, в океан. Верните двумерный список координат сетки result, где result[i] = [ri, ci] означает, что дождевая вода может течь из клетки (ri, ci) как в Тихий, так и в Атлантический океаны.

Пример:

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

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

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

2⃣Выполните поиск для каждого океана, обновляя матрицы достижимости.

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

😎 Решение:

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

public class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for (int i = 0; i < m; i++) {
            dfs(i, 0, pacific, heights, directions);
            dfs(i, n - 1, atlantic, heights, directions);
        }
        for (int j = 0; j < n; j++) {
            dfs(0, j, pacific, heights, directions);
            dfs(m - 1, j, atlantic, heights, directions);
        }
        
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    List<Integer> cell = new ArrayList<>();
                    cell.add(i);
                    cell.add(j);
                    result.add(cell);
                }
            }
        }
        return result;
    }
    
    private void dfs(int r, int c, boolean[][] ocean, int[][] heights, int[][] directions) {
        ocean[r][c] = true;
        for (int[] dir : directions) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr >= 0 && nc >= 0 && nr < heights.length && nc < heights[0].length && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                dfs(nr, nc, ocean, heights, directions);
            }
        }
    }
}

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

Задача: №29. Divide Two Integers
Сложность: medium

Даны два целых числа dividend и divisor.
Выполните деление без использования операторов *, /, %.
Результат должен быть усечён до целого и находиться в пределах 32-битного целого числа.

Пример:

Input: dividend = 10, divisor = 3 Output: 3
Input: dividend = 7, divisor = -3 Output: -2

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

1⃣Определить знак результата и привести dividend и divisor к положительным значениям типа long, чтобы избежать переполнения и упростить работу с отрицательными числами.

2⃣Найти максимальное кратное делителя (удваивая divisor и счётчик divide), не превышающее dividend.

3⃣Рекурсивно вызвать деление для остатка dividend - sum, сложить с текущим divide и вернуть результат с учётом знака.

😎 Решение:

public class Solution {
    public int divide(int dividend, int divisor) {
        long result = divideLong(dividend, divisor);
        return result > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)result;
    }

    private long divideLong(long dividend, long divisor) {
        boolean negative = dividend < 0 != divisor < 0;

        dividend = Math.abs(dividend);
        divisor = Math.abs(divisor);

        if (dividend < divisor) return 0;

        long sum = divisor;
        long divide = 1;
        while ((sum + sum) <= dividend) {
            sum += sum;
            divide += divide;
        }

        long remaining = divideLong(dividend - sum, divisor);
        return negative ? -(divide + remaining) : (divide + remaining);
    }
}

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

Задача: 727. Minimum Window Subsequence
Сложность: hard

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

Пример:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"

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

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

2⃣Поддерживайте счетчики для символов в текущем окне и требуемых символов из s2.

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

😎 Решение:

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

public class Solution {
    public String minWindow(String s1, String s2) {
        if (s1.isEmpty() || s2.isEmpty()) {
            return "";
        }

        Map<Character, Integer> dictT = new HashMap<>();
        for (char c : s2.toCharArray()) {
            dictT.put(c, dictT.getOrDefault(c, 0) + 1);
        }

        int required = dictT.size();
        int l = 0, r = 0, formed = 0;
        Map<Character, Integer> windowCounts = new HashMap<>();
        int[] ans = {Integer.MAX_VALUE, 0, 0};

        while (r < s1.length()) {
            char c = s1.charAt(r);
            windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);

            if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
                formed++;
            }

            while (l <= r && formed == required) {
                c = s1.charAt(l);

                if (r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }

                windowCounts.put(c, windowCounts.get(c) - 1);
                if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
                    formed--;
                }

                l++;
            }

            r++;
        }

        return ans[0] == Integer.MAX_VALUE ? "" : s1.substring(ans[1], ans[2] + 1);
    }
}

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

Задача: 285. Inorder Successor in BST
Сложность: medium

Дан корень бинарного дерева поиска и узел p в нем. Верните преемника этого узла в порядке возрастания в бинарном дереве поиска (BST). Если у данного узла нет преемника в порядке возрастания в дереве, верните null.

Преемник узла p — это узел с наименьшим ключом, который больше p.val.

Пример:

Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

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

1⃣Определение переменных класса:
Определите две переменные класса: previous и inorderSuccessorNode. Переменная previous будет использоваться при обработке второго случая, а inorderSuccessorNode будет содержать результат, который нужно вернуть.

2⃣Обработка двух случаев:
В функции inorderSuccessor сначала проверьте, какой из двух случаев нужно обработать, проверяя наличие правого дочернего элемента.
Правый дочерний элемент существует:
- присвойте правый дочерний элемент узлу leftmost и итерируйтесь, пока не достигнете узла (leftmost), у которого нет левого дочернего элемента. Итерируйте, присваивая leftmost = leftmost.left, пока не получите левый узел в поддереве.
Правый дочерний элемент не существует:
- определите функцию inorderCase2 и передайте ей узел и узел p.
- выполните простой обход в порядке возрастания: сначала рекурсируйте на левый дочерний элемент узла.
- когда рекурсия вернется, проверьте, равна ли переменная класса previous узлу p. Если это так, значит p является предшественником узла, или, другими словами, узел является преемником узла p. Назначьте inorderSuccessorNode узлу и вернитесь из функции.
- наконец, верните inorderSuccessorNode как результат.

3⃣Итерация и обновление:
В функции inorderCase2 обновляйте previous текущим узлом и продолжайте рекурсировать на правый дочерний элемент.

😎 Решение:

class Solution {
    
    private TreeNode previous;
    private TreeNode inorderSuccessorNode;
    
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (p.right != null) {
            
            TreeNode leftmost = p.right;
            
            while (leftmost.left != null) {
                leftmost = leftmost.left;
            }
            this.inorderSuccessorNode = leftmost;
        } else {
            this.inorderCase2(root, p);
        }
        return this.inorderSuccessorNode;
    }
    
    private void inorderCase2(TreeNode node, TreeNode p) {
        if (node == null) {
            return;
        }
        
        this.inorderCase2(node.left, p);
        
        if (this.previous == p && this.inorderSuccessorNode == null) {
            this.inorderSuccessorNode = node;
            return;
        }
        
        this.previous = node;
        this.inorderCase2(node.right, p);
    }
}

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

Задача: 1413. Minimum Value to Get Positive Step by Step Sum
Сложность: easy

Дан массив целых чисел nums, вы начинаете с начального положительного значения startValue.

На каждой итерации вы вычисляете поэтапную сумму startValue плюс элементы из nums (слева направо).

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

Пример:

Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
step by step sum
startValue = 4 | startValue = 5 | nums
  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
  (4 +2 ) = 6  | (5 +2 ) = 7    |   2

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

1⃣Инициализируйте переменные startValue со значением 1 и total со значением startValue.

2⃣Итеративно добавляйте каждый элемент массива nums к total и проверяйте, не опускается ли total ниже 1.

3⃣Если total падает ниже 1, увеличьте startValue на 1 и повторите шаги 2-3. Если total остается не менее 1, верните текущее значение startValue.

😎 Решение:

class Solution {
    public int minStartValue(int[] nums) {
        int startValue = 1;

        while (true) {
            int total = startValue;
            boolean isValid = true;

            for (int num : nums) {
                total += num;

                if (total < 1) {
                    isValid = false;
                    break;
                }
            }

            if (isValid) {
                return startValue;
            } else {
                startValue += 1;
            }
        }
    }
}

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

Задача: 143. Reorder List
Сложность: medium

Вам дана голова односвязного списка. Список можно представить в следующем виде:

L0 → L1 → … → Ln - 1 → Ln

Переупорядочите список так, чтобы он принял следующую форму:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

Вы не можете изменять значения в узлах списка. Можно изменять только сами узлы.

Пример:

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

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

1⃣Нахождение середины списка и разделение его на две части:
Используйте два указателя, slow и fast, для нахождения середины списка. Указатель slow движется на один узел за шаг, а fast — на два узла. Когда fast достигает конца списка, slow окажется в середине.
Разделите список на две части. Первая часть начинается от головы списка до slow, вторая — с узла после slow до конца списка.

2⃣Реверс второй половины списка:
Инициализируйте указатели prev как NULL и curr как slow. Перемещайтесь по второй половине списка и меняйте направление ссылок между узлами для реверсирования списка.
Продолжайте, пока не перестроите весь второй сегмент, теперь последний элемент первой части списка будет указывать на NULL, а prev станет новой головой второй половины списка.

3⃣Слияние двух частей списка в заданном порядке:
Начните с головы первой части списка (first) и головы реверсированной второй части (second).
Перекрестно связывайте узлы из первой и второй части, вставляя узлы из второй части между узлами первой части. Передвигайте указатели first и second соответственно после каждой вставки.
Продолжайте этот процесс до тех пор, пока узлы второй части не закончатся.

😎 Решение:

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;

        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode prev = null, curr = slow, tmp;
        while (curr != null) {
            tmp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tmp;
        }

        ListNode first = head, second = prev;
        while (second.next != null) {
            tmp = first.next;
            first.next = second;
            first = tmp;

            tmp = second.next;
            second.next = first;
            second = tmp;
        }
    }
}

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

Задача: 1370. Increasing Decreasing String
Сложность: easy

Дана строка s. Переставьте символы строки, используя следующий алгоритм:

Выберите наименьший символ из s и добавьте его к результату.
Выберите наименьший символ из s, который больше последнего добавленного символа, и добавьте его.
Повторяйте шаг 2, пока не сможете выбрать больше символов.
Выберите наибольший символ из s и добавьте его к результату.
Выберите наибольший символ из s, который меньше последнего добавленного символа, и добавьте его.
Повторяйте шаг 5, пока не сможете выбрать больше символов.
Повторяйте шаги с 1 по 6, пока не выберете все символы из s.
На каждом этапе, если наименьший или наибольший символ появляется более одного раза, вы можете выбрать любое его вхождение и добавить его к результату.

Верните результирующую строку после сортировки s с помощью этого алгоритма.

Пример:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

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

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

3⃣Проверка завершения:
Повторяйте шаги 2 и 3, пока не будут добавлены все символы из строки s в result.

😎 Решение:

import java.util.*;

public class Solution {
    public String sortString(String s) {
        int[] charCount = new int[26];
        for (char c : s.toCharArray()) {
            charCount[c - 'a']++;
        }
        
        StringBuilder result = new StringBuilder();
        while (result.length() < s.length()) {
            for (char c = 'a'; c <= 'z'; c++) {
                if (charCount[c - 'a'] > 0) {
                    result.append(c);
                    charCount[c - 'a']--;
                }
            }
            for (char c = 'z'; c >= 'a'; c--) {
                if (charCount[c - 'a'] > 0) {
                    result.append(c);
                    charCount[c - 'a']--;
                }
            }
        }
        
        return result.toString();
    }
}

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

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

Запутанное число - это число, которое при повороте на 180 градусов становится другим числом, каждая цифра которого действительна. Мы можем повернуть цифры числа на 180 градусов, чтобы получить новые цифры. Когда 0, 1, 6, 8 и 9 поворачиваются на 180 градусов, они становятся 0, 1, 9, 8 и 6 соответственно.
При повороте на 180 градусов 2, 3, 4, 5 и 7 становятся недействительными. Обратите внимание, что после поворота числа мы можем игнорировать ведущие нули. Например, после поворота 8000 мы получим 0008, которое считается просто 8. Если задано целое число n, верните true, если это запутанное число, или false в противном случае.

Пример:

Input: n = 6
Output: true

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

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

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

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

😎 Решение:

public class Solution {
    public boolean isConfusingNumber(int n) {
        String nStr = String.valueOf(n);
        StringBuilder rotatedStr = new StringBuilder();
        Map<Character, Character> rotationMap = Map.of(
            '0', '0', '1', '1', '6', '9', '8', '8', '9', '6'
        );

        for (char ch : nStr.toCharArray()) {
            if (!rotationMap.containsKey(ch)) {
                return false;
            }
            rotatedStr.insert(0, rotationMap.get(ch));
        }

        return !nStr.equals(rotatedStr.toString());
    }
}

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

Задача: 896. Monotonic Array
Сложность: easy

Массив является монотонным, если он либо монотонно возрастает, либо монотонно убывает. Массив nums является монотонно возрастающим, если для всех i <= j, nums[i] <= nums[j]. Массив nums является монотонно убывающим, если для всех i <= j, nums[i] >= nums[j]. Если задан целочисленный массив nums, верните true, если данный массив монотонный, или false в противном случае.

Пример:

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

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

1⃣Определить два флага: increasing и decreasing.

2⃣Пройтись по массиву:
Если текущий элемент больше следующего, установить increasing в false.
Если текущий элемент меньше следующего, установить decreasing в false.

3⃣Вернуть true, если хотя бы один из флагов true, иначе вернуть false.

😎 Решение:

class Solution {
    public boolean isMonotonic(int[] nums) {
        boolean increasing = true, decreasing = true;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) decreasing = false;
            if (nums[i] < nums[i - 1]) increasing = false;
        }
        return increasing || decreasing;
    }
}

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

Задача: 1305. All Elements in Two Binary Search Trees
Сложность: medium

Даны два бинарных дерева поиска root1 и root2. Вернуть список, содержащий все целые числа из обоих деревьев, отсортированные в порядке возрастания.

Пример:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

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

1⃣Выполните итеративный обход в порядке возрастания обоих деревьев параллельно.

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

3⃣Верните выходной список.

😎 Решение:

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    fun getAllElements(root1: TreeNode?, root2: TreeNode?): List<Int> {
        val stack1 = ArrayDeque<TreeNode>()
        val stack2 = ArrayDeque<TreeNode>()
        val output = mutableListOf<Int>()
        var root1 = root1
        var root2 = root2

        while (root1 != null

root2 != null

stack1.isNotEmpty() || stack2.isNotEmpty()) {
            while (root1 != null) {
                stack1.push(root1)
                root1 = root1.left
            }
            while (root2 != null) {
                stack2.push(root2)
                root2 = root2.left
            }
            if (stack2.isEmpty() || (stack1.isNotEmpty() && stack1.peek().`val` <= stack2.peek().`val`)) {
                root1 = stack1.pop()
                output.add(root1.`val`)
                root1 = root1.right
            } else {
                root2 = stack2.pop()
                output.add(root2.`val`)
                root2 = root2.right
            }
        }
        return output
    }
}

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

Задача: 839. Similar String Groups
Сложность: hard

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

Например, "tars" и "rats" похожи (замена на позициях 0 и 2), и "rats" и "arts" похожи, но "star" не похожа на "tars", "rats" или "arts".
Эти строки образуют две связанные группы по сходству: {"tars", "rats", "arts"} и {"star"}. Обратите внимание, что "tars" и "arts" находятся в одной группе, хотя они не похожи друг на друга. Формально, каждая группа такова, что слово находится в группе, если и только если оно похоже хотя бы на одно другое слово в группе.

Вам дан список строк strs, где каждая строка в списке является анаграммой каждой другой строки в списке. Сколько групп существует?

Пример:

Input: strs = ["tars","rats","arts","star"]
Output: 2

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

1⃣Создайте переменную n, хранящую количество слов в strs, и создайте экземпляр UnionFind размера n.

2⃣Для любых двух слов на индексах i и j, которые ведут себя как узлы, проверьте, являются ли слова strs[i] и strs[j] похожими, и выполните операции find и union для объединения различных компонентов в один, если слова похожи.

3⃣Верните количество оставшихся групп.

😎 Решение:

class UnionFind {
    int[] parent;
    int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        for (int i = 0; i < size; i++)
            parent[i] = i;
        rank = new int[size];
    }

    public int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    public void union_set(int x, int y) {
        int xset = find(x), yset = find(y);
        if (xset == yset) {
            return;
        } else if (rank[xset] < rank[yset]) {
            parent[xset] = yset;
        } else if (rank[xset] > rank[yset]) {
            parent[yset] = xset;
        } else {
            parent[yset] = xset;
            rank[xset]++;
        }
    }
}

class Solution {
    public boolean isSimilar(String a, String b) {
        int diff = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                diff++;
            }
        }
        return diff == 0 || diff == 2;
    }

    public int numSimilarGroups(String[] strs) {
        int n = strs.length;
        UnionFind dsu = new UnionFind(n);
        int count = n;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isSimilar(strs[i], strs[j]) && dsu.find(i) != dsu.find(j)) {
                    count--;
                    dsu.union_set(i, j);
                }
            }
        }

        return count;
    }
}

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