Задача: 1276. Number of Burgers with No Waste of Ingredients
Сложность: medium

Даны два целых числа tomatoSlices и cheeseSlices. Ингредиенты разных бургеров таковы: Jumbo Burger: 4 ломтика помидора и 1 ломтик сыра. Small Burger: 2 ломтика помидора и 1 ломтик сыра. Верните [total_jumbo, total_small] так, чтобы количество оставшихся tomatoSlices было равно 0, а количество оставшихся cheeseSlices было равно 0. Если невозможно сделать так, чтобы оставшиеся tomatoSlices и cheeseSlices были равны 0, верните [].

Пример:

Input: tomatoSlices = 16, cheeseSlices = 7
Output: [1,6]

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

1⃣Проверьте, возможно ли решить задачу, убедившись, что tomatoSlices четно и находится в допустимых пределах.

2⃣Решите систему уравнений:
4J + 2S = tomatoSlices
J + S = cheeseSlices

3⃣Если решение существует, верните его, иначе верните пустой список.

😎 Решение:

public class Solution {
    public List<Integer> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        if (tomatoSlices % 2 != 0 || tomatoSlices < 2 * cheeseSlices || tomatoSlices > 4 * cheeseSlices) {
            return new ArrayList<>();
        }
        int total_jumbo = (tomatoSlices - 2 * cheeseSlices) / 2;
        int total_small = cheeseSlices - total_jumbo;
        return Arrays.asList(total_jumbo, total_small);
    }
}

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

Задача: 1498. Number of Subsequences That Satisfy the Given Sum Condition
Сложность: medium

Вам дан массив целых чисел nums и целое число target.

Верните количество непустых подпоследовательностей массива nums, таких что сумма минимального и максимального элемента в них меньше или равна target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

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

1⃣Инициализация и подготовка:
Инициализируйте переменные answer равным 0 и n как длину массива nums.
Отсортируйте массив nums.
Подготовьте массив power для хранения степеней двойки до n по модулю 10^9+7.

2⃣Итерация и бинарный поиск:
Для каждого индекса left от 0 до n - 1 выполните бинарный поиск, чтобы найти самый правый индекс right, где nums[right] <= target - nums[left].
Если left <= right, добавьте количество допустимых подпоследовательностей к answer.

3⃣Возврат результата:
Верните answer по модулю 10^9+7.

😎 Решение:

class Solution {
    public static int binarySearchRightmost(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
    
    public int numSubseq(int[] nums, int target) {
        int n = nums.length;
        int mod = 1_000_000_007;
        Arrays.sort(nums);
        
        int[] power = new int[n];
        power[0] = 1;
        for (int i = 1; i < n; ++i) {
            power[i] = (power[i - 1] * 2) % mod;
        }
        
        int answer = 0;

        for (int left = 0; left < n; left++) {
            int right = binarySearchRightmost(nums, target - nums[left]) - 1;
            if (right >= left) {
                answer += power[right - left];
                answer %= mod;
            }
        }
        return answer;
    }
}

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

Задача: 1137. N-th Tribonacci Number
Сложность: easy

Трибоначчи последовательность Tn определяется следующим образом:

T0 = 0, T1 = 1, T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 для n >= 0.

Дано n, вернуть значение Tn.

Пример:

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

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

1⃣Если n < 3, вернуть значение n-го терма, как указано в описании задачи.

2⃣Инициализировать a, b и c как базовые случаи. Установить a = 0, b = 1, c = 1.

3⃣Для следующих n - 2 шагов обновлять a, b, c следующим образом: a = b, b = c, c = a + b + c. Вернуть c.

😎 Решение:

class Solution {
    public int tribonacci(int n) {
        if (n < 3) {
            return n > 0 ? 1 : 0;
        }
        
        int a = 0, b = 1, c = 1;
        for (int i = 0; i < n - 2; ++i) {
            int tmp = a + b + c;
            a = b;
            b = c;
            c = tmp;
        }
        
        return c;
    }
}

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

Задача: 255. Verify Preorder Sequence in Binary Search Tree
Сложность: medium

Дан массив уникальных целых чисел preorder. Верните true, если это правильная последовательность обхода в порядке предварительного (preorder) обхода для бинарного дерева поиска.

Пример:

Input: preorder = [5,2,1,3,6]
Output: true

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

1⃣Объявите целое число minLimit с маленьким значением, например, минус бесконечность, и стек.

2⃣Итерируйте по массиву preorder. Для каждого num:
Очистите стек. Пока верх стека меньше num, извлекайте из стека и обновляйте minLimit.
Если num <= minLimit, верните false.
Добавьте num в стек.

3⃣Верните true, если удалось пройти весь массив.

😎 Решение:

import java.util.Stack;

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int minLimit = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();
        
