Задача: 311. Sparse Matrix Multiplication
Сложность: medium

Даны две разреженные матрицы mat1 размером m x k и mat2 размером k x n. Верните результат перемножения матриц mat1 x mat2. Вы можете предположить, что умножение всегда возможно.

Пример:

Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]
Output: [[7,0,0],[-7,0,3]]

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

1⃣Инициализация результирующей матрицы
Создайте результирующую матрицу result размером m x n, заполненную нулями.

2⃣Хранение ненулевых элементов
Пройдите по каждой строке матрицы mat1 и сохраните индексы и значения ненулевых элементов в хеш-карте mat1_map. Пройдите по каждой колонке матрицы mat2 и сохраните индексы и значения ненулевых элементов в хеш-карте mat2_map.

3⃣Вычисление произведения
Для каждой строки i в mat1 и для каждой колонки j в mat2: Если в mat1_map есть ненулевой элемент в строке i и в mat2_map есть ненулевой элемент в колонке j с одинаковым индексом k, добавьте произведение этих элементов к result[i][j].

😎 Решение:

public class Solution {
    public int[][] multiply(int[][] mat1, int[][] mat2) {
        int n = mat1.length;
        int k = mat1[0].length;
        int m = mat2[0].length;
        
        int[][] ans = new int[n][m];
        
        for (int rowIndex = 0; rowIndex < n; rowIndex++) {
            for (int elementIndex = 0; elementIndex < k; elementIndex++) {
                if (mat1[rowIndex][elementIndex] != 0) {
                    for (int colIndex = 0; colIndex < m; colIndex++) {
                        ans[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex];
                    }
                }
            }
        }
        
        return ans;
    }
}

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

Задача: 282. Expression Add Operators
Сложность: hard

Дана строка num, содержащая только цифры, и целое число target. Верните все возможные варианты вставки бинарных операторов '+', '-', и/или '*' между цифрами строки num так, чтобы результирующее выражение вычислялось в значение target.

Учтите, что операнды в возвращаемых выражениях не должны содержать ведущих нулей.

Пример:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

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

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

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

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

😎 Решение:

class Solution {

  public ArrayList<String> answer;
  public String digits;
  public long target;

  public void recurse(
      int index, long previousOperand, long currentOperand, long value, ArrayList<String> ops) {
    String nums = this.digits;

    if (index == nums.length()) {
      if (value == this.target && currentOperand == 0) {
        StringBuilder sb = new StringBuilder();
        ops.subList(1, ops.size()).forEach(v -> sb.append(v));
        this.answer.add(sb.toString());
      }
      return;
    }

    currentOperand = currentOperand * 10 + Character.getNumericValue(nums.charAt(index));
    String current_val_rep = Long.toString(currentOperand);
    int length = nums.length();

    if (currentOperand > 0) {
      recurse(index + 1, previousOperand, currentOperand, value, ops);
    }

    ops.add("+");
    ops.add(current_val_rep);
    recurse(index + 1, currentOperand, 0, value + currentOperand, ops);
    ops.remove(ops.size() - 1);
    ops.remove(ops.size() - 1);

    if (ops.size() > 0) {
      ops.add("-");
      ops.add(current_val_rep);
      recurse(index + 1, -currentOperand, 0, value - currentOperand, ops);
      ops.remove(ops.size() - 1);
      ops.remove(ops.size() - 1);

      ops.add("*");
      ops.add(current_val_rep);
      recurse(
          index + 1,
          currentOperand * previousOperand,
          0,
          value - previousOperand + (currentOperand * previousOperand),
          ops);
      ops.remove(ops.size() - 1);
      ops.remove(ops.size() - 1);
    }
  }

  public List<String> addOperators(String num, int target) {
    if (num.length() == 0) {
      return new ArrayList<String>();
    }

    this.target = target;
    this.digits = num;
    this.answer = new ArrayList<String>();
    this.recurse(0, 0, 0, 0, new ArrayList<String>());
    return this.answer;
  }
}

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

Задача: 1361. Validate Binary Tree Nodes
Сложность: easy

У вас есть n узлов бинарного дерева, пронумерованных от 0 до n-1, где узел i имеет двух детей: leftChild[i] и rightChild[i]. Верните true, если и только если все заданные узлы образуют ровно одно допустимое бинарное дерево.

Если у узла i нет левого ребенка, то leftChild[i] будет равен -1, аналогично для правого ребенка.

