Задача: 634. Find the Derangement of An Array
Сложность: medium

В комбинаторной математике отклонение - это перестановка элементов множества таким образом, что ни один элемент не оказывается на прежнем месте. Вам дано целое число n. Изначально имеется массив, состоящий из n целых чисел от 1 до n в порядке возрастания, верните количество отклонений, которые он может породить. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.

Пример:

Input: n = 3
Output: 2

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

1⃣Инициализация массива для хранения результатов: Создайте массив dp для хранения количества отклонений для каждого значения от 0 до n. Установите начальные значения: dp[0] = 1 и dp[1] = 0.

2⃣Вычисление количества отклонений: Используйте динамическое программирование для вычисления количества отклонений для каждого значения от 2 до n. Формула для вычисления: dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD.

3⃣Возвращение результата: Верните значение dp[n], которое будет количеством отклонений для n элементов, по модулю 10^9 + 7.

😎 Решение:

public class Solution {
    public int countDerangements(int n) {
        final int MOD = 1000000007;
        if (n == 0) return 1;
        if (n == 1) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = (int)((long)(i - 1) * (dp[i - 1] + dp[i - 2]) % MOD);
        }
        return dp[n];
    }
}

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

Задача: 121. Best Time to Buy and Sell Stock
Сложность: easy

Вам дан массив цен, где prices[i] является ценой данной акции в i-й день.

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

Верните максимальную прибыль, которую вы можете получить от этой операции. Если прибыль получить невозможно, верните 0.

Пример:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

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

1⃣Инициализируем minprice как бесконечность и maxprofit как 0.

2⃣Проходим по массиву: если текущая цена меньше minprice, обновляем минимум. Если разница между текущей ценой и minprice больше maxprofit, обновляем прибыль.

3⃣В конце возвращаем maxprofit — максимальную разницу покупки/продажи, которую можно было получить.

😎 Решение:

public class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) minprice = prices[i];
            else if (prices[i] - minprice > maxprofit) maxprofit = prices[i] -
            minprice;
        }
        return maxprofit;
    }
}

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

Задача: 242. Valid Anagram
Сложность: easy

Даны две строки s и t, верните true, если t является анаграммой s, и false в противном случае.

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

Пример:

Input: s = "anagram", t = "nagaram"
Output: true

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

1⃣Создайте массив размером 26 для подсчета частот каждой буквы (поскольку s и t содержат только буквы от 'a' до 'z').

2⃣Пройдитесь по строке s, увеличивая счетчик соответствующей буквы. Затем пройдитесь по строке t, уменьшая счетчик для каждой буквы.

3⃣Проверьте, не опустился ли счетчик ниже нуля во время обхода строки t. Если это произошло, значит в t есть лишняя буква, которой нет в s, и следует вернуть false. Если после проверки всех букв все счетчики равны нулю, возвращайте true, указывая на то, что t является анаграммой s.

😎 Решение:

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    int[] table = new int[26];
    for (int i = 0; i < s.length(); i++) {
        table[s.charAt(i) - 'a']++;
        table[t.charAt(i) - 'a']--;
    }
    for (int count : table) {
        if (count != 0) {
            return false;
        }
    }
    return true;
}

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

Задача: 223. Rectangle Area
Сложность: medium

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

Первый прямоугольник определяется его нижним левым углом (ax1, ay1) и верхним правым углом (ax2, ay2).

Второй прямоугольник определяется его нижним левым углом (bx1, by1) и верхним правым углом (bx2, by2).

Пример:

Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45

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

1⃣Вычислить площади двух прямоугольников:
Рассчитайте площади прямоугольников A и B, умножив их ширину на высоту.

2⃣Вычислить перекрытие:
Найдите перекрытие по оси X и оси Y. Если перекрытие существует, вычислите площадь перекрытия.

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

😎 Решение:

class Solution {
    public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int areaOfA = (ay2 - ay1) * (ax2 - ax1);
        int areaOfB = (by2 - by1) * (bx2 - bx1);

        int left = Math.max(ax1, bx1);
        int right = Math.min(ax2, bx2);
        int xOverlap = right - left;

