Задача: 1406. Stone Game III
Сложность: hard

Алиса и Боб продолжают свои игры с кучами камней. Камни расположены в ряд, и каждый камень имеет ассоциированное значение, которое представлено целым числом в массиве stoneValue.
Алиса и Боб ходят по очереди, начиная с Алисы. В свой ход каждый игрок может взять 1, 2 или 3 камня из первых оставшихся камней в ряду.

Счет каждого игрока равен сумме значений взятых камней. Изначально счет каждого игрока равен 0.
Цель игры — закончить с наивысшим счетом, и победителем становится игрок с наивысшим счетом, при этом возможна ничья. Игра продолжается, пока все камни не будут взяты.

Предположим, что Алиса и Боб играют оптимально.
Верните "Alice", если Алиса выиграет, "Bob", если выиграет Боб, или "Tie", если они закончат игру с одинаковым счетом.

Пример:

Input: stoneValue = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.

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

1⃣Инициализируйте массив dp размером n+1 и установите dp[n] в 0.

2⃣Итеративно обновляйте dp[i] для всех i от n-1 до 0, вычисляя максимальную разницу в баллах, которые могут получить игроки при оптимальной игре.

3⃣Определите победителя, сравнивая dp[0] с 0: если больше, победит Алиса; если меньше, победит Боб; если равно, будет ничья.

😎 Решение:

public class Solution {
    public string StoneGameIII(int[] stoneValue) {
        int n = stoneValue.Length;
        int[] dp = new int[n + 1];
        for (int i = n - 1; i >= 0; --i) {
            dp[i] = stoneValue[i] - dp[i + 1];
            if (i + 2 <= n) {
                dp[i] = Math.Max(dp[i], stoneValue[i] + stoneValue[i + 1] - dp[i + 2]);
            }
            if (i + 3 <= n) {
                dp[i] = Math.Max(dp[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3]);
            }
        }
        if (dp[0] > 0) return "Alice";
        if (dp[0] < 0) return "Bob";
        return "Tie";
    }
}

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

Задача: 1425. Constrained Subsequence Sum
Сложность: hard

Дан целочисленный массив nums и целое число k, верните максимальную сумму непустой подпоследовательности этого массива, такую, что для любых двух последовательных целых чисел в подпоследовательности nums[i] и nums[j], где i < j, выполняется условие j - i <= k.

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

Пример:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

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

1⃣Инициализируйте очередь queue и массив dp той же длины, что и nums.

2⃣Итерируйте i по индексам nums:
Если i минус первый элемент queue больше k, удалите элемент из начала queue.
Установите dp[i] как dp[queue.front()] + nums[i]. Если queue пуст, используйте 0 вместо dp[queue.front()].
Пока dp[queue.back()] меньше dp[i], удаляйте элементы с конца queue.
Если dp[i] > 0, добавьте i в конец queue.

3⃣Верните максимальное значение в массиве dp.

😎 Решение:

public class Solution {
    public int ConstrainedSubsetSum(int[] nums, int k) {
        Deque<int> queue = new LinkedList<int>();
        int[] dp = new int[nums.Length];
        int maxSum = int.MinValue;
        
        for (int i = 0; i < nums.Length; i++) {
            if (queue.Count > 0 && i - queue.First.Value > k) {
                queue.RemoveFirst();
            }
            
            dp[i] = (queue.Count > 0 ? dp[queue.First.Value] : 0) + nums[i];
            
            while (queue.Count > 0 && dp[queue.Last.Value] < dp[i]) {
                queue.RemoveLast();
            }
            
            if (dp[i] > 0) {
                queue.AddLast(i);
            }
            
            maxSum = Math.Max(maxSum, dp[i]);
        }
        
        return maxSum;
    }
}

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

Задача: 845. Longest Mountain in Array
Сложность: medium

Вы можете вспомнить, что массив arr является горным массивом тогда и только тогда, когда:
длина массива arr >= 3
Существует индекс i (счёт начинается с 0) такой, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан целочисленный массив arr, верните длину самой длинной подпоследовательности, которая является горной. Верните 0, если такой подпоследовательности нет.

Пример:

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

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

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

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

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

😎 Решение:

class Solution {
public:
    int longestMountain(vector<int>& A) {
        int N = A.size();
        int ans = 0, base = 0;
        while (base < N) {
            int end = base;
            if (end + 1 < N && A[end] < A[end + 1]) {
                while (end + 1 < N && A[end] < A[end + 1]) end++;
                if (end + 1 < N && A[end] > A[end + 1]) {
                    while (end + 1 < N && A[end] > A[end + 1]) end++;
                    ans = max(ans, end - base + 1);
                }
            }
            base = max(end, base + 1);
        }
        return ans;
    }
};

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

