Задача: 1026. Maximum Difference Between Node and Ancestor
Сложность: medium

Учитывая корень бинарного дерева, найдите максимальное значение v, для которого существуют различные вершины a и b, где v = |a.val - b.val| и a является предком b. Вершина a является предком b, если: любой ребенок a равен b или любой ребенок a является предком b.

Пример:

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7

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

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

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

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

😎 Решение:

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

public class Solution {
    public int maxAncestorDiff(TreeNode root) {
        return dfs(root, root.val, root.val);
    }
    
    private int dfs(TreeNode node, int minVal, int maxVal) {
        if (node == null) return maxVal - minVal;
        minVal = Math.min(minVal, node.val);
        maxVal = Math.max(maxVal, node.val);
        int left = dfs(node.left, minVal, maxVal);
        int right = dfs(node.right, minVal, maxVal);
        return Math.max(left, right);
    }
}

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

Задача: 644. Maximum Average Subarray II
Сложность: hard

Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого больше или равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.

Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000

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

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

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

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

😎 Решение:

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        int currSum = 0;
        for (int i = 0; i < k; i++) {
            currSum += nums[i];
        }
        int maxSum = currSum;
        for (int i = k; i < n; i++) {
            currSum += nums[i] - nums[i - k];
            if (currSum > maxSum) {
                maxSum = currSum;
            }
        }
        return maxSum / (double) k;
    }
}

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

Задача: 60. Permutation Sequence
Сложность: hard

Множество [1, 2, 3, ..., n] содержит в общей сложности n! уникальных перестановок.

Списком и маркировкой всех перестановок по порядку, мы получаем следующую последовательность для n = 3:

"123"
"132"
"213"
"231"
"312"
"321"
Дано n и k, верните k-ю перестановку последовательности.

Пример:

Input: n = 3, k = 3
Output: "213"

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

1⃣Сгенерируйте входной массив nums чисел от 1 до N.

2⃣Вычислите все факториальные основы от 0 до (N−1)!.

3⃣Уменьшите k на 1, чтобы значение попало в интервал (0, N!−1). Используйте коэффициенты факториалов для построения перестановки. Верните строку перестановки.

😎 Решение:

class Solution {
    public String getPermutation(int n, int k) {
        int[] factorials = new int[n];
        List<Integer> nums = new ArrayList() {{
            add(1);
        }};
        
        factorials[0] = 1;
        for (int i = 1; i < n; ++i) {
            factorials[i] = factorials[i - 1] * i;
            nums.add(i + 1);
        }

        --k;

        StringBuilder sb = new StringBuilder();
        for (int i = n - 1; i > -1; --i) {
            int idx = k / factorials[i];
            k -= idx * factorials[i];

            sb.append(nums.get(idx));
            nums.remove(idx);
        }
        return sb.toString();
    }
}

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

Задача: 1200. Minimum Absolute Difference
Сложность: easy

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

Верните список пар в порядке возрастания (по отношению к парам), каждая пара [a, b] следует условиям:
a, b из arr
a < b
b - a равна минимальной абсолютной разнице между любыми двумя элементами в arr

Пример:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

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

1⃣Инициализация вспомогательного массива:
Найдите минимальный элемент minElement и максимальный элемент maxElement в массиве arr.
Инициализируйте вспомогательный массив line размером maxElement - minElement + 1 и установите смещение shift равным -minElement.
Пройдите по массиву arr и для каждого элемента value увеличьте значение в индексе value + shift на 1.

2⃣Поиск минимальной абсолютной разницы:
Пройдите по вспомогательному массиву line, начиная с индекса, соответствующего минимальному элементу.
Проверьте значения на каждом индексе curr:
- если line[curr] равно 0, пропустите этот индекс.
- если line[curr] равно 1, сравните абсолютную разницу текущей пары currPairDiff с минимальной найденной разницей minPairDiff.
- если currPairDiff больше minPairDiff, продолжайте.
- если currPairDiff равно minPairDiff, добавьте эту пару в список ответов.
- если currPairDiff меньше minPairDiff, очистите список ответов, добавьте эту пару и обновите minPairDiff.

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