        int top = Math.min(ay2, by2);
        int bottom = Math.max(ay1, by1);
        int yOverlap = top - bottom;

        int areaOfOverlap = 0;
        if (xOverlap > 0 && yOverlap > 0) {
            areaOfOverlap = xOverlap * yOverlap;
        }

        int totalArea = areaOfA + areaOfB - areaOfOverlap;

        return totalArea;
    }
}

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

Задача: 949. Largest Time for Given Digits
Сложность: medium

Учитывая массив arr из 4 цифр, найдите самое позднее 24-часовое время, которое можно составить, используя каждую цифру ровно один раз. 24-часовое время имеет формат "ЧЧ:ММ", где ЧЧ - от 00 до 23, а ММ - от 00 до 59. Самое раннее 24-часовое время - 00:00, а самое позднее - 23:59. Верните самое позднее 24-часовое время в формате "HH:MM". Если не удается определить действительное время, возвращается пустая строка.

Пример:

Input: arr = [1,2,3,4]
Output: "23:41"

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

1⃣Перебрать все возможные перестановки массива arr.

2⃣Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время.
Найти самое позднее допустимое время среди всех перестановок.

3⃣Алгоритм
Перебрать все возможные перестановки массива arr.
Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время.
Найти самое позднее допустимое время среди всех перестановок.
Вернуть найденное время в формате "HH
". Если допустимое время не найдено, вернуть пустую строку.

😎 Решение:

import java.util.*;

class Solution {
    public String largestTimeFromDigits(int[] arr) {
        int maxTime = -1;
        List<int[]> permutations = new ArrayList<>();
        permute(arr, 0, permutations);
        
        for (int[] perm : permutations) {
            int hours = perm[0] * 10 + perm[1];
            int minutes = perm[2] * 10 + perm[3];
            if (hours < 24 && minutes < 60) {
                maxTime = Math.max(maxTime, hours * 60 + minutes);
            }
        }
        
        if (maxTime == -1) {
            return "";
        }
        
        String hours = String.format("%02d", maxTime / 60);
        String minutes = String.format("%02d", maxTime % 60);
        return hours + ":" + minutes;
    }
    