Задача: 1530. Number of Good Leaf Nodes Pairs
Сложность: medium

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

Верните количество хороших пар листовых узлов в дереве.

Пример:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

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

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

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

3⃣Верните ans / 2. Мы считаем каждую пару дважды, поэтому нужно разделить на 2, чтобы получить фактическое количество.

😎 Решение:

public class Solution {
    public int CountPairs(TreeNode root, int distance) {
        var graph = new Dictionary<TreeNode, List<TreeNode>>();
        var leafNodes = new HashSet<TreeNode>();
        TraverseTree(root, null, graph, leafNodes);
        int ans = 0;
        foreach (var leaf in leafNodes) {
            var bfsQueue = new Queue<TreeNode>();
            var seen = new HashSet<TreeNode>();
            bfsQueue.Enqueue(leaf);
            seen.Add(leaf);
            for (int i = 0; i <= distance; i++) {
                int size = bfsQueue.Count;
                for (int j = 0; j < size; j++) {
                    var currNode = bfsQueue.Dequeue();
                    if (leafNodes.Contains(currNode) && currNode != leaf) {
                        ans++;
                    }
                    if (graph.ContainsKey(currNode)) {
                        foreach (var neighbor in graph[currNode]) {
                            if (!seen.Contains(neighbor)) {
                                bfsQueue.Enqueue(neighbor);
                                seen.Add(neighbor);
                            }
                        }
                    }
                }
            }
        }
        return ans / 2;
    }

    private void TraverseTree(TreeNode currNode, TreeNode prevNode,
                              Dictionary<TreeNode, List<TreeNode>> graph, HashSet<TreeNode> leafNodes) {
        if (currNode == null) {
            return;
        }
        if (currNode.left == null && currNode.right == null) {
            leafNodes.Add(currNode);
        }
        if (prevNode != null) {
            if (!graph.ContainsKey(prevNode)) {
                graph[prevNode] = new List<TreeNode>();
            }
            graph[prevNode].Add(currNode);
            if (!graph.ContainsKey(currNode)) {
                graph[currNode] = new List<TreeNode>();
            }
            graph[currNode].Add(prevNode);
        }
        TraverseTree(currNode.left, currNode, graph, leafNodes);
        TraverseTree(currNode.right, currNode, graph, leafNodes);
    }
}

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

Задача: 1062. Longest Repeating Substring
Сложность: medium

Дана строка s. Вернуть длину самой длинной повторяющейся подстроки. Если повторяющаяся подстрока отсутствует, вернуть 0.

Пример:

Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.

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

1⃣Перемещайте скользящее окно длиной L по строке длиной N.

2⃣Проверьте, находится ли строка в скользящем окне в хэш-наборе уже виденных строк. Если да, то повторяющаяся подстрока находится здесь. Если нет, сохраните строку из скользящего окна в хэш-наборе.

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

😎 Решение:

public class Solution {
    public int Search(int L, int n, string S) {
        var seen = new HashSet<string>();
        for (int start = 0; start <= n - L; ++start) {
            string tmp = S.Substring(start, L);
            if (seen.Contains(tmp)) return start;
            seen.Add(tmp);
        }
        return -1;
    }

    public int LongestRepeatingSubstring(string S) {
        int n = S.Length;
        int left = 1, right = n;
        while (left <= right) {
            int L = left + (right - left) / 2;
            if (Search(L, n, S) != -1) {
                left = L + 1;
            } else {
                right = L - 1;
            }
        }
        return left - 1;
    }
}

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

Задача: 1155. Number of Dice Rolls With Target Sum
Сложность: medium

У вас есть n кубиков, и на каждом кубике k граней, пронумерованных от 1 до k.

Даны три целых числа n, k и target. Необходимо вернуть количество возможных способов (из общего количества kn способов) выбросить кубики так, чтобы сумма выпавших чисел равнялась target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.

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

1⃣Начните с:
Индекс кубика diceIndex равен 0; это индекс кубика, который мы рассматриваем в данный момент.
Сумма чисел на предыдущих кубиках currSum равна 0.
Инициализируйте переменную ways значением 0. Итерируйтесь по значениям от 1 до k для каждого значения i. Если текущий кубик может иметь значение i, т.е. currSum после добавления i не превысит значение target, то обновите значение currSum и рекурсивно перейдите к следующему кубику. Добавьте значение, возвращенное этим рекурсивным вызовом, к ways. Иначе, если это значение невозможно, то выйдите из цикла, так как большие значения также не удовлетворят вышеуказанному условию.

