Задача: 716. Max Stack
Сложность: hard

Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова.

Пример:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

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

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

2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека.

3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно.

😎 Решение:

public class MaxStack {

    private Stack<int> stack;
    private Stack<int> maxStack;

    public MaxStack() {
        stack = new Stack<int>();
        maxStack = new Stack<int>();
    }

    public void Push(int x) {
        stack.Push(x);
        if (maxStack.Count == 0 || x >= maxStack.Peek()) {
            maxStack.Push(x);
        }
    }

    public int Pop() {
        int x = stack.Pop();
        if (x == maxStack.Peek()) {
            maxStack.Pop();
        }
        return x;
    }

    public int Top() {
        return stack.Peek();
    }

    public int PeekMax() {
        return maxStack.Peek();
    }

    public int PopMax() {
        int maxVal = maxStack.Pop();
        Stack<int> buffer = new Stack<int>();
        while (stack.Peek() != maxVal) {
            buffer.Push(stack.Pop());
        }
        stack.Pop();
        while (buffer.Count > 0) {
            Push(buffer.Pop());
        }
        return maxVal;
    }
}

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

public class Solution {
    public int[] RunningSum(int[] nums) {
        int[] result = new int[nums.Length];
        result[0] = nums[0];
        for (int i = 1; i < nums.Length; i++) {
            result[i] = result[i - 1] + nums[i];
        }
        return result;
    }
}

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

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

Для целочисленного массива nums, поверните массив вправо на k шагов, где k — неотрицательное число.

Пример:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

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

1⃣Создаем дополнительный массив, в который будем помещать каждый элемент исходного массива на его новую позицию. Элемент на позиции i в исходном массиве будет размещен на индексе (i+k) % длина массива.

2⃣Копируем элементы из нового массива в исходный массив, сохраняя новый порядок элементов.

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

😎 Решение:

public class Solution {
    public void Rotate(int[] nums, int k) {
        int n = nums.Length;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[(i + k) % n] = nums[i];
        }
        for (int i = 0; i < n; i++) {
            nums[i] = a[i];
        }
    }
}

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

Задача: 360. Sort Transformed Array
Сложность: medium

Дан отсортированный массив целых чисел nums и три целых числа a, b и c. Примените квадратичную функцию вида f(x) = ax^2 + bx + c к каждому элементу nums[i] в массиве и верните массив в отсортированном порядке.

Пример:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

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

1⃣Преобразование и сортировка
Преобразуем каждый элемент массива nums по квадратичной функции f(x) = ax^2 + bx + c и сохраняем результаты в массив transformed. Используем алгоритм поразрядной сортировки для сортировки массива transformed.

2⃣Поразрядная сортировка
Находим максимальное значение по модулю в массиве для определения количества цифр. Применяем поразрядную сортировку к массиву transformed.

3⃣Сортировка по цифре
Для каждой цифры (разряда) используем подсчет для сортировки массива.

😎 Решение:

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

public class Solution {
    public int[] SortTransformedArray(int[] nums, int a, int b, int c) {
        int[] transformed = nums.Select(x => a * x * x + b * x + c).ToArray();
        RadixSort(transformed);
        return transformed;
    }

    private void RadixSort(int[] array) {
        int maxElement = array.Select(x => Math.Abs(x)).Max();
        int placeValue = 1;

        while (maxElement / placeValue > 0) {
            CountingSortByDigit(array, placeValue);
            placeValue *= 10;
        }

        var negatives = array.Where(x => x < 0).OrderBy(x => x).ToArray();
        var positives = array.Where(x => x >= 0).OrderBy(x => x).ToArray();
        Array.Copy(negatives, 0, array, 0, negatives.Length);
        Array.Copy(positives, 0, array, negatives.Length, positives.Length);
    }

    private void CountingSortByDigit(int[] array, int placeValue) {
        int n = array.Length;
        int[] output = new int[n];
        int[] count = new int[10];

        foreach (int num in array) {
            int digit = (Math.Abs(num) / placeValue) % 10;
            count[digit]++;
        }

        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        for (int i = n - 1; i >= 0; i--) {
            int num = array[i];
            int digit = (Math.Abs(num) / placeValue) % 10;
            output[count[digit] - 1] = num;
            count[digit]--;
        }

        for (int i = 0; i < n; i++) {
            array[i] = output[i];
        }
    }
}

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int LongestStrChain(string[] words) {
        Array.Sort(words, (a, b) => a.Length - b.Length);
        var dp = new Dictionary<string, int>();
        int longestChain = 1;
        
        foreach (var word in words) {
            dp[word] = 1;
            for (int i = 0; i < word.Length; i++) {
                string predecessor = word.Substring(0, i) + word.Substring(i + 1);
                if (dp.ContainsKey(predecessor)) {
                    dp[word] = Math.Max(dp[word], dp[predecessor] + 1);
                }
            }
            longestChain = Math.Max(longestChain, dp[word]);
        }
        
        return longestChain;
    }
}

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

