Задача: 1337. The K Weakest Rows in a Matrix
Сложность: easy

Вам дана бинарная матрица размером m x n mat, состоящая из 1 (представляющих солдат) и 0 (представляющих гражданских лиц). Солдаты расположены перед гражданскими лицами. То есть, все 1 будут расположены слева от всех 0 в каждой строке.

Строка i слабее строки j, если выполнено одно из следующих условий:

Количество солдат в строке i меньше, чем в строке j.
Обе строки имеют одинаковое количество солдат, но i < j.
Верните индексы k самых слабых строк в матрице, упорядоченных от самой слабой к самой сильной.

Пример:

Input: mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
Output: [2,0,3]
Explanation: 
The number of soldiers in each row is: 
- Row 0: 2 
- Row 1: 4 
- Row 2: 1 
- Row 3: 2 
- Row 4: 5 
The rows ordered from weakest to strongest are [2,0,3,1,4].

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

1⃣Вычислите силу каждой строки матрицы и поместите пары сила/индекс в массив. Для каждой строки подсчитайте количество единиц (солдат) до первой нуля (гражданского), чтобы определить силу строки.

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

3⃣Извлеките первые k индексов из отсортированного массива и верните их. Эти индексы будут соответствовать k самым слабым строкам в порядке от самой слабой к самой сильной.

😎 Решение:

public class Solution {
    public int[] KWeakestRows(int[][] mat, int k) {
        int m = mat.Length;
        int n = mat[0].Length;

        var pairs = new List<(int strength, int index)>();

        for (int i = 0; i < m; i++) {
            int strength = 0;
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) break;
                strength++;
            }
            pairs.Add((strength, i));
        }

        pairs.Sort((a, b) => {
            if (a.strength == b.strength) return a.index - b.index;
            return a.strength - b.strength;
        });

        int[] indexes = new int[k];
        for (int i = 0; i < k; i++) {
            indexes[i] = pairs[i].index;
        }
        return indexes;
    }
}

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

Задача: 32. Longest Valid Parentheses
Сложность: hard

Дана строка, содержащая только символы '(' и ')'. Верните длину самой длинной подстроки с корректными (правильно сформированными) скобками.

Пример:

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

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

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

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

3⃣Отслеживать максимальную длину валидной последовательности.

😎 Решение:

public class Solution {
    public int LongestValidParentheses(string s) {
        Stack<int> stack = new Stack<int>();
        stack.Push(-1);
        int maxLen = 0;

        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '(') {
                stack.Push(i);
            } else {
                stack.Pop();
                if (stack.Count == 0) {
                    stack.Push(i);
                } else {
                    maxLen = Math.Max(maxLen, i - stack.Peek());
                }
            }
        }

        return maxLen;
    }
}

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

На easyoffer 2.0 появится:
База тестовых заданий

🟠Тестовые задания для разных грейдов
🟠Фильтрация тестовых заданий по технологиям и компаниям

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

В течение 1-2 дней я объявлю о краудфандинг кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки и смогут попасть на закрытое бета-тестирование. А первые 150 донатеров получать особо-выгодную цену и бонус.

🚀 Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Задача: 56. Merge Intervals
Сложность: medium

Дан массив интервалов intervals, где intervals[i] = [start_i, end_i]. Нужно объединить все перекрывающиеся интервалы и вернуть массив неперекрывающихся интервалов.

Пример:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]  
Output: [[1,6],[8,10],[15,18]]  
Explanation: Так как `[1,3]` и `[2,6]` пересекаются, объединяем их в `[1,6]`.  

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

1⃣Отсортировать интервалы по start.

2⃣Использовать List<int[]> merged, добавляя в него первый интервал.

3⃣Пройтись по остальным интервалам:
- Если current.start <= lastMerged.end, объединить интервалы.
- Иначе добавить current в merged.

4⃣Вернуть merged как int[][].

😎 Решение:

public class Solution {
    public int[][] Merge(int[][] intervals) {
        if (intervals.Length == 0) return new int[0][];

        Array.Sort(intervals, (a, b) => a[0] - b[0]);
        List<int[]> merged = new List<int[]>();

        foreach (var interval in intervals) {
            if (merged.Count == 0 || merged[^1][1] < interval[0]) {
                merged.Add(interval);
            } else {
                merged[^1][1] = Math.Max(merged[^1][1], interval[1]);
            }
        }

        return merged.ToArray();
    }
}

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

Задача: 687. Longest Univalue Path
Сложность: medium

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

Длина пути между двумя узлами представлена количеством рёбер между ними.

Пример:

