Задача: 720. Longest Word in Dictionary
Сложность: medium

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

Пример:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"

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

1⃣Отсортируйте массив слов по длине и лексикографическому порядку.

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

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

😎 Решение:

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

public class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> validWords = new HashSet<>();
        validWords.add("");
        String longest = "";
        for (String word : words) {
            if (validWords.contains(word.substring(0, word.length() - 1))) {
                validWords.add(word);
                if (word.length() > longest.length()) {
                    longest = word;
                }
            }
        }
        return longest;
    }
}

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

Задача: 1535. Find the Winner of an Array Game
Сложность: medium

Дан целочисленный массив arr из различных целых чисел и целое число k.

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

Верните число, которое выиграет игру.

Гарантируется, что у игры будет победитель.

Пример:

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

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

1⃣Инициализируйте maxElement как максимальный элемент в arr, queue как очередь с элементами массива, кроме первого, curr = arr[0] и winstreak = 0.

2⃣Пока очередь не пуста (или используйте бесконечный цикл), извлеките opponent из начала очереди. Если curr > opponent, добавьте opponent в конец очереди и увеличьте winstreak на 1. В противном случае добавьте curr в конец очереди, установите curr = opponent и winstreak = 1.

3⃣Если winstreak = k или curr = maxElement, верните curr. Код никогда не должен достигать этой точки, так как гарантированно есть победитель. Верните любое значение.

😎 Решение:

class Solution {
    public int getWinner(int[] arr, int k) {
        int maxElement = arr[0];
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i < arr.length; i++) {
            maxElement = Math.max(maxElement, arr[i]);
            queue.offer(arr[i]);
        }
        
        int curr = arr[0];
        int winstreak = 0;
        
        while (!queue.isEmpty()) {
            int opponent = queue.poll();
            
            if (curr > opponent) {
                queue.offer(opponent);
                winstreak++;
            } else {
                queue.offer(curr);
                curr = opponent;
                winstreak = 1;
            }
            
            if (winstreak == k || curr == maxElement) {
                return curr;
            }
        }
        
        return -1;
    }
}

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

Задача: 730. Count Different Palindromic Subsequences
Сложность: hard

Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi.

Пример:

Input: s = "bccb"
Output: 6

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

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

2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j.

3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок.

😎 Решение:

public class Solution {
    public int countPalindromicSubsequences(String s) {
        int MOD = 1000000007;
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    int l = i + 1, r = j - 1;
                    while (l <= r && s.charAt(l) != s.charAt(i)) l++;
                    while (l <= r && s.charAt(r) != s.charAt(j)) r--;
                    if (l > r) {
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
                    } else if (l == r) {
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1];
                    }
                } else {
                    dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
                }
                dp[i][j] = (dp[i][j] + MOD) % MOD;
            }
        }

        return dp[0][n - 1];
    }
}

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

Задача: 682. Baseball Game
Сложность: medium

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

Вам дается список строк operations, где operations[i] — это i-я операция, которую вы должны применить к записи, и она может быть одной из следующих:

Целое число x.
Записать новый счет, равный x.
'+'.
Записать новый счет, который является суммой двух предыдущих очков.
'D'.
Записать новый счет, который в два раза больше предыдущего очка.
'C'.
Аннулировать предыдущее очко, удалив его из записи.
Верните сумму всех очков в записи после применения всех операций.

Тестовые случаи сформированы таким образом, что ответ и все промежуточные вычисления умещаются в 32-битное целое число, и что все операции корректны.

Пример:

Input: ops = ["5","2","C","D","+"]
Output: 30
Explanation:
"5" - Add 5 to the record, record is now [5].
"2" - Add 2 to the record, record is now [5, 2].
"C" - Invalidate and remove the previous score, record is now [5].
"D" - Add 2 * 5 = 10 to the record, record is now [5, 10].
"+" - Add 5 + 10 = 15 to the record, record is now [5, 10, 15].
The total sum is 5 + 10 + 15 = 30.

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

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

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

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

😎 Решение:

class Solution {
    public int calPoints(String[] ops) {
        Stack<Integer> stack = new Stack<>();

        for (String op : ops) {
            if (op.equals("+")) {
                int top = stack.pop();
                int newTop = top + stack.peek();
                stack.push(top);
                stack.push(newTop);
            } else if (op.equals("C")) {
                stack.pop();
            } else if (op.equals("D")) {
                stack.push(2 * stack.peek());
            } else {
                stack.push(Integer.valueOf(op));
            }
        }

        int ans = 0;
        for (int score : stack) {
            ans += score;
        }
        return ans;
    }
}

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

Задача: 811. Subdomain Visit Count
Сложность: medium

