Java | LeetCode

Задача: 250. Count Univalue Subtrees
Сложность: medium

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

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

Пример:

Input: root = [5,1,5,5,5,null,5]
Output: 4

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

1⃣Создайте целочисленную переменную count для подсчета количества поддеревьев с одинаковыми значениями. Инициализируйте её значением 0.

2⃣Выполните обход в глубину (DFS) для данного бинарного дерева. Выполните dfs(root), где dfs — это рекурсивный метод, который принимает узел TreeNode в качестве параметра, от которого начинается обход. Метод возвращает логическое значение, указывающее, является ли поддерево, укоренённое в этом узле, поддеревом с одинаковыми значениями. Выполните следующие действия в этом методе:
Если узел равен null, верните true.
Рекурсивно проверьте, образует ли левый потомок поддерево с одинаковыми значениями. Выполните isLeftUniValue = dfs(node.left).
Рекурсивно проверьте, образует ли правый потомок поддерево с одинаковыми значениями. Выполните isRightUniValue = dfs(node.right).
Если оба потомка образуют поддеревья с одинаковыми значениями, т.е. isLeftUniValue && isRightUniValue равно true, сравните значения потомков узла со значением самого узла. Если левый потомок существует и node.left.val != node.val, верните false, так как значения не совпадают и мы не имеем поддерева с одинаковыми значениями. Аналогично, если правый потомок существует и node.right.val != node.val, верните false. В противном случае, увеличьте count на 1 и верните true.
В противном случае, одно или оба поддерева потомков не образуют поддеревья с одинаковыми значениями, поэтому дерево, укоренённое в node, также не может быть таким поддеревом. Верните false.

3⃣Верните count.

😎 Решение:

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

class Solution {
    private int count = 0;

    private boolean dfs(TreeNode node) {
        if (node == null) {
            return true;
        }

        boolean isLeftUniValue = dfs(node.left);
        boolean isRightUniValue = dfs(node.right);

        if (isLeftUniValue && isRightUniValue) {
            if (node.left != null && node.left.val != node.val) {
                return false;
            }
            if (node.right != null && node.right.val != node.val) {
                return false;
            }
            count++;
            return true;
        }
        return false;
    }

    public int countUnivalSubtrees(TreeNode root) {
        dfs(root);
        return count;
    }
}

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

Задача: 684. Redundant Connection
Сложность: medium

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

Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе.

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

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

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

1⃣Для каждого ребра (u, v) создайте представление графа с использованием списка смежности. Это позволит легко выполнять обход в глубину (DFS) для проверки соединений между узлами.

2⃣Выполняйте обход в глубину для каждого ребра, временно удаляя его из графа. Проверьте, можно ли соединить узлы u и v с помощью обхода в глубину. Если узлы остаются соединенными, значит, это ребро является дублирующимся.

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

😎 Решение:

class Solution {
    Set<Integer> seen = new HashSet<>();
    int MAX_EDGE_VAL = 1000;

    public int[] findRedundantConnection(int[][] edges) {
        ArrayList<Integer>[] graph = new ArrayList[MAX_EDGE_VAL + 1];
        for (int i = 0; i <= MAX_EDGE_VAL; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int[] edge : edges) {
            seen.clear();
            if (!graph[edge[0]].isEmpty() && !graph[edge[1]].isEmpty() &&
                    dfs(graph, edge[0], edge[1])) {
                return edge;
            }
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        throw new AssertionError();
    }

    public boolean dfs(ArrayList<Integer>[] graph, int source, int target) {
        if (!seen.contains(source)) {
            seen.add(source);
            if (source == target) return true;
            for (int nei : graph[source]) {
                if (dfs(graph, nei, target)) return true;
            }
        }
        return false;
    }
}

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

Задача: 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;
    }
}

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

Задача: 1506. Find Root of N-Ary Tree
Сложность: medium

Вам даны все узлы N-арного дерева в виде массива объектов Node, где каждый узел имеет уникальное значение.

Верните корень N-арного дерева.

Пример:

Input: tree = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]
Explanation: The tree from the input data is shown above.
The driver code creates the tree and gives findRoot the Node objects in an arbitrary order.
For example, the passed array could be [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)] or [Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)].
The findRoot function should return the root Node(1), and the driver code will serialize it and compare with the input data.
The input data and serialized Node(1) are the same, so the test passes.

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

1⃣Используйте хэшсет (named as seen) для отслеживания всех посещенных дочерних узлов. В конечном итоге корневой узел не будет в этом множестве.

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

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

😎 Решение:

class Solution {
    public Node findRoot(List<Node> tree) {
        HashSet<Integer> seen = new HashSet<Integer>();

        for (Node node : tree) {
            for (Node child : node.children) {
                seen.add(child.val);
            }
        }

        Node root = null;
        for (Node node : tree) {
            if (!seen.contains(node.val)) {
                root = node;
                break;
            }
        }
        return root;
    }
}

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

Задача: 112. Path Sum
Сложность: easy

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

Лист — это узел без детей.

Пример:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

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

1⃣Инициализация стека: Начать с помещения в стек корневого узла и соответствующей оставшейся суммы, равной sum - root.val.

2⃣Обработка узлов: Извлечь текущий узел из стека и вернуть True, если оставшаяся сумма равна 0 и узел является листом.

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

😎 Решение:

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;

        LinkedList<TreeNode> node_stack = new LinkedList();
        LinkedList<Integer> sum_stack = new LinkedList();
        node_stack.add(root);
        sum_stack.add(sum - root.val);

        TreeNode node;
        int curr_sum;
        while (!node_stack.isEmpty()) {
            node = node_stack.pollLast();
            curr_sum = sum_stack.pollLast();
            if (
                (node.right == null) && (node.left == null) && (curr_sum == 0)
            ) return true;

            if (node.right != null) {
                node_stack.add(node.right);
                sum_stack.add(curr_sum - node.right.val);
            }
            if (node.left != null) {
                node_stack.add(node.left);
                sum_stack.add(curr_sum - node.left.val);
            }
        }
        return false;
    }
}

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

Задача: 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;
    }
}

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

Задача: 74. Search a 2D Matrix
Сложность: medium

Вам дана матрица из целых чисел размером m на n с следующими двумя свойствами:

Каждая строка отсортирована в порядке неубывания.
Первое число каждой строки больше последнего числа предыдущей строки.
Дано целое число target. Верните true, если target присутствует в матрице, и false в противном случае.

Вы должны написать решение с временной сложностью O(log(m * n)).

Пример:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

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

1⃣Инициализируйте индексы слева и справа: left = 0 и right = m x n - 1.

2⃣Пока left <= right:
Выберите индекс посередине виртуального массива в качестве опорного индекса: pivot_idx = (left + right) / 2.

3⃣Индекс соответствует row = pivot_idx // n и col = pivot_idx % n в исходной матрице, и, следовательно, можно получить pivot_element. Этот элемент делит виртуальный массив на две части.
Сравните pivot_element и target, чтобы определить, в какой части нужно искать target.

😎 Решение:

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (m == 0) return false;
        int n = matrix[0].length;

        int left = 0, right = m * n - 1;
        int pivotIdx, pivotElement;
        while (left <= right) {
            pivotIdx = (left + right) / 2;
            pivotElement = matrix[pivotIdx / n][pivotIdx % n];
            if (target == pivotElement) return true;
            else {
                if (target < pivotElement) right = pivotIdx - 1;
                else left = pivotIdx + 1;
            }
        }
        return false;
    }
}

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

Задача: №30. Substring with Concatenation of All Words
Сложность: hard

Дана строка s и массив строк words, все слова одинаковой длины.
Нужно найти все стартовые индексы подстрок в s, которые являются конкатенацией всех слов из массива (в любом порядке и без повторов).
Верните список индексов, где такие подстроки начинаются.

Пример:

Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9]

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

1⃣Создать карту частот mapOfWords для слов из words, а также массив arr для подсчета символов всех слов (предварительная фильтрация).

2⃣Использовать скользящее окно длиной totalLen = k * words.length, где k — длина одного слова. На каждом шаге сравнивать текущую подстроку с шаблоном.

3⃣Проверить:
- Совпадают ли символы (arr стал нулевым по всем позициям).
- Можно ли разбить подстроку на слова, соответствующие words, без нарушений частоты и порядка.

😎 Решение:

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> answer = new ArrayList<>();
        HashMap<String, Integer> mapOfWords = new HashMap<>();
        for (String word : words) mapOfWords.put(word, mapOfWords.getOrDefault(word, 0) + 1);

        int k = words[0].length();
        int n = words.length * k;
        int sLen = s.length();
        if (sLen < n) return answer;

        int[] arr = new int[26];
        for (String word : words) {
            for (int i = 0; i < k; i++) {
                arr[word.charAt(i) - 'a']++;
            }
        }

        int start = 0, end = n - 1;
        for (int i = 0; i <= end; i++) arr[s.charAt(i) - 'a']--;

        while (end < s.length() - 1) {
            if (allZeros(arr) && validWords(s.substring(start, end + 1), new HashMap<>(mapOfWords), k)) {
                answer.add(start);
            }
            arr[s.charAt(start++) - 'a']++;
            arr[s.charAt(++end) - 'a']--;
        }

        if (allZeros(arr) && validWords(s.substring(start, end + 1), new HashMap<>(mapOfWords), k)) {
            answer.add(start);
        }

        return answer;
    }

    public boolean allZeros(int[] arr) {
        return Arrays.stream(arr).allMatch(i -> i == 0);
    }

    public boolean validWords(String s, HashMap<String, Integer> mapOfWords, int k) {
        for (int i = 0; i * k < s.length(); i++) {
            String current = s.substring(i * k, (i + 1) * k);
            if (!mapOfWords.containsKey(current) || mapOfWords.get(current) == 0) return false;
            mapOfWords.put(current, mapOfWords.get(current) - 1);
        }
        return true;
    }
}

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

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