Input: root = [5,4,5,1,1,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 5).

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

1⃣Определить рекурсивную функцию solve(), принимающую текущий узел root и значение родительского узла parent. Если root равен NULL, вернуть 0. Рекурсивно вызвать solve() для левого и правого дочернего узлов, передав значение текущего узла как значение родительского узла.

2⃣Обновить переменную ans, если сумма значений для левого и правого узлов больше текущего значения ans. Если значение текущего узла равно значению родительского узла, вернуть max(left, right) + 1, иначе вернуть 0.

3⃣Вызвать solve() с корневым узлом и значением родительского узла -1. Вернуть максимальную длину пути ans..

😎 Решение:

public class Solution {
    private int ans = 0;

    private int Solve(TreeNode root, int parent) {
        if (root == null) {
            return 0;
        }

        int left = Solve(root.left, root.val);
        int right = Solve(root.right, root.val);
        
        ans = Math.Max(ans, left + right);
        
        return root.val == parent ? Math.Max(left, right) + 1 : 0;
    }

    public int LongestUnivaluePath(TreeNode root) {
        Solve(root, -1);
        return ans;
    }
}

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

Задача: 991. Broken Calculator
Сложность: medium

Имеется неисправный калькулятор, на экране которого изначально отображается целое число startValue. За одну операцию можно:

Умножить число на экране на 2, или
Вычесть 1 из числа на экране.
Даны два целых числа startValue и target. Верните минимальное количество операций, необходимых для отображения target на калькуляторе.

Пример:

Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

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

1⃣Обратный путь:
Если target больше startValue, то попытайтесь уменьшить target, чтобы привести его к startValue.
Если target четный, разделите его на 2, иначе прибавьте 1.

2⃣Подсчет операций:
Повторяйте шаги, пока target не станет меньше или равен startValue.
После этого вычитайте из startValue оставшееся значение target.

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

😎 Решение:

public class Solution {
    public int BrokenCalc(int startValue, int target) {
        int operations = 0;
        
        while (target > startValue) {
            operations++;
            if (target % 2 == 0) {
                target /= 2;
            } else {
                target += 1;
            }
        }
        
        return operations + (startValue - target);
    }
}

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

Задача: 1424. Diagonal Traverse II
Сложность: medium

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

Пример:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

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

1⃣Инициализируйте очередь с (0, 0) и список ответов ans.

2⃣Пока очередь не пуста:
Извлеките (row, col) из очереди.
Добавьте nums[row][col] в ans.
Если col == 0 и row + 1 в пределах массива, добавьте (row + 1, col) в очередь.
Если col + 1 в пределах текущей строки, добавьте (row, col + 1) в очередь.

3⃣Верните ans.

😎 Решение:

public class Solution {
    public int[] FindDiagonalOrder(IList<IList<int>> nums) {
        var queue = new Queue<(int row, int col)>();
        queue.Enqueue((0, 0));
        var ans = new List<int>();
        
        while (queue.Count > 0) {
            var (row, col) = queue.Dequeue();
            ans.Add(nums[row][col]);
            
            if (col == 0 && row + 1 < nums.Count) {
                queue.Enqueue((row + 1, col));
            }
            
            if (col + 1 < nums[row].Count) {
                queue.Enqueue((row, col + 1));
            }
        }
        
        return ans.ToArray();
    }
}

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

Задача: 1326. Minimum Number of Taps to Open to Water a Garden
Сложность: hard

Есть одномерный сад на оси x. Сад начинается в точке 0 и заканчивается в точке n. (т.е. длина сада равна n).

В саду есть n + 1 кранов, расположенных в точках [0, 1, ..., n].

Даны целое число n и целочисленный массив ranges длиной n + 1, где ranges[i] (индексация начинается с 0) означает, что i-й кран может поливать область [i - ranges[i], i + ranges[i]], если он открыт.

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

Пример:

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]

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

1⃣Объявите массив dp размера n+1. Инициализируйте его значениями бесконечности (в коде используем большое число 10^9 для представления бесконечности). Установите dp[0] в 0 (базовый случай DP).

2⃣Итерируйтесь от i до n (через каждый кран слева направо). Рассчитайте самую левую позицию, достижимую текущим краном, как tap_start=max(0,i−ranges[i]). И самую правую позицию tap_end=min(n,i+ranges[i]).

3⃣Итерируйтесь через позиции j от tap_start до tap_end (в пределах досягаемости крана). Обновите dp[tap_end] значением dp[j]+1, если оно меньше. Если dp[n] остается бесконечным, значит, полить весь сад невозможно, и мы возвращаем −1. Верните dp[n].