Веб-сайт с доменом "discuss.leetcode.com" состоит из различных поддоменов. На верхнем уровне у нас есть "com", на следующем уровне - "leetcode.com", и на самом нижнем уровне - "discuss.leetcode.com". Когда мы посещаем домен, такой как "discuss.leetcode.com", мы также автоматически посещаем родительские домены "leetcode.com" и "com".

Домен с парным счетчиком - это домен, который имеет один из двух форматов "rep d1.d2.d3" или "rep d1.d2", где rep - это количество посещений домена, а d1.d2.d3 - это сам домен.

Например, "9001 discuss.leetcode.com" - это домен с парным счетчиком, указывающий на то, что discuss.leetcode.com был посещен 9001 раз.
Дан массив доменов с парными счетчиками cpdomains, верните массив доменов с парными счетчиками для каждого поддомена во входных данных. Вы можете вернуть ответ в любом порядке.

Пример:

Input: cpdomains = ["9001 discuss.leetcode.com"]
Output: ["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
Explanation: We only have one website domain: "discuss.leetcode.com".
As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

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

1⃣Следуем указаниям из условия задачи.

2⃣Для адреса вида a.b.c, подсчитываем a.b.c, b.c и c. Для адреса вида x.y, подсчитываем x.y и y.

3⃣Для подсчета этих строк используем хеш-таблицу. Для разделения строк на требуемые части используем библиотечные функции split.

😎 Решение:

import java.util.*;

class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        Map<String, Integer> ans = new HashMap<>();
        for (String domain : cpdomains) {
            String[] parts = domain.split(" ");
            int count = Integer.parseInt(parts[0]);
            String[] frags = parts[1].split("\\.");
            for (int i = 0; i < frags.length; i++) {
                String subdomain = String.join(".", Arrays.copyOfRange(frags, i, frags.length));
                ans.put(subdomain, ans.getOrDefault(subdomain, 0) + count);
            }
        }
        List<String> res = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : ans.entrySet()) {
            res.add(entry.getValue() + " " + entry.getKey());
        }
        return res;
    }

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

Задача: 908. Smallest Range I
Сложность: easy

Вам дан целочисленный массив nums и целое число k. За одну операцию вы можете выбрать любой индекс i, где 0 <= i < nums.length, и изменить nums[i] на nums[i] + x, где x - целое число из диапазона [-k, k]. Эту операцию можно применять не более одного раза для каждого индекса i. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после применения указанной операции не более одного раза для каждого индекса в нем.

Пример:

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

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

1⃣Найти минимальное и максимальное значения массива nums.

2⃣Рассчитать потенциальные новые минимальные и максимальные значения после применения операции.

3⃣Вычислить минимальную оценку, сравнивая разницу между всеми возможными новыми минимальными и максимальными значениями.

😎 Решение:

class Solution {
    public int smallestRangeI(int[] nums, int k) {
        int minVal = Integer.MAX_VALUE;
        int maxVal = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num < minVal) minVal = num;
            if (num > maxVal) maxVal = num;
        }
        return Math.max(0, (maxVal - k) - (minVal + k));
    }
}

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

Задача: 421. Maximum XOR of Two Numbers in an Array
Сложность: medium

Дан целочисленный массив nums, верните максимальный результат nums[i] XOR nums[j], где 0 <= i <= j < n.

Пример:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

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

1⃣Вычислите количество битов L для использования. Это длина максимального числа в двоичном представлении. Инициализируйте max_xor = 0.

2⃣Запустите цикл от i = L−1 до i = 0 (от самого левого бита L−1 до самого правого бита 0):
Сдвигайте max_xor влево, чтобы освободить следующий бит.
Инициализируйте переменную curr_xor = max_xor | 1, установив 1 в самом правом бите max_xor. Теперь проверьте, можно ли выполнить curr_xor, используя доступные префиксы.

3⃣Вычислите все возможные префиксы длины L−i, итерируя по nums:
Поместите в HashSet префиксы префикс текущего числа длиной L−i: num >> i.
Итерируйте по всем префиксам и проверьте, можно ли выполнить curr_xor, используя два из них: p1 ^ p2 == curr_xor. Используя свойство самопреобразования XOR p1 ^ p2 ^ p2 = p1, можно переписать это как p1 == curr_xor ^ p2 и просто проверить для каждого p, если curr_xor ^ p есть в префиксах. Если так, установите max_xor равным curr_xor, т.е. установите 1-бит в самом правом бите. В противном случае, пусть max_xor оставит 0-бит в самом правом бите.

😎 Решение:

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

public class Solution {
    public int findMaximumXOR(int[] nums) {
        int maxNum = nums[0];
        for (int num : nums) maxNum = Math.max(maxNum, num);
        int L = (Integer.toBinaryString(maxNum)).length();

        int maxXor = 0, currXor;
        Set<Integer> prefixes = new HashSet<>();
        for (int i = L - 1; i > -1; --i) {
            maxXor <<= 1;
            currXor = maxXor | 1;
            prefixes.clear();
            for (int num : nums) prefixes.add(num >> i);
            for (int p : prefixes) {
                if (prefixes.contains(currXor ^ p)) {
                    maxXor = currXor;
                    break;
                }
            }
        }
        return maxXor;
    }
}

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

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

