Задача: 920. Number of Music Playlists
Сложность: hard

В вашем плеере есть n разных песен. Во время путешествия вы хотите прослушать goal песен (не обязательно разных). Чтобы избежать скуки, вы создадите плейлист таким образом, чтобы: каждая песня играла хотя бы один раз. Песня может быть проиграна снова только в том случае, если было проиграно k других песен. Учитывая n, цель и k, верните количество возможных плейлистов, которые вы можете создать. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: n = 3, goal = 3, k = 1
Output: 6

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

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

2⃣Инициализировать dp[0][0] = 1, что означает, что существует один способ создать плейлист длины 0 с 0 песнями.
Заполнить массив dp, используя два случая:
Добавление новой песни, которая не была проиграна раньше: dp[i][j] += dp[i-1][j-1] * (n - j + 1)
Повторное проигрывание песни, если было проиграно k других песен: dp[i][j] += dp[i-1][j] * max(j - k, 0)

3⃣Ответ находится в dp[goal][n].

😎 Решение:

public class Solution {
    public int NumMusicPlaylists(int n, int goal, int k) {
        const int MOD = 1_000_000_007;
        long[,] dp = new long[goal + 1, n + 1];
        dp[0, 0] = 1;

        for (int i = 1; i <= goal; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i, j] = dp[i - 1, j - 1] * (n - j + 1) % MOD;
                if (j > k) {
                    dp[i, j] = (dp[i, j] + dp[i - 1, j] * (j - k) % MOD) % MOD;
                }
            }
        }

        return (int)dp[goal, n];
    }
}

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

Задача: 1249. Minimum Remove to Make Valid Parentheses
Сложность: medium

Дана строка s из '(' , ')' и строчных английских символов. Ваша задача - удалить минимальное количество скобок ( '(' или ')' в любых позициях), чтобы полученная строка со скобками была допустимой, и вернуть любую допустимую строку. Формально строка со скобками допустима тогда и только тогда, когда: она пустая, содержит только строчные символы, или может быть записана как AB (A, конкатенированная с B), где A и B - допустимые строки, или может быть записана как (A), где A - допустимая строка.

Пример:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"

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

1⃣Пройдите по строке s и сохраните индексы всех открывающих скобок '(' в стек. При встрече закрывающей скобки ')', удалите соответствующую открытую скобку из стека. Если в стеке нет соответствующей открывающей скобки, пометьте эту закрывающую скобку для удаления.

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

3⃣Создайте новую строку, удалив все помеченные скобки.

😎 Решение:

public class Solution {
    public string MinRemoveToMakeValid(string s) {
        var stack = new Stack<int>();
        var sb = new StringBuilder(s);
        for (int i = 0; i < sb.Length; i++) {
            if (sb[i] == '(') {
                stack.Push(i);
            } else if (sb[i] == ')') {
                if (stack.Count > 0) {
                    stack.Pop();
                } else {
                    sb[i] = '*';
                }
            }
        }
        while (stack.Count > 0) {
            sb[stack.Pop()] = '*';
        }
        return sb.ToString().Replace("*", "");
    }
}

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

Задача: 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⃣Если найден горный массив, обновите максимальную длину и переместите основание на конец текущего горного массива.

😎 Решение:

public class Solution {
    public int LongestMountain(int[] arr) {
        int n = arr.Length;
        int ans = 0;
        int baseIndex = 0;

        while (baseIndex < n) {
            int end = baseIndex;
            if (end + 1 < n && arr[end] < arr[end + 1]) {
                while (end + 1 < n && arr[end] < arr[end + 1]) {
                    end++;
                }
                if (end + 1 < n && arr[end] > arr[end + 1]) {
                    while (end + 1 < n && arr[end] > arr[end + 1]) {
                        end++;
                    }
                    ans = Math.Max(ans, end - baseIndex + 1);
                }
            }
            baseIndex = Math.Max(end, baseIndex + 1);
        }

        return ans;
    }
}

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

Задача: 1273. Delete Tree Nodes
Сложность: medium

Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве.

Пример:

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2

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