    private void permute(int[] nums, int start, List<int[]> res) {
        if (start == nums.length) {
            res.add(nums.clone());
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            permute(nums, start + 1, res);
            swap(nums, start, i);
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

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

Задача: 532. K-diff Pairs in an Array
Сложность: medium

Дан массив целых чисел nums и целое число k. Верните количество уникальных пар с разницей k в массиве.

Пара с разницей k — это пара целых чисел (nums[i], nums[j]), для которой выполняются следующие условия:
0 <= i, j < nums.length
i != j
|nums[i] - nums[j]| == k
Обратите внимание, что |val| обозначает абсолютное значение val.

Пример:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

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

1⃣ Создайте частотный хэш-словарь для подсчета количества каждого уникального числа в массиве nums.

2⃣ Для каждого ключа в хэш-словаре проверьте, можно ли найти пару, удовлетворяющую условиям:
Если k > 0, проверьте, существует ли ключ, равный x + k.
Если k == 0, проверьте, есть ли более одного вхождения x.

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

😎 Решение:

public class Solution {
    public int findPairs(int[] nums, int k) {

        int result = 0;

        HashMap <Integer,Integer> counter = new HashMap<>();
        for (int n: nums) {
            counter.put(n, counter.getOrDefault(n, 0)+1);
        }


        for (Map.Entry <Integer, Integer> entry: counter.entrySet()) {
            int x = entry.getKey();
            int val = entry.getValue();
            if (k > 0 && counter.containsKey(x + k)) {
                result++;
            } else if (k == 0 && val > 1) {
                result++;
            }
        }
        return result;
    }
}

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

Задача: 79. Word Search
Сложность: medium

Дана сетка символов размером m на n, называемая board, и строка word. Верните true, если слово word существует в сетке.

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

Пример:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

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

1⃣Общий подход к алгоритмам обратной трассировки: В каждом алгоритме обратной трассировки существует определенный шаблон кода. Например, один из таких шаблонов можно найти в нашем разделе "Рекурсия II". Скелет алгоритма представляет собой цикл, который проходит через каждую ячейку в сетке. Для каждой ячейки вызывается функция обратной трассировки (backtrack()), чтобы проверить, можно ли найти решение, начиная с этой ячейки.

2⃣Функция обратной трассировки: Эта функция, реализуемая как алгоритм поиска в глубину (DFS), часто представляет собой рекурсивную функцию. Первым делом проверяется, достигнут ли базовый случай рекурсии, когда слово для сопоставления пусто, то есть для каждого префикса слова уже найдено совпадение. Затем проверяется, не является ли текущее состояние недопустимым: либо позиция ячейки выходит за границы доски, либо буква в текущей ячейке не совпадает с первой буквой слова.

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

😎 Решение:

class Solution {
    private char[][] board;
    private int ROWS;
    private int COLS;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.ROWS = board.length;
        this.COLS = board[0].length;

        for (int row = 0; row < this.ROWS; ++row) {
            for (int col = 0; col < this.COLS; ++col) {
                if (this.backtrack(row, col, word, 0)) return true;
            }
        }
        return false;
    }

    protected boolean backtrack(int row, int col, String word, int index) {
        if (index >= word.length()) return true;

        if (
            row < 0 ||
            row == this.ROWS ||
            col < 0 ||
            col == this.COLS ||
            this.board[row][col] != word.charAt(index)
        ) return false;

        boolean ret = false;
        this.board[row][col] = '#';

        int[] rowOffsets = { 0, 1, 0, -1 };
        int[] colOffsets = { 1, 0, -1, 0 };
        for (int d = 0; d < 4; ++d) {
            ret = this.backtrack(
                    row + rowOffsets[d],
                    col + colOffsets[d],
                    word,
                    index + 1
                );
            if (ret) break;
        }

        this.board[row][col] = word.charAt(index);
        return ret;
    }
}

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

Задача: 892. Surface Area of 3D Shapes
Сложность: easy

Вам дана сетка n x n, на которой вы разместили несколько кубиков 1 x 1 x 1. Каждое значение v = grid[i][j] представляет собой башню из v кубиков, размещенных на вершине ячейки (i, j). После размещения кубиков вы решили склеить все непосредственно прилегающие кубики друг с другом, образовав несколько неправильных 3D-фигур. Верните общую площадь поверхности получившихся фигур. Примечание: нижняя грань каждой фигуры учитывается в площади ее поверхности.

Пример:

Input: grid = [[1,2],[3,4]]
Output: 34

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

1⃣Пройти по всей сетке и для каждой башни (ячейки) посчитать начальную площадь поверхности: добавить площадь верхней и нижней граней, а также четыре боковые грани.

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

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

😎 Решение:

public int surfaceArea(int[][] grid) {
    int n = grid.length;
    int area = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] > 0) {
                area += (grid[i][j] * 4) + 2;
            }
            if (i > 0) {
                area -= Math.min(grid[i][j], grid[i-1][j]) * 2;
            }
            if (j > 0) {
                area -= Math.min(grid[i][j], grid[i][j-1]) * 2;
            }
        }
    }
    return area;

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

Задача: 491. Non-decreasing Subsequences
Сложность: medium

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

Пример:

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

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

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

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

3⃣Возврат результата
После завершения всех рекурсивных вызовов преобразуйте множество результатов в список и верните его.

😎 Решение:

class Solution {
    private void backtrack(int[] nums, int index, List<Integer> sequence,
            Set<List<Integer>> result) {
        if (index == nums.length) {
            if (sequence.size() >= 2) {
                result.add(new ArrayList<>(sequence));
            }
            return;
        }
        if (sequence.isEmpty() ||
                sequence.get(sequence.size() - 1) <= nums[index]) {
            sequence.add(nums[index]);
            backtrack(nums, index + 1, sequence, result);
            sequence.remove(sequence.size() - 1);
        }
        backtrack(nums, index + 1, sequence, result);
    }

