Задача: 672. Bulb Switcher II
Сложность: medium

Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:

Кнопка 1: Переключает состояние всех лампочек.
Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).
Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).
Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).
Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.

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

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

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

1⃣Рассчитаем возможные множества остатков: то есть какие множества c_i = f_i (mod 2) возможны.

2⃣Так как c_i ≡ f_i и c_i ≤ f_i, если ∑f_i ≠ ∑c_i, или если ∑f_i < ∑c_i, это невозможно. В противном случае это возможно простым построением: выполните операции, указанные c_i, затем выполните операцию номер 1 с четным числом оставшихся операций.

3⃣Для каждого возможного множества остатков симулируем и запоминаем, как будут выглядеть первые 6 лампочек, сохраняя это в структуре Set. В конце возвращаем размер этого множества.

😎 Решение:

public class Solution {
    public int FlipLights(int n, int m) {
        var seen = new HashSet<int>();
        n = Math.Min(n, 6);
        int shift = Math.Max(0, 6 - n);
        for (int cand = 0; cand < 16; ++cand) {
            int bcount = Convert.ToString(cand, 2).Count(c => c == '1');
            if (bcount % 2 == m % 2 && bcount <= m) {
                int lights = 0;
                if (((cand >> 0) & 1) > 0) lights ^= 0b111111 >> shift;
                if (((cand >> 1) & 1) > 0) lights ^= 0b010101 >> shift;
                if (((cand >> 2) & 1) > 0) lights ^= 0b101010 >> shift;
                if (((cand >> 3) & 1) > 0) lights ^= 0b100100 >> shift;
                seen.Add(lights);
            }
        }
        return seen.Count;
    }
}

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

Задача: 1539. Kth Missing Positive Number
Сложность: easy

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

Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве.

Пример:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

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

1⃣Проверьте, является ли k-й отсутствующий номер меньше первого элемента массива. Если это так, верните k. Уменьшите k на количество положительных чисел, отсутствующих до начала массива: k -= arr[0] - 1.

2⃣Итерируйтесь по элементам массива. На каждом шаге вычисляйте количество отсутствующих положительных чисел между i+1-м и i-м элементами: currMissing = arr[i + 1] - arr[i] - 1. Сравните k с currMissing. Если k <= currMissing, то число для возврата находится между arr[i + 1] и arr[i], и вы можете его вернуть: arr[i] + k. В противном случае уменьшите k на currMissing и продолжайте.

3⃣Если элемент, который нужно вернуть, больше последнего элемента массива, верните его: arr[n - 1] + k.

😎 Решение:

public class Solution {
    public int FindKthPositive(int[] arr, int k) {
        if (k <= arr[0] - 1) {
            return k;
        }
        k -= arr[0] - 1;
        int n = arr.Length;
        for (int i = 0; i < n - 1; ++i) {
            int currMissing = arr[i + 1] - arr[i] - 1;
            if (k <= currMissing) {
                return arr[i] + k;
            }
            k -= currMissing;
        }
        return arr[n - 1] + k;
    }
}

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

Задача: 1208. Get Equal Substrings Within Budget
Сложность: medium

Вам даны две строки s и t одинаковой длины и целое число maxCost.
Вы хотите преобразовать s в t. Изменение i-го символа строки s на i-й символ строки t стоит |s[i] - t[i]| (т.е. абсолютная разница между значениями ASCII символов).

Верните максимальную длину подстроки s, которую можно изменить, чтобы она соответствовала соответствующей подстроке t с затратами, не превышающими maxCost. Если нет подстроки из s, которую можно изменить на соответствующую подстроку из t, верните 0.

Пример:

Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd".
That costs 3, so the maximum length is 3.

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

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

2⃣Итерация по индексам от 0 до N-1:
Добавить текущие затраты на преобразование символа s[i] в t[i] к currCost.
Удалять элементы с левого конца, уменьшая затраты до тех пор, пока currCost не станет меньше или равным maxCost.
Обновить maxLen длиной текущей подстроки.