Обратите внимание, что узлы не имеют значений и мы используем только номера узлов в этой задаче.

Пример:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

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

1⃣Проверка количества родителей для каждого узла:
Создайте массив для отслеживания количества родителей для каждого узла. Проходите через leftChild и rightChild, увеличивая счетчик для каждого ребенка. Если какой-либо узел имеет более одного родителя, возвращайте false.

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

3⃣Проверка на достижение всех узлов:
Проверьте, что количество посещенных узлов равно n. Если нет, верните false. В противном случае, верните true.

😎 Решение:

import java.util.HashSet;
import java.util.Set;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] parents = new int[n];
        
        for (int i = 0; i < n; i++) {
            if (leftChild[i] != -1) {
                parents[leftChild[i]]++;
                if (parents[leftChild[i]] > 1) {
                    return false;
                }
            }
            if (rightChild[i] != -1) {
                parents[rightChild[i]]++;
                if (parents[rightChild[i]] > 1) {
                    return false;
                }
            }
        }
        
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (parents[i] == 0) {
                if (root == -1) {
                    root = i;
                } else {
                    return false;
                }
            }
        }
        
        if (root == -1) {
            return false;
        }
        
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (!visited.add(node)) {
                return false;
            }
            if (leftChild[node] != -1) {
                queue.add(leftChild[node]);
            }
            if (rightChild[node] != -1) {
                queue.add(rightChild[node]);
            }
        }
        
        return visited.size() == n;
    }
}

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

Задача: 380. Insert Delete GetRandom O(1)
Сложность: medium

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

RandomizedSet(): Инициализирует объект RandomizedSet.
bool insert(int val): Вставляет элемент val в множество, если его там нет. Возвращает true, если элемент отсутствовал, и false в противном случае.
bool remove(int val): Удаляет элемент val из множества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае.
int getRandom(): Возвращает случайный элемент из текущего множества элементов (гарантируется, что по крайней мере один элемент существует при вызове этого метода). Каждый элемент должен иметь равную вероятность быть возвращенным.
Вы должны реализовать функции класса таким образом, чтобы каждая функция работала в среднем за O(1) по времени.

Пример:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

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

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

2⃣Метод insert(val): Проверить наличие значения в словаре. Если отсутствует, добавить значение в список и обновить словарь с новым индексом.
Метод remove(val): Проверить наличие значения в словаре. Если присутствует, заменить удаляемое значение последним элементом списка, обновить его индекс в словаре, удалить последний элемент из списка и удалить значение из словаря.

3⃣Метод getRandom(): Возвращать случайный элемент из списка, используя встроенную функцию генерации случайных чисел.

😎 Решение:

import java.util.*;

public class RandomizedSet {
    private Map<Integer, Integer> dict;
    private List<Integer> list;
    private Random rand;

    public RandomizedSet() {
        dict = new HashMap<>();
        list = new ArrayList<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        if (dict.containsKey(val)) {
            return false;
        }
        dict.put(val, list.size());
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!dict.containsKey(val)) {
            return false;
        }
        int index = dict.get(val);
        int lastElement = list.get(list.size() - 1);
        list.set(index, lastElement);
        dict.put(lastElement, index);
        list.remove(list.size() - 1);
        dict.remove(val);
        return true;
    }

    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}

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

Задача: 302. Smallest Rectangle Enclosing Black Pixels
Сложность: hard

Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель.
Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали.
Даны два целых числа x и y, которые представляют местоположение одного из черных пикселей. Верните площадь наименьшего (выравненного по осям) прямоугольника, который охватывает все черные пиксели.
Вы должны написать алгоритм со сложностью менее O(mn).

Пример:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

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

1⃣Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно.

2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника:
left = min(left, x)
right = max(right, x + 1)
top = min(top, y)
bottom = max(bottom, y + 1)

3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top).

😎 Решение:

public class Solution {
    public int minArea(char[][] image, int x, int y) {
        int m = image.length, n = image[0].length;
        int left = searchColumns(image, 0, y, 0, m, true);
        int right = searchColumns(image, y + 1, n, 0, m, false);
        int top = searchRows(image, 0, x, left, right, true);
        int bottom = searchRows(image, x + 1, m, left, right, false);
        return (right - left) * (bottom - top);
    }