Дан узел в двоичном дереве поиска, верните его последующего (in-order successor) в этом дереве. Если у узла нет последующего, верните null.

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

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

Пример:

Input: tree = [5,3,6,2,4,null,null,1], node = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

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

1⃣Проверка правого поддерева
Если у узла есть правый потомок, перейдите к правому узлу, затем спускайтесь влево до самого нижнего узла. Этот узел будет следующим узлом в порядке in-order.

2⃣Поиск предка
Если у узла нет правого потомка, поднимайтесь по дереву до тех пор, пока узел не станет левым потомком своего родителя. Родитель этого узла будет следующим узлом в порядке in-order.

3⃣Возвращение результата
Верните найденный узел или null, если следующий узел не найден.

😎 Решение:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

class Solution {
  public Node inorderSuccessor(Node x) {
    if (x.right != null) {
      x = x.right;
      while (x.left != null) x = x.left;
      return x;
    }

    while (x.parent != null && x == x.parent.right) x = x.parent;
    return x.parent;
  }
}

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

Задача: 942. DI String Match
Сложность: easy

Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] может быть представлена в виде строки s длины n, где: s[i] == 'I', если perm[i] < perm[i + 1], и s[i] == 'D', если perm[i] > perm[i + 1]. Получив строку s, восстановите перестановку perm и верните ее. Если существует несколько допустимых перестановок perm, верните любую из них.

Пример:

Input: s = "IDID"
Output: [0,4,1,3,2]

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

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

2⃣Создать массив perm длиной n + 1.
Пройти по строке s:
Если текущий символ равен 'I', добавить low в текущую позицию perm и увеличить low.
Если текущий символ равен 'D', добавить high в текущую позицию perm и уменьшить high.
Добавить оставшееся значение (low или high, так как они будут равны) в последнюю позицию perm.

3⃣Вернуть массив perm.

😎 Решение:

class Solution {
    public int[] diStringMatch(String s) {
        int n = s.length();
        int low = 0, high = n;
        int[] perm = new int[n + 1];
        
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'I') {
                perm[i] = low++;
            } else {
                perm[i] = high--;
            }
        }
        
        perm[n] = low;
        return perm;
    }
}

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

        return ans;
    }

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

        return ans;
    }

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

        return ans;
    }

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

Задача: 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;
    }
}

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

Задача: 628. Maximum Product of Three Numbers
Сложность: easy

Задав целочисленный массив nums, найдите три числа, произведение которых максимально, и верните максимальное произведение.

Пример:

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

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

1⃣Отсортируйте массив nums.

2⃣Найдите два возможных максимальных произведения: Произведение трех наибольших элементов массива. Произведение двух наименьших (отрицательных) и одного наибольшего элемента массива.

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

😎 Решение:

import java.util.Arrays;

public class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int max1 = nums[n - 1] * nums[n - 2] * nums[n - 3];
        int max2 = nums[0] * nums[1] * nums[n - 1];
        return Math.max(max1, max2);
    }
}

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

Задача: 501. Find Mode in Binary Search Tree
Сложность: easy

Дано корень бинарного дерева поиска (BST) с дубликатами. Необходимо вернуть все моды (т.е. самые часто встречающиеся элементы) в этом дереве.
Если в дереве более одной моды, верните их в любом порядке.

Предположим, что BST определяется следующим образом:
Левое поддерево узла содержит только узлы с ключами, меньшими или равными ключу этого узла.
Правое поддерево узла содержит только узлы с ключами, большими или равными ключу этого узла.
Оба поддерева также должны быть бинарными деревьями поиска.

Пример:

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

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

1⃣Обход дерева
Выполните обход дерева (inorder DFS) с использованием рекурсивной функции dfs, чтобы пройти по всем узлам дерева. На каждом узле добавьте node.val в список values.

