Задача: №25. Reverse Nodes in k-Group
Сложность: hard

Учитывая заголовок связанного списка, поменяйте местами узлы списка по k за раз и верните изменённый список.
Если количество узлов не кратно k, то последние остаются без изменений.
*Изменять можно только связи между узлами, а не их значения.*

Пример:

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

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

1⃣Создать фиктивный узел dummy, указывающий на head, и использовать указатель pointer для прохода по списку.

2⃣В каждом шаге проверять, есть ли впереди k узлов — если нет, завершить процесс. Иначе — развернуть группу из k узлов.

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

😎 Решение:

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode pointer = dummy;

    while (pointer != null) {
        ListNode node = pointer;
        for (int i = 0; i < k && node != null; i++) node = node.next;
        if (node == null) break;

        ListNode prev = null, curr = pointer.next;
        for (int i = 0; i < k; i++) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        ListNode tail = pointer.next;
        tail.next = curr;
        pointer.next = prev;
        pointer = tail;
    }

    return dummy.next;
}

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

Задача: 744. Find Smallest Letter Greater Than Target
Сложность: easy

Нам дан массив символов letters, отсортированный в неубывающем порядке, и символ target. В массиве letters есть как минимум два разных символа. Возвращается наименьший символ в letters, который лексикографически больше target. Если такого символа не существует, возвращается первый символ в буквах.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

1⃣Использовать бинарный поиск для нахождения позиции первого символа в letters, который лексикографически больше target.

2⃣Если найденный символ существует, вернуть его.

3⃣Если такого символа не существует, вернуть первый символ в letters.

😎 Решение:

public class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int left = 0, right = letters.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (letters[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return letters[left % letters.length];
    }
}

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

Задача: 320. Generalized Abbreviation
Сложность: medium

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

Например, "abcde" можно сократить следующим образом:

"a3e" ("bcd" заменено на "3")
"1bcd1" ("a" и "e" заменены на "1")
"5" ("abcde" заменено на "5")
"abcde" (без замены подстрок)
Однако следующие аббревиатуры недействительны:

"23" ("ab" заменено на "2" и "cde" заменено на "3") недействительно, так как выбранные подстроки смежные.
"22de" ("ab" заменено на "2" и "bc" заменено на "2") недействительно, так как выбранные подстроки перекрываются.
Дано слово word, верните список всех возможных обобщенных аббревиатур слова. Верните ответ в любом порядке.

Пример:

Input: word = "a"
Output: ["1","a"]

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

1⃣Создание битовых масок
Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур.

2⃣Генерация аббревиатур
Для числа x просканируйте его бит за битом, чтобы определить, какие символы следует сохранить, а какие - сократить. Если бит равен 1, сохраните соответствующий символ, если 0 - замените его на счетчик.

3⃣Перебор всех комбинаций
Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1.

😎 Решение:

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> ans = new ArrayList<>();
        for (int x = 0; x < (1 << word.length()); ++x)
            ans.add(abbr(word, x));
        return ans;
    }

    private String abbr(String word, int x) {
        StringBuilder builder = new StringBuilder();
        int k = 0, n = word.length();
        for (int i = 0; i < n; ++i, x >>= 1) {
            if ((x & 1) == 0) {
                if (k != 0) {
                    builder.append(k);
                    k = 0;
                }
                builder.append(word.charAt(i));
            } else {
                ++k;
            }
        }
        if (k != 0) builder.append(k);
        return builder.toString();
    }
}

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

Задача: 821. Shortest Distance to a Character
Сложность: easy

Дана строка s и символ c, который встречается в s. Верните массив целых чисел answer, где answer.length == s.length, и answer[i] - это расстояние от индекса i до ближайшего появления символа c в строке s.

Расстояние между двумя индексами i и j равно abs(i - j), где abs - это функция абсолютного значения.

Пример:

Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
Explanation: The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.
The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2.
For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.
The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.

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