    private int searchColumns(char[][] image, int i, int j, int top, int bottom, boolean whiteToBlack) {
        while (i != j) {
            int k = top, mid = (i + j) / 2;
            while (k < bottom && image[k][mid] == '0') ++k;
            if (k < bottom == whiteToBlack)
                j = mid;
            else
                i = mid + 1;
        }
        return i;
    }

    private int searchRows(char[][] image, int i, int j, int left, int right, boolean whiteToBlack) {
        while (i != j) {
            int k = left, mid = (i + j) / 2;
            while (k < right && image[mid][k] == '0') ++k;
            if (k < right == whiteToBlack)
                j = mid;
            else
                i = mid + 1;
        }
        return i;
    }
}

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

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

Вам дана сетка n x n, представляющая поле вишен. Каждая клетка - одно из трех возможных целых чисел. 0 означает, что клетка пуста, и вы можете пройти через нее, 1 означает, что клетка содержит вишню, которую вы можете сорвать и пройти через нее, или -1 означает, что клетка содержит шип, который преграждает вам путь. Верните максимальное количество вишен, которое вы можете собрать, следуя следующим правилам: Начиная с позиции (0, 0) и достигая (n - 1, n - 1) путем перемещения вправо или вниз через допустимые клетки пути (клетки со значением 0 или 1).
После достижения (n - 1, n - 1) вернитесь в (0, 0), двигаясь влево или вверх по клеткам с действительными путями. Проходя через клетку пути, содержащую вишню, вы поднимаете ее, и клетка становится пустой клеткой 0. Если между (0, 0) и (n - 1, n - 1) нет действительного пути, то вишни собрать нельзя.

Пример:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5

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

1⃣Используйте динамическое программирование для подсчета максимального количества вишен, которые можно собрать при движении от (0, 0) до (n - 1, n - 1).

2⃣Примените еще один проход с использованием динамического программирования для движения обратно от (n - 1, n - 1) до (0, 0), чтобы учитывать вишни, собранные на обратном пути.

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

😎 Решение:

public class Solution {
    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        int[][][] dp = new int[n][n][2 * n - 1];
        for (int[][] layer : dp) {
            for (int[] row : layer) {
                Arrays.fill(row, Integer.MIN_VALUE);
            }
        }
        dp[0][0][0] = grid[0][0];

        for (int k = 1; k < 2 * n - 1; k++) {
            for (int i1 = Math.max(0, k - n + 1); i1 <= Math.min(n - 1, k); i1++) {
                for (int i2 = Math.max(0, k - n + 1); i2 <= Math.min(n - 1, k); i2++) {
                    int j1 = k - i1, j2 = k - i2;
                    if (j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1) {
                        int maxCherries = Integer.MIN_VALUE;
                        if (i1 > 0 && i2 > 0) maxCherries = Math.max(maxCherries, dp[i1 - 1][i2 - 1][k - 1]);
                        if (i1 > 0) maxCherries = Math.max(maxCherries, dp[i1 - 1][i2][k - 1]);
                        if (i2 > 0) maxCherries = Math.max(maxCherries, dp[i1][i2 - 1][k - 1]);
                        maxCherries = Math.max(maxCherries, dp[i1][i2][k - 1]);
                        if (maxCherries != Integer.MIN_VALUE) {
                            dp[i1][i2][k] = maxCherries + grid[i1][j1];
                            if (i1 != i2) dp[i1][i2][k] += grid[i2][j2];
                        }
                    }
                }
            }
        }
        
        return Math.max(0, dp[n - 1][n - 1][2 * (n - 1)]);
    }
}

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

Задача: 437. Path Sum III
Сложность: medium

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

Путь не обязательно должен начинаться или заканчиваться в корне или на листе, но он должен идти вниз (т.е. перемещаться только от родительских узлов к дочерним).

Пример:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

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

1⃣Инициализируем счетчик путей в дереве count = 0 и хеш-таблицу h, где ключ - это префиксная сумма, а значение - сколько раз она встречалась. Выполним рекурсивный обход дерева в порядке preorder: узел -> левый -> правый. Функция preorder(node: TreeNode, curr_sum: int) принимает два аргумента: узел дерева и префиксную сумму перед этим узлом. Чтобы запустить рекурсию, вызовем preorder(root, 0).

