Java | LeetCode

Задача: 971. Flip Binary Tree To Match Preorder Traversal Сложность: medium Дано корневое дерево с n узлами, где каждому узлу уникально присвоено значение от 1 до n. Также дана последовательность из n значений voyage, которая является желаемым обходом дерева в порядке pre-order. Любой узел в бинарном дереве можно перевернуть, поменяв местами его левое и правое поддеревья. Например, переворот узла 1 будет иметь следующий эффект: Переверните минимальное количество узлов, чтобы обход дерева в порядке pre-order соответствовал voyage. Верните список значений всех перевернутых узлов. Вы можете вернуть ответ в любом порядке. Если невозможно перевернуть узлы в дереве, чтобы сделать обход в порядке pre-order соответствующим voyage, верните список [-1]. Пример:

    
        Input: root = [1,2], voyage = [2,1]
Output: [-1]
Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.{}
    

👨‍💻 Алгоритм: 1⃣Выполните поиск в глубину. Если в каком-либо узле значение узла не соответствует значению в voyage, верните [-1]. 2⃣Иначе определите, когда нужно перевернуть: если следующее ожидаемое число в voyage (voyage[i]) отличается от следующего потомка. 3⃣Переверните узел, добавьте его значение в список перевернутых узлов и продолжите обход дерева, пока весь порядок обхода pre-order не будет соответствовать voyage. 😎 Решение:

    
        class Solution {
    List<Integer> flipped;
    int index;
    int[] voyage;

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        flipped = new ArrayList<>();
        index = 0;
        this.voyage = voyage;

        dfs(root);
        if (!flipped.isEmpty() && flipped.get(0) == -1) {
            flipped = new ArrayList<>(List.of(-1));
        }

        return flipped;
    }

    public void dfs(TreeNode node) {
        if (node != null) {
            if (node.val != voyage[index++]) {
                flipped = new ArrayList<>(List.of(-1));
                return;
            }

            if (index < voyage.length && node.left != null && node.left.val != voyage[index]) {
                flipped.add(node.val);
                dfs(node.right);
                dfs(node.left);
            } else {
                dfs(node.left);
                dfs(node.right);
            }
        }
    }
}{}
    

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

Задача: 960. Delete Columns to Make Sorted III Сложность: hard Вам дан массив из n строк strs, все одинаковой длины. Мы можем выбрать любые индексы для удаления, и мы удаляем все символы в этих индексах для каждой строки. Например, если у нас есть strs = ["abcdef","uvwxyz"] и индексы удаления {0, 2, 3}, то итоговый массив после удаления будет ["bef", "vyz"]. Предположим, мы выбрали набор индексов удаления answer таким образом, что после удаления итоговый массив имеет каждую строку (ряд) в лексикографическом порядке. (т.е. (strs[0][0] <= strs[0][1] <= ... <= strs[0][strs[0].length - 1]) и (strs[1][0] <= strs[1][1] <= ... <= strs[1][strs[1].length - 1]) и так далее). Верните минимально возможное значение answer.length. Пример:

    
        Input: strs = ["babca","bbazb"]
Output: 3
Explanation: After deleting columns 0, 1, and 4, the final array is strs = ["bc", "az"].
Both these rows are individually in lexicographic order (ie. strs[0][0] <= strs[0][1] and strs[1][0] <= strs[1][1]).
Note that strs[0] > strs[1] - the array strs is not necessarily in lexicographic order.{}
    

👨‍💻 Алгоритм: 1⃣Вместо поиска количества удаляемых столбцов, найдем количество столбцов, которые нужно сохранить. В конце мы можем вычесть это значение, чтобы получить желаемый ответ. 2⃣Используйте динамическое программирование, чтобы решить проблему. Пусть dp[k] будет количеством столбцов, которые сохраняются, начиная с позиции k. Мы будем искать максимальное значение dp[k], чтобы найти количество столбцов, которые нужно сохранить. 3⃣Итоговое количество удаляемых столбцов будет равно общей длине строк минус количество сохраненных столбцов. 😎 Решение:

    
        class Solution {
    public int minDeletionSize(String[] A) {
        int W = A[0].length();
        int[] dp = new int[W];
        Arrays.fill(dp, 1);
        for (int i = W-2; i >= 0; --i)
            search: for (int j = i+1; j < W; ++j) {
                for (String row: A)
                    if (row.charAt(i) > row.charAt(j))
                        continue search;

                dp[i] = Math.max(dp[i], 1 + dp[j]);
            }

        int kept = 0;
        for (int x: dp)
            kept = Math.max(kept, x);
        return W - kept;
    }
}{}
    

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

