Задача: 1140. Stone Game II
Сложность: medium

Алиса и Боб продолжают свои игры с кучами камней. Есть несколько куч, расположенных в ряд, и в каждой куче положительное количество камней piles[i]. Цель игры - закончить с наибольшим количеством камней.
Алиса и Боб ходят по очереди, начиная с Алисы. Изначально M = 1.
В свой ход каждый игрок может взять все камни из первых X оставшихся куч, где 1 <= X <= 2M. Затем, мы устанавливаем M = max(M, X).
Игра продолжается до тех пор, пока все камни не будут взяты.
Предполагая, что Алиса и Боб играют оптимально, верните максимальное количество камней, которые может получить Алиса.

Пример:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

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

1⃣Создать рекурсивную функцию f, которая принимает три параметра: p (игрок), i (индекс текущей кучи), и m (максимальное количество куч, которые можно взять за ход). Если i равен длине массива кучи, вернуть 0 (базовый случай рекурсии). Если значение уже вычислено ранее (dp[p][i][m] != -1), вернуть его.

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

3⃣Итеративно обновлять значение res в зависимости от того, чей ход, и обновлять значения в dp[p][i][m]. В конце вернуть res.

😎 Решение:

class Solution {
    private int f(int[] piles, int[][][] dp, int p, int i, int m) {
        if (i == piles.length) {
            return 0;
        }
        if (dp[p][i][m] != -1) {
            return dp[p][i][m];
        }
        int res = p == 1 ? 1000000 : -1, s = 0;
        for (int x = 1; x <= Math.min(2 * m, piles.length - i); x++) {
            s += piles[i + x - 1];
            if (p == 0) {
                res = Math.max(res, s + f(piles, dp, 1, i + x, Math.max(m, x)));
            }
            else {
                res = Math.min(res, f(piles, dp, 0, i + x, Math.max(m, x)));
            }
        }
        return dp[p][i][m] = res;
    }
    public int stoneGameII(int[] piles) {
        int[][][] dp = new int[2][piles.length + 1][piles.length + 1];
        for (int p = 0; p < 2; p++) {
            for (int i = 0; i <= piles.length; i++) {
                for (int m = 0; m <= piles.length; m++) {
                    dp[p][i][m] = -1;
                }
            }
        }
        return f(piles, dp, 0, 0, 1);
    }
}

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

Задача: 967. Numbers With Same Consecutive Differences
Сложность: medium

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

Учтите, что целые числа не должны начинаться с нулей. Целые числа, такие как 02 и 043, не допускаются.

Пример:

Input: n = 3, k = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

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

1⃣Если n равно 1, верните массив от 0 до 9, так как все однозначные числа являются допустимыми.

2⃣Инициализируйте список очередей начальными цифрами от 1 до 9.

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

😎 Решение:

class Solution {

    public int[] numsSameConsecDiff(int N, int K) {

        if (N == 1)
            return new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

        List<Integer> queue = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
        for(int level = 1; level < N; ++ level) {
            ArrayList<Integer> nextQueue = new ArrayList<>();
            for (Integer num : queue) {
                Integer tailDigit = num % 10;

                ArrayList<Integer> nextDigits = new ArrayList<>();
                nextDigits.add(tailDigit + K);
                if (K != 0)
                    nextDigits.add(tailDigit - K);
                for (Integer nextDigit : nextDigits) {
                    if (0 <= nextDigit && nextDigit < 10) {
                        Integer newNum = num * 10 + nextDigit;
                        nextQueue.add(newNum);
                    }
                }
            }
            queue = nextQueue;
        }

        return queue.stream().mapToInt(i->i).toArray();
    }
}

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

Задача: 911. Online Election
Сложность: medium