2⃣Сначала обновим текущую префиксную сумму, добавив значение текущего узла: curr_sum += node.val. Теперь можно обновить счетчик. Рассмотрим две ситуации. В первой ситуации путь в дереве с целевой суммой начинается с корня. Это означает, что текущая префиксная сумма равна целевой сумме curr_sum == k, поэтому увеличиваем счетчик на 1: count += 1. Во второй ситуации путь с целевой суммой начинается где-то ниже. Это означает, что нужно добавить к счетчику количество раз, когда мы видели префиксную сумму curr_sum - target: count += h[curr_sum - target].

3⃣Логика проста: текущая префиксная сумма - это curr_sum, а несколько элементов назад префиксная сумма была curr_sum - target. Все элементы между ними суммируются до curr_sum - (curr_sum - target) = target. Теперь обновим хеш-таблицу: h[curr_sum] += 1. Проанализируем левое и правое поддеревья: preorder(node.left, curr_sum), preorder(node.right, curr_sum). После обработки текущего поддерева удалим текущую префиксную сумму из хеш-таблицы, чтобы не смешивать параллельные поддеревья: h[curr_sum] -= 1. Когда обход в порядке preorder завершен, счетчик обновлен. Вернем его.

😎 Решение:

class Solution {
    public int pathSum(TreeNode root, int sum) {
        final int[] count = {0};
        final int k = sum;
        Map<Integer, Integer> h = new HashMap<>();
        
        preorder(root, 0, h, count, k);
        
        return count[0];
    }
    
    private void preorder(TreeNode node, int currSum, Map<Integer, Integer> h, int[] count, int k) {
        if (node == null) return;
        
        currSum += node.val;
        
        if (currSum == k) {
            count[0]++;
        }
        
        count[0] += h.getOrDefault(currSum - k, 0);
        
        h.put(currSum, h.getOrDefault(currSum, 0) + 1);
        
        preorder(node.left, currSum, h, count, k);
        preorder(node.right, currSum, h, count, k);
        
        h.put(currSum, h.get(currSum) - 1);
    }
}

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

Задача: 674. Longest Continuous Increasing Subsequence
Сложность: easy

Дан неотсортированный массив целых чисел nums, верните длину самой длинной непрерывной возрастающей подпоследовательности (т.е. подмассива). Подпоследовательность должна быть строго возрастающей.

Непрерывная возрастающая подпоследовательность определяется двумя индексами l и r (l < r) так, что она имеет вид [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] и для каждого l <= i < r выполняется nums[i] < nums[i + 1].

Пример:

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.

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

1⃣Каждая (непрерывная) возрастающая подпоследовательность не пересекается, и граница каждой такой подпоследовательности возникает, когда nums[i-1] >= nums[i]. В этом случае начинается новая возрастающая подпоследовательность с nums[i], и мы сохраняем такой i в переменной anchor.

2⃣Например, если nums = [7, 8, 9, 1, 2, 3], то anchor начинается с 0 (nums[anchor] = 7) и затем устанавливается на anchor = 3 (nums[anchor] = 1). Независимо от значения anchor, мы записываем кандидата на ответ длиной i - anchor + 1, длина подмассива nums[anchor], nums[anchor+1], ..., nums[i], и наш ответ обновляется соответствующим образом.

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

😎 Решение:

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int ans = 0, anchor = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (i > 0 && nums[i-1] >= nums[i]) anchor = i;
            ans = Math.max(ans, i - anchor + 1);
        }
        return ans;
    }
}

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

Задача: 219. Contains Duplicate II
Сложность: easy

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

Пример:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

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

1⃣Создайте пустое множество set.

2⃣Пройдитесь по массиву nums:
Если текущий элемент уже есть в множестве, верните true.
Добавьте текущий элемент в множество.
Если размер множества больше k, удалите элемент, который был добавлен k шагов назад.

3⃣Если не найдены дублирующиеся элементы на расстоянии k или менее, верните false.

😎 Решение:

public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < nums.length; ++i) {
        if (set.contains(nums[i])) return true;
        set.add(nums[i]);
        if (set.size() > k) {
            set.remove(nums[i - k]);
        }
    }
    return false;
}

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

Задача: 1519. Number of Nodes in the Sub-Tree With the Same Label
Сложность: medium

Вам дано дерево (т.е. связный неориентированный граф без циклов), состоящее из n узлов, пронумерованных от 0 до n - 1, и ровно n - 1 ребра. Корнем дерева является узел 0, и каждый узел дерева имеет метку, которая является строчной буквой, указанной в строке labels (т.е. узел с номером i имеет метку labels[i]).

Массив edges дан в форме edges[i] = [ai, bi], что означает, что существует ребро между узлами ai и bi в дереве.