1⃣Постройте дерево из заданных узлов, значений и родителей.

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

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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int DeleteTreeNodes(int nodes, int[] parent, int[] value) {
        var tree = new Dictionary<int, List<int>>();
        for (int i = 0; i < nodes; i++) {
            if (!tree.ContainsKey(parent[i])) tree[parent[i]] = new List<int>();
            tree[parent[i]].Add(i);
        }

        (int, int) Dfs(int node) {
            int totalSum = value[node];
            int totalCount = 1;
            if (tree.ContainsKey(node)) {
                foreach (int child in tree[node]) {
                    var (childSum, childCount) = Dfs(child);
                    totalSum += childSum;
                    totalCount += childCount;
                }
            }
            return totalSum == 0 ? (0, 0) : (totalSum, totalCount);
        }

        return Dfs(0).Item2;
    }
}

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

Задача: 921. Minimum Add to Make Parentheses Valid
Сложность: medium

Строка со скобками допустима тогда и только тогда, когда: это пустая строка, ее можно записать как AB (A, совмещенное с B), где A и B - допустимые строки, или ее можно записать как (A), где A - допустимая строка. Вам дана строка s со скобками. За один ход вы можете вставить скобку в любую позицию строки. Например, если s = "()))", вы можете вставить открывающую скобку в виде "(()))" или закрывающую скобку в виде "())))". Верните минимальное количество ходов, необходимое для того, чтобы сделать s допустимой.

Пример:

Input: n = 3, goal = 3, k = 1
Output: 6

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

1⃣Инициализировать два счетчика open_needed и close_needed.

2⃣Пройти по строке s символ за символом:
Если текущий символ - открывающая скобка (, увеличьте open_needed.
Если текущий символ - закрывающая скобка ), проверьте:
Если open_needed больше 0, уменьшите open_needed.
Иначе увеличьте close_needed.

3⃣Суммируйте значения open_needed и close_needed, чтобы получить минимальное количество вставок.

😎 Решение:

public class Solution {
    public int MinAddToMakeValid(string s) {
        int openNeeded = 0;
        int closeNeeded = 0;
        
        foreach (char c in s) {
            if (c == '(') {
                openNeeded++;
            } else if (c == ')') {
                if (openNeeded > 0) {
                    openNeeded--;
                } else {
                    closeNeeded++;
                }
            }
        }
        
        return openNeeded + closeNeeded;
    }
}

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

Задача: 657. Robot Return to Origin
Сложность: easy

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

Вам дана строка moves, представляющая последовательность движений робота, где moves[i] представляет его i-ое движение. Допустимые движения: 'R' (вправо), 'L' (влево), 'U' (вверх) и 'D' (вниз).

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

Примечание: направление, в котором "смотрит" робот, не имеет значения. 'R' всегда будет перемещать робота на один шаг вправо, 'L' всегда будет перемещать его на один шаг влево и т.д. Также предполагается, что величина перемещения робота одинакова для каждого хода.

Пример:

Input: moves = "UD"
Output: true

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

1⃣Инициализация координат:
Начните с координат (0, 0).

2⃣Обработка движений:
Пройдите по строке moves и обновляйте координаты в зависимости от движения:
'R' увеличивает координату x на 1.
'L' уменьшает координату x на 1.
'U' увеличивает координату y на 1.
'D' уменьшает координату y на 1.

3⃣Проверка конечных координат:
Если после всех движений координаты снова равны (0, 0), верните true. В противном случае, верните false.

😎 Решение:

public class Solution {
    public bool JudgeCircle(string moves) {
        int x = 0, y = 0;
        foreach (char move in moves) {
            switch (move) {
                case 'R': x++; break;
                case 'L': x--; break;
                case 'U': y++; break;
                case 'D': y--; break;
            }
        }
        return x == 0 && y == 0;
    }
}

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

Задача: 909. Snakes and Ladders
Сложность: medium