Вам даны два целочисленных массива persons и times. На выборах i-й голос был отдан за person[i] в момент времени times[i]. Для каждого запроса в момент времени t найдите человека, который лидировал на выборах в момент времени t. Голоса, отданные в момент времени t, будут учитываться в нашем запросе. В случае равенства голосов побеждает тот, кто проголосовал последним (среди равных кандидатов). Реализация класса TopVotedCandidate: TopVotedCandidate(int[] persons, int[] times) Инициализирует объект с массивами persons и times. int q(int t) Возвращает номер человека, который лидировал на выборах в момент времени t в соответствии с указанными правилами.

Пример:

Input
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
Output
[null, 0, 1, 1, 0, 0, 1]

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

1⃣Использовать два массива для хранения лиц и времени голосования.

2⃣Поддерживать текущий счет для каждого кандидата и текущего лидера на момент времени.

3⃣На каждый запрос времени t, найти наибольший индекс времени, который не превышает t, и вернуть лидера на этот момент времени.

😎 Решение:

import java.util.*;

class TopVotedCandidate {
    private int[] times;
    private List<Integer> leaders;

    public TopVotedCandidate(int[] persons, int[] times) {
        this.times = times;
        this.leaders = new ArrayList<>();
        Map<Integer, Integer> counts = new HashMap<>();
        int leader = -1;

        for (int person : persons) {
            counts.put(person, counts.getOrDefault(person, 0) + 1);
            if (counts.get(person) >= counts.getOrDefault(leader, 0)) {
                leader = person;
            }
            leaders.add(leader);
        }
    }

    public int q(int t) {
        int left = 0, right = times.length - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (times[mid] <= t) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return leaders.get(left);
    }
}

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

Задача: 1199. Minimum Time to Build Blocks
Сложность: hard

Вам дан список блоков, где blocks[i] = t означает, что на строительство i-го блока требуется t единиц времени. Блок может быть построен только одним рабочим.
Рабочий может либо разделиться на двух рабочих (количество рабочих увеличивается на одного), либо построить блок и уйти домой. Оба решения требуют некоторого времени.
Время, затраченное на разделение одного рабочего на двух, задано целым числом split. Обратите внимание, что если два рабочих разделяются одновременно, они разделяются параллельно, поэтому затраты времени будут равны split.

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

Изначально есть только один рабочий.

Пример:

Input: blocks = [1,2,3], split = 1
Output: 4
Explanation: Split 1 worker into 2, then assign the first worker to the last block and split the second worker into 2.
Then, use the two unassigned workers to build the first two blocks.
The cost is 1 + max(3, 1 + max(1, 2)) = 4.

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

1⃣Подготовка кучи строительного времени:
Инициализируйте кучу строительного времени, изначально содержащую все значения времени из массива blocks.

2⃣Обработка кучи:
Пока в куче больше одного элемента:
- извлеките минимальное значение из кучи, обозначим его как x.
- извлеките следующее минимальное значение из кучи, обозначим его как y.
- создайте новое время строительства, которое равно split + y, и вставьте его обратно в кучу.

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

😎 Решение:

class Solution {
    public int minBuildTime(int[] blocks, int split) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int block : blocks) {
            pq.offer(block);
        }

        while (pq.size() > 1) {
            int x = pq.poll();
            int y = pq.poll();
            pq.offer(split + y);
        }

        return pq.poll();
    }
}

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

Задача: 1038. Binary Search Tree to Greater Sum Tree
Сложность: medium

Получив корень двоичного дерева поиска (BST), преобразуйте его в большее дерево таким образом, чтобы каждый ключ исходного BST был заменен на исходный ключ плюс сумма всех ключей, превышающих исходный ключ в BST. Напомним, что двоичное дерево поиска - это дерево, удовлетворяющее следующим ограничениям: левое поддерево узла содержит только узлы с ключами меньше, чем ключ узла. Правое поддерево узла содержит только узлы с ключами больше, чем ключ узла. И левое, и правое поддеревья должны быть двоичными деревьями поиска.

Пример:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

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

1⃣Обратный обход in-order:
Пройдите по дереву в порядке "правый, корень, левый" (обратный in-order обход). Это обеспечит посещение узлов в порядке убывания их значений.