Задача: 724. Find Pivot Index
Сложность: easy

Если задан массив целых чисел nums, вычислите поворотный индекс этого массива. Поворотный индекс - это индекс, при котором сумма всех чисел строго слева от индекса равна сумме всех чисел строго справа от индекса. Если индекс находится на левом краю массива, то сумма слева равна 0, так как слева нет элементов. Это относится и к правому краю массива. Возвращается самый левый поворотный индекс. Если такого индекса не существует, возвращается -1.

Пример:

Input: nums = [1,7,3,6,5,6]
Output: 3

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

1⃣Вычислите сумму всех элементов массива.

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

3⃣Если текущий индекс удовлетворяет условию, верните его; если нет, продолжайте проверку. Если такой индекс не найден, верните -1.

😎 Решение:

public class Solution {
    public int PivotIndex(int[] nums) {
        int totalSum = 0;
        foreach (int num in nums) {
            totalSum += num;
        }
        int leftSum = 0;
        for (int i = 0; i < nums.Length; i++) {
            if (leftSum == totalSum - leftSum - nums[i]) {
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }
}

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

Задача: 1360. Number of Days Between Two Dates
Сложность: easy

Напишите программу для подсчета количества дней между двумя датами.

Даты даны в виде строк в формате YYYY-MM-DD, как показано в примерах.

Пример:

Input: date1 = "2019-06-29", date2 = "2019-06-30"
Output: 1

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

1⃣Преобразование строк в даты:
Используйте встроенные функции для преобразования строковых представлений дат в объекты дат.

2⃣Вычисление разницы в днях:
Вычислите разницу между двумя объектами дат в днях.

3⃣Возвращение результата:
Верните абсолютное значение разницы в днях для получения положительного числа.

😎 Решение:

using System;

public class Solution {
    public int DaysBetweenDates(string date1, string date2) {
        DateTime d1 = DateTime.Parse(date1);
        DateTime d2 = DateTime.Parse(date2);
        return Math.Abs((d2 - d1).Days);
    }
}

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

Задача: 541. Reverse String II
Сложность: easy

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

Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть.

Пример:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

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

1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее.

2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут.

3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--.

😎 Решение:

class Solution {
    public string ReverseStr(string s, int k) {
        char[] a = s.ToCharArray();
        for (int start = 0; start < a.Length; start += 2 * k) {
            int i = start, j = Math.Min(start + k - 1, a.Length - 1);
            while (i < j) {
                char tmp = a[i];
                a[i++] = a[j];
                a[j--] = tmp;
            }
        }
        return new string(a);
    }
}

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

public class Solution {
    public string ReverseVowels(string s) {
        HashSet<char> vowels = new HashSet<char>{'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
        char[] chars = s.ToCharArray();
        int left = 0, right = s.Length - 1;
        
        while (left < right) {
            if (!vowels.Contains(chars[left])) {
                left++;
            } else if (!vowels.Contains(chars[right])) {
                right--;
            } else {
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
                left++;
                right--;
            }
        }
        
        return new string(chars);
    }
}

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

Задача: 477. Total Hamming Distance
Сложность: medium

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

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

Пример:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

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

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

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

3⃣Суммируем все Хэмминговы расстояния для всех пар, чтобы получить общую сумму Хэмминговых расстояний.

😎 Решение:

public class Solution {
    public int TotalHammingDistance(int[] nums) {
        int ans = 0;
        
        if (nums.Length == 0) {
            return ans;
        }
        
        for (int i = 0; i < nums.Length - 1; i++) {
            for (int j = i + 1; j < nums.Length; j++) {
                ans += CountBits(nums[i] ^ nums[j]);
            }
        }
        
        return ans;
    }

    private int CountBits(int n) {
        int count = 0;
        while (n != 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
}

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

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

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

Задача: 815. Bus Routes
Сложность: hard

Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно.

Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно.
Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах.

Верните наименьшее количество автобусов, которые вам нужно взять, чтобы доехать от source до target. Верните -1, если это невозможно.

Пример:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

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

1⃣Верните 0, если source и target совпадают. Инициализируйте пустую карту adjList, чтобы хранить ребра, где ключ - это автобусная остановка, а значение - список целых чисел, обозначающих индексы маршрутов, которые имеют эту остановку. Инициализируйте пустую очередь q и неупорядоченное множество vis, чтобы отслеживать посещенные маршруты. Вставьте начальные маршруты в очередь q и отметьте их посещенными в vis.

2⃣Итерация по очереди, пока она не пуста: извлеките маршрут из очереди, итерируйтесь по остановкам в маршруте. Если остановка равна target, верните busCount. В противном случае, итерируйтесь по маршрутам для этой остановки в карте adjList, добавьте непосещенные маршруты в очередь и отметьте их посещенными.

3⃣Верните -1 после завершения обхода в ширину (BFS).

😎 Решение:

public class Solution {
    public int NumBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) return 0;

        var adjList = new Dictionary<int, List<int>>();
        for (int route = 0; route < routes.Length; route++) {
            foreach (int stop in routes[route]) {
                if (!adjList.ContainsKey(stop)) {
                    adjList[stop] = new List<int>();
                }
                adjList[stop].Add(route);
            }
        }

        var q = new Queue<int>();
        var vis = new HashSet<int>();
        foreach (int route in adjList.GetValueOrDefault(source, new List<int>())) {
            q.Enqueue(route);
            vis.Add(route);
        }

        int busCount = 1;
        while (q.Count > 0) {
            int size = q.Count;
            for (int i = 0; i < size; i++) {
                int route = q.Dequeue();
                foreach (int stop in routes[route]) {
                    if (stop == target) return busCount;
                    foreach (int nextRoute in adjList.GetValueOrDefault(stop, new List<int>())) {
                        if (!vis.Contains(nextRoute)) {
                            vis.Add(nextRoute);
                            q.Enqueue(nextRoute);
                        }
                    }
                }
            }
            busCount++;
        }
        return -1;
    }
}

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

Задача: 42. Trapping Rain Water
Сложность: hard

Дан массив height, где height[i] представляет высоту столбца. Нужно вычислить, сколько воды может удержаться после дождя.

Пример:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]  
Output: 6  

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

1⃣Создать массив left_max, где left_max[i] — максимальная высота слева до i.

2⃣Создать массив right_max, где right_max[i] — максимальная высота справа до i.

3⃣Для каждого i, вычислить возможный объем воды как min(left_max[i], right_max[i]) - height[i] и суммировать.

😎 Решение:

public class Solution {
    public int Trap(int[] height) {
        if (height.Length == 0) return 0;

        int size = height.Length, ans = 0;
        int[] left_max = new int[size];
        int[] right_max = new int[size];

        left_max[0] = height[0];
        for (int i = 1; i < size; i++) {
            left_max[i] = Math.Max(height[i], left_max[i - 1]);
        }

        right_max[size - 1] = height[size - 1];
        for (int i = size - 2; i >= 0; i--) {
            right_max[i] = Math.Max(height[i], right_max[i + 1]);
        }

        for (int i = 1; i < size - 1; i++) {
            ans += Math.Min(left_max[i], right_max[i]) - height[i];
        }

        return ans;
    }
}

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

Задача: 1125. Smallest Sufficient Team
Сложность: hard

В проекте у вас есть список необходимых навыков req_skills и список людей. i-й человек people[i] содержит список навыков, которыми обладает этот человек.

Рассмотрим достаточную команду: набор людей, такой что для каждого необходимого навыка из req_skills, есть по крайней мере один человек в команде, который обладает этим навыком. Мы можем представить эти команды индексами каждого человека.

Например, команда = [0, 1, 3] представляет людей с навыками people[0], people[1] и people[3].
Верните любую достаточную команду наименьшего возможного размера, представленную индексами каждого человека. Вы можете вернуть ответ в любом порядке.

Гарантируется, что ответ существует.

Пример:

Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"],
people = [["algorithms","math","java"],["algorithms","math","reactjs"],
["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
Output: [1,2]

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

1⃣Инициализация и создание масок навыков:
Определите количество людей n и количество необходимых навыков m.
Создайте хэш-таблицу skillId, чтобы сопоставить каждому навыку уникальный индекс.
Создайте массив skillsMaskOfPerson, который будет содержать битовые маски навыков для каждого человека.

2⃣Динамическое программирование (DP):
Создайте массив dp размера 2^m и заполните его значениями (1 << n) - 1.
Установите dp[0] в 0 (базовый случай).
Для каждого skillsMask от 1 до 2^m - 1:
- для каждого человека i:
- вычислите smallerSkillsMask как skillsMask & ~skillsMaskOfPerson[i].
- если smallerSkillsMask отличается от skillsMask, обновите dp[skillsMask], если новая команда лучше (имеет меньше установленных битов).

3⃣Формирование ответа:
Извлеките ответ из dp и верните массив индексов людей, составляющих минимальную достаточную команду.

😎 Решение:

public class Solution {
    public int[] SmallestSufficientTeam(string[] req_skills, IList<IList<string>> people) {
        int n = people.Count, m = req_skills.Length;
        var skillId = new Dictionary<string, int>();
        for (int i = 0; i < m; i++) {
            skillId[req_skills[i]] = i;
        }
        var skillsMaskOfPerson = new int[n];
        for (int i = 0; i < n; i++) {
            foreach (var skill in people[i]) {
                if (skillId.ContainsKey(skill)) {
                    skillsMaskOfPerson[i] |= 1 << skillId[skill];
                }
            }
        }
        var dp = new long[1 << m];
        Array.Fill(dp, (1L << n) - 1);
        dp[0] = 0;
        for (int skillsMask = 1; skillsMask < (1 << m); skillsMask++) {
            for (int i = 0; i < n; i++) {
                int smallerSkillsMask = skillsMask & ~skillsMaskOfPerson[i];
                if (smallerSkillsMask != skillsMask) {
                    long peopleMask = dp[smallerSkillsMask] | (1L << i);
                    if (BitCount(peopleMask) < BitCount(dp[skillsMask])) {
                        dp[skillsMask] = peopleMask;
                    }
                }
            }
        }
        long answerMask = dp[(1 << m) - 1];
        var ans = new List<int>();
        for (int i = 0; i < n; i++) {
            if (((answerMask >> i) & 1) == 1) {
                ans.Add(i);
            }
        }
        return ans.ToArray();
    }

    private int BitCount(long value) {
        int count = 0;
        while (value != 0) {
            value &= (value - 1);
            count++;
        }
        return count;
    }
}

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

Задача: 763. Partition Labels
Сложность: medium

Вам дана строка s. Мы хотим разбить строку на как можно больше частей так, чтобы каждая буква встречалась не более чем в одной части. Обратите внимание, что разбиение выполняется так, чтобы после конкатенации всех частей по порядку получилась строка s. Верните список целых чисел, представляющих размер этих частей.

Пример:

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]

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

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

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

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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public IList<int> PartitionLabels(string s) {
        int[] lastPos = new int[26];
        for (int i = 0; i < s.Length; i++) {
            lastPos[s[i] - 'a'] = i;
        }
        
        List<int> partitions = new List<int>();
        int j = 0, anchor = 0;
        for (int i = 0; i < s.Length; i++) {
            j = Math.Max(j, lastPos[s[i] - 'a']);
            if (i == j) {
                partitions.Add(i - anchor + 1);
                anchor = i + 1;
            }
        }
        return partitions;
    }
}

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

        int m = (int)Math.Pow(2, Math.Floor(Math.Log(nodeCount + 1) / Math.Log(2))) - 1;
        MakeRotations(vineHead, nodeCount - m);
        while (m > 1) {
            m /= 2;
            MakeRotations(vineHead, m);
        }

        TreeNode balancedRoot = vineHead.right;
        return balancedRoot;
    }

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

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

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

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

Задача: 924. Minimize Malware Spread
Сложность: hard

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока не останется ни одного узла, который можно было бы заразить таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим из initial ровно один узел. Верните тот узел, удаление которого минимизирует M(initial). Если можно удалить несколько узлов, чтобы минимизировать M(initial), верните такой узел с наименьшим индексом. Обратите внимание, что если узел был удален из начального списка зараженных узлов, он все равно может быть заражен позже из-за распространения вредоносного ПО.

Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

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

1⃣Определить количество зараженных узлов после распространения вредоносного ПО для исходного списка initial.

2⃣Для каждого узла в initial удалить его и вычислить количество зараженных узлов после распространения вредоносного ПО.

3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если есть несколько таких узлов, выбрать узел с наименьшим индексом.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int MinMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.Length;
        HashSet<int> initialSet = new HashSet<int>(initial);
        Array.Sort(initial);
        int minInfected = int.MaxValue;
        int bestNode = initial[0];
        