    public List<List<Integer>> findSubsequences(int[] nums) {
        Set<List<Integer>> result = new HashSet<List<Integer>>();
        List<Integer> sequence = new ArrayList<Integer>();
        backtrack(nums, 0, sequence, result);
        return new ArrayList(result);
    }
}

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

Задача: 903. Valid Permutations for DI Sequence
Сложность: hard

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

Пример:

Input: s = "DID"
Output: 5

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

1⃣Создать двумерный массив dp, где dp[i][j] представляет количество допустимых перестановок длины i, оканчивающихся на j.

2⃣Заполнить массив dp, учитывая условия возрастания и убывания из строки s.

3⃣Вернуть сумму dp[n][j] для всех j, что даст количество допустимых перестановок длины n + 1.

😎 Решение:

class Solution {
    public int numPermsDISequence(String s) {
        int MOD = 1_000_000_007;
        int n = s.length();
        int[][] dp = new int[n + 1][n + 1];
        dp[0][0] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (s.charAt(i - 1) == 'D') {
                    for (int k = j; k < i; k++) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                    }
                } else {
                    for (int k = 0; k < j; k++) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                    }
                }
            }
        }
        
        int result = 0;
        for (int j = 0; j <= n; j++) {
            result = (result + dp[n][j]) % MOD;
        }
        
        return result;
    }
}

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

Задача: 1246. Palindrome Removal
Сложность: hard

Вам дан целочисленный массив arr. За один ход вы можете выбрать палиндромный подмассив arr[i], arr[i + 1], ..., arr[j], где i <= j, и удалить этот подмассив из данного массива. Обратите внимание, что после удаления подмассива элементы слева и справа от него перемещаются, чтобы заполнить пробел, образовавшийся в результате удаления. Верните минимальное количество ходов, необходимое для удаления всех чисел из массива.

Пример:

Input: arr = [1,2]
Output: 2

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

1⃣Базовый случай:
Если подмассив состоит из одного элемента, то его удаление займет 1 ход, поэтому dp[i][i] = 1.

2⃣Рекурсивный случай:
Если arr[i] == arr[j], то мы можем удалить их в одном ходе, если подмассив arr[i+1...j-1] можно удалить за dp[i+1][j-1] ходов, тогда dp[i][j] = dp[i+1][j-1] (если удалим подмассив arr[i+1...j-1] и затем удалим arr[i] и arr[j]).

3⃣В противном случае, минимальное количество ходов для удаления подмассива arr[i...j] будет равно 1 + минимум ходов для удаления каждого из подмассивов arr[i...k] и arr[k+1...j], где i <= k < j. То есть, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех k от i до j-1.

😎 Решение:

public class Solution {
    public int minMovesToDelete(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (arr[i] == arr[j]) {
                    dp[i][j] = length > 2 ? dp[i + 1][j - 1] : 1;
                } else {
                    dp[i][j] = Integer.MAX_VALUE;
                    for (int k = i; k < j; k++) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
        }

        return dp[0][n - 1];
    }
}

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

Задача: 461. Hamming Distance
Сложность: easy

Расстояние Хэмминга между двумя целыми числами — это количество позиций, в которых соответствующие биты различны.

Даны два целых числа x и y, верните расстояние Хэмминга между ними.

Пример:

Input: x = 3, y = 1
Output: 1

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

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

2⃣Однако, поскольку это задача на LeetCode, использование встроенных функций можно сравнить с "реализацией LinkedList с использованием LinkedList". Поэтому рассмотрим также несколько интересных ручных алгоритмов для подсчета битов.

3⃣Пошаговый подсчет битов:
Выполните побитовое XOR между x и y.
Инициализируйте счетчик bitCount = 0.
Пока число не равно нулю:
Если текущий бит равен 1, увеличьте bitCount.
Сдвиньте число вправо на один бит.
Возвращайте bitCount.

😎 Решение:

class Solution {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}

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

Задача: 384. Shuffle an Array
Сложность: medium

Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания.

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

Solution(int[] nums): Инициализирует объект целочисленным массивом nums.
int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его.
int[] shuffle(): Возвращает случайное перемешивание массива.

Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