3⃣Возврат maxLen как результата.

😎 Решение:

public class Solution {
    public int EqualSubstring(string s, string t, int maxCost) {
        int N = s.Length;
        
        int maxLen = 0;
        int start = 0;
        int currCost = 0;
        
        for (int i = 0; i < N; i++) {
            currCost += Math.Abs(s[i] - t[i]);
            
            while (currCost > maxCost) {
                currCost -= Math.Abs(s[start] - t[start]);
                start++;
            }
            
            maxLen = Math.Max(maxLen, i - start + 1);
        }
        
        return maxLen;
    }
}

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

Задача: 309. Best Time to Buy and Sell Stock with Cooldown
Сложность: medium

Дан массив prices, где prices[i] — цена данной акции в i-й день.

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

После продажи акции вы не можете покупать акции на следующий день (т. е. необходимо один день подождать).

Пример:

Input: prices = [1]
Output: 0

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

1⃣Инициализация состояний
Используйте три состояния для отслеживания максимальной прибыли: hold: максимальная прибыль на данный день, если у вас есть акция. sold: максимальная прибыль на данный день, если вы продали акцию. cooldown: максимальная прибыль на данный день, если вы находитесь в периоде ожидания после продажи.

2⃣Обновление состояний
Итерируйте по каждому дню, обновляя состояния: hold: максимальная прибыль, если у вас есть акция на текущий день. sold: максимальная прибыль, если вы продаете акцию на текущий день. cooldown: максимальная прибыль, если вы находитесь в периоде ожидания на текущий день.

3⃣Определение максимальной прибыли
В конце итерации максимальная прибыль будет максимальным значением между состояниями sold и cooldown, так как hold состояние не может быть конечным состоянием для получения максимальной прибыли.

😎 Решение:

public class Solution {
    public int MaxProfit(int[] prices) {
        if (prices.Length == 0) return 0;
        
        int hold = -prices[0];
        int sold = 0;
        int cooldown = 0;
        
        for (int i = 1; i < prices.Length; i++) {
            int newHold = Math.Max(hold, cooldown - prices[i]);
            int newSold = hold + prices[i];
            int newCooldown = Math.Max(cooldown, sold);
            
            hold = newHold;
            sold = newSold;
            cooldown = newCooldown;
        }
        
        return Math.Max(sold, cooldown);
    }
}

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

Задача: 655. Print Binary Tree
Сложность: medium

Учитывая корень двоичного дерева, постройте строковую матрицу res с индексом 0 размером m x n, которая представляет собой форматированную раскладку дерева. Форматированная матрица должна быть построена по следующим правилам: высота дерева равна height, количество строк m должно быть равно height + 1. Количество столбцов n должно быть равно 2height+1 - 1. Поместите корневой узел в середину верхней строки (более формально, в позицию res[0][(n-1)/2]).
Для каждого узла, который был помещен в матрицу в позицию res[r][c], поместите его левого ребенка в res[r+1][c-2height-r-1], а правого - в res[r+1][c+2height-r-1]. Продолжайте этот процесс, пока не будут размещены все узлы дерева. Любые пустые ячейки должны содержать пустую строку "". Верните построенную матрицу res.

Пример:

Input: root = [1,2]
Output: 
[["","1",""],
 ["2","",""]]

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

1⃣Найдите высоту дерева и определите размер матрицы (m x n).

2⃣Рекурсивно разместите узлы в матрице, начиная с корневого узла.

3⃣Верните заполненную матрицу.