        foreach (int node in initial) {
            HashSet<int> infected = new HashSet<int>(initialSet);
            infected.Remove(node);
            foreach (int i in initialSet) {
                if (i != node) {
                    Dfs(graph, i, infected);
                }
            }
            if (infected.Count < minInfected) {
                minInfected = infected.Count;
                bestNode = node;
            }
        }
        
        return bestNode;
    }
    
    private void Dfs(int[][] graph, int node, HashSet<int> infected) {
        for (int neighbor = 0; neighbor < graph.Length; neighbor++) {
            if (graph[node][neighbor] == 1 && !infected.Contains(neighbor)) {
                infected.Add(neighbor);
                Dfs(graph, neighbor, infected);
            }
        }
    }
}

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

Задача: 989. Add to Array-Form of Integer
Сложность: easy

Массивная форма целого числа num - это массив, представляющий его цифры в порядке слева направо.

Например, для num = 1321, массивная форма - это [1, 3, 2, 1].
Дано num в массивной форме целого числа и целое число k, верните массивную форму числа num + k.

Пример:

Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

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

1⃣Инициализация переменных:
Преобразуйте число k в массив его цифр и переверните оба массива (массив num и массив цифр k).
Завести переменную carry для хранения переноса и инициализировать ее нулем.
Создать пустой массив result для хранения результата.