😎 Решение:

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        int minElement = arr[0];
        int maxElement = arr[0];
        for (int num : arr) {
            minElement = Math.min(minElement, num);
            maxElement = Math.max(maxElement, num);
        }
        int shift = -minElement;
        int[] line = new int[maxElement - minElement + 1];
        List<List<Integer>> answer = new ArrayList();

        for (int num : arr) {
            line[num + shift] = 1;
        }
        
        int minPairDiff = maxElement - minElement;
        int prev = 0;
        
        for (int curr = 1; curr <= maxElement + shift; ++curr) {
            if (line[curr] == 0) {
                continue;
            }
            
            if (curr - prev == minPairDiff) {       
                answer.add(Arrays.asList(prev - shift, curr - shift));
            } else if (curr - prev < minPairDiff) {
                answer = new ArrayList();
                minPairDiff = curr - prev;
                answer.add(Arrays.asList(prev - shift, curr - shift));                
            } 

            prev = curr;
        }  
        
        return answer;
    }
}

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

Задача: 1258. Synonymous Sentences
Сложность: medium

Вам дан список эквивалентных пар строк synonyms, где synonyms[i] = [si, ti] означает, что si и ti являются эквивалентными строками. Вам также дан текст предложения. Верните все возможные синонимичные предложения, отсортированные лексикографически.

Пример:

Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"
Output: ["I am cheerful today but was sad yesterday","I am cheerful today but was sorrow yesterday","I am happy today but was sad yesterday","I am happy today but was sorrow yesterday","I am joy today but was sad yesterday","I am joy today but was sorrow yesterday"]

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

1⃣Построить граф синонимов, используя структуру данных, такую как Union-Find или просто с использованием DFS/BFS.

2⃣Пройти по каждому слову в предложении и найти все возможные синонимы.
Сгенерировать все возможные комбинации предложений.

3⃣Отсортировать полученные предложения лексикографически.

😎 Решение:

import java.util.*;

public class Solution {
    public List<String> generateSentences(List<List<String>> synonyms, String text) {
        Map<String, Set<String>> graph = new HashMap<>();
        for (List<String> pair : synonyms) {
            graph.computeIfAbsent(pair.get(0), k -> new HashSet<>()).add(pair.get(1));
            graph.computeIfAbsent(pair.get(1), k -> new HashSet<>()).add(pair.get(0));
        }

        List<String> words = Arrays.asList(text.split(" "));
        List<List<String>> synonymGroups = new ArrayList<>();
        for (String word : words) {
            synonymGroups.add(new ArrayList<>(findSynonyms(graph, word)));
        }

        List<String> sentences = new ArrayList<>();
        generate(sentences, synonymGroups, new StringBuilder(), 0);
        Collections.sort(sentences);
        return sentences;
    }

    private Set<String> findSynonyms(Map<String, Set<String>> graph, String word) {
        Set<String> synonyms = new HashSet<>();
        Stack<String> stack = new Stack<>();
        stack.push(word);
        while (!stack.isEmpty()) {
            String w = stack.pop();
            if (synonyms.add(w)) {
                stack.addAll(graph.getOrDefault(w, Collections.emptySet()));
            }
        }
        return synonyms;
    }

    private void generate(List<String> sentences, List<List<String>> groups, StringBuilder sentence, int index) {
        if (index == groups.size()) {
            sentences.add(sentence.toString().trim());
            return;
        }
        int len = sentence.length();
        for (String word : groups.get(index)) {
            sentence.append(" ").append(word);
            generate(sentences, groups, sentence, index + 1);
            sentence.setLength(len);
        }
    }
}

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

Задача: 1295. Find Numbers with Even Number of Digits
Сложность: easy

Дан массив чисел nums. Верните количество чисел в массиве, которые содержат четное количество цифр.

Пример:

Input: nums = [12,345,2,6,7896]
Output: 2
Explanation: 
12 contains 2 digits (even number of digits). 
345 contains 3 digits (odd number of digits). 
2 contains 1 digit (odd number of digits). 
6 contains 1 digit (odd number of digits). 
7896 contains 4 digits (even number of digits). 
Therefore only 12 and 7896 contain an even number of digits.

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

1⃣Определите вспомогательную функцию hasEvenDigits, которая принимает num в качестве входных данных и возвращает true, если количество цифр четное, иначе возвращает false.

2⃣Внутри функции hasEvenDigits. Инициализируйте переменную digitCount значением 0. Пока num не равно нулю: Увеличивайте digitCount на 1. Делите num на 10. Возвращайте digitCount & 1 == 0.