2⃣Базовые случаи:

Если мы перебрали все кубики, т.е. diceIndex = n, то проверьте, равна ли currSum значению target.

3⃣Верните значение ways и также сохраните его в таблице мемоизации memo, соответствующей текущему состоянию, определяемому diceIndex и currSum.

😎 Решение:

public class Solution {
    private const int MOD = 1_000_000_007;

    private int WaysToTarget(int[][] memo, int diceIndex, int n, int currSum, int target, int k) {
        if (diceIndex == n) {
            return currSum == target ? 1 : 0;
        }
        if (memo[diceIndex][currSum] != -1) {
            return memo[diceIndex][currSum];
        }

        int ways = 0;
        for (int i = 1; i <= Math.Min(k, target - currSum); i++) {
            ways = (ways + WaysToTarget(memo, diceIndex + 1, n, currSum + i, target, k)) % MOD;
        }
        memo[diceIndex][currSum] = ways;
        return ways;
    }

    public int NumRollsToTarget(int n, int k, int target) {
        int[][] memo = new int[n + 1][];
        for (int i = 0; i <= n; i++) {
            memo[i] = new int[target + 1];
            Array.Fill(memo[i], -1);
        }
        return WaysToTarget(memo, 0, n, 0, target, k);
    }
}

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

Задача: 1231. Divide Chocolate
Сложность: hard

У вас есть одна шоколадка, состоящая из нескольких кусочков. Каждый кусочек имеет свою сладость, заданную массивом сладости. Вы хотите поделиться шоколадом со своими k друзьями, поэтому начинаете разрезать шоколадку на k + 1 кусочков с помощью k разрезов, каждый кусочек состоит из нескольких последовательных кусочков. Будучи щедрым, вы съедите кусочек с минимальной общей сладостью, а остальные кусочки отдадите своим друзьям. Найдите максимальную общую сладость кусочка, который вы можете получить, оптимально разрезав шоколадку.

Пример:

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

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

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

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

3⃣Проверка делимости:
Для каждой попытки значения сладости в двоичном поиске проверим, можем ли мы разрезать шоколад так, чтобы каждая из k+1 частей имела сладость не меньше текущего значения.

😎 Решение:

public class Solution {
    public int MaximizeSweetness(int[] sweetness, int k) {
        bool CanDivide(int minSweetness) {
            int currentSum = 0, cuts = 0;
            foreach (var sweet in sweetness) {
                currentSum += sweet;
                if (currentSum >= minSweetness) {
                    cuts++;
                    currentSum = 0;
                }
            }
            return cuts >= k + 1;
        }
        
        int left = sweetness.Min();
        int right = sweetness.Sum() / (k + 1);
        
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (CanDivide(mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
}

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

Задача: 1065. Index Pairs of a String
Сложность: easy

Дана строка text и массив строк words, верните массив всех пар индексов [i, j], таких что подстрока text[i...j] находится в words.

Верните пары [i, j] в отсортированном порядке (то есть отсортируйте их по первой координате, а в случае совпадения сортируйте их по второй координате).

Пример:

Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

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

1⃣Поддерживайте хэш-набор слов.

2⃣Итерируйте i от 0 до text.length-1. Итерируйте j от i до text.length-1. Если подстрока text[i...j] принадлежит хэш-набору слов, добавьте пару [i, j] в ответ.

3⃣Верните ответ.

😎 Решение:

public class Solution {
    public IList<IList<int>> IndexPairs(string text, string[] words) {
        var wordsSet = new HashSet<string>(words);
        var ans = new List<IList<int>>();
        
        for (int i = 0; i < text.Length; i++) {
            for (int j = i; j < text.Length; j++) {
                if (wordsSet.Contains(text.Substring(i, j - i + 1))) {
                    ans.Add(new List<int> { i, j });
                }
            }
        }
        return ans;
    }
}

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

Задача: 567. Permutation in String
Сложность: medium

Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае.

Другими словами, верните true, если одна из перестановок s1 является подстрокой s2.

Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

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

1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2.

2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1.

3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.

😎 Решение:

public class Solution {
    public bool CheckInclusion(string s1, string s2) {
        int s1Len = s1.Length, s2Len = s2.Length;
        if (s1Len > s2Len) return false;
        
        int[] s1Count = new int[26];
        int[] s2Count = new int[26];
        
        for (int i = 0; i < s1Len; i++) {
            s1Count[s1[i] - 'a']++;
            s2Count[s2[i] - 'a']++;
        }
        
        for (int i = 0; i < s2Len - s1Len; i++) {
            if (s1Count.SequenceEqual(s2Count)) return true;
            s2Count[s2[i] - 'a']--;
            s2Count[s2[i + s1Len] - 'a']++;
        }
        
        return s1Count.SequenceEqual(s2Count);
    }
}

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

public class Solution {
    public IList<int> NumOfBurgers(int tomatoSlices, int cheeseSlices) {
        if (tomatoSlices % 2 != 0 || tomatoSlices < 2 * cheeseSlices || tomatoSlices > 4 * cheeseSlices) {
            return new List<int>();
        }
        int total_jumbo = (tomatoSlices - 2 * cheeseSlices) / 2;
        int total_small = cheeseSlices - total_jumbo;
        return new List<int> { total_jumbo, total_small };
    }
}

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

Задача: 753. Cracking the Safe
Сложность: medium

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

using System.Collections.Generic;
using System.Text;

public class Solution {
    public string CrackSafe(int n, int k) {
        var seen = new HashSet<string>();
        var result = new StringBuilder();

        string startNode = new string('0', n - 1);
        Dfs(startNode, k, seen, result);

        result.Append(startNode);
        return result.ToString();
    }

    private void Dfs(string node, int k, HashSet<string> seen, StringBuilder result) {
        for (int x = 0; x < k; x++) {
            string neighbor = node + x;
            if (!seen.Contains(neighbor)) {
                seen.Add(neighbor);
                Dfs(neighbor.Substring(1), k, seen, result);
                result.Append(x);
            }
        }
    }
}

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

Задача: 901. Online Stock Span
Сложность: medium

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

Например, если цены акции за последние четыре дня равны [7,2,1,2], а цена акции сегодня равна 2, то размах сегодняшнего дня равен 4, поскольку, начиная с сегодняшнего дня, цена акции была меньше или равна 2 в течение 4 дней подряд.
Также, если цена акции за последние четыре дня равна [7,34,1,2], а цена акции сегодня равна 8, то размах сегодняшнего дня равен 3, так как начиная с сегодняшнего дня цена акции была меньше или равна 8 в течение 3 дней подряд. Реализация класса StockSpanner: StockSpanner() Инициализирует объект класса. int next(int price) Возвращает размах цены акции, учитывая, что сегодняшняя цена равна price.

Пример:

Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]

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

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

2⃣Для метода next:
Установить начальный размах текущего дня равным 1.
Пока стек не пуст и верхний элемент стека имеет цену меньше или равную текущей цене:
Добавить размах верхнего элемента стека к текущему размаху.
Удалить верхний элемент стека.

3⃣Добавить текущую цену и размах на вершину стека.
Вернуть текущий размах.

😎 Решение:

using System;
using System.Collections.Generic;

public class StockSpanner {
    private Stack<Tuple<int, int>> stack;

    public StockSpanner() {
        stack = new Stack<Tuple<int, int>>();
    }

    public int Next(int price) {
        int span = 1;
        while (stack.Count > 0 && stack.Peek().Item1 <= price) {
            span += stack.Pop().Item2;
        }
        stack.Push(Tuple.Create(price, span));
        return span;
    }
}

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

Задача: 678. Valid Parenthesis String
Сложность: medium

Создайте карту, которая позволяет выполнять следующие действия:

Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:

Дана строка s, содержащая только три типа символов: '(', ')' и '*'. Вернуть true, если s является допустимой.

Следующие правила определяют допустимую строку:

Любая открывающая скобка '(' должна иметь соответствующую закрывающую скобку ')'.
Любая закрывающая скобка ')' должна иметь соответствующую открывающую скобку '('.
Открывающая скобка '(' должна идти перед соответствующей закрывающей скобкой ')'.
'*' может рассматриваться как одна закрывающая скобка ')', одна открывающая скобка '(' или пустая строка "".

Пример:

Input: s = "()"
Output: true
Example 2:

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

1⃣Инициализировать 2D вектор memo размером s.size() x s.size() - 1, представляющий неинициализированное состояние. Вызвать вспомогательную функцию isValidString с начальными параметрами index = 0, openCount = 0 и строкой s. Вернуть результат isValidString.

2⃣Вспомогательная функция isValidString. Базовый случай: если index достиг конца строки (index == s.size.), вернуть true, если openCount равен 0 (все скобки сбалансированы), и false в противном случае. Проверить, был ли результат для текущего index и openCount уже вычислен (мемоизирован) в memo. Если да, вернуть мемоизированный результат. Инициализировать isValid как false. Если текущий символ s[index] равен '*': Попробовать трактовать '*' как '(' и вызвать isValidString рекурсивно с index + 1 и openCount + 1. Если рекурсивный вызов вернет true, обновить isValid на true. Если openCount не равен нулю, попробовать трактовать '*' как ')' и вызвать isValidString рекурсивно с index + 1 и openCount - 1. Если рекурсивный вызов вернет true, обновить isValid на true. Попробовать трактовать '*' как пустой символ и вызвать isValidString рекурсивно с index + 1 и тем же openCount. Если рекурсивный вызов вернет true, обновить isValid на true.

3⃣Продолжение функции isValidString. Если текущий символ s[index] равен '(': Вызвать isValidString рекурсивно с index + 1 и openCount + 1. Обновить isValid с результатом рекурсивного вызова. Если текущий символ s[index] равен ')': Если openCount не равен нулю (есть открытые скобки), вызвать isValidString рекурсивно с index + 1 и openCount - 1. Обновить isValid с результатом рекурсивного вызова. Мемоизировать результат isValid в memo[index][openCount]. Вернуть isValid.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public bool CheckValidString(string s) {
        int n = s.Length;
        int[][] memo = new int[n][];
        for (int i = 0; i < n; i++) {
            memo[i] = new int[n];
            Array.Fill(memo[i], -1);
        }
        return IsValidString(0, 0, s, memo);
    }

    private bool IsValidString(int index, int openCount, string str, int[][] memo) {
        if (index == str.Length) {
            return openCount == 0;
        }

        if (memo[index][openCount] != -1) {
            return memo[index][openCount] == 1;
        }

        bool isValid = false;

        if (str[index] == '*') {
            isValid = IsValidString(index + 1, openCount + 1, str, memo);
            if (openCount > 0) {
                isValid = isValid || IsValidString(index + 1, openCount - 1, str, memo);
            }
            isValid = isValid || IsValidString(index + 1, openCount, str, memo);
        } else if (str[index] == '(') {
            isValid = IsValidString(index + 1, openCount + 1, str, memo);
        } else if (openCount > 0) {
            isValid = IsValidString(index + 1, openCount - 1, str, memo);
        }

        memo[index][openCount] = isValid ? 1 : 0;
        return isValid;
    }
}

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

Задача: 1361. Validate Binary Tree Nodes
Сложность: easy

У вас есть n узлов бинарного дерева, пронумерованных от 0 до n-1, где узел i имеет двух детей: leftChild[i] и rightChild[i]. Верните true, если и только если все заданные узлы образуют ровно одно допустимое бинарное дерево.

Если у узла i нет левого ребенка, то leftChild[i] будет равен -1, аналогично для правого ребенка.

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

Пример:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

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

1⃣Проверка количества родителей для каждого узла:
Создайте массив для отслеживания количества родителей для каждого узла. Проходите через leftChild и rightChild, увеличивая счетчик для каждого ребенка. Если какой-либо узел имеет более одного родителя, возвращайте false.

2⃣Поиск корневого узла и проверка на единственное дерево:
Найдите корневой узел (узел с нулевым количеством родителей). Если корневых узлов нет или больше одного, верните false. Используйте BFS или DFS, чтобы проверить, что все узлы достижимы от корня и что нет циклов.

3⃣Проверка на достижение всех узлов:
Проверьте, что количество посещенных узлов равно n. Если нет, верните false. В противном случае, верните true.
😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public bool ValidateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] parents = new int[n];
        
        for (int i = 0; i < n; i++) {
            if (leftChild[i] != -1) {
                if (++parents[leftChild[i]] > 1) {
                    return false;
                }
            }
            if (rightChild[i] != -1) {
                if (++parents[rightChild[i]] > 1) {
                    return false;
                }
            }
        }
        
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (parents[i] == 0) {
                if (root == -1) {
                    root = i;
                } else {
                    return false;
                }
            }
        }
        
        if (root == -1) {
            return false;
        }
        
        HashSet<int> visited = new HashSet<int>();
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(root);
        
        while (queue.Count > 0) {
            int node = queue.Dequeue();
            if (!visited.Add(node)) {
                return false;
            }
            if (leftChild[node] != -1) {
                queue.Enqueue(leftChild[node]);
            }
            if (rightChild[node] != -1) {
                queue.Enqueue(rightChild[node]);
            }
        }
        
        return visited.Count == n;
    }
}

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

