Задача: №19. Remove Nth Node From End of List
Сложность: medium

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

Пример:

Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]

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

1⃣Создать фиктивный узел dummy, указывающий на head, чтобы удобно было обрабатывать крайние случаи (например, удаление головы).

2⃣Инициализировать два указателя fast и slow, оба на dummy. Сначала сдвинуть fast на n шагов вперёд.

3⃣Затем двигать оба указателя, пока fast.next не станет null. Теперь slow находится перед узлом, который нужно удалить.


😎 Решение:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy;
        ListNode slow = dummy;

        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;

        return dummy.next;
    }
}

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

Задача: 1238. Circular Permutation in Binary Representation
Сложность: medium

Даны 2 целых числа n и start. Ваша задача - вернуть любую перестановку p из (0,1,2.....,2^n -1) такую, что : p[0] = start p[i] и p[i+1] отличаются только одним битом в их двоичном представлении. p[0] и p[2^n -1] также должны отличаться только одним битом в их двоичном представлении.

Пример:

Input: n = 2, start = 3
Output: [3,2,0,1]

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

1⃣Генерация Грей-кода:
Генерация Грей-кода для чисел от 0 до 2𝑛−1

2⃣Определение начальной позиции:
Находим индекс числа start в последовательности Грей-кода.

3⃣Построение перестановки:
Формируем перестановку, начиная с числа start и следуя по циклическому Грей-коду.

😎 Решение:

import java.util.*;

public class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        List<Integer> gray = grayCode(n);
        int startIndex = gray.indexOf(start);
        List<Integer> result = new ArrayList<>();
        result.addAll(gray.subList(startIndex, gray.size()));
        result.addAll(gray.subList(0, startIndex));
        return result;
    }

    private List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        int numElements = 1 << n;
        for (int i = 0; i < numElements; i++) {
            result.add(i ^ (i >> 1));
        }
        return result;
    }
}

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

Задача: 972. Equal Rational Numbers
Сложность: hard

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

Рациональное число может быть представлено с использованием до трех частей: <ЦелаяЧасть>, <НеповторяющаясяЧасть> и <ПовторяющаясяЧасть>. Число будет представлено одним из следующих трех способов:

<ЦелаяЧасть>
Например, 12, 0 и 123.
<ЦелаяЧасть><.><НеповторяющаясяЧасть>
Например, 0.5, 1., 2.12 и 123.0001.
<ЦелаяЧасть><.><НеповторяющаясяЧасть><(><ПовторяющаясяЧасть><)>
Например, 0.1(6), 1.(9), 123.00(1212).
Повторяющаяся часть десятичного разложения обозначается в круглых скобках. Например:

1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66).

Пример:

Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

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

1⃣Преобразование дроби. Определите и изолируйте повторяющуюся часть дроби. Преобразуйте строку, представляющую число, в выражение вида S=x/(10^k-1), где x — повторяющаяся часть, а k — её длина.

2⃣Вычисление геометрической суммы. Преобразуйте повторяющуюся часть в сумму вида S=x*(r/(1-r)), где r = 10^(-k). Найдите значение дроби для повторяющейся части, используя формулу геометрической прогрессии.

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

😎 Решение:

class Solution {
    public boolean isRationalEqual(String S, String T) {
        Fraction f1 = convert(S);
        Fraction f2 = convert(T);
        return f1.n == f2.n && f1.d == f2.d;
    }

    public Fraction convert(String S) {
        int state = 0;
        Fraction ans = new Fraction(0, 1);
        int decimal_size = 0;

        for (String part: S.split("[.()]")) {
            state++;
            if (part.isEmpty()) continue;
            long x = Long.valueOf(part);
            int sz = part.length();

            if (state == 1) {
                ans.iadd(new Fraction(x, 1));
            } else if (state == 2) {
                ans.iadd(new Fraction(x, (long) Math.pow(10, sz)));
                decimal_size = sz;
            } else {
                long denom = (long) Math.pow(10, decimal_size);
                denom *= (long) (Math.pow(10, sz) - 1);
                ans.iadd(new Fraction(x, denom));
            }
        }
        return ans;
    }
}