Верните массив размера n, где ans[i] — это количество узлов в поддереве узла i, которые имеют ту же метку, что и узел i.

Поддерево дерева T — это дерево, состоящее из узла в T и всех его дочерних узлов.

Пример:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

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

1⃣Создайте список смежности, где adj[X] содержит всех соседей узла X.

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

3⃣Начните обход в глубину (DFS).

😎 Решение:

class Solution {
    public int[] dfs(int node, int parent, Map<Integer, List<Integer>> adj, char[] labels, int[] ans) {
        int[] nodeCounts = new int[26];
        nodeCounts[labels[node] - 'a'] = 1;

        if (!adj.containsKey(node))
            return nodeCounts;

        for (int child : adj.get(node)) {
            if (child == parent) {
                continue;
            }
            int[] childCounts = dfs(child, node, adj, labels, ans);
            for (int i = 0; i < 26; i++) {
                nodeCounts[i] += childCounts[i];
            }
        }

        ans[node] = nodeCounts[labels[node] - 'a'];
        return nodeCounts;
    }

    public int[] countSubTrees(int n, int[][] edges, String labels) {
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int[] edge : edges) {
            int a = edge[0], b = edge[1];
            adj.computeIfAbsent(a, value -> new ArrayList<>()).add(b);
            adj.computeIfAbsent(b, value -> new ArrayList<>()).add(a);
        }

        int[] ans = new int[n];
        char[] label = labels.toCharArray();
        dfs(0, -1, adj, label, ans);
        return ans;
    }
}

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

Задача: 104. Maximum Depth of Binary Tree
Сложность: easy

Дан корень бинарного дерева, верните его максимальную глубину.

Максимальная глубина бинарного дерева — это количество узлов вдоль самого длинного пути от корневого узла до самого удалённого листового узла.

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: 3

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

1⃣Можно обойти дерево, используя стратегию поиска в глубину (DFS) или поиска в ширину (BFS).

2⃣Для данной задачи подойдет несколько способов.

3⃣Здесь мы демонстрируем решение, реализованное с использованием стратегии DFS и рекурсии.

😎 Решение:

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int left_height = maxDepth(root.left);
            int right_height = maxDepth(root.right);
            return java.lang.Math.max(left_height, right_height) + 1;
        }
    }
}

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

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

Дан корень бинарного дерева. Определите, является ли это дерево допустимым бинарным деревом поиска (BST).

Допустимое BST определяется следующим образом:

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

Пример:

Input: root = [2,1,3]
Output: true

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

1⃣Давайте воспользуемся порядком узлов при симметричном обходе (inorder traversal):
Левый -> Узел -> Правый. Здесь узлы перечисляются в порядке их посещения, и вы можете следовать последовательности 1-2-3-4-5 для сравнения различных стратегий.
Порядок "Левый -> Узел -> Правый" при симметричном обходе означает, что для BST каждый элемент должен быть меньше следующего.

2⃣Следовательно, алгоритм с временной сложностью O(N) и пространственной сложностью O(N) может быть простым:
Вычислить список симметричного обхода inorder.
Проверить, меньше ли каждый элемент в списке inorder следующего за ним.

3⃣Нужно ли сохранять весь список симметричного обхода?
На самом деле, нет. Достаточно последнего добавленного элемента inorder, чтобы на каждом шаге убедиться, что дерево является BST (или нет). Следовательно, можно объединить оба шага в один и уменьшить используемое пространство.

😎 Решение:

class Solution {
    private Integer prev;

    public boolean isValidBST(TreeNode root) {
        prev = null;
        return inorder(root);
    }

    private boolean inorder(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!inorder(root.left)) {
            return false;
        }
        if (prev != null && root.val <= prev) {
            return false;
        }
        prev = root.val;
        return inorder(root.right);
    }
}

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

Задача: 1427. Perform String Shifts
Сложность: easy

Вам дана строка s, содержащая строчные английские буквы, и матрица shift, где shift[i] = [directioni, amounti]:
directioni может быть 0 (для сдвига влево) или 1 (для сдвига вправо).
amounti - это количество, на которое строка s должна быть сдвинута.
Сдвиг влево на 1 означает удаление первого символа строки s и добавление его в конец.
Аналогично, сдвиг вправо на 1 означает удаление последнего символа строки s и добавление его в начало.
Верните итоговую строку после всех операций.

Пример:

Input: s = "abc", shift = [[0,1],[1,2]]
Output: "cab"
Explanation: 
[0,1] means shift to left by 1. "abc" -> "bca"
[1,2] means shift to right by 2. "bca" -> "cab"

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

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

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

😎 Решение:

class Solution {
  public String stringShift(String string, int[][] shift) {
    
    int[] overallShifts = new int[2];
    for (int[] move : shift) {
      overallShifts[move[0]] += move[1];
    }
    int leftShifts = overallShifts[0];
    int rightShifts = overallShifts[1];
      
    int len = string.length();
    if (leftShifts > rightShifts) {
      leftShifts = (leftShifts - rightShifts) % len;
      string = string.substring(leftShifts) + string.substring(0, leftShifts);
    }
    else if (rightShifts > leftShifts) {
      rightShifts = (rightShifts - leftShifts) % len;
      string = string.substring(len - rightShifts) + string.substring(0, len - rightShifts);
    }
    
    return string;
  }
}

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

Задача: 368. Largest Divisible Subset
Сложность: medium

Дан набор различных положительных целых чисел nums. Вернуть наибольшее подмножество answer, такое что каждая пара (answer[i], answer[j]) элементов в этом подмножестве удовлетворяет условию:

answer[i] % answer[j] == 0, или
answer[j] % answer[i] == 0
Если существует несколько решений, вернуть любое из них.

Пример:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

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

1⃣Если число 8 может быть разделено на элемент X_i, то добавив число 8 к EDS(X_i), мы получим еще одно делимое подмножество, которое заканчивается на 8, согласно нашему следствию I. И это новое подмножество является потенциальным значением для EDS(8). Например, поскольку 8 % 2 == 0, то {2,8} может быть конечным значением для EDS(8), и аналогично для подмножества {2,4,8}, полученного из EDS(4).

2⃣Если число 8 не может быть разделено на элемент X_i, то можно быть уверенным, что значение EDS(X_i) не повлияет на EDS(8), согласно определению делимого подмножества. Например, подмножество EDS(7)={7} не имеет влияния на EDS(8).

3⃣Затем мы выбираем наибольшие новые подмножества, которые мы формируем с помощью EDS(X_i). В частности, подмножество {8} является допустимым кандидатом для EDS(8). И в гипотетическом случае, когда 8 не может быть разделено ни на один из предыдущих элементов, мы бы имели EDS(8)={8}.

😎 Решение:

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

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        if (n == 0) return new ArrayList<>();

        Arrays.sort(nums);
        List<List<Integer>> EDS = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            EDS.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            List<Integer> maxSubset = new ArrayList<>();
            for (int k = 0; k < i; k++) {
                if (nums[i] % nums[k] == 0 && maxSubset.size() < EDS.get(k).size()) {
                    maxSubset = EDS.get(k);
                }
            }
            EDS.get(i).addAll(maxSubset);
            EDS.get(i).add(nums[i]);
        }

        List<Integer> ret = new ArrayList<>();
        for (List<Integer> subset : EDS) {
            if (ret.size() < subset.size()) {
                ret = subset;
            }
        }
        return ret;
    }
}

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

Задача: 1146. Snapshot Array
Сложность: medium

Реализуйте SnapshotArray, который поддерживает следующий интерфейс:
SnapshotArray(int length) инициализирует структуру данных, похожую на массив, с заданной длиной. Изначально каждый элемент равен 0.
void set(index, val) устанавливает элемент с заданным индексом равным val.
int snap() делает снимок массива и возвращает snap_id: общее количество вызовов snap() минус 1.
int get(index, snap_id) возвращает значение на заданном индексе в момент, когда мы сделали снимок с указанным snap_id.

Пример:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

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

1⃣Инициализация: Для каждого элемента nums[i] в массиве создайте пустой список для хранения его исторических значений в формате [snap_id, value]. Инициализируйте каждый список, добавив первую запись [0, 0].

2⃣Метод set: Добавьте историческую запись [snap_id, value] в список записей historyRecords[index].

3⃣Методы snap и get:
Метод snap возвращает snap_id и увеличивает его на 1.
Метод get использует бинарный поиск, чтобы найти индекс последней вставки snap_id в данный снимок (целевой индекс будет snap_index - 1). Возвращает historyRecords[index][snap_index - 1][1].

😎 Решение:

class SnapshotArray {
    int snapId = 0;
    TreeMap<Integer, Integer>[] historyRecords;
    