2⃣Поиск мод
Инициализируйте переменные maxStreak, currStreak, currNum как 0 и пустой список ans. Пройдите по списку values. Для каждого числа num: если num равно currNum, увеличьте currStreak. Иначе, установите currStreak равным 1, а currNum равным num. Если currStreak больше maxStreak, обновите maxStreak и сбросьте ans. Если currStreak равен maxStreak, добавьте num в ans.

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

😎 Решение:

class Solution {
    public int[] findMode(TreeNode root) {
        List<Integer> values = new ArrayList();
        dfs(root, values);

        int maxStreak = 0;
        int currStreak = 0;
        int currNum = 0;
        List<Integer> ans = new ArrayList();

        for (int num : values) {
            if (num == currNum) {
                currStreak++;
            } else {
                currStreak = 1;
                currNum = num;
            }
            
            if (currStreak > maxStreak) {
                ans = new ArrayList();
                maxStreak = currStreak;
            }
            
            if (currStreak == maxStreak) {
                ans.add(num);
            }
        }
        
        int[] result = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            result[i] = ans.get(i);
        }
        
        return result;
    }
    
    public void dfs(TreeNode node, List<Integer> values) {
        if (node == null) {
            return;
        }
        
        dfs(node.left, values);
        values.add(node.val);
        dfs(node.right, values);
    }
}

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

Задача: 845. Longest Mountain in Array
Сложность: medium

Вы можете вспомнить, что массив arr является горным массивом тогда и только тогда, когда:
длина массива arr >= 3
Существует индекс i (счёт начинается с 0) такой, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан целочисленный массив arr, верните длину самой длинной подпоследовательности, которая является горной. Верните 0, если такой подпоследовательности нет.

Пример:

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

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

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

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

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

😎 Решение:

class Solution {
    public int longestMountain(int[] A) {
        int N = A.length;
        int ans = 0, base = 0;
        while (base < N) {
            int end = base;
            if (end + 1 < N && A[end] < A[end + 1]) {
                while (end + 1 < N && A[end] < A[end + 1]) end++;

                if (end + 1 < N && A[end] > A[end + 1]) {
                    while (end + 1 < N && A[end] > A[end + 1]) end++;
                    ans = Math.max(ans, end - base + 1);
                }
            }

            base = Math.max(end, base + 1);
        }

        return ans;
    }
}

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

Задача: 1464. Maximum Product of Two Elements in an Array
Сложность: easy

Дан массив целых чисел nums, выберите два разных индекса i и j этого массива. Верните максимальное значение (nums[i]-1)*(nums[j]-1).

Пример:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. 

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

1⃣Инициализируйте biggest = 0 и secondBiggest = 0.

2⃣Итерируйте по каждому элементу массива nums:
Если текущий элемент больше biggest, обновите secondBiggest = biggest и biggest = текущий элемент.
Иначе обновите secondBiggest, если текущий элемент больше secondBiggest.

3⃣Верните (biggest - 1) * (secondBiggest - 1).

😎 Решение:

class Solution {
    public int maxProduct(int[] nums) {
        int biggest = 0;
        int secondBiggest = 0;
        for (int num : nums) {
            if (num > biggest) {
                secondBiggest = biggest;
                biggest = num;
            } else {
                secondBiggest = Math.max(secondBiggest, num);
            }
        }
        
        return (biggest - 1) * (secondBiggest - 1);
    }
}

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

Задача: 767. Reorganize String
Сложность: medium

Дана строка s, переставьте символы строки s так, чтобы любые два соседних символа не были одинаковыми.

Верните любую возможную перестановку строки s или верните "", если это невозможно.

Пример:

Input: s = "aab"
Output: "aba"

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

1⃣Инициализируйте пустой список ans для хранения переставленных символов. Создайте приоритетную очередь pq, используя структуру данных кучи. Каждый элемент в pq — это кортеж, содержащий количество символов и сам символ. Приоритетная очередь упорядочена так, что элементы с большим количеством имеют более высокий приоритет.

2⃣Извлеките элемент с наивысшим приоритетом из pq. Присвойте его количество и символ переменным count_first и char_first соответственно. Если ans пуст или текущий символ char_first отличается от последнего символа в ans, добавьте char_first в ans. Если количество char_first не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Перейдите к следующей итерации.

3⃣В противном случае, если char_first совпадает с последним символом в ans, нужно выбрать другой символ. Если pq пуста, верните пустую строку, так как переставить символы невозможно. Извлеките следующий элемент из pq, присвоив его количество и символ переменным count_second и char_second соответственно. Добавьте char_second в ans. Если количество char_second не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Наконец, поместите оригинальный char_first обратно в pq. Верните переставленные символы как строку, объединив элементы в ans.

