C# | LeetCode

Задача: 945. Minimum Increment to Make Array Unique Сложность: medium Вам дан целочисленный массив nums. За один ход вы можете выбрать индекс i, где 0 <= i < nums.length, и увеличить nums[i] на 1. Верните минимальное количество ходов, чтобы каждое значение в nums было уникальным. Тестовые примеры генерируются так, чтобы ответ умещался в 32-битное целое число. Пример:

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

👨‍💻 Алгоритм: 1⃣Отсортировать массив nums. Инициализировать переменную moves для подсчета количества ходов. 2⃣Пройти по массиву и для каждого элемента, начиная со второго: Если текущий элемент меньше или равен предыдущему элементу, увеличить текущий элемент до значения предыдущего элемента + 1 и обновить счетчик ходов. 3⃣Вернуть общее количество ходов. 😎 Решение:

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

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

Задача: 1518. Water Bottles Сложность: easy Есть numBottles бутылок с водой, которые изначально наполнены водой. Вы можете обменять numExchange пустых бутылок на одну полную бутылку воды на рынке. Операция питья полной бутылки воды превращает её в пустую бутылку. Даны два целых числа numBottles и numExchange. Верните максимальное количество бутылок с водой, которые вы можете выпить. Пример:

    
        Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.{}
    

👨‍💻 Алгоритм: 1⃣Инициализируйте переменную ответа consumedBottles значением 0. 2⃣Продолжайте выполнять следующие действия, пока количество numBottles больше или равно numExchange: — Выпейте numExchange количество полных бутылок, т.е. добавьте numExchange к consumedBottles. — Уменьшите numExchange от доступных полных бутылок numBottles. — Обменяйте пустые бутылки на одну полную бутылку, т.е. увеличьте numBottles на одну. 3⃣Верните consumedBottles + numBottles. 😎 Решение:

    
        public class Solution {
    public int NumWaterBottles(int numBottles, int numExchange) {
        int consumedBottles = 0;

        while (numBottles >= numExchange) {
            consumedBottles += numExchange;
            numBottles -= numExchange;
            numBottles++;
        }

        return consumedBottles + numBottles;
    }
}{}
    

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

Задача: 1051. Height Checker Сложность: easy Школа пытается сделать ежегодную фотографию всех учеников. Учеников просят встать в одну шеренгу в неубывающем порядке по росту. Пусть этот порядок представлен целочисленным массивом expected, где expected[i] - ожидаемый рост i-го студента в очереди. Вам дан целочисленный массив heights, представляющий текущий порядок, в котором стоят студенты. Каждый heights[i] - это высота i-го студента в очереди (с индексом 0). Верните количество индексов, в которых heights[i] != expected[i]. Пример:

    
        Input: heights = [1,1,4,2,1,3]
Output: 3{}
    

👨‍💻 Алгоритм: 1⃣Создай отсортированную копию массива heights, чтобы получить ожидаемый порядок высот. 2⃣Пройди по обоим массивам и сравни элементы. 3⃣Подсчитай количество индексов, где элементы двух массивов не равны 😎 Решение:

    
        public class Solution {
    public int HeightChecker(int[] heights) {
        int[] expected = (int[])heights.Clone();
        Array.Sort(expected);
        int count = 0;
        for (int i = 0; i < heights.Length; i++) {
            if (heights[i] != expected[i]) {
                count++;
            }
        }
        return count;
    }
}{}
    

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

Задача: 409. Longest Palindrome Сложность: easy Если задана строка s, состоящая из строчных или прописных букв, верните длину самого длинного палиндрома, который можно построить из этих букв. Буквы чувствительны к регистру, например, "Aa" не считается палиндромом. Пример:

    
        Input: s = "abccccdd"
Output: 7{}
    

👨‍💻 Алгоритм: 1⃣Создайте словарь для подсчета количества каждого символа в строке. 2⃣Пройдитесь по словарю и добавьте четное количество каждого символа к длине палиндрома. Если встречается нечетное количество символа, добавьте (count - 1) к длине палиндрома. 3⃣Если есть хотя бы один символ с нечетным количеством, добавьте 1 к длине палиндрома для центрального символа. 😎 Решение:

    
        using System.Collections.Generic;

public class Solution {
    public int LongestPalindrome(string s) {
        Dictionary<char, int> charCount = new Dictionary<char, int>();
        foreach (char c in s) {
            if (charCount.ContainsKey(c)) {
                charCount[c]++;
            } else {
                charCount[c] = 1;
            }
        }
        int length = 0;
        bool oddFound = false;
        foreach (int count in charCount.Values) {
            if (count % 2 == 0) {
                length += count;
            } else {
                length += count - 1;
                oddFound = true;
            }
        }
        return oddFound ? length + 1 : length;
    }
}{}
    

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

Задача: 131. Palindrome Partitioning Сложность: medium Дана строка s. Разделите строку таким образом, чтобы каждая подстрока разделения была палиндромом. Верните все возможные варианты разделения строки s на палиндромы. Пример:

    
        Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]{}
    

