Задача: 740. Delete and Earn
Сложность: medium

Вам дан целочисленный массив nums. Вы хотите максимизировать количество очков, выполнив следующую операцию любое количество раз: Выберите любой элемент nums[i] и удалите его, чтобы заработать nums[i] очков. После этого вы должны удалить каждый элемент, равный nums[i] - 1, и каждый элемент, равный nums[i] + 1. Верните максимальное количество очков, которое вы можете заработать, применив вышеуказанную операцию некоторое количество раз.

Пример:

Input: nums = [3,4,2]
Output: 6

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

1⃣Подсчитайте количество каждого числа в массиве nums.

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

3⃣Для каждого числа num в nums, учитывайте два случая: не брать число или взять число и добавить его очки.

😎 Решение:

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

public class Solution {
    public int DeleteAndEarn(int[] nums) {
        var count = new Dictionary<int, int>();
        foreach (var num in nums) {
            if (!count.ContainsKey(num)) {
                count[num] = 0;
            }
            count[num]++;
        }
        
        int avoid = 0, using = 0, prev = -1;
        foreach (var num in count.Keys.OrderBy(x => x)) {
            if (num - 1 != prev) {
                int newAvoid = Math.Max(avoid, using);
                using = num * count[num] + Math.Max(avoid, using);
                avoid = newAvoid;
            } else {
                int newAvoid = Math.Max(avoid, using);
                using = num * count[num] + avoid;
                avoid = newAvoid;
            }
            prev = num;
        }
        
        return Math.Max(avoid, using);
    }
}

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

Задача: 137. Single Number II
Сложность: medium

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

Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.

Пример:

Input: nums = [2,2,3,2]
Output: 3

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

1⃣Сортировка массива:
Отсортируйте массив nums. Это упорядочит все элементы так, чтобы одинаковые числа находились рядом.

2⃣Итерация с проверкой:
Используйте цикл for для перебора элементов массива от начала до nums.size() - 2 с шагом 3. Таким образом, каждый проверяемый индекс будет иметь следующий за ним индекс в пределах массива.
Если элемент на текущем индексе совпадает с элементом на следующем индексе (проверка nums[i] == nums[i + 1]), продолжайте следующую итерацию цикла.

3⃣Возврат уникального элемента:
Если элемент на текущем индексе не совпадает с следующим, значит, это искомый уникальный элемент, который встречается только один раз. В этом случае возвращайте элемент на текущем индексе.
Если до последнего элемента цикл не нашёл уникального элемента, возвращайте последний элемент массива nums[nums.size() - 1], поскольку он, очевидно, будет уникальным, если предыдущие проверки не выявили уникального элемента раньше.

😎 Решение:

public class Solution {
    public int SingleNumber(int[] nums) {
        Array.Sort(nums);
        for (int i = 0; i < nums.Length - 1; i += 3) {
            if (nums[i] == nums[i + 1]) {
                continue;
            } else {
                return nums[i];
            }
        }

        return nums[nums.Length - 1];
    }
}

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

Задача: 979. Distribute Coins in Binary Tree
Сложность: medium

Вам дан корень бинарного дерева с n узлами, где каждый узел в дереве содержит node.val монет. Всего по всему дереву распределено n монет.

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

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

Пример:

Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

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

1⃣Инициализация и определение рекурсивной функции. Инициализируйте переменную moves = 0. Определите рекурсивную функцию dfs, которая считает количество перемещений монет. Базовый случай: если текущий узел равен null, верните 0.

2⃣Рекурсивный обход дерева. Внутри dfs вызовите dfs для левого и правого поддеревьев, чтобы получить количество монет, которые нужно переместить в каждом поддереве. Вычислите количество перемещений для текущего узла: добавьте абсолютные значения перемещаемых монет в moves.

3⃣Возвращение результата. Верните количество монет, которые текущий узел может передать своему родителю: значение узла плюс количество монет в левом и правом поддеревьях минус 1. Вызовите dfs от корня дерева и верните moves.

😎 Решение:

public class Solution {
    private int moves;