😎 Решение:

import java.util.*;

class Solution {
    public String reorganizeString(String s) {
        int[] charCounts = new int[26];
        for (char c : s) {
            charCounts[c - 'a']++;
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int i = 0; i < 26; i++) {
            if (charCounts[i] > 0) {
                pq.add(new int[]{charCounts[i], i + 'a'});
            }
        }
        
        StringBuilder result = new StringBuilder();
        while (!pq.isEmpty()) {
            int[] first = pq.poll();
            if (result.length() == 0 || first[1] != result.charAt(result.length() - 1)) {
                result.append((char)first[1]);
                if (--first[0] > 0) {
                    pq.add(first);
                }
            } else {
                if (pq.isEmpty()) {
                    return "";
                }
                int[] second = pq.poll();
                result.append((char)second[1]);
                if (--second[0] > 0) {
                    pq.add(second);
                }
                pq.add(first);
            }
        }

        return result.toString();
    }
}

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

Задача: 201. Bitwise AND of Numbers Range
Сложность: medium

Даны два целых числа left и right, которые представляют диапазон [left, right], верните побитовое И всех чисел в этом диапазоне включительно.

Пример:

Input: left = 5, right = 7
Output: 4

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

1⃣Сдвигать left и right вправо, пока они не станут равными.

2⃣Подсчитать количество сдвигов.

3⃣Сдвинуть left влево на количество сдвигов и вернуть результат.

😎 Решение:

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m < n) {
            m >>= 1;
            n >>= 1;
            ++shift;
        }
        return m << shift;
    }
}

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

Задача: 168. Excel Sheet Column Title
Сложность: easy

Дано целое число columnNumber, верните соответствующий заголовок столбца, как он отображается в таблице Excel.

Например:
A -> 1
B -> 2
C -> 3
Z -> 26
AA -> 27
AB -> 28

Пример:

Input: columnNumber = 1
Output: "A"

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

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

2⃣Циклическое преобразование числа в буквы:
Пока columnNumber больше 0, выполняйте следующие действия:
Вычтите 1 из columnNumber для корректировки индекса (Excel использует 1-индексацию).
Найдите символ, соответствующий остатку от деления columnNumber на 26, и добавьте его в начало строки ans.
Присвойте columnNumber значение от деления columnNumber на 26

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

😎 Решение:

class Solution {
    public String convertToTitle(int columnNumber) {
        StringBuilder ans = new StringBuilder();

        while (columnNumber > 0) {
            columnNumber--;
            ans.append((char) (((columnNumber) % 26) + 'A'));
            columnNumber = (columnNumber) / 26;
        }
        return ans.reverse().toString();
    }
}

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

Задача: 244. Shortest Word Distance II
Сложность: medium

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

Реализуйте класс WordDistance:

WordDistance(String[] wordsDict) инициализирует объект с массивом строк wordsDict.
int shortest(String word1, String word2) возвращает наименьшее расстояние между word1 и word2 в массиве wordsDict.

Пример:

Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]
Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");    // return 1

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

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

2⃣Для данной пары слов получите список индексов (вхождений в исходный массив слов). Назовём эти два массива loc1 и loc2. Инициализируйте две переменные-указателя l1 = 0 и l2 = 0.

3⃣Для данных l1 и l2 обновите (если возможно) минимальную разницу (расстояние) до текущего момента, т.е. dist = min(dist, abs(loc1[l1] - loc2[l2])). Затем проверьте, если loc1[l1] < loc2[l2], и если это так, переместите l1 на один шаг вперёд, т.е. l1 = l1 + 1. В противном случае, переместите l2 на один шаг вперёд, т.е. l2 = l2 + 1. Продолжайте это делать, пока все элементы в меньшем из двух массивов позиций не будут обработаны. Верните глобальное минимальное расстояние между словами.

😎 Решение:

import java.util.*;

class WordDistance {
    Map<String, List<Integer>> locations;

    public WordDistance(String[] words) {
        locations = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            locations.computeIfAbsent(words[i], k -> new ArrayList<>()).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> loc1 = locations.get(word1);
        List<Integer> loc2 = locations.get(word2);
        int l1 = 0, l2 = 0, minDiff = Integer.MAX_VALUE;

        while (l1 < loc1.size() && l2 < loc2.size()) {
            minDiff = Math.min(minDiff, Math.abs(loc1.get(l1) - loc2.get(l2)));
            if (loc1.get(l1) < loc2.get(l2)) {
                l1++;
            } else {
                l2++;
            }
        }
        return minDiff;
    }
}

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