        for (int num: preorder) {
            while (!stack.isEmpty() && stack.peek() < num) {
                minLimit = stack.pop();
            }
            
            if (num <= minLimit) {
                return false;
            }
            
            stack.push(num);
        }
        
        return true;
    }
}

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

Задача: 108. Convert Sorted Array to Binary Search Tree
Сложность: easy

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

Пример:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

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

1⃣Инициализация функции помощника: Реализуйте функцию помощника helper(left, right), которая строит двоичное дерево поиска (BST) из элементов массива nums между индексами left и right.
Если left > right, это означает, что элементов для построения поддерева нет, возвращаем None.

2⃣Выбор корня и разделение массива:
Выберите элемент в середине для корня: p = (left + right) // 2.
Инициализируйте корень: root = TreeNode(nums[p]).

3⃣Рекурсивное построение поддеревьев:
Рекурсивно стройте левое поддерево: root.left = helper(left, p - 1). Рекурсивно стройте правое поддерево: root.right = helper(p + 1, right).
В качестве результата возвращайте helper(0, len(nums) - 1), начиная с корня дерева.

😎 Решение:

class Solution {
    int[] nums;

    public TreeNode helper(int left, int right) {
        if (left > right) return null;

        int p = (left + right) / 2;
        TreeNode root = new TreeNode(nums[p]);
        root.left = helper(left, p - 1);
        root.right = helper(p + 1, right);
        return root;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        this.nums = nums;
        return helper(0, nums.length - 1);
    }
}

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

Задача: 520. Detect Capital
Сложность: easy

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

Все буквы в этом слове заглавные, как "USA".
Все буквы в этом слове строчные, как "leetcode".
Только первая буква в этом слове заглавная, как "Google".
Дана строка word. Верните true, если использование заглавных букв в ней правильное.

Пример:

Input: word = "USA"
Output: true

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

1⃣Шаблон для первого случая в регулярном выражении: [A-Z]*, где [A-Z] соответствует одной заглавной букве от 'A' до 'Z', а * означает повторение предыдущего шаблона 0 или более раз. Этот шаблон представляет "Все заглавные буквы".

2⃣Шаблон для второго случая в регулярном выражении: [a-z]*, где [a-z] соответствует одной строчной букве от 'a' до 'z'. Этот шаблон представляет "Все строчные буквы". Шаблон для третьего случая в регулярном выражении: [A-Z][a-z]*, где первая буква заглавная, а остальные строчные.

3⃣Объедините эти три шаблона: [A-Z]*|[a-z]*|[A-Z][a-z]*, где | означает "или". Мы можем объединить второй и третий случай, получив . [a-z]*, где . соответствует любому символу. Итоговый шаблон: [A-Z]*|.[a-z]*.

😎 Решение:

import java.util.regex.*;

class Solution {
    public boolean detectCapitalUse(String word) {
        String pattern = "[A-Z]*|.[a-z]*";
        return Pattern.matches(pattern, word);
    }
}

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

Задача: 107. Binary Tree Level Order Traversal II
Сложность: medium

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

Пример:

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

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

1⃣Инициализируйте список вывода levels. Длина этого списка определяет, какой уровень в данный момент обновляется. Вам следует сравнить этот уровень len(levels) с уровнем узла level, чтобы убедиться, что вы добавляете узел на правильный уровень. Если вы все еще находитесь на предыдущем уровне, добавьте новый уровень, вставив новый список в levels.

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

3⃣Рекурсивно обработайте дочерние узлы, если они не равны None, используя функцию helper(node.left / node.right, level + 1).