    public int DistributeCoins(TreeNode root) {
        moves = 0;
        Dfs(root);
        return moves;
    }

    private int Dfs(TreeNode current) {
        if (current == null) return 0;
        int leftCoins = Dfs(current.left);
        int rightCoins = Dfs(current.right);
        moves += Math.Abs(leftCoins) + Math.Abs(rightCoins);
        return current.val - 1 + leftCoins + rightCoins;
    }
}

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

Задача: 346. Moving Average from Data Stream
Сложность: easy

Дан поток целых чисел и размер окна, вычислите скользящее среднее всех целых чисел в скользящем окне.

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

MovingAverage(int size) Инициализирует объект с размером окна size.
double next(int val) Возвращает скользящее среднее последних size значений потока.

Пример:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

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

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

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

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

😎 Решение:

using System;
using System.Collections.Generic;

public class MovingAverage {
    private int size;
    private Queue<int> queue;
    private int sum;
    
    public MovingAverage(int size) {
        this.size = size;
        this.queue = new Queue<int>();
        this.sum = 0;
    }
    
    public double Next(int val) {
        queue.Enqueue(val);
        sum += val;
        if (queue.Count > size) {
            sum -= queue.Dequeue();
        }
        return (double)sum / queue.Count;
    }
}

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

Задача: 1091. Shortest Path in Binary Matrix
Сложность: medium

Дан бинарный матричный массив grid размером n x n. Верните длину самого короткого чистого пути в матрице. Если чистого пути не существует, верните -1.

Чистый путь в бинарной матрице — это путь из верхнего левого угла (т.е. (0, 0)) в нижний правый угол (т.е. (n - 1, n - 1)), такой что:

Все посещенные клетки пути равны 0.
Все соседние клетки пути соединены по 8 направлениям (т.е. они различны и имеют общую сторону или угол).
Длина чистого пути — это количество посещенных клеток этого пути.

Пример:

Input: grid = [[0,1],[1,0]]
Output: 2

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

1⃣Проверить, что начальная и конечная клетки открыты (равны 0). Если нет, вернуть -1.

2⃣Выполнить поиск в ширину (BFS) из начальной клетки, добавляя в очередь соседние клетки, если они открыты и еще не посещены. Обновлять длину пути для каждой клетки.

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

😎 Решение:

using System.Collections.Generic;

public class Solution {
    private static readonly int[][] directions = new int[][] {
        new int[] {-1, -1}, new int[] {-1, 0}, new int[] {-1, 1}, 
        new int[] {0, -1}, new int[] {0, 1}, 
        new int[] {1, -1}, new int[] {1, 0}, new int[] {1, 1}
    };

    public int ShortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] != 0 || grid[grid.Length - 1][grid[0].Length - 1] != 0) {
            return -1;
        }

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

        while (queue.Count > 0) {
            var cell = queue.Dequeue();
            int row = cell[0], col = cell[1], distance = grid[row][col];
            if (row == grid.Length - 1 && col == grid[0].Length - 1) {
                return distance;
            }
            foreach (var direction in directions) {
                int newRow = row + direction[0];
                int newCol = col + direction[1];
                if (newRow >= 0 && newCol >= 0 && newRow < grid.Length && newCol < grid[0].Length && grid[newRow][newCol] == 0) {
                    queue.Enqueue(new int[] { newRow, newCol });
                    grid[newRow][newCol] = distance + 1;
                }
            }
        }
        return -1;
    }
}

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

Задача: 171. Excel Sheet Column Number
Сложность: easy

Дана строка columnTitle, представляющая название столбца, как это отображается в Excel. Вернуть соответствующий номер столбца.

Пример:

Input: columnTitle = "A"
Output: 1

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

1⃣Создайте отображение букв алфавита и их соответствующих значений (начиная с 1).

2⃣Инициализируйте переменную-аккумулятор result.

3⃣Начиная справа налево, вычислите значение символа в
зависимости от его позиции и добавьте его к result.

😎 Решение:

