Задача: 84. Largest Rectangle in Histogram
Сложность: hard

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

Пример:

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

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

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

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

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

😎 Решение:

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxarea = 0;
        for (int i = 0; i < heights.length; i++) {
            for (int j = i; j < heights.length; j++) {
                int minheight = Integer.MAX_VALUE;
                for (int k = i; k <= j; k++) minheight = Math.min(
                    minheight,
                    heights[k]
                );
                maxarea = Math.max(maxarea, minheight * (j - i + 1));
            }
        }
        return maxarea;
    }
}

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

Задача: 367. Valid Perfect Square
Сложность: easy

Дано положительное целое число num, вернуть true, если num является идеальным квадратом, или false в противном случае.

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

Вы не должны использовать какие-либо встроенные библиотечные функции, такие как sqrt.

Пример:

Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.

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

1⃣Если num < 2, вернуть True. Установить левую границу в 2, а правую границу в num / 2.

2⃣Пока left <= right, взять x = (left + right) / 2, вычислить guess_squared = x * x и сравнить его с num:
Если guess_squared == num, вернуть True.
Если guess_squared > num, сдвинуть правую границу right = x - 1.
В противном случае сдвинуть левую границу left = x + 1.

3⃣Если вышли из цикла, вернуть False.

😎 Решение:

class Solution {
    public boolean isPerfectSquare(int num) {
        if (num < 2) {
            return true;
        }

        long x = num / 2;
        while (x * x > num) {
            x = (x + num / x) / 2;
        }
        return x * x == num;
    }
}

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

Задача: 1213. Intersection of Three Sorted Arrays
Сложность: easy

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

Пример:

Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
Output: [1,5]
Explanation: Only 1 and 5 appeared in the three arrays.

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

1⃣Инициализируйте counter как TreeMap для записи чисел, которые появляются в трех массивах, и количество их появлений.

2⃣Пройдитесь по массивам arr1, arr2 и arr3, чтобы посчитать частоты появления элементов.

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

😎 Решение:

class Solution {
    public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
        List<Integer> ans = new ArrayList<>();

        Map<Integer, Integer> counter = new TreeMap<>();

        for (Integer e: arr1) {
            counter.put(e, counter.getOrDefault(e, 0) + 1);
        }
        for (Integer e: arr2) {
            counter.put(e, counter.getOrDefault(e, 0) + 1);
        }
        for (Integer e: arr3) {
            counter.put(e, counter.getOrDefault(e, 0) + 1);
        }

        for (Integer item: counter.keySet()) {
            if (counter.get(item) == 3) {
                ans.add(item);
            }
        }
        return ans;

    }
}

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

Задача: 1344. Angle Between Hands of a Clock
Сложность: medium

Даны два числа, hour и minutes. Вернуть меньший угол (в градусах), образованный часовой и минутной стрелками.

Ответы с точностью до 10^-5 от фактического значения будут считаться правильными.

Пример:

Input: hour = 12, minutes = 30
Output: 165

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

1⃣Рассчитать углы: minutes_angle = 6 * minutes и hour_angle = (hour % 12 + minutes / 60) * 30.

2⃣Найти разницу: diff = abs(hour_angle - minutes_angle).

3⃣Вернуть меньший угол: min(diff, 360 - diff).

😎 Решение:

class Solution {
    public double angleClock(int hour, int minutes) {
        int oneMinAngle = 6;
        int oneHourAngle = 30;

        double minutesAngle = oneMinAngle * minutes;
        double hourAngle = (hour % 12 + minutes / 60.0) * oneHourAngle;

        double diff = Math.abs(hourAngle - minutesAngle);
        return Math.min(diff, 360 - diff);
    }
}

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

Задача: 279. Perfect Squares
Сложность: medium

Дано целое число n, верните наименьшее количество чисел, являющихся совершенными квадратами, сумма которых равна n.

Совершенный квадрат — это целое число, являющееся квадратом целого числа; другими словами, это произведение некоторого целого числа на самого себя. Например, 1, 4, 9 и 16 являются совершенными квадратами, тогда как 3 и 11 не являются.

Пример:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

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

1⃣Инициализация:
Создайте массив dp размером n + 1 и заполните его значениями Integer.MAX_VALUE, кроме dp[0], которое установите в 0.
Предварительно вычислите все совершенные квадраты, которые меньше или равны n, и сохраните их в массиве square_nums.

2⃣Заполнение массива dp:
Для каждого числа i от 1 до n:
Для каждого совершенного квадрата s из массива square_nums:
Если i меньше текущего совершенного квадрата s, прервите внутренний цикл.
Обновите dp[i], чтобы он содержал минимальное количество чисел, сумма которых равна i.

3⃣Возврат результата:
Верните значение dp[n], которое будет содержать наименьшее количество совершенных квадратов, сумма которых равна n.

😎 Решение:

class Solution {

  public int numSquares(int n) {
    int dp[] = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;

    int max_square_index = (int) Math.sqrt(n) + 1;
    int square_nums[] = new int[max_square_index];
    for (int i = 1; i < max_square_index; ++i) {
      square_nums[i] = i * i;
    }

    for (int i = 1; i <= n; ++i) {
      for (int s = 1; s < max_square_index; ++s) {
        if (i < square_nums[s])
          break;
        dp[i] = Math.min(dp[i], dp[i - square_nums[s]] + 1);
      }
    }
    return dp[n];
  }
}

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

Задача: CodeTestcaseTest ResultTest Result1523. Count Odd Numbers in an Interval Range
Сложность: easy

Даны два неотрицательных целых числа low и high. Верните количество нечётных чисел между low и high (включительно).

Пример:

Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].

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

1⃣Проверьте, является ли число low нечётным. Это можно легко сделать с помощью оператора %, но мы используем побитовый оператор &, так как он более эффективен.

2⃣Если low нечётное, увеличьте его на 1.

3⃣Верните (high - low) / 2 + 1. Важный момент здесь - проверить, не стало ли low больше, чем high после увеличения. Это произойдёт, если low = high, и в этом случае следует вернуть 0.

😎 Решение:

class Solution {
    public int countOdds(int low, int high) {
        if ((low & 1) == 0) {
            low++;
        }
        return low > high ? 0 : (high - low) / 2 + 1;
    }
}

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

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

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