Вам дана доска с целочисленной матрицей n x n, клетки которой помечены метками от 1 до n2 в стиле Бустрофедона, начиная с левого нижнего края доски (т.е. board[n - 1][0]) и чередуя направление в каждой строке. Вы начинаете на клетке 1 доски. В каждый ход, начиная с клетки curr, вы делаете следующее: выбираете клетку назначения next с меткой в диапазоне [curr + 1, min(curr + 6, n2)]. Этот выбор имитирует результат стандартного броска 6-гранного кубика: то есть всегда существует не более 6 мест назначения, независимо от размера доски. Если next имеет змейку или лестницу, вы должны двигаться к месту назначения этой змейки или лестницы. В противном случае вы переходите на следующий. Игра заканчивается, когда вы достигаете клетки n2. Клетка доски в строке r и столбце c имеет змейку или лестницу, если board[r][c] != -1. Местом назначения этой змейки или лестницы является доска[r][c]. В клетках 1 и n2 нет змейки или лестницы. Обратите внимание, что вы можете взять змейку или лестницу не более одного раза за ход. Если конечный пункт змейки или лестницы является началом другой змейки или лестницы, вы не ходите по последующей змейке или лестнице. Например, предположим, что доска имеет вид [[-1,4],[-1,3]], и на первом ходу ваш конечный квадрат - 2. Вы ходите по лестнице до квадрата 3, но не ходите по последующей лестнице до 4. Верните наименьшее количество ходов, необходимое для достижения квадрата n2. Если достичь квадрата невозможно, верните -1.

Пример:

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output: 4

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

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

2⃣Использовать BFS (поиск в ширину) для минимизации количества ходов до клетки n2.
В каждом ходе проверять клетки от curr + 1 до min(curr + 6, n2) и перемещаться по змейкам и лестницам, если они существуют.

3⃣Если достижение клетки n2 невозможно, вернуть -1.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int SnakesAndLadders(int[][] board) {
        int n = board.Length;

        int[] GetPos(int x) {
            int quot = (x - 1) / n;
            int rem = (x - 1) % n;
            int row = n - 1 - quot;
            int col = (row % 2 != n % 2) ? rem : n - 1 - rem;
            return new int[] { row, col };
        }

        var visited = new HashSet<int>();
        var queue = new Queue<int[]>();
        queue.Enqueue(new int[] { 1, 0 });

        while (queue.Count > 0) {
            var curr = queue.Dequeue();
            int pos = curr[0];
            int steps = curr[1];
            for (int i = 1; i <= 6; i++) {
                int nextPos = pos + i;
                if (nextPos > n * n) continue;
                var rc = GetPos(nextPos);
                int r = rc[0], c = rc[1];
                if (board[r][c] != -1) {
                    nextPos = board[r][c];
                }
                if (nextPos == n * n) {
                    return steps + 1;
                }
                if (!visited.Contains(nextPos)) {
                    visited.Add(nextPos);
                    queue.Enqueue(new int[] { nextPos, steps + 1 });
                }
            }
        }
        return -1;
    }
}

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

Задача: 1043. Partition Array for Maximum Sum
Сложность: medium

Если задан целочисленный массив arr, разбейте его на (смежные) подмассивы длины не более k. После разбиения значения каждого подмассива меняются так, чтобы стать максимальным значением этого подмассива. Верните наибольшую сумму заданного массива после разбиения. Тестовые примеры генерируются таким образом, чтобы ответ умещался в 32-битное целое число.

Пример:

Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84

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

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

2⃣Заполнение массива dp:
Проходим по массиву arr и для каждой позиции i пытаемся разбить подмассив длины до k и обновить dp[i] с максимальной возможной суммой.

3⃣Поддержание максимального значения в подмассиве:
Для каждого подмассива длины 1 до k, вычисляем максимальное значение в этом подмассиве и обновляем dp[i].

😎 Решение:

public class Solution {
    public int MaxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.Length;
        int[] dp = new int[n];
        