😎 Решение:

class Solution {
    List<List<Integer>> levels = new ArrayList<List<Integer>>();

    public void helper(TreeNode node, int level) {
        if (levels.size() == level) levels.add(new ArrayList<Integer>());
        levels.get(level).add(node.val);
        if (node.left != null) helper(node.left, level + 1);
        if (node.right != null) helper(node.right, level + 1);
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) return levels;
        helper(root, 0);
        Collections.reverse(levels);
        return levels;
    }
}

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

Задача: 1429. First Unique Number
Сложность: medium

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

Реализуйте класс FirstUnique:
- FirstUnique(int[] nums) Инициализирует объект числами в очереди.
- int showFirstUnique() возвращает значение первого уникального элемента в очереди и возвращает -1, если такого элемента нет.
- void add(int value) вставляет значение в очередь.

Пример:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output: 
[null,2,null,2,null,3,null,-1]
Explanation: 
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5);            // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1

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

1⃣Инициализируйте объект FirstUnique с числами в очереди, добавляя их в структуру данных для отслеживания уникальности и порядка.

2⃣Метод showFirstUnique возвращает значение первого уникального элемента в очереди, если таковой существует, или -1, если уникальных элементов нет.

3⃣Метод add добавляет новое значение в очередь. Если значение уже было добавлено ранее, обновляет его статус уникальности и удаляет его из множества уникальных значений, если оно больше не уникально.

😎 Решение:

class FirstUnique {
  
  private Set<Integer> setQueue = new LinkedHashSet<>();
  private Map<Integer, Boolean> isUnique = new HashMap<>();
  
  public FirstUnique(int[] nums) {
    for (int num : nums) {
      this.add(num);
    }
  }
    
  public int showFirstUnique() {
    if (!setQueue.isEmpty()) {
       return setQueue.iterator().next();
    }
    return -1;
  }
    
  public void add(int value) {
    if (!isUnique.containsKey(value)) {
      isUnique.put(value, true);
      setQueue.add(value);
    } else if (isUnique.get(value)) {
      isUnique.put(value, false);
      setQueue.remove(value);
    }
  }
}

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

Задача: 523. Continuous Subarray Sum
Сложность: medium

Дан целочисленный массив nums и целое число k. Верните true, если в nums есть хорошая подмассив, или false в противном случае.

Хороший подмассив — это подмассив, который:

имеет длину не менее двух, и
сумма элементов подмассива является кратной k.
Учтите:

Подмассив — это непрерывная часть массива.
Целое число x является кратным k, если существует целое число n такое, что x = n * k. Число 0 всегда является кратным k.

Пример:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

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

1⃣Инициализируйте целое число prefixMod = 0 и хеш-таблицу modSeen. Инициализируйте modSeen[0] значением -1, чтобы учесть начальное значение prefixMod.

2⃣Итеративно пройдите по всем элементам массива nums.

3⃣Вычислите prefixMod как (prefixMod + nums[i]) % k. Если prefixMod существует в хеш-таблице: Если размер самого длинного подмассива с модулем k составляет не менее 2, верните true. Если prefixMod не существует в хеш-таблице: Установите modSeen[prefixMod] = i. Если после завершения итерации не найден хороший подмассив, верните false.

😎 Решение:

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int prefixMod = 0;
        Map<Integer, Integer> modSeen = new HashMap<>();
        modSeen.put(0, -1);
        
        for (int i = 0; i < nums.length; i++) {
            prefixMod = (prefixMod + nums[i]) % k;
            
            if (modSeen.containsKey(prefixMod)) {
                if (i - modSeen.get(prefixMod) > 1) {
                    return true;
                }
            } else {
                modSeen.put(prefixMod, i);
            }
        }
        
        return false;
    }
}

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

Задача: 668. Kth Smallest Number in Multiplication Table
Сложность: hard

Почти каждый использовал таблицу умножения. Таблица умножения размером m x n - это целочисленная матрица mat, где mat[i][j] == i * j (индексация начинается с 1).

Даны три целых числа m, n и k. Верните k-й наименьший элемент в таблице умножения размером m x n.

Пример:

Input: m = 3, n = 3, k = 5
Output: 3
Explanation: The 5th smallest number is 3.

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

1⃣Установка границ поиска:
Установите нижнюю границу left равной 1 и верхнюю границу right равной m * n.

2⃣Бинарный поиск:
Используйте бинарный поиск, чтобы найти k-й наименьший элемент.
Для каждого среднего значения mid, посчитайте количество элементов в таблице умножения, которые меньше или равны mid.

3⃣Проверка количества элементов:
Если количество элементов меньше k, увеличьте нижнюю границу (left).
Если количество элементов больше или равно k, уменьшите верхнюю границу (right).

😎 Решение:

public class Solution {
    public int findKthNumber(int m, int n, int k) {
        int left = 1, right = m * n;
        
        while (left < right) {
            int mid = (left + right) / 2;
            if (countLessEqual(m, n, mid) < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
    
    private int countLessEqual(int m, int n, int x) {
        int count = 0;
        for (int i = 1; i <= m; i++) {
            count += Math.min(x / i, n);
        }
        return count;
    }
}

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

Задача: 59. Spiral Matrix II
Сложность: medium

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

Пример:

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

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

1⃣Определение направлений движения:
Для обхода матрицы используются четыре направления, формирующие слои. Создается массив dir, который хранит изменения координат x и y для каждого направления. Например, при движении слева направо (направление №1) координата x остается неизменной, а y увеличивается (x=0, y=1). При движении справа налево (направление №3) x остается неизменным, а y уменьшается (x=0, y=-1).

2⃣Перемещение по матрице:
Переменные row и col представляют текущие координаты x и y соответственно. Они обновляются в зависимости от направления движения. Применяется предварительно определенный массив dir с изменениями координат x и y для каждого из четырех направлений.

3⃣Изменение направления:
Направление изменяется, когда следующая строка или столбец в определенном направлении имеют ненулевое значение, что указывает на то, что они уже были пройдены. Переменная d представляет текущий индекс направления. Переход к следующему направлению в массиве dir осуществляется с использованием формулы (d+1)%4. Это позволяет вернуться к направлению 1 после завершения одного полного круга от направления 1 до направления 4.

😎 Решение:

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int cnt = 1;
        int dir[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
        int d = 0;
        int row = 0;
        int col = 0;
        while (cnt <= n * n) {
            result[row][col] = cnt++;
            int r = Math.floorMod(row + dir[d][0], n);
            int c = Math.floorMod(col + dir[d][1], n);

            if (result[r][c] != 0) d = (d + 1) % 4;

            row += dir[d][0];
            col += dir[d][1];
        }
        return result;
    }
}

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

Задача: 379. Design Phone Directory
Сложность: medium

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

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

PhoneDirectory(int maxNumbers) Инициализирует телефонный справочник с количеством доступных слотов maxNumbers.
int get() Предоставляет номер, который никому не назначен. Возвращает -1, если номера недоступны.
bool check(int number) Возвращает true, если слот доступен, и false в противном случае.
void release(int number) Перераспределяет или освобождает номер слота.

Пример:

Input
["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"]
[[3], [], [], [2], [], [2], [2], [2]]
Output
[null, 0, 1, true, 2, false, null, true]

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

1⃣Инициализировать массив isSlotAvailable размером maxNumbers, установив значение true во всех индексах.

2⃣Метод get(): Проходить по массиву isSlotAvailable. Если найдется true на каком-либо индексе, установить isSlotAvailable[i] = false и вернуть i. Если доступных слотов нет, вернуть -1.
Метод check(number): Вернуть значение isSlotAvailable[number].

3⃣Метод release(number): Установить isSlotAvailable[number] = true.

😎 Решение:

public class PhoneDirectory {
    private boolean[] isSlotAvailable;

    public PhoneDirectory(int maxNumbers) {
        isSlotAvailable = new boolean[maxNumbers];
        for (int i = 0; i < maxNumbers; i++) {
            isSlotAvailable[i] = true;
        }
    }

    public int get() {
        for (int i = 0; i < isSlotAvailable.length; i++) {
            if (isSlotAvailable[i]) {
                isSlotAvailable[i] = false;
                return i;
            }
        }
        return -1;
    }

    public boolean check(int number) {
        return isSlotAvailable[number];
    }

    public void release(int number) {
        isSlotAvailable[number] = true;
    }
}

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

Задача: 1044. Longest Duplicate Substring
Сложность: hard

Учитывая строку s, рассмотрите все дублированные подстроки: (смежные) подстроки s, которые встречаются 2 или более раз.Вхождения могут перекрываться. Верните любую дублированную подстроку, которая имеет наибольшую возможную длину.Если в s нет дублирующейся подстроки, ответом будет "".

Пример:

Input: s = "banana"
Output: "ana"

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

1⃣Использование двоичного поиска для определения длины дублированной подстроки:
Двоичный поиск используется для поиска максимальной длины дублированной подстроки.

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

3⃣Хеширование с помощью функции rolling hash:
Rolling hash позволяет быстро вычислять хеши подстрок фиксированной длины и сравнивать их для поиска дубликатов.

😎 Решение:

public class Solution {
    public String longestDupSubstring(String s) {
        int n = s.length();
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) nums[i] = (int)s.charAt(i) - (int)'a';
        int a = 26;
        long modulus = (long)Math.pow(2, 32);
        
        int left = 1, right = n;
        String result = "";
        while (left < right) {
            int mid = (left + right) / 2;
            String dup = search(mid, a, modulus, n, nums);
            if (dup != null) {
                result = dup;
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return result;
    }

    private String search(int L, int a, long modulus, int n, int[] nums) {
        long h = 0;
        for (int i = 0; i < L; ++i) h = (h * a + nums[i]) % modulus;
        HashSet<Long> seen = new HashSet<>();
        seen.add(h);
        long aL = 1;
        for (int i = 1; i <= L; ++i) aL = (aL * a) % modulus;
        for (int start = 1; start < n - L + 1; ++start) {
            h = (h * a - nums[start - 1] * aL % modulus + modulus) % modulus;
            h = (h + nums[start + L - 1]) % modulus;
            if (seen.contains(h)) return s.substring(start, start + L);
            seen.add(h);
        }
        return null;
    }
}

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

Задача: 1005. Maximize Sum Of Array After K Negations
Сложность: easy

Учитывая целочисленный массив nums и целое число k, измените массив следующим образом: выберите индекс i и замените nums[i] на -nums[i]. Вы должны применить этот процесс ровно k раз. Вы можете выбрать один и тот же индекс i несколько раз. Верните наибольшую возможную сумму массива после его модификации таким образом.

Пример:

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

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

1⃣Сортировка массива:
Отсортируйте массив nums по возрастанию, чтобы наибольшее количество раз менять самые маленькие (отрицательные) значения на их противоположные.

2⃣Модификация массива:
Пройдитесь по отсортированному массиву и замените k наименьших значений на их противоположные (умножьте на -1). Если встретите 0, прекратите дальнейшие изменения, так как изменение 0 на -0 не имеет смысла.

3⃣Проверка остатка изменений:
Если после первого прохода остались изменения (k нечетное), то найдите минимальное значение в измененном массиве и еще раз поменяйте его знак. Это обеспечит максимальную сумму.

😎 Решение:

import java.util.Arrays;

public class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length; i++) {
            if (k > 0 && nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        
        if (k % 2 == 1) {
            Arrays.sort(nums);
            nums[0] = -nums[0];
        }
        
        return Arrays.stream(nums).sum();
    }
}

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

Задача: 983. Minimum Cost For Tickets
Сложность: medium

Вы запланировали несколько поездок на поезде за год вперёд. Дни года, в которые вы будете путешествовать, заданы в виде целочисленного массива days. Каждый день — это целое число от 1 до 365.

Билеты на поезд продаются тремя различными способами:

однодневный билет продаётся за costs[0] долларов,
семидневный билет продаётся за costs[1] долларов, и
тридцатидневный билет продаётся за costs[2] долларов.
Билеты позволяют путешествовать указанное количество дней подряд.

Например, если мы покупаем семидневный билет на 2-й день, то мы можем путешествовать в течение 7 дней: 2, 3, 4, 5, 6, 7 и 8.
Верните минимальное количество долларов, которое вам нужно, чтобы путешествовать каждый день, указанный в списке days.

Пример:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.

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

1⃣Создайте массив dp размером на один больше последнего дня, в который нужно путешествовать. Инициализируйте все значения -1, что означает, что ответ для этого дня ещё не был вычислен. Также создайте хэш-набор isTravelNeeded из days.

2⃣Создайте функцию solve, которая принимает аргумент currDay. Если currDay больше последнего дня, когда нужно путешествовать, просто верните 0, так как все дни уже покрыты. Если currDay отсутствует в isTravelNeeded, перейдите к currDay + 1. Если ответ для currDay в массиве dp не равен -1, это означает, что ответ уже был вычислен, поэтому просто верните его.

3⃣Найдите стоимость трёх билетов, которые можно использовать в этот день, добавьте соответствующую стоимость и обновите dp[currDay] соответственно в рекурсивном вызове. Вызовите solve, передав currDay = 1, и верните ответ.

😎 Решение:

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

class Solution {
    private Set<Integer> isTravelNeeded = new HashSet<>();
    
    private int solve(int[] dp, int[] days, int[] costs, int currDay) {
        if (currDay > days[days.length - 1]) {
            return 0;
        }
        
        if (!isTravelNeeded.contains(currDay)) {
            return solve(dp, days, costs, currDay + 1);
        }
        
        if (dp[currDay] != -1) {
            return dp[currDay];
        }
        
        int oneDay = costs[0] + solve(dp, days, costs, currDay + 1);
        int sevenDay = costs[1] + solve(dp, days, costs, currDay + 7);
        int thirtyDay = costs[2] + solve(dp, days, costs, currDay + 30);
        
        dp[currDay] = Math.min(oneDay, Math.min(sevenDay, thirtyDay));
        return dp[currDay];
    }
    
    public int mincostTickets(int[] days, int[] costs) {
        int lastDay = days[days.length - 1];
        int[] dp = new int[lastDay + 1];
        for (int i = 0; i <= lastDay; i++) {
            dp[i] = -1;
        }
        
        for (int day : days) {
            isTravelNeeded.add(day);
        }
        
        return solve(dp, days, costs, 1);
    }
}

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

Задача: 1416. Restore The Array
Сложность: hard

Программа должна была напечатать массив целых чисел. Программа забыла напечатать пробелы, и массив напечатан как строка цифр s, и всё, что мы знаем, это что все числа в массиве были в диапазоне [1, k] и в массиве нет ведущих нулей.

Учитывая строку s и целое число k, верните количество возможных массивов, которые могут быть напечатаны как s с использованием упомянутой программы. Так как ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]

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

1⃣Создать массив dp размера m + 1, чтобы хранить значения dfs(x).

2⃣Для получения значения dfs(start), если dp[start] не равно нулю, вернуть его значение. Иначе:
Если s[start] == 0, вернуть 0.
Если start = m, вернуть 1.
Инициализировать count = 0, чтобы считать количество возможных массивов.
Перебрать все возможные конечные индексы end, и если s[start ~ end] представляет допустимое число, продолжить рекурсивный вызов dfs(end + 1) и обновить count как count += dfs(end + 1).
Обновить dp[start] значением dfs(start).

3⃣Вернуть dfs(0).

😎 Решение:

class Solution {
    int mod = 1_000_000_007;