1⃣При проходе слева направо будем запоминать индекс prev последнего символа C, который мы видели. Тогда ответ будет i - prev.

2⃣При проходе справа налево будем запоминать индекс prev последнего символа C, который мы видели. Тогда ответ будет prev - i.

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

😎 Решение:

class Solution {
    public int[] shortestToChar(String S, char C) {
        int N = S.length();
        int[] ans = new int[N];
        int prev = -N;

        for (int i = 0; i < N; ++i) {
            if (S.charAt(i) == C) {
                prev = i;
            }
            ans[i] = i - prev;
        }

        prev = 2 * N;
        for (int i = N - 1; i >= 0; --i) {
            if (S.charAt(i) == C) {
                prev = i;
            }
            ans[i] = Math.min(ans[i], prev - i);
        }

        return ans;
    }

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

Задача: 1228. Missing Number In Arithmetic Progression
Сложность: easy

В массиве arr значения находились в арифметической прогрессии: значения arr[i + 1] - arr[i] равны для всех 0 <= i < arr.length - 1.

Из массива arr было удалено значение, которое не было первым или последним значением в массиве.

Дан массив arr, вернуть удаленное значение.

Пример:

Input: arr = [5,7,11,13]
Output: 9
Explanation: The previous array was [5,7,9,11,13].

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

1⃣Рассчитать разность difference между элементами арифметической прогрессии.

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

3⃣Вернуть первое ожидаемое значение, которое не совпадает с текущим значением в массиве.

😎 Решение:

class Solution {
    public int missingNumber(int[] arr) {
        int n = arr.length;

        int difference = (arr[arr.length - 1] - arr[0]) / n;

        int expected = arr[0];

        for (int val : arr) {
            if (val != expected) return expected;

            expected += difference;
        }
        return expected;
    }
}

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

Завтра последний день!

Успей купить пожизненный easyoffer PRO - по цене 1 года

Покупаешь один раз — пользуешься всю жизнь.

👉 Акция до 31 марта: https://easyoffer.ru/pro

Задача: 1009. Complement of Base 10 Integer
Сложность: easy

Дополнение целого числа - это целое число, которое получается, если перевернуть все 0 в 1 и все 1 в 0 в его двоичном представлении. Например, целое число 5 - это "101" в двоичном представлении, а его дополнение - "010", то есть целое число 2. Если задано целое число n, верните его дополнение.

Пример:

Input: n = 5
Output: 2

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

1⃣Определение длины двоичного представления:
Найдите длину двоичного представления числа n.

2⃣Создание маски:
Создайте маску, которая состоит из всех единиц и имеет ту же длину, что и двоичное представление числа n.

3⃣Вычисление дополнения:
Примените побитовую операцию XOR между числом n и маской, чтобы получить дополнение числа.

😎 Решение:

public class Solution {
    public int findComplement(int num) {
        int length = Integer.toBinaryString(num).length();
        int mask = (1 << length) - 1;
        return num ^ mask;
    }
}

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

Задача: 509. Fibonacci Number
Сложность: easy

Числа Фибоначчи, обычно обозначаемые как F(n), образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.
Дано n, вычислите F(n).

Пример:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

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

1⃣Проверка начального условия
Если N <= 1, вернуть N.

2⃣Инициализация переменных
Инициализируйте current значением 0. Инициализируйте prev1 значением 1, что будет представлять fib(N-1) при вычислении текущего значения. Инициализируйте prev2 значением 0, что будет представлять fib(N-2) при вычислении текущего значения.

3⃣Итерация и вычисление
Итерация от 2 до N включительно. На каждой итерации: установите current как сумму prev1 и prev2. Обновите prev2 значением prev1. Обновите prev1 значением current. Вернуть значение current после завершения итерации.

😎 Решение:

class Solution {
    public int fib(int N) {
        if (N <= 1) {
            return N;
        }

        int current = 0;
        int prev1 = 1;
        int prev2 = 0;

        for (int i = 2; i <= N; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return current;
    }
}

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

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

Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.

Пример:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

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

1⃣Отсортируйте массив nums в неубывающем порядке.

2⃣Итерируйте через массив, выбирая каждый второй элемент (начиная с первого).

3⃣Суммируйте выбранные элементы и верните эту сумму.

😎 Решение:

public class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i += 2) {
            sum += nums[i];
        }
        return sum;
    }
}

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