2⃣Накопление суммы:
Во время обхода поддерживайте переменную для хранения накопленной суммы. На каждом узле добавляйте значение узла к накопленной сумме и обновляйте значение узла этой накопленной суммой.

3⃣Преобразование узлов:
Преобразуйте значение каждого узла в накопленную сумму.

😎 Решение:

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

class Solution {
    private int sum = 0;
    
    public TreeNode bstToGst(TreeNode root) {
        reverseInorder(root);
        return root;
    }
    
    private void reverseInorder(TreeNode node) {
        if (node == null) return;
        reverseInorder(node.right);
        sum += node.val;
        node.val = sum;
        reverseInorder(node.left);
    }
}

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

Задача: 1035. Uncrossed Lines
Сложность: medium

Вам даны два целочисленных массива nums1 и nums2. Запишем целые числа nums1 и nums2 (в том порядке, в котором они даны) на двух отдельных горизонтальных линиях. Мы можем провести соединительные линии: прямую линию, соединяющую два числа nums1[i] и nums2[j] так, что: nums1[i] == nums2[j], и проведенная линия не пересекает никакую другую соединительную (негоризонтальную) линию. Обратите внимание, что соединительная линия не может пересекаться даже в конечных точках (т.е, каждое число может принадлежать только одной соединительной линии). Верните максимальное количество соединительных линий, которые мы можем нарисовать таким образом.

Пример:

Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2

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

1⃣Определение задачи как задачи о нахождении наибольшей общей подпоследовательности (LCS):
Эта задача является классической задачей динамического программирования, где нам нужно найти максимальную длину наибольшей общей подпоследовательности (LCS) между nums1 и nums2.

2⃣Построение таблицы динамического программирования:
Создайте двумерный массив dp, где dp[i][j] будет представлять длину наибольшей общей подпоследовательности для подмассивов nums1[0..i-1] и nums2[0..j-1].
Инициализируйте первый ряд и первый столбец нулями, так как если один из массивов пуст, LCS также будет пустым.

3⃣Заполнение таблицы динамического программирования:
Пройдите по элементам массивов nums1 и nums2. Если текущие элементы совпадают, увеличьте значение ячейки dp[i][j] на 1 от диагонального значения dp[i-1][j-1]. Если не совпадают, установите значение ячейки dp[i][j] как максимальное из значений dp[i-1][j] и dp[i][j-1].
Результат будет находиться в ячейке dp[nums1.length][nums2.length].

😎 Решение:

import java.util.*;

public class Solution {
    public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        List<int[]> cells = new ArrayList<>();
        
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                int distance = Math.abs(r - rCenter) + Math.abs(c - cCenter);
                cells.add(new int[] { distance, r, c });
            }
        }
        
        cells.sort((a, b) -> Integer.compare(a[0], b[0]));
        
        int[][] result = new int[cells.size()][2];
        for (int i = 0; i < cells.size(); ++i) {
            result[i][0] = cells.get(i)[1];
            result[i][1] = cells.get(i)[2];
        }
        
        return result;
    }
}

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

Задача: 1003. Check If Word Is Valid After Substitutions
Сложность: medium

Дана строка s, определите, является ли она допустимой. Строка s допустима, если, начиная с пустой строки t = "", вы можете преобразовать t в s, выполнив следующую операцию любое количество раз: вставить строку "abc" в любую позицию в t. Более формально, t становится tleft + "abc" + tright, где t == tleft + tright. Обратите внимание, что tleft и tright могут быть пустыми. Верните true, если s - допустимая строка, иначе верните false.

Пример:

Input: s = "aabcbc"
Output: true

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

1⃣Проверка допустимости длины строки:
Проверьте, что длина строки s кратна 3. Если нет, верните false.

2⃣Использование стека для проверки:
Инициализируйте пустой стек. Проходите по каждому символу строки s.
Если текущий символ является 'c', проверьте, что два предыдущих символа в стеке - это 'b' и 'a' соответственно. Если это так, удалите 'b' и 'a' из стека. Если нет, верните false.
Если текущий символ не 'c', добавьте его в стек.