1⃣Алгоритм Фишера-Йейтса удивительно похож на решение грубой силы. На каждой итерации алгоритма мы генерируем случайное целое число между текущим индексом и последним индексом массива.

2⃣Затем мы меняем местами элементы на текущем индексе и выбранном индексе. Это симулирует выбор (и удаление) элемента из "шляпы", так как следующий диапазон, из которого мы выбираем случайный индекс, не будет включать последний обработанный элемент.

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

😎 Решение:

class Solution {
    private int[] array;
    private int[] original;

    Random rand = new Random();

    private int randRange(int min, int max) {
        return rand.nextInt(max - min) + min;
    }

    private void swapAt(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public Solution(int[] nums) {
        array = nums;
        original = nums.clone();
    }
    
    public int[] reset() {
        array = original;
        original = original.clone();
        return original;
    }
    
    public int[] shuffle() {
        for (int i = 0; i < array.length; i++) {
            swapAt(i, randRange(i, array.length));
        }
        return array;
    }
}

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

Задача: 605. Can Place Flowers
Сложность: easy

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

Дан целочисленный массив flowerbed, содержащий 0 и 1, где 0 означает пустой участок, а 1 — занятый участок, и целое число n. Верните true, если n новых цветов можно посадить на клумбе, не нарушая правила о соседних цветах, и false в противном случае.

Пример:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

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

1⃣Решение очень простое. Мы можем определить максимальное количество дополнительных цветов, count, которые можно посадить для данного расположения клумбы. Для этого мы проходим по всем элементам массива flowerbed и находим те элементы, которые равны 0 (означает пустую позицию).

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

3⃣Если полученное количество count больше или равно n, требуемому количеству цветов для посадки, мы можем посадить n цветов на пустые места, иначе - нет.

😎 Решение:

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        for (int i = 0; i < flowerbed.length; i++) {
            if (flowerbed[i] == 0) {
                boolean emptyLeft = i == 0 || flowerbed[i - 1] == 0;
                boolean emptyRight = i == flowerbed.length - 1 || flowerbed[i + 1] == 0;
                if (emptyLeft && emptyRight) {
                    flowerbed[i] = 1;
                    count++;
                }
            }
        }
        return count >= n;
    }
}

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

Задача: 187. Repeated DNA Sequences
Сложность: medium

ДНК состоит из серии нуклеотидов, обозначаемых как 'A', 'C', 'G' и 'T'.

Например, "ACGAATTCCG" — это последовательность ДНК.
При изучении ДНК полезно определять повторяющиеся последовательности внутри молекулы ДНК.

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

Пример:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

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

1⃣Перебираем начальные позиции последовательности от 1 до 𝑁−𝐿, где 𝑁 — длина строки, а 𝐿 — длина подстроки (в данном случае 10):
Если начальная позиция 𝑠𝑡𝑎𝑟𝑡==0, вычисляем хеш первой последовательности 𝑠[0:𝐿].
В противном случае вычисляем скользящий хеш из предыдущего значения хеша.

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

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

😎 Решение:

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        int L = 10, n = s.length();
        if (n <= L) return new ArrayList();
        int a = 4, aL = (int) Math.pow(a, L);
        Map<Character, Integer> toInt = new HashMap() {
            {
                put('A', 0);
                put('C', 1);
                put('G', 2);
                put('T', 3);
            }
        };
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) nums[i] = toInt.get(s.charAt(i));

        int h = 0;
        Set<Integer> seen = new HashSet();
        Set<String> output = new HashSet();
        for (int start = 0; start < n - L + 1; ++start) {
            if (start != 0) h = h * a -
            nums[start - 1] * aL +
            nums[start + L - 1];
            else for (int i = 0; i < L; ++i) h = h * a + nums[i];
            if (seen.contains(h)) output.add(s.substring(start, start + L));
            seen.add(h);
        }
        return new ArrayList<String>(output);
    }
}

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

Задача: 359. Logger Rate Limiter
Сложность: easy