Задача: 330. Patching Array
Сложность: hard

Дан отсортированный массив целых чисел nums и целое число n. Добавьте/дополните элементы в массив таким образом, чтобы любое число в диапазоне [1, n] включительно могло быть сформировано как сумма некоторых элементов массива.

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

Пример:

Input: nums = [1,3], n = 6
Output: 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

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

1⃣Инициализация переменных:
Создайте переменную miss, представляющую наименьшее пропущенное число, которое еще не покрыто, и установите ее значение на 1. Создайте переменную patches для подсчета необходимых дополнений и переменную i для итерации по массиву nums.

2⃣Основной цикл:
Используйте цикл while, который будет выполняться до тех пор, пока miss не станет больше n.
Внутри цикла проверьте, покрывает ли текущий элемент nums[i] значение miss. Если да, добавьте nums[i] к miss и увеличьте i. Если нет, добавьте значение miss к самому себе (это означает добавление нового элемента в массив) и увеличьте счетчик patches.

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

😎 Решение:

public class Solution {
    public int minPatches(int[] nums, int n) {
        int patches = 0, i = 0;
        long miss = 1;
        while (miss <= n) {
            if (i < nums.length && nums[i] <= miss)
                miss += nums[i++];
            else {
                miss += miss;
                patches++;
            }
        }
        return patches;
    }
}

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

Задача: 252. Meeting Rooms
Сложность: easy

Дан массив интервалов времени встреч, где intervals[i] = [starti, endi]. Определите, может ли человек посетить все встречи.

Пример:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

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

1⃣Создайте функцию для проверки перекрытия двух интервалов:
Возвращайте true, если начало одного интервала находится внутри другого интервала.

2⃣Проверьте каждый интервал с каждым другим интервалом:
Если найдено перекрытие, верните false.

3⃣Если все интервалы проверены и перекрытий не найдено, верните true.

😎 Решение:

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        for (int i = 0; i < intervals.length; i++) {
            for (int j = i + 1; j < intervals.length; j++) {
                if (overlap(intervals[i], intervals[j])) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean overlap(int[] interval1, int[] interval2) {
        return (interval1[0] >= interval2[0] && interval1[0] < interval2[1])
            || (interval2[0] >= interval1[0] && interval2[0] < interval1[1]);
    }
}

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

Задача: 1323. Maximum 69 Number
Сложность: easy

Дано положительное целое число num, состоящее только из цифр 6 и 9.

Верните максимальное число, которое можно получить, изменив не более одной цифры (6 становится 9, а 9 становится 6).

Пример:

Input: num = 9669
Output: 9969
Explanation: 
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666.
The maximum number is 9969.

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

1⃣Преобразуйте входное целое число num в итерируемый и изменяемый объект num_obj.

2⃣Пройдитесь по num_obj и, если найдете цифру 6, замените её на 9 и прекратите итерацию.

3⃣Верните целое число, преобразованное из измененного num_obj.

😎 Решение:

class Solution {
    public int maximum69Number (int num) {
        StringBuilder numSB = new StringBuilder();
        numSB.append(num);
        for (int i = 0; i < numSB.length(); ++i) {
            if (numSB.charAt(i) == '6') {
                numSB.setCharAt(i, '9');
                break;
            }
        }
        return Integer.parseInt(numSB.toString());
    }
}

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

Задача: 484. Find Permutation
Сложность: medium

Перестановка perm из n целых чисел всех чисел в диапазоне [1, n] может быть представлена в виде строки s длиной n - 1, где:

s[i] == 'I', если perm[i] < perm[i + 1], и
s[i] == 'D', если perm[i] > perm[i + 1].
Дана строка s, восстановите лексикографически наименьшую перестановку perm и верните её.

Пример:

Input: s = "I"
Output: [1,2]
Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.

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

1⃣Инициализация
Создайте пустой стек stack. Создайте пустой список result для хранения конечной перестановки.

2⃣Для каждого числа i
Если текущий символ в строке s равен 'D', добавьте i в стек. Если текущий символ в строке s равен 'I', добавьте i в стек, затем извлеките все элементы из стека и добавьте их в result.

3⃣Завершение
Добавьте n в стек и извлеките все элементы из стека, добавив их в result. Верните список result, который представляет лексикографически наименьшую перестановку.

😎 Решение:

public class Solution {
    public int[] findPermutation(String s) {
        int[] res = new int[s.length() + 1];
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 1; i <= s.length(); i++) {
            if (s.charAt(i - 1) == 'I') {
                stack.push(i);
                while (!stack.isEmpty()) {
                    res[j++] = stack.pop();
                }
            } else {
                stack.push(i);
            }
        }
        stack.push(s.length() + 1);
        while (!stack.isEmpty()) {
            res[j++] = stack.pop();
        }
        return res;
    }
}

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