😎 Решение:

public class Solution {
    public int MinTaps(int n, int[] ranges) {
        const int INF = int.MaxValue;
        int[] dp = new int[n + 1];
        Array.Fill(dp, INF);
        dp[0] = 0;
        
        for (int i = 0; i <= n; i++) {
            int tapStart = Math.Max(0, i - ranges[i]);
            int tapEnd = Math.Min(n, i + ranges[i]);
            
            for (int j = tapStart; j <= tapEnd; j++) {
                dp[tapEnd] = Math.Min(dp[tapEnd], dp[j] + 1);
            }
        }
        
        return dp[n] == INF ? -1 : dp[n];
    }
}

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

Задача: 1167. Minimum Cost to Connect Sticks
Сложность: medium

У вас есть несколько палочек с положительными целыми длинами. Эти длины даны в виде массива sticks, где sticks[i] — длина i-й палочки.

Вы можете соединить любые две палочки длиной x и y в одну палочку, заплатив стоимость x + y. Вы должны соединить все палочки, пока не останется только одна палочка.

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

Пример:

Input: sticks = [5]
Output: 0
Explanation: There is only one stick, so you don't need to do anything. The total cost is 0.

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

1⃣Всегда выбирайте две самые маленькие палочки для соединения и продолжайте делать это, пока не останется только одна палочка. Рассмотрим 4 палочки следующих длин: sticks=[a1, a2, a3, a4]. Попробуем соединить их слева направо. После первого соединения у нас будет: sticks=[(a1 + a2), a3, a4], стоимость=(a1 + a2). После второго соединения у нас будет: sticks=[(a1 + a2 + a3), a4], стоимость=(a1 + a2)+(a1 + a2 + a3). И, наконец, последняя палочка будет выглядеть так: sticks=[(a1 + a2 + a3 + a4)], стоимость=(a1 + a2)+(a1 + a2 + a3)+(a1 + a2 + a3 + a4).

2⃣Итоговая стоимость может быть переписана следующим образом: стоимость=(3a1 + 3a2 + 2a3 + a4). Как видим, палочки, которые соединяются первыми, включаются в итоговую стоимость больше, чем те, которые выбираются позже. Следовательно, оптимально сначала выбирать меньшие палочки, чтобы получить наименьшую стоимость.

3⃣Для выполнения следующих задач будет оптимальна структура данных min heap (которая обычно реализуется как PriorityQueue в большинстве языков): получить две самые маленькие палочки (stick1 и stick2) из массива; добавить одну палочку (stick1 + stick2) обратно в массив. Эта структура данных дает сложность O(logN) для обеих операций.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int ConnectSticks(int[] sticks) {
        int totalCost = 0;
        PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
        
        foreach (int stick in sticks) {
            pq.Enqueue(stick, stick);
        }
        
        while (pq.Count > 1) {
            int stick1 = pq.Dequeue();
            int stick2 = pq.Dequeue();
            int cost = stick1 + stick2;
            totalCost += cost;
            pq.Enqueue(cost, cost);
        }
        
        return totalCost;
    }
}

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

Задача: 1248. Count Number of Nice Subarrays
Сложность: medium

Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.

Пример:

Input: arr = [1,2]
Output: 2

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

1⃣Преобразуйте массив чисел nums, заменив все чётные числа на 0, а все нечётные числа на 1.

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

3⃣Подсчитайте количество таких подмассивов и верните этот результат.

😎 Решение:

public class Solution {
    public int NumberOfSubarrays(int[] nums, int k) {
        return AtMost(nums, k) - AtMost(nums, k - 1);
    }

    private int AtMost(int[] nums, int k) {
        int res = 0, left = 0, count = 0;
        for (int right = 0; right < nums.Length; right++) {
            if (nums[right] % 2 == 1) count++;
            while (count > k) {
                if (nums[left++] % 2 == 1) count--;
            }
            res += right - left + 1;
        }
        return res;
    }
}

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

Задача: 1146. Snapshot Array
Сложность: medium

Реализуйте SnapshotArray, который поддерживает следующий интерфейс:
SnapshotArray(int length) инициализирует структуру данных, похожую на массив, с заданной длиной. Изначально каждый элемент равен 0.
void set(index, val) устанавливает элемент с заданным индексом равным val.
int snap() делает снимок массива и возвращает snap_id: общее количество вызовов snap() минус 1.
int get(index, snap_id) возвращает значение на заданном индексе в момент, когда мы сделали снимок с указанным snap_id.

Пример:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

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