3⃣В функции findNumbers. Инициализируйте переменную evenDigitCount значением 0. Для каждого числа num в массиве nums, проверяйте, возвращает ли hasEvenDigits(num) значение true. Если да, увеличивайте evenDigitCount на 1. Возвращайте evenDigitCount.

😎 Решение:

class Solution {
    private boolean hasEvenDigits(int num) {
        int digitCount = 0;
        while (num > 0) {
            digitCount++;
            num /= 10;
        }
        return (digitCount & 1) == 0;
    }

    public int findNumbers(int[] nums) {
        int evenDigitCount = 0;
        for (int num : nums) {
            if (hasEvenDigits(num)) {
                evenDigitCount++;
            }
        }
        return evenDigitCount;
    }
}

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

Задача: 865. Smallest Subtree with all the Deepest Nodes
Сложность: medium

Дан корень бинарного дерева, глубина каждого узла — это кратчайшее расстояние до корня.

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

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

Поддерево узла — это дерево, состоящее из этого узла и всех его потомков.

Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.

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

1⃣В первой фазе используем поиск в глубину (DFS), чтобы аннотировать узлы. Каждый узел будет хранить информацию о своей глубине и о самой большой глубине среди его потомков.

2⃣Во второй фазе также используем DFS для функции answer(node), которая возвращает наименьшее поддерево, содержащее все самые глубокие узлы. Функция сравнивает глубины левых и правых поддеревьев узла для определения наименьшего поддерева.

3⃣Функция answer(node) возвращает поддерево, которое содержит все самые глубокие узлы всего дерева, а не только рассматриваемого поддерева.

😎 Решение:

class Solution {
    Map<TreeNode, Integer> depth;
    int maxDepth;

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        depth = new HashMap<>();
        depth.put(null, -1);
        dfs(root, null);
        maxDepth = depth.values().stream().max(Integer::compare).orElse(-1);
        return answer(root);
    }

    private void dfs(TreeNode node, TreeNode parent) {
        if (node != null) {
            depth.put(node, depth.get(parent) + 1);
            dfs(node.left, node);
            dfs(node.right, node);
        }
    }

    private TreeNode answer(TreeNode node) {
        if (node == null || depth.get(node) == maxDepth) return node;
        TreeNode L = answer(node.left), R = answer(node.right);
        if (L != null && R != null) return node;
        return L != null ? L : R;
    }
}

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

Задача: 1230. Toss Strange Coins
Сложность: medium

У вас есть несколько монет. Вероятность выпадения орла для i-й монеты равна prob[i].

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

Пример:

Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125

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

1⃣Инициализация:
Создайте переменную n и инициализируйте её размером массива prob.
Создайте 2D массив dp размером n + 1 строк и target + 1 столбцов, где dp[i][j] хранит вероятность получить j орлов, используя первые i монет.
Установите базовый случай dp[0][0] = 1.

2⃣Итерация:
Используйте два вложенных цикла для заполнения массива dp.
Внешний цикл итерируется от i = 1 до n. Для каждого i установите dp[i][0], что обозначает вероятность получить 0 орлов при использовании i монет: dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1]).
Внутренний цикл итерируется от j = 1 до target. Для каждого j вычислите dp[i][j] по формуле: dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1]).

3⃣Возврат результата:
Верните значение dp[n][target], которое содержит искомую вероятность.

😎 Решение:

class Solution {
    public double probabilityOfHeads(double[] prob, int target) {
        int n = prob.length;
        double[][] dp = new double[n + 1][target + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1]);
            for (int j = 1; j <= target && j <= i; j++) {
                dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1]);
            }
        }

        return dp[n][target];
    }
}

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

Задача: 937. Reorder Data in Log Files
Сложность: medium

Вам дается массив журналов. Каждый журнал представляет собой строку слов, ограниченную пробелами, где первое слово является идентификатором. Существует два типа журналов: Буквенные журналы: Все слова (кроме идентификатора) состоят из строчных английских букв. Цифровые журналы: Все слова (кроме идентификатора) состоят из цифр. Упорядочите эти журналы таким образом: буквенные журналы идут перед всеми цифровыми журналами. Буквенные журналы сортируются лексикографически по их содержанию. Если их содержимое одинаково, то отсортируйте их лексикографически по их идентификаторам. Цифровые журналы сохраняют свой относительный порядок. Верните окончательный порядок журналов.

Пример:

Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]

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

1⃣Разделить журналы на буквенные и цифровые.