Задача: 278. First Bad Version
Сложность: easy

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

Предположим, у вас есть n версий [1, 2, ..., n], и вы хотите выяснить первую плохую версию, которая вызывает все последующие версии быть плохими.

Вам предоставлен API bool isBadVersion(version), который возвращает, является ли версия плохой. Реализуйте функцию для нахождения первой плохой версии. Вы должны минимизировать количество вызовов API.

Пример:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

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

1⃣Инициализация границ поиска:
Устанавливаем начальные значения левой и правой границ поиска: left = 1 и right = n.

2⃣Бинарный поиск:
Пока левая граница меньше правой, находим среднюю точку mid и проверяем, является ли она плохой версией с помощью isBadVersion(mid).
Если текущая версия mid плохая, смещаем правую границу к mid, иначе смещаем левую границу на mid + 1.

3⃣Возврат результата:
Когда левая граница станет равной правой, возвращаем left как индекс первой плохой версии.

😎 Решение:

public class Solution {
    public int FirstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (IsBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

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

Задача: 600. Non-negative Integers without Consecutive Ones
Сложность: hard

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

Пример:

Input: n = 5
Output: 5
Explanation:
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 

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

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

2⃣Чтобы проверить, существует ли 1 на позиции x (считая от младшего значащего бита), в текущем числе n, поступаем следующим образом. Сдвигаем двоичную 1 x−1 раз влево, чтобы получить число y, которое имеет 1 только на x-й позиции. Логическое И числа n и y даст результат 1 только если n содержит 1 на позиции x.

3⃣В конце подсчитываем и возвращаем количество чисел в диапазоне [0, n], не содержащих последовательных единиц.

😎 Решение:

public class Solution {
    public int FindIntegers(int num) {
        int count = 0;
        for (int i = 0; i <= num; i++) {
            if (Check(i)) {
                count++;
            }
        }
        return count;
    }

    public bool Check(int n) {
        int i = 31;
        while (i > 0) {
            if ((n & (1 << i)) != 0 && (n & (1 << (i - 1))) != 0) {
                return false;
            }
            i--;
        }
        return true;
    }
}

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

Задача: 787. Cheapest Flights Within K Stops
Сложность: medium

Есть n городов, соединенных некоторым количеством рейсов. Вам дан массив flights, где flights[i] = [fromi, toi, pricei] указывает на то, что существует рейс из города fromi в город toi с ценой pricei.

Также даны три целых числа src, dst и k. Верните самую дешевую цену от src до dst с не более чем k остановками. Если такого маршрута нет, верните -1.

Пример:

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

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

1⃣Создайте список смежности, где adj[X] содержит всех соседей узла X и соответствующую цену, которую нужно заплатить, чтобы перейти к соседу. Инициализируйте массив dist, хранящий минимальную цену для достижения узла из узла src. Инициализируйте его большими значениями. Инициализируйте очередь, хранящую пары {node, distance}. Изначально очередь должна содержать только {src, 0}. Создайте переменную stops и установите ее значение равным 0.

2⃣Выполняйте поиск в ширину (BFS), пока очередь не станет пустой или пока stops > k. Итерируйте по всем узлам на определенном уровне. Это будет сделано путем запуска вложенного цикла и посещения всех узлов, которые в данный момент находятся в очереди. В каждой паре {node, distance} итерируйте по всем соседям узла. Для каждого соседа проверьте, меньше ли dist[neighbor] чем distance + цена ребра. Если это так, обновите dist[neighbor] и добавьте {neighbor, dist[neighbor]} в очередь.

3⃣После итерации по всем узлам на текущем уровне увеличьте stops на один. Мы посетили все узлы на определенном уровне и готовы посетить следующий уровень узлов. Когда мы достигнем условия, при котором либо очередь станет пустой, либо stops == k, у нас будет наш ответ в dist[dst]. Если dist[dst] не изменилось с начального большого значения, значит, мы никогда не достигли его, и следует вернуть -1.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        var adj = new List<(int, int)>[n];
        for (int i = 0; i < n; i++) adj[i] = new List<(int, int)>();
        foreach (var flight in flights) {
            adj[flight[0]].Add((flight[1], flight[2]));
        }
        var dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        var q = new Queue<(int node, int distance)>();
        q.Enqueue((src, 0));
        int stops = 0;

        while (stops <= k && q.Count > 0) {
            int sz = q.Count;
            for (int i = 0; i < sz; i++) {
                var (node, distance) = q.Dequeue();
                foreach (var (neighbour, price) in adj[node]) {
                    if (price + distance >= dist[neighbour]) continue;
                    dist[neighbour] = price + distance;
                    q.Enqueue((neighbour, dist[neighbour]));
                }
            }
            stops++;
        }
        return dist[dst] == int.MaxValue ? -1 : dist[dst];
    }
}

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

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