Задача: 1382. Balance a Binary Search Tree
Сложность: medium

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

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

Пример:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

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

1⃣Инициализация. Создайте пустой список inorder для хранения значений узлов после обхода в порядке возрастания.

2⃣Выполнение обхода в порядке возрастания. Обойдите бинарное дерево поиска (BST) и заполните список inorder значениями узлов в отсортированном порядке.

3⃣Перестроение сбалансированного BST. Определите рекурсивную функцию createBalancedBST, которая принимает список inorder, начальный индекс и конечный индекс в качестве параметров. Если начальный индекс больше конечного, верните null (или эквивалент). Вычислите средний индекс как середину текущего диапазона. Создайте новый узел дерева со значением в среднем индексе. Рекурсивно создайте левое поддерево, используя левую половину текущего диапазона. Рекурсивно создайте правое поддерево, используя правую половину текущего диапазона. Верните корень вновь построенного сбалансированного BST.

😎 Решение:

class Solution {
    public TreeNode balanceBST(TreeNode root) {
        if (root == null) return null;

        TreeNode vineHead = new TreeNode(0);
        vineHead.right = root;
        TreeNode current = vineHead;

        while (current.right != null) {
            if (current.right.left != null) {
                rightRotate(current, current.right);
            } else {
                current = current.right;
            }
        }

        int nodeCount = 0;
        current = vineHead.right;
        while (current != null) {
            nodeCount++;
            current = current.right;
        }

        int m = (int) Math.pow(2, Math.floor(Math.log(nodeCount + 1) / Math.log(2))) - 1;
        makeRotations(vineHead, nodeCount - m);
        while (m > 1) {
            m /= 2;
            makeRotations(vineHead, m);
        }

        TreeNode balancedRoot = vineHead.right;
        return balancedRoot;
    }

    private void rightRotate(TreeNode parent, TreeNode node) {
        TreeNode tmp = node.left;
        node.left = tmp.right;
        tmp.right = node;
        parent.right = tmp;
    }

    private void leftRotate(TreeNode parent, TreeNode node) {
        TreeNode tmp = node.right;
        node.right = tmp.left;
        tmp.left = node;
        parent.right = tmp;
    }

    private void makeRotations(TreeNode vineHead, int count) {
        TreeNode current = vineHead;
        for (int i = 0; i < count; i++) {
            TreeNode tmp = current.right;
            leftRotate(current, tmp);
            current = current.right;
        }
    }
}

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

Задача: 690. Employee Importance
Сложность: medium

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

Вам дан массив сотрудников employees, где:

employees[i].id — это идентификатор i-го сотрудника.
employees[i].importance — значение важности i-го сотрудника.
employees[i].subordinates — список идентификаторов прямых подчиненных i-го сотрудника.
Дан целочисленный id, представляющий идентификатор сотрудника. Верните суммарное значение важности этого сотрудника и всех его прямых и косвенных подчиненных.

Пример:

Input: employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1
Output: 11
Explanation: Employee 1 has an importance value of 5 and has two direct subordinates: employee 2 and employee 3.
They both have an importance value of 3.
Thus, the total importance value of employee 1 is 5 + 3 + 3 = 11.

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

1⃣Создайте хеш-таблицу emap для быстрого доступа к сотрудникам по их идентификаторам.

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

3⃣Используйте DFS для вычисления общей важности, начиная с заданного идентификатора сотрудника.

😎 Решение:

class Solution {
    Map<Integer, Employee> emap;
    
    public int getImportance(List<Employee> employees, int queryid) {
        emap = new HashMap<>();
        for (Employee e : employees) {
            emap.put(e.id, e);
        }
        return dfs(queryid);
    }

    public int dfs(int eid) {
        Employee employee = emap.get(eid);
        int ans = employee.importance;
        for (Integer subid : employee.subordinates) {
            ans += dfs(subid);
        }
        return ans;
    }
}

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

Задача: 756. Pyramid Transition Matrix
Сложность: medium

Вы складываете блоки так, чтобы получилась пирамида. Каждый блок имеет цвет, который представлен одной буквой. Каждый ряд блоков содержит на один блок меньше, чем ряд под ним, и располагается по центру сверху. Чтобы пирамида выглядела эстетично, допускаются только определенные треугольные узоры. Треугольный узор состоит из одного блока, уложенного поверх двух блоков. Шаблоны задаются в виде списка допустимых трехбуквенных строк, где первые два символа шаблона представляют левый и правый нижние блоки соответственно, а третий символ - верхний блок. Например, "ABC" представляет треугольный шаблон с блоком 'C', уложенным поверх блоков 'A' (слева) и 'B' (справа). Обратите внимание, что это отличается от "BAC", где "B" находится слева внизу, а "A" - справа внизу. Вы начинаете с нижнего ряда блоков bottom, заданного в виде одной строки, который вы должны использовать в качестве основания пирамиды. Учитывая bottom и allowed, верните true, если вы можете построить пирамиду до самой вершины так, чтобы каждый треугольный узор в пирамиде был в allowed, или false в противном случае.

Пример:

Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
Output: true

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

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

2⃣Напишите рекурсивную функцию, которая проверяет возможность построения следующего уровня пирамиды.

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

😎 Решение:

import java.util.*;

public class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        Map<String, List<Character>> allowedDict = new HashMap<>();
        
        for (String pattern : allowed) {
            String key = pattern.substring(0, 2);
            char value = pattern.charAt(2);
            allowedDict.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
        }

        return canBuild(bottom, allowedDict);
    }

    private boolean canBuild(String currentLevel, Map<String, List<Character>> allowedDict) {
        if (currentLevel.length() == 1) return true;

        List<List<Character>> nextLevelOptions = new ArrayList<>();
        for (int i = 0; i < currentLevel.length() - 1; i++) {
            String key = currentLevel.substring(i, i + 2);
            if (!allowedDict.containsKey(key)) return false;
            nextLevelOptions.add(allowedDict.get(key));
        }

        return canBuildNextLevel(nextLevelOptions, 0, "", allowedDict);
    }

    private boolean canBuildNextLevel(List<List<Character>> options, int index, String nextLevel, Map<String, List<Character>> allowedDict) {
        if (index == options.size()) return canBuild(nextLevel, allowedDict);
        for (char option : options.get(index)) {
            if (canBuildNextLevel(options, index + 1, nextLevel + option, allowedDict)) return true;
        }
        return false;
    }

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

Задача: 170. Two Sum III - Data structure design
Сложность: easy

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

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