😎 Решение:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    private int FindHeight(TreeNode root) {
        if (root == null) return -1;
        return 1 + Math.Max(FindHeight(root.left), FindHeight(root.right));
    }

    private void Fill(string[,] res, TreeNode root, int r, int c, int height) {
        if (root == null) return;
        res[r, c] = root.val.ToString();
        if (root.left != null) {
            Fill(res, root.left, r + 1, c - (1 << (height - r - 1)), height);
        }
        if (root.right != null) {
            Fill(res, root.right, r + 1, c + (1 << (height - r - 1)), height);
        }
    }

    public IList<IList<string>> PrintTree(TreeNode root) {
        int height = FindHeight(root);
        int m = height + 1;
        int n = (1 << (height + 1)) - 1;
        string[,] res = new string[m, n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res[i, j] = "";
            }
        }
        Fill(res, root, 0, (n - 1) / 2, height);
        IList<IList<string>> result = new List<IList<string>>();
        for (int i = 0; i < m; i++) {
            IList<string> row = new List<string>();
            for (int j = 0; j < n; j++) {
                row.Add(res[i, j]);
            }
            result.Add(row);
        }
        return result;
    }
}

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

Задача: 90. Subsets II
Сложность: medium

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

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

Пример:

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

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

1⃣Отсортируйте массив nums, чтобы элементы совпадали, шли подряд — это упростит проверку на дубликаты.

2⃣Сгенерируйте все возможные подмножества с помощью битовой маски. Для каждого из них subsetIndexпроверьте 0выбранные 2^n - 1биты и укажите подмножество.

3⃣Используйте HashSet, чтобы записывать отдельные подмножества по строковому представлению. Это предотвращает добавление дубликатов в результат.

😎 Решение:

public class Solution {
    public IList<IList<int>> SubsetsWithDup(int[] nums) {
        IList<IList<int>> subsets = new List<IList<int>>();
        int n = nums.Length;
        Array.Sort(nums);
        int maxNumberOfSubsets = (int)Math.Pow(2, n);
        HashSet<string> seen = new HashSet<string>();
        for (int subsetIndex = 0; subsetIndex < maxNumberOfSubsets; subsetIndex++) {
            List<int> currentSubset = new List<int>();
            StringBuilder hashcode = new StringBuilder();
            for (int j = 0; j < n; j++) {
                int mask = 1 << j;
                int isSet = mask & subsetIndex;
                if (isSet != 0) {
                    currentSubset.Add(nums[j]);
                    hashcode.Append(nums[j]).Append(",");
                }
            }

            if (!seen.Contains(hashcode.ToString())) {
                seen.Add(hashcode.ToString());
                subsets.Add(currentSubset);
            }
        }

        return subsets;
    }
}

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

Задача: 174. Dungeon Game
Сложность: hard

Демоны захватили принцессу и заточили её в правом нижнем углу подземелья. Подземелье состоит из m x n комнат, расположенных в виде двумерной сетки. Наш отважный рыцарь изначально находится в левом верхнем углу и должен пробиться через подземелье, чтобы спасти принцессу.

У рыцаря есть начальное количество очков здоровья, представленное положительным целым числом. Если в какой-то момент его очки здоровья упадут до 0 или ниже, он немедленно умрёт.

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

Чтобы как можно быстрее добраться до принцессы, рыцарь решает двигаться только вправо или вниз на каждом шаге.

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

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

Пример:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

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

1⃣Определяем матрицу dp[row][col], где элемент dp[row][col] указывает минимальное количество очков здоровья, которое потребуется рыцарю, начиная с соответствующей ячейки подземелья dungeon[row][col], чтобы добраться до цели.

2⃣Для расчета значений матрицы dp начинаем с правого нижнего угла подземелья и идем в порядке справа-налево и снизу-вверх. Для каждой ячейки подземелья рассчитываем соответствующее значение dp[row][col].