Дано корневое дерево двоичного поиска и нижняя и верхняя границы как low и high. Обрежьте дерево так, чтобы все его элементы лежали в диапазоне [low, high]. Обрезка дерева не должна изменять относительную структуру элементов, которые останутся в дереве (то есть любой потомок узла должен оставаться потомком). Можно доказать, что существует единственный ответ.

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

Пример:

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

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

1⃣Если node.val > high, то обрезанное двоичное дерево должно находиться слева от узла.

2⃣Если node.val < low, то обрезанное двоичное дерево должно находиться справа от узла.

3⃣В противном случае обрезаем обе стороны дерева.

😎 Решение:

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

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

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

Задача: 589. N-ary Tree Preorder Traversal
Сложность: easy

Дан корень N-арного дерева, верните значения его узлов в порядке предварительного (preorder) обхода.

Сериализация ввода N-арного дерева представлена в их обходе уровнями. Каждая группа детей разделена значением null (См. примеры).

Пример:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

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

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

2⃣Итеративный обход
Пока stack не пуст, извлекайте узел из stack и добавляйте его значение в output. Разверните список дочерних узлов текущего узла и добавьте их в stack.

3⃣Возврат результата
Верните список output как результат.

😎 Решение:

class Solution {
    public List<Integer> preorder(Node root) {
        LinkedList<Node> stack = new LinkedList<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }

        stack.add(root);
        while (!stack.isEmpty()) {
            Node node = stack.pollLast();
            output.add(node.val);
            Collections.reverse(node.children);
            for (Node item : node.children) {
                stack.add(item);
            }
        }
        return output;
    }
    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val,List<Node> _children) {
            val = _val;
            children = _children;
        }
    }
}

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

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

Дан массив целых чисел nums. Верните true, если существуют такие три индекса (i, j, k), что i < j < k и nums[i] < nums[j] < nums[k]. Если таких индексов не существует, верните false.

Пример:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

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

1⃣Инициализация переменных:
Создайте две переменные first_num и second_num и установите их значение на максимальное целое значение (Integer.MAX_VALUE или аналогичный максимум для выбранного языка программирования). Эти переменные будут хранить минимальные значения, необходимые для проверки существования возрастающей тройки.

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

3⃣Возврат результата:
Если после завершения итерации по массиву не была найдена возрастающая тройка, верните false.

😎 Решение:

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int first_num = Integer.MAX_VALUE;
        int second_num = Integer.MAX_VALUE;
        for (int n: nums) {
            if (n <= first_num) {
                first_num = n;
            } else if (n <= second_num) {
                second_num = n;
            } else {
                return true;
            }
        }
        return false;
    }
}

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

Задача: 978. Longest Turbulent Subarray
Сложность: medium

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

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

Более формально, подмассив [arr[i], arr[i + 1], ..., arr[j]] массива arr считается турбулентным тогда и только тогда, когда:

Для всех i <= k < j:
arr[k] > arr[k + 1], когда k нечетное, и
arr[k] < arr[k + 1], когда k четное.
Или, для всех i <= k < j:
arr[k] > arr[k + 1], когда k четное, и
arr[k] < arr[k + 1], когда k нечетное.

Пример:

Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

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

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

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

3⃣Повторяйте шаг 2 до конца массива и верните максимальную длину турбулентного подмассива.

😎 Решение:

class Solution {
    public int maxTurbulenceSize(int[] A) {
        int N = A.length;
        int ans = 1;
        int anchor = 0;

        for (int i = 1; i < N; ++i) {
            int c = Integer.compare(A[i - 1], A[i]);
            if (c == 0) {
                anchor = i;
            } else if (i == N - 1 || c * Integer.compare(A[i], A[i + 1]) != -1) {
                ans = Math.max(ans, i - anchor + 1);
                anchor = i;
            }
        }

        return ans;
    }
}

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

Задача: 1248. Count Number of Nice Subarrays
Сложность: medium

Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.

Пример:

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

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

1⃣Преобразуйте массив чисел nums, заменив все чётные числа на 0, а все нечётные числа на 1.

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

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

😎 Решение:

public class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }

    private int atMost(int[] nums, int k) {
        int res = 0, left = 0, count = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] % 2 == 1) count++;
            while (count > k) {
                if (nums[left++] % 2 == 1) count--;
            }
            res += right - left + 1;
        }
        return res;
    }
}

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

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

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

        memo.put(index, ans);

        return ans;
    }
}

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

Пример:

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

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

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

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

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

Решение:

import java.util.*;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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