Задача: 459. Repeated Substring Pattern Сложность: easy Дана строка s, проверьте, может ли она быть построена путем взятия подстроки и добавления нескольких копий этой подстроки друг за другом. Пример:

    
        Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.{}
    

👨‍💻 Алгоритм: 1⃣Создайте целочисленную переменную n, равную длине строки s. 2⃣Итерация по всем префиксным подстрокам длины i от 1 до n/2: Если i делит n, объявите пустую строку pattern. Используйте внутренний цикл, который выполняется n/i раз для конкатенации подстроки, сформированной из первых i символов строки s. Если pattern равен s, вернуть true. 3⃣Если нет подстроки, которую можно повторить для формирования s, вернуть false. 😎 Решение:

    
        class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int i = 1; i <= n / 2; i++) {
            if (n % i == 0) {
                StringBuilder pattern = new StringBuilder();
                for (int j = 0; j < n / i; j++) {
                    pattern.append(s.substring(0, i));
                }
                if (s.equals(pattern.toString())) {
                    return true;
                }
            }
        }
        return false;
    }
}{}
    

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

Задача: 521. Longest Uncommon Subsequence I Сложность: easy Даны две строки a и b. Верните длину самой длинной несообщей подпоследовательности между a и b. Если такой несообщей подпоследовательности не существует, верните -1. Несообщая подпоследовательность между двумя строками — это строка, которая является подпоследовательностью только одной из них. Пример:

    
        Input: a = "aba", b = "cdc"
Output: 3
Explanation: One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc".
Note that "cdc" is also a longest uncommon subsequence.{}
    

👨‍💻 Алгоритм: 1⃣Если строка a равна строке b, верните -1, так как не существует несообщей подпоследовательности. 2⃣В противном случае: Вычислите длины строк a и b. 3⃣Вернуть длину более длинной строки. 😎 Решение:

    
        class Solution {
    public int findLUSlength(String a, String b) {
        if (a.equals(b)) {
            return -1;
        } else {
            return Math.max(a.length(), b.length());
        }
    }
}{}
    

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

Задача: CodeTestcaseTest ResultTest Result865. 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;
    }
}{}
    

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

Изучите HTML и CSS - бесплатно! Попробуйте бесплатно — освоите базу HTML & CSS, создадите свою первую веб страницу и поймете, стоит ли погружаться в IT глубже. Почему стоит попробовать? - Никакой воды — только практика - Проверь профессию до того, как вложить в обучение 150+ тыс. - Убедитесь, что код — это не страшно, даже если раньше не получалось А чтобы у вас все получилось, мы добавили бонусы: ✅ 8 пошаговых гайдов — от первого кода до первых заработков в IT. ✅ До 1500 монет за задания, которые можно обменять на дальнейшее обучение. ✅ Закрытый чат с наставником — получите ответы на все вопросы. ✅ Полезный IT-канал в Telegram — оставайтесь в теме после курса. ⚡ Главное — вы попробуете профессию разработчика! Попробовать #реклама 16+ learn.result-university.com О рекламодателе

Задача: 813. Largest Sum of Averages Сложность: medium Вам дан целочисленный массив nums и целое число k. Вы можете разбить массив на не более чем k непустых смежных подмассивов. Оценка разбиения равна сумме средних значений каждого подмассива. Обратите внимание, что при разбиении должны быть использованы все целые числа из nums, и что оценка не обязательно является целым числом. Верните максимальную оценку, которую можно достичь среди всех возможных разбиений. Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты. Пример:

    
        Input: nums = [9,1,2,3,9], k = 3
Output: 20.00000
Explanation: 
The best choice is to partition nums into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned nums into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.{}
    