3⃣Проверка остатка стека:
В конце, если стек пуст, верните true. Иначе верните false.

😎 Решение:

public class Solution {
    public boolean isValid(String s) {
        if (s.length() % 3 != 0) return false;

        Stack<Character> stack = new Stack<>();
        for (char ch : s.toCharArray()) {
            if (ch == 'c') {
                if (stack.size() < 2 || stack.pop() != 'b' || stack.pop() != 'a') {
                    return false;
                }
            } else {
                stack.push(ch);
            }
        }

        return stack.isEmpty();
    }
}

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

Задача: 838. Push Dominoes
Сложность: medium

Есть n домино, выстроенные в линию, и каждое домино стоит вертикально. Вначале мы одновременно толкаем некоторые домино либо влево, либо вправо.
Через каждую секунду каждое падающее влево домино толкает соседнее домино слева. Точно так же домино, падающие вправо, толкают соседние домино, стоящие справа.
Когда вертикальное домино оказывается под воздействием падающих домино с обеих сторон, оно остаётся неподвижным из-за баланса сил.

В рамках этой задачи мы будем считать, что падающее домино не передаёт дополнительную силу падающему или уже упавшему домино.
Вам дано строковое представление начального состояния домино:
dominoes[i] = 'L', если i-е домино толкнули влево,
dominoes[i] = 'R', если i-е домино толкнули вправо, и
dominoes[i] = '.', если i-е домино не было толкнуто.
Верните строку, представляющую конечное состояние.

Пример:

Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

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

1⃣Пройдите по строке и сохраните индексы и символы не пустых домино в массивы.

2⃣Добавьте фиктивные домино 'L' в начале и 'R' в конце для упрощения логики.

3⃣Обработайте промежутки между соседними домино, обновляя их состояния согласно правилам.

😎 Решение:

class Solution {
    public String pushDominoes(String dominoes) {
        int N = dominoes.length();
        int[] indexes = new int[N+2];
        char[] symbols = new char[N+2];
        int len = 1;
        indexes[0] = -1;
        symbols[0] = 'L';

        for (int i = 0; i < N; ++i)
            if (dominoes.charAt(i) != '.') {
                indexes[len] = i;
                symbols[len++] = dominoes.charAt(i);
            }

        indexes[len] = N;
        symbols[len++] = 'R';

        char[] ans = dominoes.toCharArray();
        for (int index = 0; index < len - 1; ++index) {
            int i = indexes[index], j = indexes[index+1];
            char x = symbols[index], y = symbols[index+1];
            char write;
            if (x == y) {
                for (int k = i+1; k < j; ++k)
                    ans[k] = x;
            } else if (x > y) { // RL
                for (int k = i+1; k < j; ++k)
                    ans[k] = k-i == j-k ? '.' : k-i < j-k ? 'R' : 'L';
            }
        }

        return String.valueOf(ans);
    }
}

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

Задача: 1469. Find All The Lonely Nodes
Сложность: easy

В бинарном дереве одиночный узел — это узел, который является единственным ребёнком своего родительского узла. Корень дерева не является одиночным, так как у него нет родительского узла.

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

Пример:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
Output: [6,2]
Explanation: Light blue nodes are lonely nodes.
Please remember that order doesn't matter, [2,6] is also an acceptable answer.

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

1⃣Определите рекурсивную функцию DFS, которая принимает корень дерева, булеву переменную isLonely и список одиночных узлов ans в качестве аргументов. Если корень равен NULL, завершите выполнение функции.

2⃣Если isLonely равен true, добавьте значение корня в список ans. Рекурсивно обрабатывайте левого потомка корня, устанавливая флаг isLonely в true, если правый потомок равен NULL, и правого потомка, устанавливая флаг isLonely в true, если левый потомок равен NULL.

3⃣Вызовите DFS с корнем и false в качестве значения isLonely. Верните ans.

😎 Решение:

class Solution {
    void DFS(TreeNode root, boolean isLonely, List<Integer> ans) {
        if (root == null) {
            return;
        }
        
        if (isLonely) {
            ans.add(root.val);
        }
        
        DFS(root.left, root.right == null, ans);
        DFS(root.right, root.left == null, ans);
    }
    
    public List<Integer> getLonelyNodes(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        DFS(root, false, ans);

        return ans;
    }
}

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

Задача: 1015. Smallest Integer Divisible by K
Сложность: medium

Задано целое положительное число k, необходимо найти длину наименьшего целого положительного числа n, такого, что n делится на k, и n содержит только цифру 1. Верните длину n. Если такого n не существует, верните -1. Примечание: n может не поместиться в 64-битное знаковое целое число.

Пример:

Input: k = 1
Output: 1

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

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

2⃣Итеративное нахождение числа:
Используйте цикл, чтобы умножать num на 10 и добавлять 1 в каждой итерации, и каждый раз вычисляйте остаток от деления num на k.
Увеличивайте length на 1 в каждой итерации.
Если в какой-то итерации num % k == 0, верните length.

3⃣Проверка бесконечного цикла:
Если цикл длится слишком долго (например, 10^6 итераций), верните -1, чтобы предотвратить бесконечный цикл для случаев, когда решение не существует.

😎 Решение:

public class Solution {
    public int smallestRepunitDivByK(int k) {
        int num = 1, length = 1;
        Set<Integer> seen = new HashSet<>();
        
        while (num % k != 0) {
            if (seen.contains(num % k)) {
                return -1;
            }
            seen.add(num % k);
            num = (num * 10 + 1) % k;
            length++;
        }
        
        return length;
    }
}

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

Задача: 1039. Minimum Score Triangulation of Polygon
Сложность: medium

У вас есть выпуклый n-сторонний многоугольник, каждая вершина которого имеет целочисленное значение. Вам дан целочисленный массив values, где values[i] - это значение i-й вершины (т.е. по часовой стрелке). Вы должны триангулировать многоугольник на n - 2 треугольника. Для каждого треугольника значение этого треугольника равно произведению значений его вершин, а общий балл триангуляции равен сумме этих значений для всех n - 2 треугольников в триангуляции. Верните наименьший возможный общий балл, который вы можете получить с помощью некоторой триангуляции многоугольника.

Пример:

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

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

1⃣Инициализация:
Создаем двумерный массив dp, где dp[i][j] будет хранить минимальный возможный общий балл триангуляции многоугольника, состоящего из вершин от i до j.

2⃣Основное заполнение dp:
Проходим по всем возможным длинам подмногоугольников, начиная с треугольников (длина 3) до всего многоугольника (длина n).
Для каждого подмногоугольника находим минимальный возможный общий балл, проверяя все возможные треугольники, которые могут быть образованы из этого подмногоугольника.
Заполнение dp для каждого подмногоугольника:
Для каждого подмногоугольника от i до j, и для каждой возможной вершины k между i и j, обновляем значение dp[i][j], как сумму минимальных значений триангуляций левой и правой частей подмногоугольника, а также значения текущего треугольника, образованного вершинами i, k и j.

3⃣Возврат результата:
Ответ будет в dp[0][n-1], который хранит минимальный возможный общий балл триангуляции для всего многоугольника.

😎 Решение:

public class Solution {
    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        int[][] dp = new int[n][n];
        
        for (int length = 2; length < n; ++length) {
            for (int i = 0; i < n - length; ++i) {
                int j = i + length;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; ++k) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]);
                }
            }
        }
        
        return dp[0][n - 1];
    }
}

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

Задача: 783. Minimum Distance Between BST Nodes
Сложность: easy

Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве.

Пример:

Input: root = [4,2,6,1,3]
Output: 1

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

1⃣Инициализируйте minDistance значением MAX_VALUE; это переменная для хранения минимальной разницы.

2⃣Выполните обход дерева поиска в порядке возрастания (in-order traversal) и сохраните узлы в списке inorderNodes.