👨‍💻 Алгоритм: 1⃣Инициация рекурсивного обхода: В алгоритме обратного отслеживания (backtracking) мы рекурсивно пробегаем по строке, используя метод поиска в глубину (depth-first search). Для каждого рекурсивного вызова задаётся начальный индекс строки start. Итеративно генерируем все возможные подстроки, начиная с индекса start. Индекс end увеличивается от start до конца строки. 2⃣Проверка на палиндром и продолжение поиска: Для каждой сгенерированной подстроки проверяем, является ли она палиндромом. Если подстрока оказывается палиндромом, она становится потенциальным кандидатом. Добавляем подстроку в currentList и выполняем поиск в глубину для оставшейся части строки. Если текущая подстрока заканчивается на индексе end, то end+1 становится начальным индексом для следующего рекурсивного вызова. 3⃣Возврат (Backtracking) и сохранение результатов: Возвращаемся, если начальный индекс start больше или равен длине строки, и добавляем currentList в результат. 😎 Решение:

    
        public class Solution {
    public IList<IList<string>> Partition(string s) {
        var ans = new List<IList<string>>();
        Dfs(0, new List<string>(), s, ans);
        return ans;
    }

    private void Dfs(int start, List<string> currentList, string s,
                     List<IList<string>> result) {
        if (start >= s.Length)
            result.Add(new List<string>(currentList));
        else {
            for (int end = start; end < s.Length; end++) {
                if (IsPalindrome(s, start, end)) {
                    currentList.Add(s.Substring(start, end - start + 1));
                    Dfs(end + 1, currentList, s, result);
                    currentList.RemoveAt(currentList.Count - 1);
                }
            }
        }
    }

    bool IsPalindrome(string s, int low, int high) {
        while (low < high)
            if (s[low++] != s[high--])
                return false;
        return true;
    }
}{}
    

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

Задача: 647. Palindromic Substrings Сложность: medium Если задана строка s, верните количество палиндромных подстрок в ней. Строка является палиндромом, если она читается так же, как задом наперед. Подстрока - это непрерывная последовательность символов в строке. Пример:

    
        Input: s = "abc"
Output: 3{}
    

👨‍💻 Алгоритм: 1⃣Инициализируйте счетчик для подсчета палиндромных подстрок. 2⃣Для каждой позиции в строке используйте два метода расширения: один для палиндромов нечетной длины и один для палиндромов четной длины. 3⃣Расширяйте от центра, проверяя, является ли подстрока палиндромом, и увеличивайте счетчик, если условие выполняется. 😎 Решение:

    
        public class Solution {
    public int CountSubstrings(string s) {
        int totalCount = 0;

        for (int i = 0; i < s.Length; i++) {
            totalCount += ExpandAroundCenter(s, i, i);
            totalCount += ExpandAroundCenter(s, i, i + 1);
        }

        return totalCount;
    }

    private int ExpandAroundCenter(string s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.Length && s[left] == s[right]) {
            count++;
            left--;
            right++;
        }
        return count;
    }
}{}
    

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

Задача: 188. Best Time to Buy and Sell Stock IV Сложность: hard Дан массив целых чисел prices, где prices[i] - это цена данной акции в i-й день, и целое число k. Найдите максимальную прибыль, которую вы можете получить. Вы можете завершить не более чем k транзакций, т.е. вы можете купить не более k раз и продать не более k раз. Обратите внимание: Вы не можете участвовать в нескольких транзакциях одновременно (т.е., вы должны продать акцию, прежде чем снова купить). Пример:

    
        Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.{}
    

👨‍💻 Алгоритм: 1⃣Инициализация DP массива: Инициализируйте трехмерный массив dp, где dp[i][j][l] представляет максимальную прибыль на конец i-го дня с j оставшимися транзакциями и l акциями в портфеле. Начните с dp[0][0][0] = 0 (нет прибыли без акций и транзакций) и dp[0][1][1] = -prices[0] (покупка первой акции). 2⃣Вычисление переходов: Для каждого дня и каждого возможного количества транзакций вычислите возможные действия: держать акцию, не держать акцию, купить акцию, если j > 0, или продать акцию. Обновляйте dp с использованием: dp[i][j][1] = max(dp[i−1][j][1], dp[i−1][j−1][0] - prices[i]) (максимум между удержанием акции и покупкой новой). dp[i][j][0] = max(dp[i−1][j][0], dp[i−1][j][1] + prices[i]) (максимум между неудержанием акции и продажей). 3⃣Расчет результатов: По завершении всех дней, возвращайте максимальное значение dp[n-1][j][0] для всех j от 0 до k, что представляет максимальную прибыль без удержания акций на последний день. Обработайте специальный случай, когда 𝑘×2≥𝑛, чтобы избежать лишних расчетов. 😎 Решение:

    
        public class Solution {
    public int MaxProfit(int k, int[] prices) {
        int n = prices.Length;
        if (n == 0 || k == 0) return 0;
        if (k * 2 >= n) {
            int res = 0;
            for (int i = 1; i < n; i++)
                res += Math.Max(0, prices[i] - prices[i - 1]);
            return res;
        }

        var dp = new int[n, k + 1, 2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i, j, 0] = Int32.MinValue / 2;
                dp[i, j, 1] = Int32.MinValue / 2;
            }
        }
        dp[0, 0, 0] = 0;
        dp[0, 1, 1] = -prices[0];

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i, j, 0] = Math.Max(dp[i - 1, j, 0], dp[i - 1, j, 1] + prices[i]);
                if (j > 0)
                    dp[i, j, 1] = Math.Max(dp[i - 1, j, 1], dp[i - 1, j - 1, 0] - prices[i]);
            }
        }
        int res = 0;
        for (int j = 0; j <= k; j++)
            res = Math.Max(res, dp[n - 1, j, 0]);
        return res;
    }
}{}
    

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