        for (int i = 0; i < n; i++) {
            int maxVal = 0;
            for (int j = 1; j <= k; j++) {
                if (i - j + 1 >= 0) {
                    maxVal = Math.Max(maxVal, arr[i - j + 1]);
                    if (i - j >= 0) {
                        dp[i] = Math.Max(dp[i], dp[i - j] + maxVal * j);
                    } else {
                        dp[i] = Math.Max(dp[i], maxVal * j);
                    }
                }
            }
        }
        
        return dp[n - 1];
    }
}

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

Задача: 1255. Maximum Score Words Formed by Letters
Сложность: hard

Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно.

Пример:

Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23

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

1⃣Создайте функцию для вычисления оценки слова.

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

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

😎 Решение:

public class Solution {
    public int MaxScoreWords(string[] words, char[] letters, int[] score) {
        Dictionary<char, int> letterCount = new Dictionary<char, int>();
        foreach (char ch in letters) {
            if (!letterCount.ContainsKey(ch)) {
                letterCount[ch] = 0;
            }
            letterCount[ch]++;
        }

        int WordScore(string word) {
            int total = 0;
            foreach (char ch in word) {
                total += score[ch - 'a'];
            }
            return total;
        }

        bool CanFormWord(string word, Dictionary<char, int> letterCount) {
            Dictionary<char, int> count = new Dictionary<char, int>();
            foreach (char ch in word) {
                if (!count.ContainsKey(ch)) {
                    count[ch] = 0;
                }
                count[ch]++;
                if (count[ch] > letterCount.GetValueOrDefault(ch, 0)) {
                    return false;
                }
            }
            return true;
        }

        int maxScore = 0;
        int n = words.Length;
        for (int i = 1; i < (1 << n); i++) {
            int currScore = 0;
            Dictionary<char, int> usedLetters = new Dictionary<char, int>();
            bool valid = true;
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    string word = words[j];
                    if (CanFormWord(word, letterCount)) {
                        currScore += WordScore(word);
                        foreach (char ch in word) {
                            if (!usedLetters.ContainsKey(ch)) {
                                usedLetters[ch] = 0;
                            }
                            usedLetters[ch]++;
                        }
                    } else {
                        valid = false;
                        break;
                    }
                }
            }
            if (valid) {
                maxScore = Math.Max(maxScore, currScore);
            }
        }

        return maxScore;
    }
}

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<int> CircularPermutation(int n, int start) {
        var gray = GrayCode(n);
        int startIndex = gray.IndexOf(start);
        var result = new List<int>();
        result.AddRange(gray.Skip(startIndex));
        result.AddRange(gray.Take(startIndex));
        return result;
    }

    private List<int> GrayCode(int n) {
        var result = new List<int>();
        int numElements = 1 << n;
        for (int i = 0; i < numElements; i++) {
            result.Add(i ^ (i >> 1));
        }
        return result;
    }
}

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

Задача: 1122. Relative Sort Array
Сложность: easy

Даны два массива arr1 и arr2, элементы arr2 уникальны, и все элементы arr2 также присутствуют в arr1.

Отсортируйте элементы arr1 таким образом, чтобы относительный порядок элементов в arr1 был таким же, как в arr2. Элементы, которые не встречаются в arr2, должны быть размещены в конце arr1 в порядке возрастания.

Пример:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

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

1⃣Инициализация и подсчёт:
Инициализируйте пустой массив result и массив remaining для хранения оставшихся элементов.
Создайте хеш-таблицу countMap для хранения количества вхождений каждого элемента из arr2 в arr1.

2⃣Заполнение countMap и remaining:
Пройдитесь по элементам arr1 и если элемент присутствует в countMap, увеличьте его счетчик. Если элемент не присутствует в arr2, добавьте его в remaining.

3⃣Формирование результирующего массива:
Пройдитесь по arr2 и добавьте элементы в result в соответствии с их количеством в countMap.
Отсортируйте массив remaining и добавьте его элементы в result.
Верните result в виде массива.

😎 Решение:

public class Solution {
    public int[] RelativeSortArray(int[] arr1, int[] arr2) {
        var countMap = new Dictionary<int, int>();
        var remaining = new List<int>();
        var result = new List<int>();

        foreach (var value in arr2) {
            countMap[value] = 0;
        }

        foreach (var value in arr1) {
            if (countMap.ContainsKey(value)) {
                countMap[value]++;
            } else {
                remaining.Add(value);
            }
        }

        remaining.Sort();

        foreach (var value in arr2) {
            for (int i = 0; i < countMap[value]; i++) {
                result.Add(value);
            }
        }

        result.AddRange(remaining);
        return result.ToArray();
    }
}

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

Задача: 33. Search in Rotated Sorted Array
Сложность: medium

Дан отсортированный массив nums, который мог быть повернут в неизвестном индексе. Необходимо найти индекс элемента target или вернуть -1, если его нет. Алгоритм должен работать за O(log n).

Пример:

Input: nums = [4,5,6,7,0,1,2], target = 0  
Output: 4  

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

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

2⃣Определить, в какой из двух отсортированных частей массива находится target.

3⃣Выполнить бинарный поиск в нужной части массива.

😎 Решение:

public class Solution {
    public int Search(int[] nums, int target) {
        int left = 0, right = nums.Length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) return mid;

            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }

        return -1;
    }
}

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

Задача: 1463. Cherry Pickup II
Сложность: hard

Дана матрица grid размером rows x cols, представляющая поле с вишнями, где grid[i][j] обозначает количество вишен, которые можно собрать с клетки (i, j).

У вас есть два робота, которые могут собирать вишни:
Робот №1 находится в левом верхнем углу (0, 0), а
Робот №2 находится в правом верхнем углу (0, cols - 1).

Верните максимальное количество собранных вишен с помощью обоих роботов, следуя приведённым ниже правилам:
Из клетки (i, j) роботы могут перемещаться в клетку (i + 1, j - 1), (i + 1, j) или (i + 1, j + 1).
Когда любой робот проходит через клетку, он подбирает все вишни, и клетка становится пустой.
Когда оба робота находятся в одной клетке, только один из них собирает вишни.
Оба робота не могут выходить за пределы матрицы в любой момент времени.
Оба робота должны достичь нижней строки в матрице grid.

Пример:

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

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

1⃣Определите трехмерный массив dp, где dp[row][col1][col2] представляет максимальное количество вишен, которые можно собрать, если робот 1 находится в (row, col1), а робот 2 находится в (row, col2).

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

3⃣Верните dp[0][0][n-1], что представляет максимальное количество вишен, которое можно собрать, начиная с верхнего левого и верхнего правого углов.

😎 Решение:

public class Solution {
    public int CherryPickup(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        int[,,] dp = new int[m, n, n];
        
        for (int row = m - 1; row >= 0; row--) {
            for (int col1 = 0; col1 < n; col1++) {
                for (int col2 = 0; col2 < n; col2++) {
                    int result = grid[row][col1];
                    if (col1 != col2) {
                        result += grid[row][col2];
                    }
                    if (row != m - 1) {
                        int maxCherries = 0;
                        for (int newCol1 = col1 - 1; newCol1 <= col1 + 1; newCol1++) {
                            for (int newCol2 = col2 - 1; newCol2 <= col2 + 1; newCol2++) {
                                if (newCol1 >= 0 && newCol1 < n && newCol2 >= 0 && newCol2 < n) {
                                    maxCherries = Math.Max(maxCherries, dp[row + 1, newCol1, newCol2]);
                                }
                            }
                        }
                        result += maxCherries;
                    }
                    dp[row, col1, col2] = result;
                }
            }
        }
        return dp[0, 0, n - 1];
    }
}

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

Задача: 1002. Find Common Characters
Сложность: easy

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

Пример:

Input: words = ["bella","label","roller"]
Output: ["e","l","l"]

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

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

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

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

😎 Решение:

public class Solution {
    public IList<string> CommonChars(string[] words) {
        int[] minFreq = new int[26];
        Array.Fill(minFreq, int.MaxValue);
        
        foreach (string word in words) {
            int[] freq = new int[26];
            foreach (char c in word) {
                freq[c - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                minFreq[i] = Math.Min(minFreq[i], freq[i]);
            }
        }
        
        IList<string> result = new List<string>();
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < minFreq[i]; j++) {
                result.Add(((char)('a' + i)).ToString());
            }
        }
        return result;
    }
}

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