1⃣Инициализация: Для каждого элемента nums[i] в массиве создайте пустой список для хранения его исторических значений в формате [snap_id, value]. Инициализируйте каждый список, добавив первую запись [0, 0].

2⃣Метод set: Добавьте историческую запись [snap_id, value] в список записей historyRecords[index].

3⃣Методы snap и get:
Метод snap возвращает snap_id и увеличивает его на 1.
Метод get использует бинарный поиск, чтобы найти индекс последней вставки snap_id в данный снимок (целевой индекс будет snap_index - 1). Возвращает historyRecords[index][snap_index - 1][1].

😎 Решение:

public class SnapshotArray {
    private int snapId = 0;
    private List<SortedDictionary<int, int>> historyRecords;
    
    public SnapshotArray(int length) {
        historyRecords = new List<SortedDictionary<int, int>>(length);
        for (int i = 0; i < length; i++) {
            historyRecords.Add(new SortedDictionary<int, int> { { 0, 0 } });
        }
    }

    public void Set(int index, int val) {
        historyRecords[index][snapId] = val;
    }

    public int Snap() {
        return snapId++;
    }

    public int Get(int index, int snapId) {
        var record = historyRecords[index];
        while (snapId >= 0) {
            if (record.ContainsKey(snapId)) {
                return record[snapId];
            }
            snapId--;
        }
        return 0;
    }
}

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

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

😎 Решение:

public class Solution {
    public int[] NumsSameConsecDiff(int N, int K) {
        if (N == 1) return Enumerable.Range(0, 10).ToArray();
        
        var queue = new List<int>(Enumerable.Range(1, 9));
        for (int level = 1; level < N; ++level) {
            var nextQueue = new List<int>();
            foreach (int num in queue) {
                int tailDigit = num % 10;
                var nextDigits = new int[] { tailDigit + K, tailDigit - K };
                
                foreach (int nextDigit in nextDigits) {
                    if (nextDigit >= 0 && nextDigit < 10) {
                        nextQueue.Add(num * 10 + nextDigit);
                    }
                }
            }
            queue = nextQueue;
        }
        
        return queue.ToArray();
    }
}

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

Задача: 1037. Valid Boomerang
Сложность: easy

Если задан массив points, где points[i] = [xi, yi] представляет точку на плоскости X-Y, верните true, если эти точки являются бумерангом. Бумеранг - это набор из трех точек, которые отличаются друг от друга и не являются прямой линией.

Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

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

1⃣Проверка уникальности точек:
Убедитесь, что все три точки уникальны. Если любые две точки совпадают, то это не бумеранг.

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

3⃣Результат:
Если точки уникальны и не коллинеарны, верните true. В противном случае, верните false.

😎 Решение:

public class Solution {
    public bool IsBoomerang(int[][] points) {
        int x1 = points[0][0], y1 = points[0][1];
        int x2 = points[1][0], y2 = points[1][1];
        int x3 = points[2][0], y3 = points[2][1];
        return (x1 != x2 || y1 != y2) && 
               (x1 != x3 || y1 != y3) && 
               (x2 != x3 || y2 != y3) && 
               (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) != 0;
    }
}

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

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

Алиса и Боб поочередно играют в игру, причем Алиса начинает первой.

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

Кроме того, если игрок не может сделать ход, он/она проигрывает игру.

Дано положительное целое число n, верните true, если и только если Алиса выиграет игру, иначе верните false, предполагая, что оба игрока играют оптимально.

Пример:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

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

1⃣Функция dfs(remain) представляет собой проверку, должен ли текущий игрок выиграть при оставшихся remain камнях.

2⃣Для определения результата dfs(n) необходимо итерировать k от 0, чтобы проверить, существует ли такое k, что dfs(remain - k*k) == False. Чтобы предотвратить избыточные вычисления, используйте карту для хранения результатов функции dfs.

3⃣Не забудьте базовые случаи: dfs(0) == False и dfs(1) == True.

😎 Решение:

public class Solution {
    public bool WinnerSquareGame(int n) {
        Dictionary<int, bool> cache = new Dictionary<int, bool>();
        cache[0] = false;
        return Dfs(cache, n);
    }

    public bool Dfs(Dictionary<int, bool> cache, int remain) {
        if (cache.ContainsKey(remain)) {
            return cache[remain];
        }
        int sqrtRoot = (int) Math.Sqrt(remain);
        for (int i = 1; i <= sqrtRoot; ++i) {
            if (!Dfs(cache, remain - i * i)) {
                cache[remain] = true;
                return true;
            }
        }
        cache[remain] = false;
        return false;
    }
}

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

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

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