public class Solution {
    public int TitleToNumber(string s) {
        int result = 0;

        Dictionary<Char, int> alpha_map = new Dictionary<Char, int>();
        for (int i = 0; i < 26; i++) {
            Char c = Convert.ToChar(i + 65);
            alpha_map[c] = i + 1;
        }

        int n = s.Length;
        for (int i = 0; i < n; i++) {
            char cur_char = s[n - 1 - i];
            result += alpha_map[cur_char] * (int)Math.Pow(26, i);
        }

        return result;
    }
}

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

Задача: 1030. Matrix Cells in Distance Order
Сложность: easy

Вам даны четыре целых числа row, cols, rCenter и cCenter. Имеется матрица rows x cols, и вы находитесь на ячейке с координатами (rCenter, cCenter). Верните координаты всех ячеек в матрице, отсортированные по их расстоянию от (rCenter, cCenter) от наименьшего расстояния до наибольшего. Вы можете вернуть ответ в любом порядке, удовлетворяющем этому условию. Расстояние между двумя ячейками (r1, c1) и (r2, c2) равно |r1 - r2| + |c1 - c2|.

Пример:

Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output: [[0,0],[0,1]]

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

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

2⃣Сортировка списка:
Отсортируйте список по расстоянию в порядке возрастания.

3⃣Извлечение координат:
Извлеките координаты из отсортированного списка и верните их.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int[][] AllCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        var cells = new List<(int, int, int)>();
        
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                int distance = Math.Abs(r - rCenter) + Math.Abs(c - cCenter);
                cells.Add((distance, r, c));
            }
        }
        
        cells.Sort((a, b) => a.Item1.CompareTo(b.Item1));
        
        var result = new List<int[]>();
        foreach (var cell in cells) {
            result.Add(new int[] { cell.Item2, cell.Item3 });
        }
        
        return result.ToArray();
    }
}

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

Задача: 758. Bold Words in String
Сложность: medium

При наличии массива ключевых слов и строки a выделите все ключевые слова [i] жирным шрифтом. Все буквы между тегами <b> и </b> выделяются жирным шрифтом.

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

Пример:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"

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

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

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

3⃣Постройте результирующую строку, добавляя теги <b> и </b> на основе массива флагов.

😎 Решение:

public class Solution {
    public string AddBoldTags(string[] keywords, string s) {
        int n = s.Length;
        bool[] bold = new bool[n];
        
        foreach (string word in keywords) {
            int start = s.IndexOf(word);
            while (start != -1) {
                for (int i = start; i < start + word.Length; i++) {
                    bold[i] = true;
                }
                start = s.IndexOf(word, start + 1);
            }
        }
        
        var result = new StringBuilder();
        int j = 0;
        while (j < n) {
            if (bold[j]) {
                result.Append("<b>");
                while (j < n && bold[j]) {
                    result.Append(s[j]);
                    j++;
                }
                result.Append("</b>");
            } else {
                result.Append(s[j]);
                j++;
            }
        }
        
        return result.ToString();
    }
}

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

Задача: 907. Sum of Subarray Minimums
Сложность: medium

Учитывая массив целых чисел arr, найдите сумму min(b), где b находится в каждом (смежном) подмассиве arr. Поскольку ответ может быть большим, верните ответ по модулю 109 + 7.

Пример:

Input: arr = [3,1,2,4]
Output: 17

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

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

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

3⃣Вычислить сумму минимальных значений для всех подмассивов и вернуть результат по модулю 10^9 + 7.

😎 Решение:

public class Solution {
    public int SumSubarrayMins(int[] arr) {
        const int MOD = 1_000_000_007;
        int n = arr.Length;
        int[] left = new int[n];
        int[] right = new int[n];
        Stack<int> stack = new Stack<int>();

        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && arr[stack.Peek()] > arr[i]) {
                stack.Pop();
            }
            left[i] = stack.Count == 0 ? i + 1 : i - stack.Peek();
            stack.Push(i);
        }

        stack.Clear();

        for (int i = n - 1; i >= 0; i--) {
            while (stack.Count > 0 && arr[stack.Peek()] >= arr[i]) {
                stack.Pop();
            }
            right[i] = stack.Count == 0 ? n - i : stack.Peek() - i;
            stack.Push(i);
        }

        long result = 0;
        for (int i = 0; i < n; i++) {
            result = (result + (long)arr[i] * left[i] * right[i]) % MOD;
        }

        return (int)result;
    }
}

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