3⃣Значение dp[row][col] определяется следующими условиями:
Если возможно, сделав шаг вправо из текущей ячейки подземелья, рыцарь может нуждаться в right_health очках здоровья.
Если возможно, сделав шаг вниз из текущей ячейки подземелья, рыцарь может нуждаться в down_health очках здоровья.
Если существует хотя бы одна из вышеуказанных альтернатив, берём минимальное значение из них для dp[row][col].
Если ни одна из вышеуказанных альтернатив не существует, то есть мы находимся в целевой ячейке, возможны два случая:
Если текущая ячейка содержит магический шар, то достаточно одного очка здоровья.
Если текущая ячейка содержит демона, то рыцарь должен иметь одно очко здоровья плюс очки урона, которые нанесет демон.

😎 Решение:

public class Solution {
    const int inf = int.MaxValue;
    int[,] dp;
    int rows, cols;

    public int GetMinHealth(int currCell, int nextRow, int nextCol) {
        if (nextRow >= this.rows || nextCol >= this.cols)
            return inf;
        int nextCell = this.dp[nextRow, nextCol];
        return Math.Max(1, nextCell - currCell);
    }

    public int CalculateMinimumHP(int[][] dungeon) {
        this.rows = dungeon.Length;
        this.cols = dungeon[0].Length;
        this.dp = new int[rows, cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                dp[i, j] = inf;
            }
        }

        int currCell, rightHealth, downHealth, nextHealth, minHealth;
        for (int row = this.rows - 1; row >= 0; --row) {
            for (int col = this.cols - 1; col >= 0; --col) {
                currCell = dungeon[row][col];

                rightHealth = GetMinHealth(currCell, row, col + 1);
                downHealth = GetMinHealth(currCell, row + 1, col);
                nextHealth = Math.Min(rightHealth, downHealth);

                if (nextHealth != inf) {
                    minHealth = nextHealth;
                } else {
                    minHealth = currCell >= 0 ? 1 : 1 - currCell;
                }

                this.dp[row, col] = minHealth;
            }
        }

        return this.dp[0, 0];
    }
}

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

Задача: 422. Valid Word Square
Сложность: easy

Дан массив строк words, верните true, если он образует правильный квадрат слов.

Последовательность строк образует правильный квадрат слов, если k-я строка и k-й столбец читаются одинаково, где 0 <= k < max(numRows, numColumns).

Пример:

Input: words = ["abcd","bnrt","crmy","dtye"]
Output: true
Explanation:
The 1st row and 1st column both read "abcd".
The 2nd row and 2nd column both read "bnrt".
The 3rd row and 3rd column both read "crmy".
The 4th row and 4th column both read "dtye".
Therefore, it is a valid word square.

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

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

2⃣Итерация по массиву words, определение максимальной длины слова для cols, проверка, что количество строк равно количеству столбцов. Если условие не выполняется, возвращаем false.

3⃣Для каждого столбца col от 0 до cols - 1, формируем строку newWord из символов на позиции (row, col) для каждой строки. Сохраняем newWord в массиве newWords. В конце, если newWords и words равны, возвращаем true, иначе false.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public bool ValidWordSquare(IList<string> words) {
        int cols = 0;
        int rows = words.Count;
        var newWords = new List<string>();
        
        foreach (var word in words) {
            cols = Math.Max(cols, word.Length);
        }

        if (cols != words[0].Length || rows != cols) {
            return false;
        }

        for (int col = 0; col < cols; ++col) {
            var newWord = string.Empty;
            for (int row = 0; row < rows; ++row) {
                if (col < words[row].Length) {
                    newWord += words[row][col];
                }
            }
            newWords.Add(newWord);
        }

        return words.SequenceEqual(newWords);
    }
}

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

Задача: 712. Minimum ASCII Delete Sum for Two Strings
Сложность: medium

Если даны две строки s1 и s2, верните наименьшую ASCII-сумму удаленных символов, чтобы сделать две строки равными.

Пример:

Input: s1 = "sea", s2 = "eat"
Output: 231

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

1⃣Создайте двумерный массив dp размером (len(s1) + 1) x (len(s2) + 1), где dp[i][j] будет хранить наименьшую ASCII-сумму удаленных символов для первых i символов s1 и первых j символов s2.

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