2⃣Сложение массивов:
Пройдите по элементам массивов num и цифр k, начиная с их конца, сложите соответствующие цифры вместе с переносом (carry).
Если сумма больше 9, сохраните последнюю цифру в текущей позиции результата, а carry установите в 1.
Если сумма меньше 10, установите carry в 0.
Добавьте результат текущего сложения в массив result

3⃣Обработка оставшихся цифр и переноса:
Если один из массивов закончился раньше, продолжайте сложение оставшихся цифр другого массива с переносом.
Если после окончания всех сложений остается перенос (carry), добавьте его в начало массива result.
Переверните массив result обратно и верните его.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public IList<int> AddToArrayForm(int[] num, int k) {
        List<int> result = new List<int>();
        int n = num.Length;

        for (int i = n - 1; i >= 0; i--) {
            k += num[i];
            result.Add(k % 10);
            k /= 10;
        }
        while (k > 0) {
            result.Add(k % 10);
            k /= 10;
        }
        result.Reverse();
        return result;
    }
}

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

Задача: 997. Find the Town Judge
Сложность: easy

В городе есть n человек, помеченных от 1 до n. Ходят слухи, что один из этих людей тайно является городским судьей. Если городской судья существует, то: городской судья никому не доверяет. Все (кроме городского судьи) доверяют городскому судье. Существует ровно один человек, удовлетворяющий свойствам 1 и 2. Вам дан массив trust, где trust[i] = [ai, bi], представляющий, что человек, помеченный ai, доверяет человеку, помеченному bi. Если в массиве trust не существует доверительных отношений, то таких отношений не существует. Верните метку городского судьи, если городской судья существует и может быть идентифицирован, или верните -1 в противном случае.