- TwoSum() инициализирует объект TwoSum с изначально пустым массивом.
- void add(int number) добавляет число в структуру данных.
- boolean find(int value) возвращает true, если существует хотя бы одна пара чисел, сумма которых равна значению value, в противном случае возвращает false.

Пример:

Input
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output
[null, null, null, null, true, false]

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

1⃣Инициализация указателей:
Инициализируйте два указателя low и high, которые указывают на первый и последний элементы списка соответственно.

2⃣Итерация с использованием двух указателей:
Запустите цикл для итерации по списку. Цикл завершится, когда будет найдено решение с двумя суммами или когда два указателя встретятся.
На каждом шаге цикла перемещайте один из указателей в зависимости от различных условий:
Если сумма элементов, на которые указывают текущие указатели, меньше желаемого значения, то необходимо попытаться увеличить сумму для достижения желаемого значения, то есть переместить указатель low вперёд для получения большего значения.
Если сумма элементов больше желаемого значения, то следует попытаться уменьшить сумму, перемещая указатель high в сторону указателя low.
Если сумма равна желаемому значению, можно сразу выполнить возврат из функции.

3⃣Завершение цикла:
Если цикл завершается тем, что два указателя встречаются, то можно быть уверенным, что решения для желаемого значения не существует.

😎 Решение:

import java.util.Collections;

class TwoSum {
    private ArrayList<Integer> nums;
    private boolean is_sorted;
    public TwoSum() {
        this.nums = new ArrayList<Integer>();
        this.is_sorted = false;
    }
    public void add(int number) {
        this.nums.add(number);
        this.is_sorted = false;
    }
    public boolean find(int value) {
        if (!this.is_sorted) {
            Collections.sort(this.nums);
            this.is_sorted = true;
        }
        int low = 0, high = this.nums.size() - 1;
        while (low < high) {
            int twosum = this.nums.get(low) + this.nums.get(high);
            if (twosum < value) low += 1;
            else if (twosum > value) high -= 1;
            else return true;
        }
        return false;
    }
}

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

Задача: 591. Tag Validator
Сложность: hard

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

Фрагмент кода считается корректным, если соблюдаются все следующие правила:
Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен.
Закрытый тег (не обязательно корректный) имеет точно следующий формат: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Среди них <TAG_NAME> — это начальный тег, а </TAG_NAME> — конечный тег. TAG_NAME в начальном и конечном тегах должен быть одинаковым. Закрытый тег корректен, если и только если TAG_NAME и TAG_CONTENT корректны.
Корректное TAG_NAME содержит только заглавные буквы и имеет длину в диапазоне [1, 9]. В противном случае TAG_NAME некорректен.
Корректное TAG_CONTENT может содержать другие корректные закрытые теги, cdata и любые символы (см. примечание 1), КРОМЕ неподходящих <, неподходящих начальных и конечных тегов, и неподходящих или закрытых тегов с некорректным TAG_NAME. В противном случае TAG_CONTENT некорректен.
Начальный тег неподходящий, если нет конечного тега с тем же TAG_NAME, и наоборот. Однако нужно также учитывать проблему несбалансированных тегов, когда они вложены.
< неподходящий, если не удается найти последующий >. И когда вы находите < или </, все последующие символы до следующего > должны быть разобраны как TAG_NAME (не обязательно корректный).
cdata имеет следующий формат: <![CDATA[CDATA_CONTENT]]>. Диапазон CDATA_CONTENT определяется как символы между <![CDATA[ и первым последующим ]]>.
CDATA_CONTENT может содержать любые символы. Функция cdata заключается в том, чтобы запретить валидатору разбирать CDATA_CONTENT, поэтому даже если в нем есть символы, которые могут быть разобраны как тег (корректный или некорректный), вы должны рассматривать их как обычные символы.

Пример:

Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: true

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

1⃣Инициализируйте стек для отслеживания открытых тегов и флаг для определения наличия тегов. Используйте регулярное выражение для проверки корректности TAG_NAME, TAG_CONTENT и CDATA.