2⃣Отсортировать буквенные журналы:
Лексикографически по содержимому.
Если содержимое одинаково, отсортировать по идентификатору.
Объединить отсортированные буквенные журналы и цифровые журналы в исходном порядке.

3⃣Вернуть окончательный результат.

😎 Решение:

import java.util.Arrays;

class Solution {
    public String[] reorderLogFiles(String[] logs) {
        Arrays.sort(logs, (log1, log2) -> {
            String[] split1 = log1.split(" ", 2);
            String[] split2 = log2.split(" ", 2);
            boolean isDigit1 = Character.isDigit(split1[1].charAt(0));
            boolean isDigit2 = Character.isDigit(split2[1].charAt(0));
            
            if (!isDigit1 && !isDigit2) {
                int cmp = split1[1].compareTo(split2[1]);
                if (cmp != 0) return cmp;
                return split1[0].compareTo(split2[0]);
            }
            return isDigit1 ? 1 : -1;
        });
        return logs;
    }
}

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

Задача: 32. Longest Valid Parentheses
Сложность: hard

Дана строка, содержащая только символы '(' и ')'. Верните длину самой длинной подстроки с корректными (правильно сформированными) скобками.

Пример:

Input: s = "(()"
Output: 2

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

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

2⃣Каждый раз, когда мы встречаем символ ‘(’, мы кладём его в стек. Для каждого встреченного символа ‘)’ мы извлекаем из стека символ ‘(’. Если символ ‘(’ недоступен в стеке для извлечения в любой момент или если в стеке остались элементы после обработки всей подстроки, подстрока скобок является некорректной.

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

😎 Решение:

import java.util.Stack;

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push('(');
            } else if (!stack.isEmpty() && stack.peek() == '(') {
                stack.pop();
            } else {
                return false;
            }
        }
        return stack.isEmpty();
    }

    public int longestValidParentheses(String s) {
        int maxlen = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 2; j <= s.length(); j += 2) {
                String substring = s.substring(i, j);
                if (isValid(substring)) {
                    maxlen = Math.max(maxlen, j - i);
                }
            }
        }
        return maxlen;
    }
}

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

Задача: 269. Alien Dictionary
Сложность: hard

Есть новый инопланетный язык, который использует английский алфавит. Однако порядок букв в нем неизвестен.

Вам дан список строк words из словаря инопланетного языка. Утверждается, что строки в words отсортированы лексикографически по правилам этого нового языка.

Если это утверждение неверно и данное расположение строк в words не может соответствовать никакому порядку букв, верните "".

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

Пример:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

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

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

2⃣Подсчет числа входящих ребер:
Подсчитать количество входящих ребер (in-degree) для каждой буквы.
Построить исходящий список смежности и одновременно считать входящие ребра для каждой буквы.

3⃣Обход в ширину (BFS):
Инициализировать очередь буквами с нулевым in-degree.
Выполнять BFS, добавляя буквы в результат, когда их in-degree становится нулевым.
Продолжать до тех пор, пока очередь не станет пустой.
Проверить наличие циклов и вернуть результат.

😎 Решение:

import java.util.*;

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> adjList = new HashMap<>();
        Map<Character, Integer> inDegree = new HashMap<>();

        for (String word : words) {
            for (char c : word.toCharArray()) {
                inDegree.put(c, 0);
            }
        }

        for (int i = 0; i < words.length - 1; i++) {
            String firstWord = words[i];
            String secondWord = words[i + 1];
            for (int j = 0; j < Math.min(firstWord.length(), secondWord.length()); j++) {
                char c = firstWord.charAt(j);
                char d = secondWord.charAt(j);
                if (c != d) {
                    if (!adjList.containsKey(c)) {
                        adjList.put(c, new HashSet<>());
                    }
                    if (adjList.get(c).add(d)) {
                        inDegree.put(d, inDegree.get(d) + 1);
                    }
                    break;
                }
            }
            if (secondWord.length() < firstWord.length() && firstWord.startsWith(secondWord)) {
                return "";
            }
        }

        Queue<Character> queue = new LinkedList<>();
        for (Map.Entry<Character, Integer> entry : inDegree.entrySet()) {
            if (entry.getValue() == 0) {
                queue.add(entry.getKey());
            }
        }

        StringBuilder output = new StringBuilder();
        while (!queue.isEmpty()) {
            char c = queue.poll();
            output.append(c);
            if (adjList.containsKey(c)) {
                for (char d : adjList.get(c)) {
                    inDegree.put(d, inDegree.get(d) - 1);
                    if (inDegree.get(d) == 0) {
                        queue.add(d);
                    }
                }
            }
        }

        if (output.length() < inDegree.size()) {
            return "";
        }

        return output.toString();
    }
}

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

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