👨‍💻 Алгоритм: 1⃣Пусть dp(i, k) будет лучшей оценкой для разбиения массива A[i:] на не более чем k частей. Если первая группа, в которую мы разбиваем A[i:], заканчивается перед j, тогда наше разбиение-кандидат имеет оценку average(i, j) + dp(j, k-1), где average(i, j) = (A[i] + A[i+1] + ... + A[j-1]) / (j - i) (деление с плавающей запятой). Мы берем наивысшую оценку из этих вариантов, помня, что разбиение необязательно - dp(i, k) также может быть просто average(i, N). 2⃣В общем случае наша рекурсия выглядит так: dp(i, k) = max(average(i, N), max_{j > i}(average(i, j) + dp(j, k-1))). Мы можем рассчитывать average немного быстрее, используя префиксные суммы. Если P[x+1] = A[0] + A[1] + ... + A[x], тогда average(i, j) = (P[j] - P[i]) / (j - i). 3⃣Наша реализация демонстрирует подход "снизу вверх" для динамического программирования. На шаге k во внешнем цикле, dp[i] представляет собой dp(i, k) из обсуждения выше, и мы рассчитываем следующий слой dp(i, k+1). Завершение второго цикла для i = 0..N-1 означает завершение расчета правильного значения для dp(i, t), а внутренний цикл выполняет расчет max_{j > i}(average(i, j) + dp(j, k)). 😎 Решение:

    
        class Solution {
    public double largestSumOfAverages(int[] A, int K) {
        int N = A.length;
        double[] P = new double[N + 1];
        for (int i = 0; i < N; ++i)
            P[i + 1] = P[i] + A[i];
        
        double[][] dp = new double[N][N];
        for (int i = 0; i < N; ++i)
            dp[i][0] = (P[N] - P[i]) / (N - i);
        
        for (int k = 0; k < K - 1; ++k) {
            for (int i = 0; i < N; ++i) {
                for (int j = i + 1; j < N; ++j) {
                    dp[i][0] = Math.max(dp[i][0], (P[j] - P[i]) / (j - i) + dp[j][0]);
                }
            }
        }
        
        return dp[0][0];
    }{}
    

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

Задача: 392. Is Subsequence Сложность: easy Даны две строки s и t. Верните true, если s является подпоследовательностью t, иначе верните false. Подпоследовательность строки — это новая строка, которая формируется из исходной строки путем удаления некоторых (возможно, ни одного) символов без нарушения относительных позиций оставшихся символов. (например, "ace" является подпоследовательностью "abcde", тогда как "aec" не является). Пример:

    
        Input: s = "abc", t = "ahbgdc"
Output: true{}
    

👨‍💻 Алгоритм: 1⃣Назначьте два указателя: левый для исходной строки и правый для целевой строки. Эти указатели будут использоваться для итерации по строкам и сравнения их символов. 2⃣Перемещайте указатели в зависимости от совпадения символов. Если символы на текущих позициях указателей совпадают, переместите оба указателя на один шаг вперед. Если символы не совпадают, переместите только правый указатель целевой строки. 3⃣Итерация завершается, когда один из указателей выходит за пределы своей строки. Если в конце итерации все символы исходной строки были найдены в целевой строке, исходная строка является подпоследовательностью целевой строки. 😎 Решение:

    
        class Solution {
    public boolean isSubsequence(String s, String t) {
        int leftBound = s.length(), rightBound = t.length();
        int pLeft = 0, pRight = 0;

        while (pLeft < leftBound && pRight < rightBound) {
            if (s.charAt(pLeft) == t.charAt(pRight)) {
                pLeft += 1;
            }
            pRight += 1;
        }
        return pLeft == leftBound;
    }
}{}
    

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

Дизайн в FIGMA с нуля. Бесплатный курс + портфолио Онлайн-программа с наставником и чатом. Дизайн от профессионалов. Доступ 0 руб. Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

Задача: 400. Nth Digit Сложность: medium Дано целое число n, вернуть n-ю цифру бесконечной последовательности чисел [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]. Пример:

    
        Input: n = 3
Output: 3{}
    

👨‍💻 Алгоритм: 1⃣Определение диапазона Начните с определения количества цифр в числах текущего диапазона (1-9, 10-99, 100-999 и т.д.). Уменьшайте значение n, вычитая количество цифр в текущем диапазоне, пока не найдете диапазон, в который попадает n-я цифра. 2⃣Нахождение конкретного числа Когда определите диапазон, найдите точное число, содержащее n-ю цифру. Определите индекс цифры в этом числе. 3⃣Возвращение n-й цифры Извлеките и верните n-ю цифру из найденного числа. 😎 Решение:

    
        class Solution {
    public int findNthDigit(int n) {
        int length = 1;
        long count = 9;
        int start = 1;
        
        while (n > length * count) {
            n -= length * count;
            length++;
            count *= 10;
            start *= 10;
        }
        
        start += (n - 1) / length;
        String s = Integer.toString(start);
        return s.charAt((n - 1) % length) - '0';
    }
}{}
    

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