class Fraction {
    long n, d;
    Fraction(long n, long d) {
        long g = gcd(n, d);
        this.n = n / g;
        this.d = d / g;
    }

    public void iadd(Fraction other) {
        long numerator = this.n * other.d + this.d * other.n;
        long denominator = this.d * other.d;
        long g = Fraction.gcd(numerator, denominator);
        this.n = numerator / g;
        this.d = denominator / g;
    }

    static long gcd(long x, long y) {
        return x != 0 ? gcd(y % x, x) : y;
    }
}

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

🔥 Записал видос "Как за 3 минуты настроить Автоотклики на вакансии HeadHunter" больше не придется заниматься этой унылой рутиной

📺 Видео: https://youtu.be/G_FOwEGPwlw

Задача: 956. Tallest Billboard
Сложность: hard

Вы устанавливаете рекламный щит и хотите, чтобы он имел наибольшую высоту. У рекламного щита будет две стальные опоры, по одной с каждой стороны. Каждая стальная опора должна быть одинаковой высоты. Вам дается набор стержней, которые можно сварить вместе. Например, если у вас есть стержни длиной 1, 2 и 3, вы можете сварить их вместе, чтобы получилась опора длиной 6. Верните наибольшую возможную высоту вашей рекламной установки. Если вы не можете установить рекламный щит, верните 0.

Пример:

Input: rods = [1,2,3,6]
Output: 6

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

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

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

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

😎 Решение:

class Solution {
    public int minDeletionSize(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();
        boolean[] deleteCount = new boolean[m];
        
        while (!isSorted(strs, deleteCount)) {
            for (int j = 0; j < m; j++) {
                if (deleteCount[j]) continue;
                for (int i = 0; i < n - 1; i++) {
                    if (strs[i].charAt(j) > strs[i + 1].charAt(j)) {
                        deleteCount[j] = true;
                        break;
                    }
                }
                if (deleteCount[j]) break;
            }
        }
        
        int count = 0;
        for (boolean del : deleteCount) {
            if (del) count++;
        }
        return count;
    }
    
    private boolean isSorted(String[] strs, boolean[] deleteCount) {
        int n = strs.length;
        int m = deleteCount.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < m; j++) {
                if (deleteCount[j]) continue;
                if (strs[i].charAt(j) > strs[i + 1].charAt(j)) return false;
                if (strs[i].charAt(j) < strs[i + 1].charAt(j)) break;
            }
        }
        return true;
    }
}

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

Задача: 526. Beautiful Arrangement
Сложность: medium

Предположим, у вас есть n целых чисел, пронумерованных от 1 до n. Перестановка этих n целых чисел perm (нумерация с 1) считается красивой, если для каждого i (1 <= i <= n) выполняется одно из следующих условий:
perm[i] делится на i.
i делится на perm[i].
Дано целое число n, верните количество красивых перестановок, которые вы можете создать.

Пример:

Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1

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

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

2⃣ Рекурсивное создание перестановок и проверка условий:
Напишите рекурсивную функцию для создания всех возможных перестановок массива, начиная с текущей позиции l.
На каждом шаге перестановки проверяйте, удовлетворяет ли текущий элемент условиям делимости. Если условие выполняется, продолжайте создание перестановок рекурсивно для следующей позиции.

3⃣ Возврат результата:
В основной функции вызовите рекурсивную функцию с начальной позицией 0 и верните значение счетчика красивых перестановок.

😎 Решение:

public class Solution {
    int count = 0;
    public int countArrangement(int N) {
        int[] nums = new int[N];
        for (int i = 1; i <= N; i++)
            nums[i - 1] = i;
        permute(nums, 0);
        return count;
    }
    public void permute(int[] nums, int l) {
        if (l == nums.length) {
            count++;
        }
        for (int i = l; i < nums.length; i++) {
            swap(nums, i, l);
            if (nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0)
                permute(nums, l + 1);
            swap(nums, i, l);
        }
    }
    public void swap(int[] nums, int x, int y) {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
}

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

Задача: 1428. Leftmost Column with at Least a One
Сложность: medium

Строково-отсортированная бинарная матрица означает, что все элементы равны 0 или 1, и каждая строка матрицы отсортирована в неубывающем порядке.
Дана строково-отсортированная бинарная матрица binaryMatrix, верните индекс (начиная с 0) самого левого столбца, содержащего 1. Если такого индекса не существует, верните -1.
Вы не можете напрямую обращаться к бинарной матрице. Вы можете получить доступ к матрице только через интерфейс BinaryMatrix:
- BinaryMatrix.get(row, col) возвращает элемент матрицы с индексом (row, col) (начиная с 0).
- BinaryMatrix.dimensions() возвращает размеры матрицы в виде списка из 2 элементов [rows, cols], что означает, что матрица имеет размер rows x cols.

Отправки, делающие более 1000 вызовов к BinaryMatrix.get, будут оценены как неправильный ответ. Кроме того, любые решения, пытающиеся обойти проверку, будут дисквалифицированы.

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

Пример:

Input: mat = [[0,0],[0,1]]
Output: 1

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

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

2⃣Повторяйте поиск до тех пор, пока указатели не выйдут за границы матрицы:
Если текущий элемент равен 0, сдвигайте указатель строки вниз.
Если текущий элемент равен 1, сдвигайте указатель столбца влево.

3⃣Если указатель столбца остается на последнем столбце, значит, все элементы матрицы равны 0, и верните -1. В противном случае верните индекс самого левого столбца с 1.

😎 Решение:

class Solution {
    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        int rows = binaryMatrix.dimensions().get(0);
        int cols = binaryMatrix.dimensions().get(1);

        int currentRow = 0;
        int currentCol = cols - 1;
    
        while (currentRow < rows && currentCol >= 0) {
            if (binaryMatrix.get(currentRow, currentCol) == 0) {
                currentRow++;
            } else {
                currentCol--; 
            }
        }
    
        return (currentCol == cols - 1) ? -1 : currentCol + 1;
    }
}

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

Задача: 1094. Car Pooling
Сложность: medium

Есть автомобиль с пустыми сиденьями емкостью capacity. Автомобиль движется только на восток (то есть он не может повернуть и ехать на запад).

Дан целочисленный параметр capacity и массив поездок trips, где trips[i] = [numPassengersi, fromi, toi] указывает, что на i-й поездке numPassengersi пассажиров должны быть забраны на позиции fromi и высажены на позиции toi. Позиции заданы как количество километров на восток от начальной точки автомобиля.

Верните true, если возможно забрать и высадить всех пассажиров для всех указанных поездок, или false в противном случае.

Пример:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

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

1⃣Простая идея заключается в том, чтобы пройти от начала до конца и проверить, превышает ли фактическая вместимость capacity.

2⃣Чтобы узнать фактическую вместимость, нужно просто знать изменение количества пассажиров в каждый момент времени.

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

😎 Решение:

import java.util.*;

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        Map<Integer, Integer> timestamp = new TreeMap<>();
        for (int[] trip : trips) {
            timestamp.put(trip[1], timestamp.getOrDefault(trip[1], 0) + trip[0]);
            timestamp.put(trip[2], timestamp.getOrDefault(trip[2], 0) - trip[0]);
        }
        int usedCapacity = 0;
        for (int passengerChange : timestamp.values()) {
            usedCapacity += passengerChange;
            if (usedCapacity > capacity) {
                return false;
            }
        }
        return true;
    }
}

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

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

Если глубина дерева меньше 5, то это дерево можно представить в виде массива трехзначных чисел. Для каждого числа в этом массиве:

Сотни представляют глубину d этого узла, где 1 <= d <= 4.
Десятки представляют позицию p этого узла на уровне, которому он принадлежит, где 1 <= p <= 8. Позиция соответствует позиции в полном бинарном дереве.
Единицы представляют значение v этого узла, где 0 <= v <= 9.
Дан массив возрастающих трехзначных чисел nums, представляющих бинарное дерево с глубиной меньше 5. Верните сумму всех путей от корня к листьям.

Гарантируется, что данный массив представляет собой валидное связанное бинарное дерево.

Пример:

Input: nums = [113,215,221]
Output: 12
Explanation: The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.

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

1⃣Создание структуры дерева:
Пройдите по массиву nums и для каждого элемента создайте узел дерева.
Сохраните узлы в словаре для удобного доступа по их позиции.

2⃣Связывание узлов:
Пройдите по массиву и свяжите узлы друг с другом, исходя из их позиции и глубины.
Найдите левого и правого ребенка для каждого узла и установите соответствующие связи.

3⃣Подсчет суммы путей:
Выполните обход дерева (например, используя DFS) и подсчитайте сумму всех путей от корня к листьям.

😎 Решение:

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

public class Solution {
    public int pathSum(int[] nums) {
        Map<Integer, Integer> tree = new HashMap<>();
        
        for (int num : nums) {
            int depth = num / 100;
            int pos = (num / 10) % 10;
            int val = num % 10;
            tree.put(depth * 10 + pos, val);
        }
        
        return dfs(tree, 1, 1, 0);
    }
    
    private int dfs(Map<Integer, Integer> tree, int depth, int pos, int currentSum) {
        int key = depth * 10 + pos;
        if (!tree.containsKey(key)) {
            return 0;
        }
        currentSum += tree.get(key);
        int leftChild = (depth + 1) * 10 + 2 * pos - 1;
        int rightChild = (depth + 1) * 10 + 2 * pos;
        if (!tree.containsKey(leftChild) && !tree.containsKey(rightChild)) {
            return currentSum;
        }
        return dfs(tree, depth + 1, 2 * pos - 1, currentSum) + dfs(tree, depth + 1, 2 * pos, currentSum);
    }
}

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

Задача: 395. Longest Substring with At Least K Repeating Characters
Сложность: medium

Дана строка s и целое число k, верните длину самой длинной подстроки строки s, такая что частота каждого символа в этой подстроке больше или равна k.

Если такой подстроки не существует, верните 0.

Пример:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

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

1⃣Генерируйте подстроки из строки s, начиная с индекса start и заканчивая индексом end. Используйте массив countMap для хранения частоты каждого символа в подстроке.

2⃣Метод isValid использует countMap для проверки, что каждый символ в подстроке встречается как минимум k раз. Если условие выполняется, текущая подстрока считается допустимой.

3⃣Отслеживайте максимальную длину допустимой подстроки, обновляя её, когда найдена более длинная подстрока, удовлетворяющая условиям. В конце возвращайте длину самой длинной подстроки.

😎 Решение:

class Solution {
    public int longestSubstring(String s, int k) {
        if (s.length() == 0 || k > s.length()) {
            return 0;
        }
        int[] countMap = new int[26];
        int n = s.length();
        int result = 0;
        
        for (int start = 0; start < n; start++) {
            Arrays.fill(countMap, 0);
            for (int end = start; end < n; end++) {
                countMap[s.charAt(end) - 'a']++;
                if (isValid(countMap, k)) {
                    result = Math.max(result, end - start + 1);
                }
            }
        }
        return result;
    }

    private boolean isValid(int[] countMap, int k) {
        int countLetters = 0, countAtLeastK = 0;
        for (int count : countMap) {
            if (count > 0) countLetters++;
            if (count >= k) countAtLeastK++;
        }
        return countLetters == countAtLeastK;
    }
}

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

