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

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

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

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

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

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

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

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

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

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

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

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