Задача: 1133. Largest Unique Number
Сложность: easy

Вам Дан целочисленный массив nums, верните наибольшее целое число, которое встречается только один раз. Если ни одно целое число не встречается один раз, верните -1.

Пример:

Input: nums = [5,7,3,9,4,9,8,3,1]
Output: 8
Explanation: The maximum integer in the array is 9 but it is repeated. The number 8 occurs only once, so it is the answer.

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

1⃣Создайте хеш-таблицу для хранения количества каждого числа в массиве.

2⃣Пройдите по массиву и заполните хеш-таблицу количеством каждого числа.

3⃣Инициализируйте результат значением -1. Пройдите по хеш-таблице и если значение ключа равно 1, установите результат равным максимальному значению между ключом и текущим результатом. Верните результат.

😎 Решение:

public class Solution {
    public int LargestUniqueNumber(int[] nums) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        
        foreach (int num in nums) {
            if (count.ContainsKey(num)) {
                count[num]++;
            } else {
                count[num] = 1;
            }
        }
        
        int result = -1;
        foreach (var entry in count) {
            if (entry.Value == 1) {
                result = Math.Max(result, entry.Key);
            }
        }
        
        return result;
    }
}

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

Задача: 784. Letter Case Permutation
Сложность: medium

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

Пример:

Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

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

1⃣Если следующий символ c является буквой, то мы удвоим все слова в нашем текущем ответе, и добавим lowercase(c) к каждому слову в первой половине, и uppercase(c) к каждому слову во второй половине.

2⃣Если c является цифрой, мы добавим его к каждому слову.

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

😎 Решение:

public class Solution {
    public IList<string> LetterCasePermutation(string S) {
        var ans = new List<List<char>> { new List<char>() };

        foreach (var c in S) {
            int n = ans.Count;
            if (char.IsLetter(c)) {
                for (int i = 0; i < n; i++) {
                    var current = new List<char>(ans[i]);
                    ans.Add(current);
                    ans[i].Add(char.ToLower(c));
                    ans[n + i].Add(char.ToUpper(c));
                }
            } else {
                for (int i = 0; i < n; i++) {
                    ans[i].Add(c);
                }
            }
        }

        return ans.Select(list => new string(list.ToArray())).ToList();
    }
}

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

Задача: 465. Optimal Account Balancing
Сложность: medium

Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.

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

Пример:

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2

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

1⃣Создать хеш-таблицу для хранения чистого баланса каждого человека.

2⃣Собрать все ненулевые чистые балансы в массив balance_list.

3⃣Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]:
Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1.
Если cur = n, вернуть 0.
В противном случае установить cost на большое значение, например, inf.
Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0,
Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur].
Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1).
Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат).
Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации.
Вернуть cost, когда итерация завершена. Вернуть dfs(0).

😎 Решение:

public class Solution {
    private List<int> creditList;
    
    public int MinTransfers(int[][] transactions) {
        var creditMap = new Dictionary<int, int>();
        foreach (var t in transactions) {
            if (!creditMap.ContainsKey(t[0])) creditMap[t[0]] = 0;
            if (!creditMap.ContainsKey(t[1])) creditMap[t[1]] = 0;
            creditMap[t[0]] += t[2];
            creditMap[t[1]] -= t[2];
        }
        
        creditList = new List<int>();
        foreach (var amount in creditMap.Values) {
            if (amount != 0) {
                creditList.Add(amount);
            }
        }
        
        int n = creditList.Count;
        return Dfs(0, n);
    }
    
    private int Dfs(int cur, int n) {
        while (cur < n && creditList[cur] == 0) {
            cur++;
        }
    
        if (cur == n) {
            return 0;
        }
        
        int cost = int.MaxValue;
        for (int nxt = cur + 1; nxt < n; nxt++) {
            if (creditList[nxt] * creditList[cur] < 0) {
                creditList[nxt] += creditList[cur];
                cost = Math.Min(cost, 1 + Dfs(cur + 1, n));
                creditList[nxt] -= creditList[cur];
            }
        }
        
        return cost;
    }
}

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