Если задан исходный массив arr, то каждый день вы создаете новый массив, используя массив предыдущего дня. В i-й день вы выполняете следующие операции над массивом дня i-1, чтобы получить массив дня i: если элемент меньше своего левого и правого соседа, то этот элемент увеличивается. Если элемент больше своего левого и правого соседа, то этот элемент уменьшается. Первый и последний элементы никогда не меняются. Через несколько дней массив не меняется. Верните этот окончательный массив.

Пример:

Input: arr = [6,2,3,4]
Output: [6,3,3,4]

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

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

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

3⃣Первый и последний элементы массива остаются неизменными.

😎 Решение:

import java.util.Arrays;

public class Solution {
    public int[] transformArray(int[] arr) {
        boolean changed;
        do {
            changed = false;
            int[] newArr = arr.clone();
            for (int i = 1; i < arr.length - 1; i++) {
                if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) {
                    newArr[i]++;
                    changed = true;
                } else if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
                    newArr[i]--;
                    changed = true;
                }
            }

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

Задача: 914. X of a Kind in a Deck of Cards
Сложность: easy

Вам дан целочисленный массив deck, где deck[i] - число, написанное на i-й карте. Разделите карты на одну или несколько групп так, чтобы: в каждой группе было ровно x карт, где x > 1, и на всех картах в одной группе было написано одно и то же целое число. Верните true, если такое разделение возможно, или false в противном случае.

Пример:

Input: deck = [1,2,3,4,4,3,2,1]
Output: true

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

1⃣Создать словарь для подсчета частоты каждого числа в массиве deck.

2⃣Найти наибольший общий делитель (НОД) всех частот.

3⃣Проверить, больше ли НОД 1, чтобы определить, можно ли разделить карты на группы.

😎 Решение:

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : deck) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        
        int g = count.values().stream().reduce(this::gcd).orElse(0);
        return g > 1;
    }
    
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}

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

Задача: 1480. Running Sum of 1d Array
Сложность: easy

Дан массив nums. Мы определяем текущую сумму массива как runningSum[i] = сумма(nums[0]…nums[i]).

Верните массив текущих сумм для nums.

Пример:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

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

1⃣Инициализация:
Определите массив result.
Инициализируйте первый элемент массива result первым элементом входного массива nums.

2⃣Вычисление текущих сумм:
На индексе i добавьте сумму элемента nums[i] и предыдущей текущей суммы result[i - 1] в массив result.

3⃣Повторение для всех индексов:
Повторите шаг 2 для всех индексов от 1 до n-1.

😎 Решение:

class Solution {
public int[] runningSum(int[] nums) {
        int[] result = new int[nums.length];

        result[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            result[i] = result[i - 1] + nums[i];
        }
        return result;
    }
}

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

Задача: 1463. Cherry Pickup II
Сложность: hard

Дана матрица grid размером rows x cols, представляющая поле с вишнями, где grid[i][j] обозначает количество вишен, которые можно собрать с клетки (i, j).

У вас есть два робота, которые могут собирать вишни:
Робот №1 находится в левом верхнем углу (0, 0), а
Робот №2 находится в правом верхнем углу (0, cols - 1).

Верните максимальное количество собранных вишен с помощью обоих роботов, следуя приведённым ниже правилам:
Из клетки (i, j) роботы могут перемещаться в клетку (i + 1, j - 1), (i + 1, j) или (i + 1, j + 1).
Когда любой робот проходит через клетку, он подбирает все вишни, и клетка становится пустой.
Когда оба робота находятся в одной клетке, только один из них собирает вишни.
Оба робота не могут выходить за пределы матрицы в любой момент времени.
Оба робота должны достичь нижней строки в матрице grid.

Пример:

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

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

1⃣Определите трехмерный массив dp, где dp[row][col1][col2] представляет максимальное количество вишен, которые можно собрать, если робот 1 находится в (row, col1), а робот 2 находится в (row, col2).

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