3⃣Итеративно проходите по списку inorderNodes, начиная с индекса 1. Для каждого элемента на позиции i найдите разницу с элементом на индексе i - 1 и соответствующим образом обновите переменную minDistance.
Верните minDistance.

😎 Решение:

class Solution {
    List<Integer> inorderNodes = new ArrayList<>();
    
    private void inorderTraversal(TreeNode root) {
        if (root == null) return;
        
        inorderTraversal(root.left);
        inorderNodes.add(root.val);
        inorderTraversal(root.right);
    }
    
    public int minDiffInBST(TreeNode root) {
        inorderTraversal(root);
        
        int minDistance = Integer.MAX_VALUE;
        for (int i = 1; i < inorderNodes.size(); i++) {
            minDistance = Math.min(minDistance, inorderNodes.get(i) - inorderNodes.get(i - 1));
        }
        
        return minDistance;
    }
}

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

Задача: 1048. Longest String Chain
Сложность: easy

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

Например, "abc" является предшественником "abac", а "cba" не является предшественником "bcad". Цепочка слов - это последовательность слов [word1, word2, ..., wordk] с k >= 1, где word1 является предшественником word2, word2 является предшественником word3 и так далее. Одиночное слово тривиально является цепочкой слов с k == 1. Верните длину самой длинной возможной цепочки слов со словами, выбранными из заданного списка слов.

Пример:

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4

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

1⃣Отсортируй список слов по длине.

2⃣Используй динамическое программирование для вычисления длины самой длинной цепочки для каждого слова.

3⃣Верни максимальную длину среди всех цепочек.

😎 Решение:

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

public class Solution {
    public int longestStrChain(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        Map<String, Integer> dp = new HashMap<>();
        int longestChain = 1;
        
        for (String word : words) {
            dp.put(word, 1);
            for (int i = 0; i < word.length(); i++) {
                StringBuilder sb = new StringBuilder(word);
                String predecessor = sb.deleteCharAt(i).toString();
                if (dp.containsKey(predecessor)) {
                    dp.put(word, Math.max(dp.get(word), dp.get(predecessor) + 1));
                }
            }
            longestChain = Math.max(longestChain, dp.get(word));
        }
        
        return longestChain;
    }
}

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

Задача: 686. Repeated String Match
Сложность: medium

Даны две строки a и b. Верните минимальное количество повторений строки a, чтобы строка b стала её подстрокой. Если сделать b подстрокой a невозможно, верните -1.

Обратите внимание: строка "abc", повторенная 0 раз, это "", повторенная 1 раз - "abc", повторенная 2 раза - "abcabc".

Пример:

Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.

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

1⃣Найти минимальное количество повторений строки A, чтобы её длина стала больше или равна длине B. Это значение q = ceil(len(B) / len(A)).

2⃣Проверить, является ли B подстрокой строки A, повторенной q раз. Если да, вернуть q. Иначе, проверить строку A, повторенную (q+1) раз. Если B является подстрокой этой строки, вернуть q+1.

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

😎 Решение:

class Solution {
    public int repeatedStringMatch(String A, String B) {
        int q = 1;
        StringBuilder S = new StringBuilder(A);
        while (S.length() < B.length()) {
            S.append(A);
            q++;
        }
        if (S.indexOf(B) >= 0) return q;
        if (S.append(A).indexOf(B) >= 0) return q + 1;
        return -1;
    }
}

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

Задача: 943. Find the Shortest Superstring
Сложность: hard

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

Пример:

Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"

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

1⃣Реализовать функцию overlap для вычисления максимального перекрытия двух строк, где одна строка заканчивается, а другая начинается.

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

3⃣Вернуть результат.

😎 Решение:

import java.util.ArrayList;
import java.util.List;