Задача: 981. Time Based Key-Value Store
Сложность: medium

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

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

TimeMap() Инициализирует объект структуры данных.
void set(String key, String value, int timestamp) Сохраняет ключ key с значением value в заданное время timestamp.
String get(String key, int timestamp) Возвращает значение, такое что set был вызван ранее с timestamp_prev <= timestamp. Если таких значений несколько, возвращается значение, связанное с наибольшим timestamp_prev. Если значений нет, возвращается "".

Пример:

Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]

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

1⃣Создайте hashmap keyTimeMap, который хранит строку в качестве ключа и другой hashmap в качестве значения, как обсуждалось выше.

2⃣В функции set() сохраните значение в позиции timestamp в корзине ключа keyTimeMap, т.е. keyTimeMap[key][timestamp] = value.

3⃣В функции get() итерируйтесь по всем временам в порядке убывания от timestamp до 1. Для любого времени во время итерации, если существует значение в корзине ключа, верните это значение. В противном случае, в конце верните пустую строку.

😎 Решение:

public class Solution {
    public IList<int> PancakeSort(int[] A) {
        var ans = new List<int>();
        for (int valueToSort = A.Length; valueToSort > 0; valueToSort--) {
            int index = Find(A, valueToSort);
            if (index == valueToSort - 1) {
                continue;
            }
            if (index != 0) {
                ans.Add(index + 1);
                Flip(A, index + 1);
            }
            ans.Add(valueToSort);
            Flip(A, valueToSort);
        }
        return ans;
    }

    protected void Flip(int[] sublist, int k) {
        int i = 0;
        while (i < k / 2) {
            int temp = sublist[i];
            sublist[i] = sublist[k - i - 1];
            sublist[k - i - 1] = temp;
            i += 1;
        }
    }