3⃣Верните dp[0][0][n-1], что представляет максимальное количество вишен, которое можно собрать, начиная с верхнего левого и верхнего правого углов.

😎 Решение:

class Solution {

    public int cherryPickup(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int dp[][][] = new int[m][n][n];

        for (int row = m - 1; row >= 0; row--) {
            for (int col1 = 0; col1 < n; col1++) {
                for (int col2 = 0; col2 < n; col2++) {
                    int result = 0;
                    result += grid[row][col1];
                    if (col1 != col2) {
                        result += grid[row][col2];
                    }
                    if (row != m - 1) {
                        int max = 0;
                        for (int newCol1 = col1 - 1; newCol1 <= col1 + 1; newCol1++) {
                            for (int newCol2 = col2 - 1; newCol2 <= col2 + 1; newCol2++) {
                                if (newCol1 >= 0 && newCol1 < n && newCol2 >= 0 && newCol2 < n) {
                                    max = Math.max(max, dp[row + 1][newCol1][newCol2]);
                                }
                            }
                        }
                        result += max;
                    }
                    dp[row][col1][col2] = result;
                }
            }
        }
        return dp[0][0][n - 1];
    }
}

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

Задача: 667. Beautiful Arrangement II
Сложность: medium

Даны два целых числа n и k, составьте список answer, содержащий n различных положительных чисел в диапазоне от 1 до n, который соответствует следующему требованию:

Предположим, что этот список answer = [a1, a2, a3, ... , an], тогда список [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] имеет ровно k различных чисел. Верните список answer. Если существует несколько допустимых ответов, верните любой из них.

Пример:

Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1

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

1⃣Инициализация списка:
Начните с создания списка от 1 до n: [1, 2, 3, ..., n].

2⃣Конструирование шаблона с k различиями:
Для обеспечения k различных значений разностей используйте следующий подход:
Включайте числа попеременно с конца и начала списка, начиная с n и 1, чтобы создать как можно больше уникальных разностей.
Если требуется меньше k, оставшиеся числа просто добавляйте в порядке возрастания, чтобы не увеличивать количество уникальных разностей.

3⃣Заполнение списка:
Заполните оставшуюся часть списка последовательными числами, чтобы сохранить уникальные числа в диапазоне от 1 до n.

😎 Решение:

public class Solution {
    public int[] constructArray(int n, int k) {
        int[] answer = new int[n];
        int left = 1, right = n;
        
        for (int i = 0; i <= k; i++) {
            if (i % 2 == 0) {
                answer[i] = left++;
            } else {
                answer[i] = right--;
            }
        }
        
        if (k % 2 == 0) {
            for (int i = k + 1; i < n; i++) {
                answer[i] = right--;
            }
        } else {
            for (int i = k + 1; i < n; i++) {
                answer[i] = left++;
            }
        }
        
        return answer;
    }
}

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

Задача: 1040. Moving Stones Until Consecutive II
Сложность: medium

Есть несколько камней, расположенных в разных позициях на оси X. Вам дан целочисленный массив stones - позиции камней. Назовите камень конечным, если он имеет наименьшую или наибольшую позицию. За один ход вы берете конечный камень и перемещаете его в незанятую позицию так, чтобы он перестал быть конечным. В частности, если камни находятся, скажем, в позиции stones = [1,2,5], вы не можете переместить конечный камень в позицию 5, поскольку перемещение его в любую позицию (например, 0 или 3) сохранит этот камень в качестве конечного. Игра заканчивается, когда вы не можете сделать больше ни одного хода (т.е, камни находятся в трех последовательных позициях). Возвращает целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сделать, а answer[1] - максимальное количество ходов, которое вы можете сделать.

Пример:

Input: stones = [7,4,9]
Output: [1,2]

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

1⃣Сортировка:
Сначала отсортируем массив камней.

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

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

😎 Решение:

import java.util.Arrays;

public class Solution {
    public int[] numMovesStonesII(int[] stones) {
        Arrays.sort(stones);
        int n = stones.length;
        
        int maxMoves = stones[n-1] - stones[0] + 1 - n;
        maxMoves -= Math.min(stones[1] - stones[0] - 1, stones[n-1] - stones[n-2] - 1);

        int minMoves = Integer.MAX_VALUE;
        int j = 0;

        for (int i = 0; i < n; ++i) {
            while (j < n && stones[j] - stones[i] + 1 <= n) {
                ++j;
            }
            int alreadyInWindow = j - i;
            if (alreadyInWindow == n - 1 && stones[j-1] - stones[i] + 1 == n - 1) {
                minMoves = Math.min(minMoves, 2);
            } else {
                minMoves = Math.min(minMoves, n - alreadyInWindow);
            }
        }

        return new int[] { minMoves, maxMoves };
    }
}

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