😎 Решение:

public class Solution {
    public int Maximum69Number (int num) {
        char[] numArr = num.ToString().ToCharArray();
        for (int i = 0; i < numArr.Length; i++) {
            if (numArr[i] == '6') {
                numArr[i] = '9';
                break;
            }
        }
        return int.Parse(new string(numArr));
    }
}

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

Задача: 1197. Minimum Knight Moves
Сложность: medium

На бесконечной шахматной доске с координатами от -бесконечности до +бесконечности у вас есть конь на клетке [0, 0].
У коня есть 8 возможных ходов. Каждый ход представляет собой два квадрата в кардинальном направлении, затем один квадрат в ортогональном направлении.

Верните минимальное количество шагов, необходимых для перемещения коня на клетку [x, y]. Гарантируется, что ответ существует.

Пример:

Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

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

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

2⃣Реализация двунаправленного поиска в ширину (BFS):
Выполняйте шаги из очередей, расширяя круги поиска как от начальной, так и от конечной точки.
Если круги пересекаются, возвращайте сумму расстояний до точки пересечения.

3⃣ Расширение кругов поиска:
Для каждой текущей точки из очередей расширяйте круг поиска по всем возможным ходам коня.
Обновляйте расстояния и добавляйте новые точки в очереди, если они еще не были посещены.
Увеличивайте units на значение, извлеченное из кучи.