3⃣Заполните оставшуюся часть массива dp следующим образом: Если символы s1[i-1] и s2[j-1] равны, dp[i][j] = dp[i-1][j-1]. Иначе, dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1])).

😎 Решение:

public class Solution {
    public int MinimumDeleteSum(string s1, string s2) {
        int[][] dp = new int[s1.Length + 1][];
        for (int i = 0; i < dp.Length; i++) {
            dp[i] = new int[s2.Length + 1];
        }
        for (int i = 1; i <= s1.Length; i++) {
            dp[i][0] = dp[i - 1][0] + s1[i - 1];
        }
        for (int j = 1; j <= s2.Length; j++) {
            dp[0][j] = dp[0][j - 1] + s2[j - 1];
        }
        for (int i = 1; i <= s1.Length; i++) {
            for (int j = 1; j <= s2.Length; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.Min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);
                }
            }
        }
        return dp[s1.Length][s2.Length];
    }
}

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

Задача: 236. Lowest Common Ancestor of a Binary Tree
Сложность: medium

Дано бинарное дерево. Найдите наименьший общий предок (LCA) двух заданных узлов в дереве.

Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)."

Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

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

1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Если текущий узел является одним из узлов p или q, установите переменную mid в значение True и продолжите поиск другого узла в левой и правой ветвях.

2⃣Проверка поддеревьев: Выполните рекурсивный обход левой и правой ветвей дерева. Если какая-либо из ветвей (левая или правая) возвращает True, это означает, что один из двух узлов найден ниже по дереву.

3⃣Определение LCA: Если в любой момент обхода дерева две из трех переменных (left, right или mid) становятся True, это означает, что найден наименьший общий предок (LCA) для узлов p и q.

😎 Решение:

public class Solution {
    private TreeNode ans;

    public Solution() {
        this.ans = null;
    }

    private bool RecurseTree(TreeNode currentNode, TreeNode p, TreeNode q) {
        if (currentNode == null) {
            return false;
        }

        int left = this.RecurseTree(currentNode.left, p, q) ? 1 : 0;
        int right = this.RecurseTree(currentNode.right, p, q) ? 1 : 0;
        int mid = (currentNode == p || currentNode == q) ? 1 : 0;

        if (mid + left + right >= 2) {
            this.ans = currentNode;
        }

        return (mid + left + right > 0);
    }

    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.RecurseTree(root, p, q);
        return this.ans;
    }
}

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

Задача: 680. Valid Palindrome II
Сложность: easy

Дана строка s, вернуть true, если s может быть палиндромом после удаления не более одного символа из нее.

Пример:

Input: s = "aba"
Output: true

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

1⃣Создайте вспомогательную функцию checkPalindrome, которая принимает строку s и два указателя i и j. Эта функция возвращает логическое значение, указывающее, является ли подстрока s.substring(i, j) палиндромом.

2⃣Инициализируйте два указателя: i = 0 и j = s.length() - 1. Пока i < j, проверьте, совпадают ли символы в индексах i и j. Если нет, это значит, что нам нужно удалить один из этих символов.

3⃣Попробуйте оба варианта, используя checkPalindrome. Верните true, если либо checkPalindrome(s, i, j - 1), либо checkPalindrome(s, i + 1, j) возвращает true. Если мы выходим из цикла while, это значит, что исходная строка является палиндромом. Поскольку нам не нужно было использовать удаление, следует вернуть true.

😎 Решение:

public class Solution {
    private bool CheckPalindrome(string s, int i, int j) {
        while (i < j) {
            if (s[i] != s[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    
    public bool ValidPalindrome(string s) {
        int i = 0;
        int j = s.Length - 1;
        
        while (i < j) {
            if (s[i] != s[j]) {
                return CheckPalindrome(s, i, j - 1) || CheckPalindrome(s, i + 1, j);
            }
            i++;
            j--;
        }
        
        return true;
    }
}

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

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

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