Задача: №22. Generate Parentheses
Сложность: medium

Учитывая n пар круглых скобок, напишите функцию, которая генерирует все возможные комбинации правильных (валидных) круглых скобок.

Пример:

Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]

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

1⃣Если n == 1, возвращаем базовый набор: ["()"].

2⃣Для n > 1 вызываем рекурсивную функцию, которая для n - 1 генерирует все предыдущие комбинации и вставляет "()" в каждую возможную позицию каждой строки.

3⃣Используем Set, чтобы избежать дубликатов, так как одна и та же комбинация может получиться при вставке "()" в разные позиции.

😎 Решение:

public List<String> generateParenthesis(int n) {
    Set<String> ans = new HashSet<>();
    ans = createParenthesis(n, ans);
    return new ArrayList<>(ans);
}

private static Set<String> createParenthesis(int n, Set<String> currentList) {
    Set<String> temp = new HashSet<>();
    if (n <= 0) return new HashSet<>();
    if (n == 1) {
        temp.add("()");
        return temp;
    }
    currentList = createParenthesis(n - 1, currentList);
    for (String parenthesis : currentList) {
        for (int i = 0; i <= parenthesis.length(); i++) {
            String newStr = parenthesis.substring(0, i) + "()" + parenthesis.substring(i);
            temp.add(newStr);
        }
    }
    return temp;
}

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

Айтишники, это вам — в телеграм есть комьюнити по каждому направлению в IT

Там есть буквально всё: чаты для общения, тонны материала(книги, курсы, ресурсы и гайды), свежие новости и конечно же мемы

Выбирайте своё направление:

💩 Frontend 🐍 Python

🐧 Linux 👩‍💻 С/С++

👩‍💻 C# 🤔 Хакинг & ИБ

📱 GitHub 🖥 SQL

👩‍💻 Сисадмин 🤟 DevOps

⚙️ Backend 🖥 Data Science

🧑‍💻 Java 🐞 Тестирование

🖥 PM / PdM 👩‍💻 GameDev

🧑‍💻 Golang 🤵‍♂️ IT-Митапы

🧑‍💻 PHP 💻 WebDev

🖥 Моб. Dev 🖥Анали.(SA&BA)

👩‍💻 Дизайн 🖥 Нейросети

💛 1C 🤓 Книги IT

➡️ Сохраняйте в закладки

Задача: 1243. Array Transformation
Сложность: easy

Если задан исходный массив arr, то каждый день вы создаете новый массив, используя массив предыдущего дня. В i-й день вы выполняете следующие операции над массивом дня i-1, чтобы получить массив дня i: если элемент меньше своего левого и правого соседа, то этот элемент увеличивается. Если элемент больше своего левого и правого соседа, то этот элемент уменьшается. Первый и последний элементы никогда не меняются. Через несколько дней массив не меняется. Верните этот окончательный массив.

Пример:

Input: arr = [6,2,3,4]
Output: [6,3,3,4]

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

1⃣Инициализация нового массива с такими же значениями, как у исходного массива.
Циклически изменяем массив в соответствии с правилами, пока он не перестанет меняться.

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

3⃣Первый и последний элементы массива остаются неизменными.

😎 Решение:

import java.util.Arrays;