    private int dfs(int[] dp, int start, String s, int k) {
        if (dp[start] != 0)
            return dp[start];

        if (start == s.length())
            return 1;

        if (s.charAt(start) == '0')
            return 0;

        int count = 0;
        for (int end = start; end < s.length(); ++end) {
            String currNumber = s.substring(start, end + 1);
            if (Long.parseLong(currNumber) > k)
                break;
            count = (count + dfs(dp, end + 1, s, k)) % mod;
        }

        dp[start] = count;
        return count;
    }
    
    public int numberOfArrays(String s, int k) {
        int m = s.length();
        int[] dp = new int[m + 1];
        return dfs(dp, 0, s, k);
    }
}

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

Задача: 124. Binary Tree Maximum Path Sum
Сложность: hard

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

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

Пример:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1

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

1⃣Наивный способ — разделить массив на две части и в каждой найти ошибку.
Но он потратил O(n²) времени, так как мы заново просматриваем массив для разделения каждой точки.

2⃣Оптимизируем с помощью динамического программирования:
создаём два массива:
leftProfits[i]— максимальная прибыль от 0 до i
rightProfits[i]— максимальная прибыль от i до конца.
Этот подход уменьшает сложность до O(n).

3⃣После расчета двух массивов суммируемая прибыль из левой и правой частей по каждому соединению:
maxProfit = max(maxProfit, leftProfits[i] + rightProfits[i+1])

😎 Решение:

class Solution {
    public int maxProfit(int[] prices) {
        int length = prices.length;
        if (length <= 1) return 0;

        int leftMin = prices[0];
        int rightMax = prices[length - 1];

        int[] leftProfits = new int[length];
        int[] rightProfits = new int[length + 1];

        for (int l = 1; l < length; ++l) {
            leftProfits[l] = Math.max(leftProfits[l - 1], prices[l] - leftMin);
            leftMin = Math.min(leftMin, prices[l]);

            int r = length - 1 - l;
            rightProfits[r] = Math.max(
                rightProfits[r + 1],
                rightMax - prices[r]
            );
            rightMax = Math.max(rightMax, prices[r]);
        }

        int maxProfit = 0;
        for (int i = 0; i < length; ++i) {
            maxProfit = Math.max(
                maxProfit,
                leftProfits[i] + rightProfits[i + 1]
            );
        }
        return maxProfit;
    }
}

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

Задача: 1261. Find Elements in a Contaminated Binary Tree
Сложность: medium

Дано двоичное дерево со следующими правилами: root.val == 0 Если treeNode.val == x и treeNode.left != null, то treeNode.left.val == 2 * x + 1 Если treeNode.val == x и treeNode.right != null, то treeNode.right.val == 2 * x + 2 Теперь двоичное дерево загрязнено, то есть все treeNode.val были изменены на -1. Реализация класса FindElements: FindElements(TreeNode* root) Инициализирует объект с загрязненным двоичным деревом и восстанавливает его. bool find(int target) Возвращает true, если целевое значение существует в восстановленном двоичном дереве.

Пример:

Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output
[null,false,true]

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

1⃣Восстановление дерева: Начните с корневого узла, установите его значение на 0. Затем рекурсивно восстановите значения для всех узлов, используя правила left.val = 2 * parent.val + 1 и right.val = 2 * parent.val + 2.

2⃣Сохранение значений: Используйте структуру данных, такую как множество (set), для хранения всех восстановленных значений узлов.

3⃣Поиск значений: Реализуйте метод поиска, который проверяет, содержится ли целевое значение в множестве восстановленных значений.

😎 Решение:

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

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

public class FindElements {
    private TreeNode root;
    private Set<Integer> values = new HashSet<>();
    