class Solution {
    public String shortestSuperstring(String[] words) {
        int n = words.length;
        while (n > 1) {
            int maxOverlap = -1, l = 0, r = 0;
            String merged = "";
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i != j) {
                        int overlapLen = overlap(words[i], words[j]);
                        if (overlapLen > maxOverlap) {
                            maxOverlap = overlapLen;
                            l = i;
                            r = j;
                            merged = merge(words[i], words[j], overlapLen);
                        }
                    }
                }
            }
            words[l] = merged;
            words[r] = words[n - 1];
            n--;
        }
        return words[0];
    }

    private int overlap(String a, String b) {
        int maxOverlap = 0;
        for (int i = 1; i <= Math.min(a.length(), b.length()); i++) {
            if (a.substring(a.length() - i).equals(b.substring(0, i))) {
                maxOverlap = i;
            }
        }
        return maxOverlap;
    }

    private String merge(String a, String b, int overlapLen) {
        return a + b.substring(overlapLen);
    }
}

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

Задача: 970. Powerful Integers
Сложность: medium

Даны три целых числа x, y и bound. Верните список всех мощных чисел, которые имеют значение меньше или равное bound.

Целое число является мощным, если оно может быть представлено как x^i + y^j для некоторых целых чисел i >= 0 и j >= 0.

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

Пример:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation:
2 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32

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

1⃣Вычислите степени a и b как логарифмы bound по основаниям x и y соответственно. Создайте множество powerfulIntegers для хранения результатов.

2⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.

3⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.

😎 Решение:

class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        int a = x == 1 ? bound : (int) (Math.log(bound) / Math.log(x));
        int b = y == 1 ? bound : (int) (Math.log(bound) / Math.log(y));
        HashSet<Integer> powerfulIntegers = new HashSet<Integer>();

        for (int i = 0; i <= a; i++) {
            for (int j = 0; j <= b; j++) {
                int value = (int) Math.pow(x, i) + (int) Math.pow(y, j);
                if (value <= bound) {
                    powerfulIntegers.add(value);
                }
                if (y == 1) {
                    break;
                }
            }
            if (x == 1) {
                break;
            }
        }

        return new ArrayList<Integer>(powerfulIntegers);
    }
}

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

Задача: 345. Reverse Vowels of a String
Сложность: easy

Дана строка s, переверните только все гласные в строке и верните её.

Гласные: 'a', 'e', 'i', 'o', 'u', а также их верхние регистры.

Пример:

Input: s = "hello"
Output: "holle"

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

1⃣Инициализация указателей и гласных:
Создайте набор гласных для быстрой проверки.
Установите два указателя: один на начало строки (left), другой на конец строки (right).

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

3⃣Завершение работы:
Когда указатели пересекутся, остановите процесс и верните строку.

😎 Решение:

public class Solution {
    public String reverseVowels(String s) {
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
        char[] chars = s.toCharArray();
        int left = 0, right = s.length() - 1;
        
        while (left < right) {
            if (!vowels.contains(chars[left])) {
                left++;
            } else if (!vowels.contains(chars[right])) {
                right--;
            } else {
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
                left++;
                right--;
            }
        }
        
        return new String(chars);
    }
}

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

Задача: 1372. Longest ZigZag Path in a Binary Tree
Сложность: medium

Вам дан корень бинарного дерева.

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

Выберите любой узел в бинарном дереве и направление (вправо или влево).
Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу.
Измените направление с вправо на влево или с влево на вправо.
Повторяйте второй и третий шаги, пока не сможете двигаться по дереву.
Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0).

Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве.

Пример:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

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

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

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

😎 Решение:

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

public class Solution {
    private int maxLength = 0;

    public int longestZigZag(TreeNode root) {
        dfs(root, true, 0);
        dfs(root, false, 0);
        return maxLength;
    }

    private void dfs(TreeNode node, boolean isLeft, int length) {
        if (node == null) {
            return;
        }
        maxLength = Math.max(maxLength, length);
        if (isLeft) {
            dfs(node.left, false, length + 1);
            dfs(node.right, true, 1);
        } else {
            dfs(node.right, true, length + 1);
            dfs(node.left, false, 1);
        }
    }
}

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