public class Solution {
    public int[] transformArray(int[] arr) {
        boolean changed;
        do {
            changed = false;
            int[] newArr = arr.clone();
            for (int i = 1; i < arr.length - 1; i++) {
                if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) {
                    newArr[i]++;
                    changed = true;
                } else if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
                    newArr[i]--;
                    changed = true;
                }
            }

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

"Ты че, дурак?" – базовая реакция сеньора на тех, кто покупает IT курсы

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

Трушные ребята учатся на жизненных каналах для айтишников. Вот топ-5 от тимлида из Сбера:

⚙️ Технолоджия – для тех, кто хочет быть в курсе новостей в айти

🧠 Ai-чница – способы превратить нейросети в заработок $$$

💻 ИИ тебя заменит! – тенденции айти рынка в связке с нейросетями

4️⃣ Войти в IT – тонны бесплатного обучения для прогеров

😄 IT индус – сборник айти мемов

Задача: 659. Split Array into Consecutive Subsequences
Сложность: medium

Вам дан отсортированный в неубывающем порядке массив целых чисел nums.

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

Каждая подпоследовательность является последовательностью последовательных возрастающих чисел (то есть каждое целое число на 1 больше предыдущего).
Все подпоследовательности имеют длину 3 или более.
Верните true, если можно разделить nums согласно вышеуказанным условиям, или false в противном случае.

Подпоследовательность массива — это новый массив, который формируется из исходного массива путем удаления некоторых (может быть, ни одного) элементов без нарушения относительных позиций оставшихся элементов. (например, [1,3,5] является подпоследовательностью [1,2,3,4,5], тогда как [1,3,2] не является).

Пример:

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

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

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

2⃣Создание подпоследовательностей:
Создайте хеш-таблицу для отслеживания количества подпоследовательностей, которые могут быть продолжены для каждого элемента.
Пройдите по каждому элементу в массиве и выполните следующие действия:
Если элемент можно добавить к существующей подпоследовательности (проверяя хеш-таблицу подпоследовательностей), добавьте его и обновите хеш-таблицу.
Если элемент нельзя добавить к существующей подпоследовательности, начните новую последовательность длиной 3 или более элементов.
Если ни одно из условий не выполнено, верните false.

3⃣Проверка результата:
Верните true, если все элементы успешно распределены по подпоследовательностям.

😎 Решение:

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

public class Solution {
    public boolean isPossible(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        Map<Integer, Integer> need = new HashMap<>();
        
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        
        for (int num : nums) {
            if (freq.get(num) == 0) continue;
            if (need.getOrDefault(num, 0) > 0) {
                need.put(num, need.get(num) - 1);
                need.put(num + 1, need.getOrDefault(num + 1, 0) + 1);
            } else if (freq.getOrDefault(num + 1, 0) > 0 && freq.getOrDefault(num + 2, 0) > 0) {
                freq.put(num + 1, freq.get(num + 1) - 1);
                freq.put(num + 2, freq.get(num + 2) - 1);
                need.put(num + 3, need.getOrDefault(num + 3, 0) + 1);
            } else {
                return false;
            }
            freq.put(num, freq.get(num) - 1);
        }
        
        return true;
    }
}

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

Задача: 732. My Calendar III
Сложность: hard

k-бронирование происходит, когда k событий имеют некоторое непустое пересечение (т.е, дано некоторое время, общее для всех k событий). Даны некоторые события [startTime, endTime), после каждого данного события верните целое число k, представляющее максимальное k-бронирование между всеми предыдущими событиями. Реализация класса MyCalendarThree: MyCalendarThree() Инициализирует объект. int book(int startTime, int endTime) Возвращает целое число k, представляющее наибольшее целое число, при котором в календаре существует k-бронирование.

Пример:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

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

1⃣Создайте два словаря для хранения изменений времени бронирования: один для начала событий, другой для конца событий.

2⃣Для каждого нового события обновите словари начала и конца событий.

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

😎 Решение:

import java.util.Map;
import java.util.TreeMap;

public class MyCalendarThree {
    private TreeMap<Integer, Integer> events;

    public MyCalendarThree() {
        events = new TreeMap<>();
    }

    public int book(int startTime, int endTime) {
        events.put(startTime, events.getOrDefault(startTime, 0) + 1);
        events.put(endTime, events.getOrDefault(endTime, 0) - 1);
        
        int active = 0;
        int maxActive = 0;
        for (Map.Entry<Integer, Integer> entry : events.entrySet()) {
            active += entry.getValue();
            maxActive = Math.max(maxActive, active);
        }
        
        return maxActive;
    }
}

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