Задача: 839. Similar String Groups
Сложность: hard

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

Например, "tars" и "rats" похожи (замена на позициях 0 и 2), и "rats" и "arts" похожи, но "star" не похожа на "tars", "rats" или "arts".
Эти строки образуют две связанные группы по сходству: {"tars", "rats", "arts"} и {"star"}. Обратите внимание, что "tars" и "arts" находятся в одной группе, хотя они не похожи друг на друга. Формально, каждая группа такова, что слово находится в группе, если и только если оно похоже хотя бы на одно другое слово в группе.

Вам дан список строк strs, где каждая строка в списке является анаграммой каждой другой строки в списке. Сколько групп существует?

Пример:

Input: strs = ["tars","rats","arts","star"]
Output: 2

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

1⃣Создайте переменную n, хранящую количество слов в strs, и создайте экземпляр UnionFind размера n.

2⃣Для любых двух слов на индексах i и j, которые ведут себя как узлы, проверьте, являются ли слова strs[i] и strs[j] похожими, и выполните операции find и union для объединения различных компонентов в один, если слова похожи.

3⃣Верните количество оставшихся групп.

😎 Решение:

public class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; ++i) {
            parent[i] = i;
        }
    }

    public int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }

    public void Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}

public class Solution {
    public bool IsSimilar(string a, string b) {
        int diff = 0;
        for (int i = 0; i < a.Length; ++i) {
            if (a[i] != b[i]) {
                diff++;
            }
        }
        return diff == 0 || diff == 2;
    }

    public int NumSimilarGroups(string[] strs) {
        int n = strs.Length;
        UnionFind dsu = new UnionFind(n);
        int count = n;

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (IsSimilar(strs[i], strs[j]) && dsu.Find(i) != dsu.Find(j)) {
                    count--;
                    dsu.Union(i, j);
                }
            }
        }

        return count;
    }
}

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

Задача: 415. Add Strings
Сложность: easy

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

Пример:

Input: num1 = "11", num2 = "123"
Output: "134"

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

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

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

3⃣Верните третье максимальное число, если оно существует, иначе верните первое максимальное число.

😎 Решение:

public class Solution {
    public int ThirdMax(int[] nums) {
        int? first = null;
        int? second = null;
        int? third = null;
        
        foreach (int num in nums) {
            if (num == first || num == second || num == third) {
                continue;
            }
            if (first == null || num > first) {
                third = second;
                second = first;
                first = num;
            } else if (second == null || num > second) {
                third = second;
                second = num;
            } else if (third == null || num > third) {
                third = num;
            }
        }
        
        return third ?? first.Value;
    }
}

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

Задача: 38. Count and Say
Сложность: medium

Последовательность "считай и скажи" (countAndSay) строится рекурсивно:

- countAndSay(1) = "1"
- countAndSay(n) — это кодирование длин серий из countAndSay(n - 1).

Пример кодирования длин серий (RLE):
- "3322251" → "23321511"

Для заданного n верните n-й элемент последовательности.

Пример:

Input: n = 4  
Output: "1211"  

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

1⃣Начать с s = "1".

2⃣Для каждого шага n-1 раз:
- Пройти по s, группируя одинаковые символы.
- Для каждой группы записать количество и сам символ.
- Обновить s.

3⃣Вернуть итоговую строку.

😎 Решение:

public class Solution {
    public string CountAndSay(int n) {
        string s = "1";
        for (int i = 0; i < n - 1; i++) {
            StringBuilder current = new StringBuilder();
            for (int j = 0; j < s.Length; j++) {
                int count = 1;
                while (j < s.Length - 1 && s[j] == s[j + 1]) {
                    j++;
                    count++;
                }
                current.Append(count).Append(s[j]);
            }
            s = current.ToString();
        }
        return s;
    }
}

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