😎 Решение:

public class Solution {
    public int MinKnightMoves(int x, int y) {
        int[][] offsets = new int[][] {
            new int[] {1, 2}, new int[] {2, 1}, new int[] {2, -1}, new int[] {1, -2},
            new int[] {-1, -2}, new int[] {-2, -1}, new int[] {-2, 1}, new int[] {-1, 2}
        };
        
        var originQueue = new Queue<int[]>();
        originQueue.Enqueue(new int[] {0, 0, 0});
        var originDistance = new Dictionary<string, int> {{"0,0", 0}};
        
        var targetQueue = new Queue<int[]>();
        targetQueue.Enqueue(new int[] {x, y, 0});
        var targetDistance = new Dictionary<string, int> {{$"{x},{y}", 0}};
        
        while (true) {
            var origin = originQueue.Dequeue();
            var originKey = $"{origin[0]},{origin[1]}";
            if (targetDistance.ContainsKey(originKey)) {
                return origin[2] + targetDistance[originKey];
            }
            
            var target = targetQueue.Dequeue();
            var targetKey = $"{target[0]},{target[1]}";
            if (originDistance.ContainsKey(targetKey)) {
                return target[2] + originDistance[targetKey];
            }
            
            foreach (var offset in offsets) {
                var nextOrigin = new int[] {origin[0] + offset[0], origin[1] + offset[1], origin[2] + 1};
                var nextOriginKey = $"{nextOrigin[0]},{nextOrigin[1]}";
                if (!originDistance.ContainsKey(nextOriginKey)) {
                    originQueue.Enqueue(nextOrigin);
                    originDistance[nextOriginKey] = nextOrigin[2];
                }
                
                var nextTarget = new int[] {target[0] + offset[0], target[1] + offset[1], target[2] + 1};
                var nextTargetKey = $"{nextTarget[0]},{nextTarget[1]}";
                if (!targetDistance.ContainsKey(nextTargetKey)) {
                    targetQueue.Enqueue(nextTarget);
                    targetDistance[nextTargetKey] = nextTarget[2];
                }
            }
        }
    }
}

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

Задача: 146. LRU Cache
Сложность: medium

Реализуйте класс LRUCache:
LRUCache(int capacity) - инициализирует LRU-кэш с положительным размером capacity.
int get(int key) - возвращает значение по ключу, если ключ существует, в противном случае возвращает -1.
void put(int key, int value) - обновляет значение по ключу, если ключ существует. В противном случае добавляет пару ключ-значение в кэш. Если количество ключей превышает установленную емкость после этой операции, удаляет наименее недавно использованный ключ.

Функции get и put должны выполняться за среднее время O(1).

Пример:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

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