Пример:

Input: n = 2, trust = [[1,2]]
Output: 2

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

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

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

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

😎 Решение:

public class Solution {
    public int FindJudge(int n, int[][] trust) {
        if (trust.Length == 0 && n == 1) {
            return 1;
        }

        int[] trustCount = new int[n + 1];
        int[] trustedBy = new int[n + 1];

        foreach (var t in trust) {
            trustCount[t[0]]++;
            trustedBy[t[1]]++;
        }

        for (int i = 1; i <= n; i++) {
            if (trustCount[i] == 0 && trustedBy[i] == n - 1) {
                return i;
            }
        }

        return -1;
    }
}

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

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

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

Пример:

Input: arr = ["un","iq","ue"]
Output: 4

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

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

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

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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int MaxLength(IList<string> arr) {
        return Backtrack(arr, 0, "");
    }

    private bool IsUnique(string s) {
        HashSet<char> charSet = new HashSet<char>(s);
        return charSet.Count == s.Length;
    }

    private int Backtrack(IList<string> arr, int index, string current) {
        if (!IsUnique(current)) return 0;
        int maxLength = current.Length;
        for (int i = index; i < arr.Count; i++) {
            maxLength = Math.Max(maxLength, Backtrack(arr, i + 1, current + arr[i]));
        }
        return maxLength;
    }
}

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