Задача: 899. Orderly Queue
Сложность: hard

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

Пример:

Input: s = "cba", k = 1
Output: "acb"

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

1⃣Если k равно 1, найти лексикографически наименьшую строку путем вращения строки и поиска минимального варианта.

2⃣Если k больше 1, отсортировать строку, так как любое количество перемещений позволит упорядочить все символы в строке.

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

😎 Решение:

using System;
using System.Linq;

public class Solution {
    public string OrderlyQueue(string s, int k) {
        if (k == 1) {
            string minString = s;
            for (int i = 1; i < s.Length; i++) {
                string rotated = s.Substring(i) + s.Substring(0, i);
                if (rotated.CompareTo(minString) < 0) {
                    minString = rotated;
                }
            }
            return minString;
        } else {
            return new string(s.OrderBy(c => c).ToArray());
        }
    }
}

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

Задача: 820. Short Encoding of Words
Сложность: medium

Допустимым кодированием массива слов является любая опорная строка s и массив индексов indices, такие что:

words.length == indices.length
Опорная строка s заканчивается символом '#'.
Для каждого индекса indices[i], подстрока строки s, начинающаяся с indices[i] и заканчивающаяся (но не включительно) следующим символом '#', равна words[i].
Дан массив слов, верните длину самой короткой возможной опорной строки s для любого допустимого кодирования слов.

Пример:

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"

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

1⃣Поскольку слово имеет не более 6 собственных суффиксов (так как words[i].length <= 7), давайте итерироваться по всем из них. Для каждого собственного суффикса мы попытаемся удалить его из нашего списка слов. Для эффективности сделаем words множеством.

2⃣Затем создадим список оставшихся слов и сформируем опорную строку, объединяя каждое слово с символом '#'.

3⃣В конце вернем длину полученной опорной строки.

😎 Решение:

public class Solution {
    public int MinimumLengthEncoding(string[] words) {
        var good = new HashSet<string>(words);
        foreach (var word in words) {
            for (int k = 1; k < word.Length; k++) {
                good.Remove(word.Substring(k));
            }
        }
        int length = 0;
        foreach (var word in good) {
            length += word.Length + 1;
        }
        return length;
    }
}

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

Задача: 34. Find First and Last Position of Element in Sorted Array
Сложность: medium

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

Пример:

Input: nums = [5,7,7,8,8,10], target = 8  
Output: [3,4]  

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

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

2⃣Если target не найден, вернуть [-1, -1].

3⃣Использовать FindBound снова для нахождения последней позиции target.

😎 Решение:

public class Solution {
    public int[] SearchRange(int[] nums, int target) {
        int first = FindBound(nums, target, true);
        if (first == -1) return new int[] { -1, -1 };
        
        int last = FindBound(nums, target, false);
        return new int[] { first, last };
    }