2⃣Пройдитесь по строке, проверяя каждый символ. Если встретите <, определите тип тега (начальный, конечный или CDATA). Обновите стек и индексы в зависимости от найденного типа.

3⃣В конце проверьте, что стек пуст (все теги корректно закрыты) и верните результат.

😎 Решение:

import java.util.regex.*;

public class Solution {
    Stack<String> stack = new Stack<>();
    boolean containsTag = false;

    public boolean isValidTagName(String s, boolean ending) {
        if (ending) {
            if (!stack.isEmpty() && stack.peek().equals(s)) stack.pop();
            else return false;
        } else {
            containsTag = true;
            stack.push(s);
        }
        return true;
    }

    public boolean isValid(String code) {
        if (!Pattern.matches("<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*", code))
            return false;

        for (int i = 0; i < code.length(); i++) {
            boolean ending = false;
            if (stack.isEmpty() && containsTag) return false;
            if (code.charAt(i) == '<') {
                if (code.charAt(i + 1) == '!') {
                    i = code.indexOf("]]>", i + 1);
                    continue;
                }
                if (code.charAt(i + 1) == '/') {
                    i++;
                    ending = true;
                }
                int closeIndex = code.indexOf('>', i + 1);
                if (closeIndex < 0 || !isValidTagName(code.substring(i + 1, closeIndex), ending))
                    return false;
                i = closeIndex;
            }
        }
        return stack.isEmpty();
    }
}

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

Задача: 342. Power of Four
Сложность: easy

Дано целое число n. Верните true, если оно является степенью числа четыре. В противном случае верните false.

Целое число n является степенью числа четыре, если существует целое число x такое, что n == 4^x.

Пример:

Input: n = 16
Output: true

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

1⃣Проверка неотрицательности:
Убедитесь, что n больше нуля, так как степени числа четыре всегда положительны.

2⃣Проверка логарифмом:
Используйте логарифм для проверки, является ли число степенью четырех. Число n является степенью четырех, если логарифм n по основанию 4 является целым числом.

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

😎 Решение:

public class Solution {
    public boolean isPowerOfFour(int n) {
        if (n <= 0) return false;
        double log_n_base_4 = Math.log(n) / Math.log(4);
        return log_n_base_4 == Math.floor(log_n_base_4);
    }
}

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

Задача: 441. Arranging Coins
Сложность: easy

У вас есть n монет, и вы хотите построить лестницу из этих монет. Лестница состоит из k рядов, где i-й ряд содержит ровно i монет. Последний ряд лестницы может быть неполным.

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

Пример:

Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.

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

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

2⃣Напомним, что условие задачи можно выразить следующим образом: k(k + 1) ≤ 2N.

3⃣Это можно решить методом выделения полного квадрата, (k + 1/2)² - 1/4 ≤ 2N. Что приводит к следующему ответу: k = [sqrt(2N + 1/4) - 1/2].

😎 Решение:

class Solution {
    public int arrangeCoins(int n) {
        return (int)(Math.sqrt(2 * (long)n + 0.25) - 0.5);
    }
}

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

Задача: 1480. Running Sum of 1d Array
Сложность: easy

Дан массив nums. Мы определяем текущую сумму массива как runningSum[i] = сумма(nums[0]…nums[i]).

Верните массив текущих сумм для nums.

Пример:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

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

1⃣Инициализация:
Определите массив result.
Инициализируйте первый элемент массива result первым элементом входного массива nums.

2⃣Вычисление текущих сумм:
На индексе i добавьте сумму элемента nums[i] и предыдущей текущей суммы result[i - 1] в массив result.

3⃣Повторение для всех индексов:
Повторите шаг 2 для всех индексов от 1 до n-1.

😎 Решение:

class Solution {
public int[] runningSum(int[] nums) {
        int[] result = new int[nums.length];

        result[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            result[i] = result[i - 1] + nums[i];
        }
        return result;
    }
}

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