    public FindElements(TreeNode root) {
        this.root = root;
        root.val = 0;
        values.add(0);
        recover(root);
    }
    
    private void recover(TreeNode node) {
        if (node.left != null) {
            node.left.val = 2 * node.val + 1;
            values.add(node.left.val);
            recover(node.left);
        }
        if (node.right != null) {
            node.right.val = 2 * node.val + 2;
            values.add(node.right.val);
            recover(node.right);
        }
    }
    
    public boolean find(int target) {
        return values.contains(target);
    }
}

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

Задача: 1663. Smallest String With A Given Numeric Value
Сложность: medium

Числовое значение строчной буквы определяется ее позицией (начиная с 1) в алфавите, поэтому числовое значение a равно 1, числовое значение b равно 2, числовое значение c равно 3 и так далее.

Числовое значение строки, состоящей из строчных букв, определяется как сумма числовых значений ее символов. Например, числовое значение строки "abe" равно 1 + 2 + 5 = 8.

Вам даны два целых числа n и k. Верните лексикографически наименьшую строку длиной n с числовым значением, равным k.

Обратите внимание, что строка x лексикографически меньше строки y, если x идет перед y в словарном порядке, то есть либо x является префиксом y, либо, если i - первая позиция, где x[i] != y[i], то x[i] идет перед y[i] в алфавитном порядке.

Пример:

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

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

1⃣Построить строку или массив символов result для хранения выбранных символов для каждой позиции.

2⃣Итерация от позиции 1 до n и заполнение символом каждой позиции:
Найти позиции, которые нужно заполнить, исключая текущую позицию, задаваемую переменной positionsLeft как n - position - 1.
Если значение k больше, чем positionsLeft * 26, зарезервировать числовое значение 26 (символ z) для всех оставшихся позиций positionsLeft. Вычислить значение текущей позиции, заданное переменной add, как k - (positionsLeft * 26). Вычесть рассчитанное значение add из k, чтобы найти оставшееся значение k после заполнения текущей позиции.
Иначе, заполнить текущую позицию символом a, имеющим числовое значение 1. Вычесть 1 из k, чтобы найти оставшееся значение k после заполнения текущей позиции.

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

😎 Решение:

class Solution {
    public String getSmallestString(int n, int k) {
        char[] result = new char[n];
        for (int position = 0; position < n; position++) {
            int positionsLeft = (n - position - 1);
            if (k > positionsLeft * 26) {
                int add = k - (positionsLeft * 26);
                result[position] = (char) ('a' + add - 1);
                k -= add;
            } else {
                result[position] = 'a';
                k--;
            }
        }
        return new String(result);
    }
}

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

Задача: 679. 24 Game
Сложность: hard

Дан массив целых чисел cards длиной 4. У вас есть четыре карты, каждая из которых содержит число в диапазоне от 1 до 9. Вам нужно расположить числа на этих картах в математическом выражении, используя операторы ['+', '-', '*', '/'] и скобки '(' и ')' так, чтобы получить значение 24.

Вы ограничены следующими правилами:

Оператор деления '/' представляет собой реальное деление, а не целочисленное деление.
Например, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
Каждая операция выполняется между двумя числами. В частности, мы не можем использовать '-' как унарный оператор.
Например, если cards = [1, 1, 1, 1], выражение "-1 - 1 - 1 - 1" не допускается.
Вы не можете объединять числа вместе.
Например, если cards = [1, 2, 1, 2], выражение "12 + 12" недопустимо.
Вернуть true, если вы можете получить такое выражение, которое оценивается в 24, и false в противном случае.

Пример:

Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

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

1⃣Создайте функцию generatePossibleResults(a, b), которая возвращает массив результатов всех возможных математических операций над двумя числами.

2⃣ Создайте функцию checkIfResultReached(list), чтобы проверить, можем ли мы достичь результата 24, используя текущий массив list. Сначала проверьте базовые условия: если размер массива равен 1, верните true, если результат равен 24, иначе верните false.

3⃣Если размер массива больше 1, выберите любые два числа из списка, выполните все математические операции над ними, создайте новый список с обновленными элементами и снова вызовите рекурсивную функцию с этим новым списком. Если ни одна комбинация не приводит к результату 24, верните false. Вызовите checkIfResultReached с исходным списком карт.

😎 Решение:

import java.util.*;

class Solution {
    public List<Double> generatePossibleResults(double a, double b) {
        List<Double> res = new ArrayList<>(Arrays.asList(a + b, a - b, b - a, a * b));
        if (a != 0) res.add(b / a);
        if (b != 0) res.add(a / b);
        return res;
    }

    public boolean checkIfResultReached(List<Double> list) {
        if (list.size() == 1) return Math.abs(list.get(0) - 24) <= 0.1;

        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                List<Double> newList = new ArrayList<>();
                for (int k = 0; k < list.size(); k++) {
                    if (k != i && k != j) newList.add(list.get(k));
                }
                for (double res : generatePossibleResults(list.get(i), list.get(j))) {
                    newList.add(res);
                    if (checkIfResultReached(newList)) return true;
                    newList.remove(newList.size() - 1);
                }
            }
        }
        return false;
    }

    public boolean judgePoint24(int[] cards) {
        List<Double> list = new ArrayList<>();
        for (int card : cards) {
            list.add((double) card);
        }
        return checkIfResultReached(list);
    }
}

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