Создайте систему логирования, которая получает поток сообщений вместе с их временными метками. Каждое уникальное сообщение должно печататься не чаще, чем раз в 10 секунд (то есть, сообщение, напечатанное во временной метке t, предотвратит печать других идентичных сообщений до временной метки t + 10).
Все сообщения будут приходить в хронологическом порядке. Несколько сообщений могут поступить в одно и то же время.

Реализуйте класс Logger:
Logger() Инициализирует объект логгера.
bool shouldPrintMessage(int timestamp, string message) Возвращает true, если сообщение должно быть напечатано в данной временной метке, в противном случае возвращает false.

Пример:

Input
["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [1, "foo"], [2, "bar"], [3, "foo"], [8, "bar"], [10, "foo"], [11, "foo"]]
Output
[null, true, true, false, false, false, true]

Explanation
Logger logger = new Logger();
logger.shouldPrintMessage(1, "foo");  // return true, next allowed timestamp for "foo" is 1 + 10 = 11
logger.shouldPrintMessage(2, "bar");  // return true, next allowed timestamp for "bar" is 2 + 10 = 12
logger.shouldPrintMessage(3, "foo");  // 3 < 11, return false
logger.shouldPrintMessage(8, "bar");  // 8 < 12, return false
logger.shouldPrintMessage(10, "foo"); // 10 < 11, return false
logger.shouldPrintMessage(11, "foo"); // 11 >= 11, return true, next allowed timestamp for "foo" is 11 + 10 = 21

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

1⃣Инициализируем хеш-таблицу/словарь для хранения сообщений вместе с временной меткой.

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

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

😎 Решение:

class Logger {
  private HashMap<String, Integer> msgDict;

  public Logger() {
    msgDict = new HashMap<String, Integer>();
  }

  public boolean shouldPrintMessage(int timestamp, String message) {

    if (!this.msgDict.containsKey(message)) {
      this.msgDict.put(message, timestamp);
      return true;
    }

    Integer oldTimestamp = this.msgDict.get(message);
    if (timestamp - oldTimestamp >= 10) {
      this.msgDict.put(message, timestamp);
      return true;
    } else
      return false;
  }
}

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

Задача: 487. Max Consecutive Ones II
Сложность: medium

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

Пример:

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.

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

1⃣Для каждого возможного начала последовательности в массиве nums начните считать количество нулей.

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

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

😎 Решение:

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int longestSequence = 0;
        for (int left = 0; left < nums.length; left++) {
            int numZeroes = 0;

            for (int right = left; right < nums.length; right++) {
                if (nums[right] == 0) {
                    numZeroes += 1;
                }
                if (numZeroes <= 1) {
                    longestSequence = Math.max(longestSequence, right - left + 1);
                }
            }
        }
        return longestSequence;
    }
}

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

Задача: 1229. Meeting Scheduler
Сложность: medium

Даны массивы доступных временных слотов slots1 и slots2 для двух человек и продолжительность встречи duration, верните самый ранний временной слот, который подходит обоим и имеет продолжительность duration.

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

Формат временного слота — это массив из двух элементов [start, end], представляющий инклюзивный временной диапазон от start до end.

Гарантируется, что никакие два доступных временных слота одного и того же человека не пересекаются друг с другом. То есть для любых двух временных слотов [start1, end1] и [start2, end2] одного и того же человека либо start1 > end2, либо start2 > end1.

Пример:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68]

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

1⃣Отсортируйте оба массива slots1 и slots2 по времени начала.

2⃣Инициализируйте два указателя, указывающие на начало slots1 и slots2 соответственно.

3⃣Перебирайте, пока указатель1 не достигнет конца slots1 или указатель2 не достигнет конца slots2:
Найдите общий слот между slots1[pointer1] и slots2[pointer2].
Если общий слот больше или равен duration, верните результат.
В противном случае найдите слот, который заканчивается раньше, и передвиньте указатель.
Если общий слот не найден, верните пустой массив.

😎 Решение:

class Solution {
    public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        Arrays.sort(slots1, (a, b) -> a[0] - b[0]);
        Arrays.sort(slots2, (a, b) -> a[0] - b[0]);