    private int FindBound(int[] nums, int target, bool isFirst) {
        int left = 0, right = nums.Length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                if (isFirst) {
                    if (mid == left || nums[mid - 1] != target) return mid;
                    right = mid - 1;
                } else {
                    if (mid == right || nums[mid + 1] != target) return mid;
                    left = mid + 1;
                }
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

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

Задача: 1485. Clone Binary Tree With Random Pointer
Сложность: medium

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

Дерево представлено в том же формате ввода/вывода, что и обычные бинарные деревья, где каждый узел представлен в виде пары [val, random_index], где:
- val: целое число, представляющее Node.val
- random_index: индекс узла (во входных данных), на который указывает случайный указатель, или null, если он не указывает ни на один узел.

Вам будет дано дерево в классе Node, и вы должны вернуть клонированное дерево в классе NodeCopy. Класс NodeCopy является клоном класса Node с такими же атрибутами и конструкторами.

Пример:

Input: root = [[1,null],null,[4,3],[7,0]]
Output: [[1,null],null,[4,3],[7,0]]
Explanation: The original binary tree is [1,null,4,7].
The random pointer of node one is null, so it is represented as [1, null].
The random pointer of node 4 is node 7, so it is represented as [4, 3] where 3 is the index of node 7 in the array representing the tree.
The random pointer of node 7 is node 1, so it is represented as [7, 0] where 0 is the index of node 1 in the array representing the tree.

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

1⃣Глубокое копирование дерева:
Инициализируйте хэш-таблицу newOldPairs, которая сопоставляет узлы старого дерева с узлами нового дерева.
Создайте функцию deepCopy(root), которая принимает корень данного дерева и возвращает корень нового дерева. Эта функция создаёт новый узел с теми же значениями, что и корневой узел, и рекурсивно копирует левое и правое поддеревья. Затем она сохраняет пару старого и нового узлов в хэш-таблицу и возвращает новый корень.

2⃣Сопоставление случайных указателей:
Создайте функцию mapRandomPointers(oldNode), которая принимает корень старого дерева и рекурсивно сопоставляет случайные указатели нового дерева с соответствующими узлами старого дерева, используя хэш-таблицу newOldPairs.

3⃣Возвращение клонированного дерева:
Создайте глубокую копию дерева, используя функцию deepCopy(root), и сопоставьте все случайные указатели нового дерева с помощью функции mapRandomPointers(root). Верните новый корень.

😎 Решение:

public class Node {
    public int val;
    public Node left;
    public Node right;
    public Node random;

    public Node(int _val) {
        val = _val;
        left = null;
        right = null;
        random = null;
    }
}

public class NodeCopy {
    public int val;
    public NodeCopy left;
    public NodeCopy right;
    public NodeCopy random;

    public NodeCopy(int _val) {
        val = _val;
        left = null;
        right = null;
        random = null;
    }
}

public class Solution {
    private Dictionary<Node, NodeCopy> newOldPairs = new Dictionary<Node, NodeCopy>();

    private NodeCopy DeepCopy(Node root) {
        if (root == null) return null;
        NodeCopy newRoot = new NodeCopy(root.val);
        newRoot.left = DeepCopy(root.left);
        newRoot.right = DeepCopy(root.right);
        newOldPairs[root] = newRoot;
        return newRoot;
    }

    private void MapRandomPointers(Node oldNode) {
        if (oldNode == null) return;
        if (newOldPairs.TryGetValue(oldNode, out NodeCopy newNode)) {
            newNode.random = newOldPairs.GetValueOrDefault(oldNode.random);
            MapRandomPointers(oldNode.left);
            MapRandomPointers(oldNode.right);
        }
    }

    public NodeCopy CopyRandomBinaryTree(Node root) {
        NodeCopy newRoot = DeepCopy(root);
        MapRandomPointers(root);
        return newRoot;
    }
}

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

Задача: 968. Binary Tree Cameras
Сложность: hard

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

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

Пример:

Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

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

1⃣Рекурсивное решение (solve):
Для каждого узла определите три состояния:
- [State 0] Строгое поддерево: все узлы ниже этого узла покрыты, но не сам узел.
- [State 1] Нормальное поддерево: все узлы ниже и включая этот узел покрыты, но на этом узле нет камеры.
- [State 2] Установленная камера: все узлы ниже и включая этот узел покрыты, и на этом узле установлена камера.
Рассчитайте эти состояния для левого и правого поддеревьев.

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

3⃣Минимальное количество камер:
Запустите функцию solve на корневом узле и верните минимальное значение между состояниями 1 и 2.

😎 Решение:

public class Solution {
    public int MinCameraCover(TreeNode root) {
        var ans = Solve(root);
        return Math.Min(ans[1], ans[2]);
    }

    private int[] Solve(TreeNode node) {
        if (node == null) {
            return new int[] { 0, 0, 99999 };
        }

        var L = Solve(node.left);
        var R = Solve(node.right);
        int mL12 = Math.Min(L[1], L[2]);
        int mR12 = Math.Min(R[1], R[2]);

        int d0 = L[1] + R[1];
        int d1 = Math.Min(L[2] + mR12, R[2] + mL12);
        int d2 = 1 + Math.Min(L[0], mL12) + Math.Min(R[0], mR12);
        return new int[] { d0, d1, d2 };
    }
}

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