Задача: 520. Detect Capital Сложность: easy Мы определяем правильное использование заглавных букв в слове, когда выполняется одно из следующих условий: Все буквы в этом слове заглавные, как "USA". Все буквы в этом слове строчные, как "leetcode". Только первая буква в этом слове заглавная, как "Google". Дана строка word. Верните true, если использование заглавных букв в ней правильное. Пример:

    
        Input: word = "USA"
Output: true{}
    

👨‍💻 Алгоритм: 1⃣Шаблон для первого случая в регулярном выражении: [A-Z]*, где [A-Z] соответствует одной заглавной букве от 'A' до 'Z', а * означает повторение предыдущего шаблона 0 или более раз. Этот шаблон представляет "Все заглавные буквы". 2⃣Шаблон для второго случая в регулярном выражении: [a-z]*, где [a-z] соответствует одной строчной букве от 'a' до 'z'. Этот шаблон представляет "Все строчные буквы". Шаблон для третьего случая в регулярном выражении: [A-Z][a-z]*, где первая буква заглавная, а остальные строчные. 3⃣Объедините эти три шаблона: [A-Z]*|[a-z]*|[A-Z][a-z]*, где | означает "или". Мы можем объединить второй и третий случай, получив . [a-z]*, где . соответствует любому символу. Итоговый шаблон: [A-Z]*|.[a-z]*. 😎 Решение:

    
        using System.Text.RegularExpressions;

public class Solution {
    public bool DetectCapitalUse(string word) {
        string pattern = @"[A-Z]*|.[a-z]*";
        return Regex.IsMatch(word, pattern);
    }
}{}
    

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

Задача: 908. Smallest Range I Сложность: easy Вам дан целочисленный массив nums и целое число k. За одну операцию вы можете выбрать любой индекс i, где 0 <= i < nums.length, и изменить nums[i] на nums[i] + x, где x - целое число из диапазона [-k, k]. Эту операцию можно применять не более одного раза для каждого индекса i. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после применения указанной операции не более одного раза для каждого индекса в нем. Пример:

    
        Input: nums = [1], k = 0
Output: 0{}
    

👨‍💻 Алгоритм: 1⃣Найти минимальное и максимальное значения массива nums. 2⃣Рассчитать потенциальные новые минимальные и максимальные значения после применения операции. 3⃣Вычислить минимальную оценку, сравнивая разницу между всеми возможными новыми минимальными и максимальными значениями. 😎 Решение:

    
        public class Solution {
    public int SmallestRangeI(int[] nums, int k) {
        int minVal = int.MaxValue;
        int maxVal = int.MinValue;
        foreach (int num in nums) {
            if (num < minVal) minVal = num;
            if (num > maxVal) maxVal = num;
        }
        return Math.Max(0, (maxVal - k) - (minVal + k));
    }
}{}
    

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

Задача: 1150. Check If a Number Is Majority Element in a Sorted Array Сложность: easy Дан целочисленный массив nums, отсортированный в неубывающем порядке, и целое число target. Верните true, если target является элементом большинства, или false в противном случае. Элемент большинства в массиве nums — это элемент, который встречается в массиве более чем nums.length / 2 раз. Пример:

    
        Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation: The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.{}
    

👨‍💻 Алгоритм: 1⃣Инициализация переменной count: Инициализируйте переменную count значением 0.. 2⃣Итерация по списку nums: Пройдите по каждому элементу списка nums. Если элемент num равен target, увеличьте значение переменной count. 3⃣Проверка условия мажоритарного элемента: Если count больше чем половина длины списка nums, верните true. В противном случае верните false. 😎 Решение:

    
        public class Solution {
    public bool IsMajorityElement(int[] nums, int target) {
        int count = 0;
        foreach (int num in nums) {
            if (num == target) {
                count++;
            }
        }
        return count > nums.Length / 2;
    }
}{}
    

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