    public SnapshotArray(int length) {
        historyRecords = new TreeMap[length];
        for (int i = 0; i < length; i++) {
            historyRecords[i] = new TreeMap<Integer, Integer>();
            historyRecords[i].put(0, 0);
        }
    }

    public void set(int index, int val) {
        historyRecords[index].put(snapId, val);
    }

    public int snap() {
        return snapId++;
    }

    public int get(int index, int snapId) {
        return historyRecords[index].floorEntry(snapId).getValue();
    }
}

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

Задача: 120. Triangle
Сложность: medium

Дан массив в виде треугольника, верните минимальную сумму пути сверху вниз.

На каждом шаге вы можете перейти к соседнему числу в строке ниже. Более формально, если вы находитесь на индексе i в текущей строке, вы можете перейти либо к индексу i, либо к индексу i + 1 в следующей строке.

Пример:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

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

1⃣Простейший способ реализации этого заключается в перезаписи входных данных, то есть в использовании алгоритма "на месте". В подходе 2 мы рассмотрим, как модифицировать алгоритм так, чтобы он не перезаписывал входные данные, но при этом не требовал более чем O(n) дополнительного пространства.

2⃣Когда этот алгоритм завершит свою работу, каждая ячейка (строка, столбец) входного треугольника будет перезаписана минимальной суммой пути от (0, 0) (вершины треугольника) до (строка, столбец) включительно.
Совет на собеседовании: Алгоритмы "на месте" перезаписывают входные данные для экономии места, но иногда это может вызвать проблемы. Вот несколько ситуаций, когда алгоритм "на месте" может быть неуместен.

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

😎 Решение:

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        for (int row = 1; row < triangle.size(); row++) {
            for (int col = 0; col <= row; col++) {
                int smallestAbove = Integer.MAX_VALUE;
                if (col > 0) {
                    smallestAbove = triangle.get(row - 1).get(col - 1);
                }
                if (col < row) {
                    smallestAbove = Math.min(
                        smallestAbove,
                        triangle.get(row - 1).get(col)
                    );
                }
                int path = smallestAbove + triangle.get(row).get(col);
                triangle.get(row).set(col, path);
            }
        }
        return Collections.min(triangle.get(triangle.size() - 1));
    }
}

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

Задача: 987. Vertical Order Traversal of a Binary Tree
Сложность: medium

Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.

Верните пересечение этих двух списков интервалов.

Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.

Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

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

1⃣Инициализация указателей:
Создать словарь для хранения узлов по их координатам (col, row).
Создать очередь для обхода в ширину (BFS), содержащую начальную пару (root, (0, 0)).

2⃣Поиск пересечений:
Выполнить BFS обход дерева. Для каждого узла сохранить его значение в словаре по ключу (col, row).
Добавить левый потомок в очередь с координатами (row + 1, col - 1).
Добавить правый потомок в очередь с координатами (row + 1, col + 1).

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

😎 Решение:

import java.util.*;

public class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, List<int[]>> colTable = new TreeMap<>();
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{root, 0, 0});
        
        while (!queue.isEmpty()) {
            int[] info = queue.poll();
            TreeNode node = (TreeNode) info[0];
            int row = info[1], col = info[2];
            
            colTable.putIfAbsent(col, new ArrayList<>());
            colTable.get(col).add(new int[]{row, node.val});
            
            if (node.left != null) {
                queue.offer(new int[]{node.left, row + 1, col - 1});
            }
            if (node.right != null) {
                queue.offer(new int[]{node.right, row + 1, col + 1});
            }
        }
        
        List<List<Integer>> result = new ArrayList<>();
        for (int col : colTable.keySet()) {
            Collections.sort(colTable.get(col), (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
            List<Integer> sortedCol = new ArrayList<>();
            for (int[] p : colTable.get(col)) {
                sortedCol.add(p[1]);
            }
            result.add(sortedCol);
        }
        
        return result;
    }
}

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

Задача: 37. Sudoku Solver
Сложность: hard

Напишите программу для решения головоломки Судоку, заполнив пустые ячейки.

Решение Судоку должно удовлетворять всем следующим правилам:

Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждой строке.
Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждом столбце.
Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждом из 9 подблоков 3x3 сетки.
Символ '.' обозначает пустые ячейки.

Пример:

Input: board = 
[["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
Output: 
[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

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

1⃣Теперь все готово для написания функции обратного поиска backtrack(row = 0, col = 0). Начните с верхней левой ячейки row = 0, col = 0. Продолжайте, пока не дойдете до первой свободной ячейки.

2⃣Итерируйте по числам от 1 до 9 и попробуйте поставить каждое число d в ячейку (row, col).
Если число d еще не в текущей строке, столбце и блоке:
Поместите d в ячейку (row, col).
Запишите, что d теперь присутствует в текущей строке, столбце и блоке.

3⃣Если вы на последней ячейке row == 8, col == 8:
Это означает, что судоку решено.
В противном случае продолжайте размещать дальнейшие числа.
Откат, если решение еще не найдено: удалите последнее число из ячейки (row, col).

😎 Решение:

import java.util.*;

class Solution {
    public void solveSudoku(char[][] board) {
        int n = 3, N = n * n;
        List<Map<Character, Integer>> track = new ArrayList<>(N * 3);
        for (int i = 0; i < N * 3; i++) track.add(new HashMap<>());

        for (int r = 0; r < N; r++) for (int c = 0; c < N; c++) 
            if (board[r][c] != '.') update(board, r, c, board[r][c], true, n, track);

        backtrack(board, 0, 0, n, N, track);
    }

    private boolean backtrack(char[][] board, int r, int c, int n, int N, List<Map<Character, Integer>> track) {
        if (c == N) { r++; c = 0; }
        if (r == N) return true;

        if (board[r][c] != '.') return backtrack(board, r, c + 1, n, N, track);

        for (char num = '1'; num <= '9'; num++) 
            if (canPlace(num, r, c, n, track)) {
                update(board, r, c, num, true, n, track);
                if (backtrack(board, r, c + 1, n, N, track)) return true;
                update(board, r, c, num, false, n, track);
            }

        return false;
    }

    private boolean canPlace(char num, int r, int c, int n, List<Map<Character, Integer>> track) {
        int idx = r / n * n + c / n;
        return track.get(r).getOrDefault(num, 0) == 0 && track.get(n + c).getOrDefault(num, 0) == 0 
            && track.get(2 * n + idx).getOrDefault(num, 0) == 0;
    }

    private void update(char[][] board, int r, int c, char num, boolean place, int n, List<Map<Character, Integer>> track) {
        int idx = r / n * n + c / n, delta = place ? 1 : -1;
        track.get(r).put(num, track.get(r).getOrDefault(num, 0) + delta);
        track.get(n + c).put(num, track.get(n + c).getOrDefault(num, 0) + delta);
        track.get(2 * n + idx).put(num, track.get(2 * n + idx).getOrDefault(num, 0) + delta);
        board[r][c] = place ? num : '.';
    }
}

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

Задача: 222. Count Complete Tree Nodes
Сложность: easy

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

Согласно Википедии, в полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. Он может содержать от 1 до 2 в степени n узлов включительно на последнем уровне n.

Разработайте алгоритм, который выполняется за время, меньшее, чем O(n).

Пример:

Input: root = [1,2,3,4,5,6]
Output: 6

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

1⃣Инициализация и проверка пустоты дерева
Если дерево пустое, вернуть 0.
Рассчитать глубину дерева d.

2⃣Поиск узлов на последнем уровне
Использовать двоичный поиск, чтобы найти количество узлов на последнем уровне. Функция exists используется для проверки наличия узла по индексу.

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

😎 Решение:

class Solution {
  public int computeDepth(TreeNode node) {
    int d = 0;
    while (node.left != null) {
      node = node.left;
      ++d;
    }
    return d;
  }

  public boolean exists(int idx, int d, TreeNode node) {
    int left = 0, right = (int)Math.pow(2, d) - 1;
    int pivot;
    for(int i = 0; i < d; ++i) {
      pivot = left + (right - left) / 2;
      if (idx <= pivot) {
        node = node.left;
        right = pivot;
      }
      else {
        node = node.right;
        left = pivot + 1;
      }
    }
    return node != null;
  }

  public int countNodes(TreeNode root) {
    if (root == null) return 0;

    int d = computeDepth(root);
    if (d == 0) return 1;

    int left = 1, right = (int)Math.pow(2, d) - 1;
    int pivot;
    while (left <= right) {
      pivot = left + (right - left) / 2;
      if (exists(pivot, d, root)) left = pivot + 1;
      else right = pivot - 1;
    }

    return (int)Math.pow(2, d) - 1 + left;
  }
}

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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