        int pointer1 = 0, pointer2 = 0;

        while (pointer1 < slots1.length && pointer2 < slots2.length) {
            int intersectLeft = Math.max(slots1[pointer1][0], slots2[pointer2][0]);
            int intersectRight = Math.min(slots1[pointer1][1], slots2[pointer2][1]);
            if (intersectRight - intersectLeft >= duration) {
                return new ArrayList<Integer>(Arrays.asList(intersectLeft, intersectLeft + duration));
            }
            if (slots1[pointer1][1] < slots2[pointer2][1]) {
                pointer1++;
            } else {
                pointer2++;
            }
        }
        return new ArrayList<Integer>();
    }
}

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

Задача: 863. All Nodes Distance K in Binary Tree
Сложность: medium

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

Ответ можно вернуть в любом порядке.

Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.

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

1⃣Определите рекурсивную функцию add_parent(cur, parent), чтобы рекурсивно добавлять указатель на родителя к узлу cur. Если cur не пустой, добавьте указатель на parent: cur.parent = parent. Затем рекурсивно вызовите add_parent для левого и правого детей cur: add_parent(cur.left, cur) и add_parent(cur.right, cur). Вызовите add_parent(root, None), чтобы добавить все указатели на родителей (корневой узел не имеет родителя).

2⃣Инициализируйте пустой массив answer и пустое множество visited. Определите рекурсивную функцию dfs(cur, distance) для поиска всех узлов на расстоянии k от узла target. Если cur пустой или уже был посещён, вернитесь. Добавьте cur в visited, чтобы его не посещали повторно. Если distance = k, добавьте cur в answer и вернитесь.

3⃣Рекурсивно вызовите dfs для детей и родителя cur. Вызовите dfs(target, 0), чтобы найти все узлы на расстоянии k. Верните answer после завершения DFS.

😎 Решение:

class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        addParent(root, null);
        
        List<Integer> answer = new ArrayList<>();
        Set<TreeNode> visited = new HashSet<>();
        
        dfs(target, k, visited, answer);
        return answer;
    }
    
    private void addParent(TreeNode cur, TreeNode parent) {
        if (cur != null) {
            cur.parent = parent;
            addParent(cur.left, cur);
            addParent(cur.right, cur);
        }
    }
    
    private void dfs(TreeNode cur, int distance, Set<TreeNode> visited, List<Integer> answer) {
        if (cur == null || visited.contains(cur)) return;
        visited.add(cur);
        if (distance == 0) {
            answer.add(cur.val);
            return;
        }
        dfs(cur.parent, distance - 1, visited, answer);
        dfs(cur.left, distance - 1, visited, answer);
        dfs(cur.right, distance - 1, visited, answer);
    }
}

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

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

Задача: №44. Wildcard Matching
Сложность: hard

Учитывая входную строку s и шаблон p, реализуйте сопоставление шаблонов с подстановочными знаками с поддержкой:
- '?' — соответствует любому одному символу
- '*' — соответствует любой последовательности символов (включая пустую)

Сопоставление должно охватывать всю строку s.

Пример:

Input: s = "adceb", p = "*a*b" Output: true

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

1⃣Создать двумерный булев массив dp размером (s.length + 1) × (p.length + 1), где dp[i][j] — true, если s[0..i-1] соответствует p[0..j-1].

2⃣Инициализировать базовые случаи:
- dp[0][0] = true
- dp[0][j] = true, если p[0..j-1] состоит только из * (иначе — false)

3⃣Заполнить таблицу:
- Если p[j-1] == s[i-1] или p[j-1] == '?' → dp[i][j] = dp[i-1][j-1]
- Если p[j-1] == '*' → dp[i][j] = dp[i][j-1] || dp[i-1][j]
- Иначе → dp[i][j] = false

😎 Решение:

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;

        for (int i = 1; i <= m; i++) {
            if (p.charAt(i - 1) == '*') {
                dp[0][i] = dp[0][i - 1];
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else {
                    dp[i][j] = false;
                }
            }
        }

        return dp[n][m];
    }
}

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