Задача: 423. Reconstruct Original Digits from English
Сложность: medium

Дана строка s, содержащая неупорядоченное английское представление цифр от 0 до 9, верните цифры в порядке возрастания.

Пример:

Input: s = "owoztneoer"
Output: "012"

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

1⃣Подсчитайте количество каждого символа в строке s с помощью хэш-таблицы или массива, чтобы определить количество каждого символа.

2⃣Используйте уникальные символы, присутствующие только в одном числе (например, 'z' для 0, 'w' для 2, 'u' для 4, 'x' для 6, 'g' для 8), чтобы определить количество этих цифр в строке. Затем определите количество остальных цифр, вычитая уже найденные цифры.

3⃣Соберите найденные цифры в строку в порядке возрастания и верните результат.

😎 Решение:

class Solution {
    public String originalDigits(String s) {
        int[] count = new char[26 + (int)'a'];
        for(char letter: s.toCharArray()) {
            count[letter]++;
        }

        int[] out = new int[10];
        out[0] = count['z'];
        out[2] = count['w'];
        out[4] = count['u'];
        out[6] = count['x'];
        out[8] = count['g'];
        out[3] = count['h'] - out[8];
        out[5] = count['f'] - out[4];
        out[7] = count['s'] - out[6];
        out[9] = count['i'] - out[5] - out[6] - out[8];
        out[1] = count['n'] - out[7] - 2 * out[9];

        StringBuilder output = new StringBuilder();
        for(int i = 0; i < 10; i++)
            for (int j = 0; j < out[i]; j++)
                output.append(i);
        return output.toString();
    }
}

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

Задача: 654. Maximum Binary Tree
Сложность: medium

Вам дан целочисленный массив nums без дубликатов. Из nums можно рекурсивно построить максимальное двоичное дерево, используя следующий алгоритм: создайте корневой узел, значение которого равно максимальному значению в nums. Рекурсивно постройте левое поддерево по префиксу подмассива слева от максимального значения. Рекурсивно постройте правое поддерево по суффиксу подмассива справа от максимального значения. Верните максимальное двоичное дерево, построенное из nums.

Пример:

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

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

1⃣Найдите максимальное значение в текущем подмассиве и создайте узел с этим значением.

2⃣Рекурсивно постройте левое поддерево для подмассива слева от максимального значения.

3⃣Рекурсивно постройте правое поддерево для подмассива справа от максимального значения.

😎 Решение:

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

public class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length);
    }

    private TreeNode build(int[] nums, int l, int r) {
        if (l == r) return null;
        int maxIndex = max(nums, l, r);
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = build(nums, l, maxIndex);
        root.right = build(nums, maxIndex + 1, r);
        return root;
    }

    private int max(int[] nums, int l, int r) {
        int maxIndex = l;
        for (int i = l + 1; i < r; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}

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

Задача: 1257. Smallest Common Region
Сложность: medium

Вам даны списки регионов, в которых первый регион каждого списка включает все остальные регионы этого списка. Естественно, если регион x содержит другой регион y, то x больше y. Также, по определению, регион x содержит сам себя. Даны два региона: region1 и region2, верните наименьший регион, который содержит их оба. Если вам даны регионы r1, r2 и r3 такие, что r1 включает r3, то гарантированно не существует r2 такого, что r2 включает r3. Гарантированно существует наименьший регион.

Пример:

Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"

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

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

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

3⃣Найдем последний общий регион в путях двух заданных регионов.

😎 Решение:

import java.util.*;

public class Solution {
    public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
        Map<String, String> parent = new HashMap<>();

        for (List<String> regionList : regions) {
            for (int i = 1; i < regionList.size(); i++) {
                parent.put(regionList.get(i), regionList.get(0));
            }
        }

        Set<String> ancestors1 = new HashSet<>();
        while (region1 != null) {
            ancestors1.add(region1);
            region1 = parent.get(region1);
        }

        while (!ancestors1.contains(region2)) {
            region2 = parent.get(region2);
        }

        return region2;
    }
}

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