1⃣Метод добавления узла в конец связного списка (add):
Получите текущий узел в конце списка, это "реальный" хвост: tail.prev, обозначим его как previousEnd.
Вставьте node после previousEnd, установив previousEnd.next = node.
Настройте указатели узла: node.prev = previousEnd и node.next = tail.
Обновите tail.prev = node, делая node новым "реальным" хвостом списка.

2⃣Метод удаления узла из связного списка (remove):
Узел node должен быть удален из списка. Для этого определите узлы nextNode = node.next и prevNode = node.prev.
Чтобы удалить node, переназначьте prevNode.next = nextNode и nextNode.prev = prevNode, эффективно исключая node из списка.
Это превратит, например, последовательность A <-> B <-> C в A <-> C, где prevNode = A и nextNode = C.

3⃣Методы get и put:
get(int key): Проверьте, существует ли ключ в хэш-карте. Если нет, верните -1. Иначе, получите узел, связанный с ключом, переместите его в конец списка с помощью remove(node) и add(node). Верните node.val.
put(int key, int value): Если ключ уже существует, найдите соответствующий узел и удалите его методом remove. Создайте новый узел с key и value, добавьте его в хэш-карту и в конец списка методом add(node). Если размер кэша превышает установленную емкость после добавления, удалите самый редко используемый узел (который находится в голове списка после фиктивного узла head), затем удалите соответствующий ключ из хэш-карты.

😎 Решение:

public class Node {
    public int key { get; set; }
    public int value { get; set; }
    public Node next { get; set; }
    public Node prev { get; set; }

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

public class LRUCache {
    private int capacity;
    private Dictionary<int, Node> dic;
    private Node head;
    private Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dic = new Dictionary<int, Node>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    public int Get(int key) {
        if (!dic.ContainsKey(key)) {
            return -1;
        }

        Node node = dic[key];
        Remove(node);
        Add(node);
        return node.value;
    }

    public void Put(int key, int value) {
        if (dic.ContainsKey(key)) {
            Node oldNode = dic[key];
            Remove(oldNode);
        }

        Node node = new Node(key, value);
        dic[key] = node;
        Add(node);
        if (dic.Count > capacity) {
            Node nodeToDelete = head.next;
            Remove(nodeToDelete);
            dic.Remove(nodeToDelete.key);
        }
    }

    private void Add(Node node) {
        Node previousEnd = tail.prev;
        previousEnd.next = node;
        node.prev = previousEnd;
        node.next = tail;
        tail.prev = node;
    }

    private void Remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

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

Задача: 957. Prison Cells After N Days
Сложность: medium

Есть 8 тюремных камер в ряду, и каждая камера либо занята, либо пуста.
Каждый день статус камеры, занята она или пуста, меняется по следующим правилам:
Если у камеры два соседних соседа, которые оба заняты или оба пусты, то камера становится занятой.
В противном случае, она становится пустой.
Учтите, что поскольку тюрьма — это ряд, у первой и последней камер в ряду не может быть двух соседних соседей.

Вам дан целочисленный массив cells, где cells[i] == 1, если i-я камера занята, и cells[i] == 0, если i-я камера пуста, и вам дано целое число n.
Верните состояние тюрьмы после n дней (т.е. после n таких изменений, описанных выше).

Пример:

Input: cells = [0,1,0,1,1,0,0,1], n = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

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

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

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

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

😎 Решение:

public class Solution {
    protected int CellsToBitmap(int[] cells) {
        int stateBitmap = 0;
        foreach (int cell in cells) {
            stateBitmap = (stateBitmap << 1) | cell;
        }
        return stateBitmap;
    }

    protected int[] NextDay(int[] cells) {
        int[] newCells = new int[cells.Length];
        for (int i = 1; i < cells.Length - 1; ++i) {
            newCells[i] = (cells[i - 1] == cells[i + 1]) ? 1 : 0;
        }
        return newCells;
    }

    public int[] PrisonAfterNDays(int[] cells, int N) {
        Dictionary<int, int> seen = new Dictionary<int, int>();
        bool isFastForwarded = false;

        while (N > 0) {
            if (!isFastForwarded) {
                int stateBitmap = CellsToBitmap(cells);
                if (seen.ContainsKey(stateBitmap)) {
                    N %= seen[stateBitmap] - N;
                    isFastForwarded = true;
                } else {
                    seen[stateBitmap] = N;
                }
            }

            if (N > 0) {
                N--;
                cells = NextDay(cells);
            }
        }
        return cells;
    }
}

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