    protected int Find(int[] a, int target) {
        for (int i = 0; i < a.Length; i++) {
            if (a[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

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

Задача: 1004. Max Consecutive Ones III
Сложность: medium

Если задан двоичный массив nums и целое число k, верните максимальное количество последовательных 1 в массиве, если можно перевернуть не более k 0.

Пример:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6

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

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

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

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

😎 Решение:

public class Solution {
    public int LongestOnes(int[] nums, int k) {
        int left = 0, maxOnes = 0, zeroCount = 0;

        for (int right = 0; right < nums.Length; right++) {
            if (nums[right] == 0) {
                zeroCount++;
            }

            while (zeroCount > k) {
                if (nums[left] == 0) {
                    zeroCount--;
                }
                left++;
            }

            maxOnes = Math.Max(maxOnes, right - left + 1);
        }

        return maxOnes;
    }
}

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

Задача: 273. Integer to English Words
Сложность: hard

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

Пример:

Input: num = 123
Output: "One Hundred Twenty Three"

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

1⃣Обработка чисел до 20 и кратных 10 до 90:
Создать массивы или словари для чисел от 1 до 19 и для кратных 10 от 20 до 90.
Если число попадает в эти диапазоны, сразу вернуть соответствующее словесное представление.

2⃣Обработка сотен, тысяч, миллионов и миллиардов:
Разделить число на группы по три цифры (единицы, тысячи, миллионы, миллиарды).
Для каждой группы сформировать словесное представление с использованием рекурсивной функции для чисел от 1 до 999.

3⃣Формирование окончательного результата:
Собрать словесное представление всех групп, добавив соответствующие суффиксы (тысячи, миллионы, миллиарды).
Соединить все части в одну строку, удалив лишние пробелы.

😎 Решение:

public class Solution {
    private string[] belowTwenty = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private string[] tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    private string[] thousands = {"", "Thousand", "Million", "Billion"};

    public string NumberToWords(int num) {
        if (num == 0) return "Zero";
        int i = 0;
        string result = "";
        
        while (num > 0) {
            if (num % 1000 != 0) {
                result = Helper(num % 1000) + thousands[i] + " " + result;
            }
            num /= 1000;
            i++;
        }
        return result.Trim();
    }

    private string Helper(int num) {
        if (num == 0) return "";
        else if (num < 20) return belowTwenty[num] + " ";
        else if (num < 100) return tens[num / 10] + " " + Helper(num % 10);
        else return belowTwenty[num / 100] + " Hundred " + Helper(num % 100);
    }
}

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

Задача: 1279. Traffic Light Controlled Intersection
Сложность: easy

Здесь есть пересечение двух дорог. Первая дорога - это дорога A, по которой автомобили движутся с севера на юг в направлении 1 и с юга на север в направлении 2. Вторая дорога - дорога B, по которой машины едут с запада на восток в направлении 3 и с востока на запад в направлении 4. На каждой дороге перед перекрестком есть светофор. Зеленый означает, что автомобили могут пересекать перекресток в обоих направлениях. Красный означает, что автомобили в обоих направлениях не могут пересекать перекресток и должны ждать, пока загорится зеленый свет. Светофор не может гореть зеленым одновременно на обеих дорогах. Это значит, что когда на дороге А горит зеленый свет, на дороге Б он красный, а когда на дороге Б горит зеленый свет, на дороге А он красный.
Изначально на дороге A горит зеленый сигнал светофора, а на дороге B - красный. Когда на одной дороге горит зеленый свет, все автомобили могут пересекать перекресток в обоих направлениях, пока на другой дороге не загорится зеленый.Два автомобиля, движущиеся по разным дорогам, не должны пересекать перекресток одновременно. Разработайте систему управления светофором на этом перекрестке без тупиков. Реализуйте функцию void carArrived(carId, roadId, direction, turnGreen, crossCar), где: carId - идентификатор автомобиля, который приехал. roadId - идентификатор дороги, по которой едет автомобиль.
direction - направление движения автомобиля. turnGreen - функция, которую можно вызвать, чтобы переключить светофор на зеленый свет на текущей дороге. crossCar - функция, которую можно вызвать, чтобы позволить текущему автомобилю пересечь перекресток. Ваш ответ считается правильным, если он позволяет избежать тупика на перекрестке.Переключение светофора на зеленый свет на дороге, где он уже был зеленым, считается неправильным ответом.

Пример:

Input: cars = [1,2,3,4,5], directions = [2,4,3,3,1], arrivalTimes = [10,20,30,40,40]
Output: [
"Car 1 Has Passed Road A In Direction 2",    // Traffic light on road A is green, car 1 can cross the intersection.
"Traffic Light On Road B Is Green",          // Car 2 requests green light for road B.
"Car 2 Has Passed Road B In Direction 4",    // Car 2 crosses as the light is green on road B now.
"Car 3 Has Passed Road B In Direction 3",    // Car 3 crosses as the light is green on road B now.
"Traffic Light On Road A Is Green",          // Car 5 requests green light for road A.
"Car 5 Has Passed Road A In Direction 1",    // Car 5 crosses as the light is green on road A now.
"Traffic Light On Road B Is Green",          // Car 4 requests green light for road B. Car 4 blocked until car 5 crosses and then traffic light is green on road B.
"Car 4 Has Passed Road B In Direction 3"     // Car 4 crosses as the light is green on road B now.
]

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

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

2⃣Если на дороге, по которой едет автомобиль, красный свет, вызываем функцию turnGreen, чтобы переключить свет на зеленый, и затем вызываем функцию crossCar.

3⃣Обеспечиваем, что функции turnGreen и crossCar вызываются атомарно для предотвращения гонок и тупиков

😎 Решение:

using System;
using System.Threading;

public class TrafficLight {
    private int greenRoad = 1;
    private readonly object lockObj = new object();

    public void CarArrived(
        int carId,
        int roadId,
        int direction,
        Action turnGreen,
        Action crossCar
    ) {
        lock (lockObj) {
            if (greenRoad != roadId) {
                turnGreen();
                greenRoad = roadId;
            }
            crossCar();
        }
    }
}

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