C# | LeetCode

Задача: 682. Baseball Game Сложность: medium Вы ведете учет очков в бейсбольной игре с необычными правилами. В начале игры у вас пустая запись. Вам дается список строк operations, где operations[i] — это i-я операция, которую вы должны применить к записи, и она может быть одной из следующих: Целое число x. Записать новый счет, равный x. '+'. Записать новый счет, который является суммой двух предыдущих очков. 'D'. Записать новый счет, который в два раза больше предыдущего очка. 'C'. Аннулировать предыдущее очко, удалив его из записи. Верните сумму всех очков в записи после применения всех операций. Тестовые случаи сформированы таким образом, что ответ и все промежуточные вычисления умещаются в 32-битное целое число, и что все операции корректны. Пример:

Input: ops = ["5","2","C","D","+"]
Output: 30
Explanation:
"5" - Add 5 to the record, record is now [5].
"2" - Add 2 to the record, record is now [5, 2].
"C" - Invalidate and remove the previous score, record is now [5].
"D" - Add 2 * 5 = 10 to the record, record is now [5, 10].
"+" - Add 5 + 10 = 15 to the record, record is now [5, 10, 15].
The total sum is 5 + 10 + 15 = 30.

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

public class Solution {
    public int CalPoints(string[] ops) {
        Stack<int> stack = new Stack<int>();

        foreach (string op in ops) {
            if (op == "+") {
                int top = stack.Pop();
                int newTop = top + stack.Peek();
                stack.Push(top);
                stack.Push(newTop);
            } else if (op == "C") {
                stack.Pop();
            } else if (op == "D") {
                stack.Push(2 * stack.Peek());
            } else {
                stack.Push(int.Parse(op));
            }
        }

        int ans = 0;
        foreach (int score in stack) {
            ans += score;
        }
        return ans;
    }
}

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

Задача: 246. Strobogrammatic Number Сложность: easy Дана строка num, представляющая собой целое число. Верните true, если num является стробограмматическим числом. Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами). Пример:

Input: num = "69"
Output: true

👨‍💻 Алгоритм: 1⃣Создайте новую строку, перебирая оригинальную строку num в обратном порядке. Для каждого символа проверьте, является ли он допустимым для поворота (0, 1, 6, 8, 9). Если символ недопустим (2, 3, 4, 5, 7), немедленно верните false. 2⃣Для каждого допустимого символа добавьте его соответствующее значение после поворота (0 ⟶ 0, 1 ⟶ 1, 6 ⟶ 9, 8 ⟶ 8, 9 ⟶ 6) в новую строку. 3⃣Сравните полученную строку с исходной строкой num. Если они равны, верните true, в противном случае верните false. 😎 Решение:

using System.Text;

public class Solution {
    public bool IsStrobogrammatic(string num) {
        StringBuilder rotated = new StringBuilder();
        for (int i = num.Length - 1; i >= 0; i--) {
            char c = num[i];
            if (c == '0' || c == '1' || c == '8') {
                rotated.Append(c);
            } else if (c == '6') {
                rotated.Append('9');
            } else if (c == '9') {
                rotated.Append('6');
            } else {
                return false;
            }
        }
        return num == rotated.ToString();
    }
}

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

Задача: 112. Path Sum Сложность: easy Дан корень бинарного дерева и целое число targetSum. Верните true, если в дереве существует путь от корня до листа, такой, что сумма всех значений вдоль пути равна targetSum. Лист — это узел без детей. Пример:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

👨‍💻 Алгоритм: 1⃣Инициализация стека: Начать с помещения в стек корневого узла и соответствующей оставшейся суммы, равной sum - root.val. 2⃣Обработка узлов: Извлечь текущий узел из стека и вернуть True, если оставшаяся сумма равна 0 и узел является листом. 3⃣Добавление дочерних узлов в стек: Если оставшаяся сумма не равна нулю или узел не является листом, добавить в стек дочерние узлы с соответствующими оставшимися суммами. 😎 Решение:

public class Solution {
    public bool HasPathSum(TreeNode root, int sum) {
        if (root == null)
            return false;
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<int> sumStack = new Stack<int>();
        nodeStack.Push(root);
        sumStack.Push(sum - root.val);
        while (nodeStack.Count > 0) {
            TreeNode node = nodeStack.Pop();
            int currSum = sumStack.Pop();
            if (node.left == null && node.right == null && currSum == 0)
                return true;
            if (node.left != null) {
                nodeStack.Push(node.left);
                sumStack.Push(currSum - node.left.val);
            }

            if (node.right != null) {
                nodeStack.Push(node.right);
                sumStack.Push(currSum - node.right.val);
            }
        }

        return false;
    }
}

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

Задача: 350. Intersection of Two Arrays II Сложность: easy Даны два целочисленных массива nums1 и nums2. Верните массив их пересечения. Каждый элемент в результате должен появляться столько раз, сколько он встречается в обоих массивах. Вы можете вернуть результат в любом порядке. Пример:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

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

public class Solution {
    public int[] Intersect(int[] nums1, int[] nums2) {
        Dictionary<int, int> counts = new Dictionary<int, int>();
        List<int> result = new List<int>();
        
        foreach (int num in nums1) {
            if (counts.ContainsKey(num)) {
                counts[num]++;
            } else {
                counts[num] = 1;
            }
        }
        
        foreach (int num in nums2) {
            if (counts.ContainsKey(num) && counts[num] > 0) {
                result.Add(num);
                counts[num]--;
            }
        }
        
        return result.ToArray();
    }
}

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

Задача: 165. Compare Version Numbers Сложность: medium Даны две строки версий, version1 и version2. Сравните их. Строка версии состоит из ревизий, разделенных точками '.'. Значение ревизии — это её целочисленное преобразование с игнорированием ведущих нулей. Для сравнения строк версий сравнивайте их значения ревизий в порядке слева направо. Если одна из строк версий имеет меньше ревизий, то отсутствующие значения ревизий следует считать равными 0. Верните следующее: - Если version1 < version2, верните -1. - Если version1 > version2, верните 1. - В противном случае верните 0. Пример:

Input: version1 = "1.2", version2 = "1.10"
Output: -1
Explanation:
version1's second revision is "2" and version2's second revision is "10": 2 < 10, so version1 < version2.

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

public class Solution {
    public int CompareVersion(string version1, string version2) {
        string[] nums1 = version1.Split('.');
        string[] nums2 = version2.Split('.');
        int n1 = nums1.Length, n2 = nums2.Length;
        int i1, i2;
        for (int i = 0; i < Math.Max(n1, n2); ++i) {
            i1 = i < n1 ? Int32.Parse(nums1[i]) : 0;
            i2 = i < n2 ? Int32.Parse(nums2[i]) : 0;

            if (i1 != i2)
                return i1 > i2 ? 1 : -1;
        }

        return 0;
    }
}

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

Задача: 604. Design Compressed String Iterator Сложность: easy Разработайте и реализуйте структуру данных для итератора сжатой строки. Данная сжатая строка будет в виде каждой буквы, за которой следует положительное целое число, представляющее количество этой буквы в оригинальной несжатой строке. Реализуйте класс StringIterator: - next(): Возвращает следующий символ, если в оригинальной строке еще остались несжатые символы, в противном случае возвращает пробел. - hasNext(): Возвращает true, если в оригинальной строке остались символы, которые нужно распаковать, в противном случае возвращает false. Пример:

Input
["StringIterator", "next", "next", "next", "next", "next", "next", "hasNext", "next", "hasNext"]
[["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []]
Output
[null, "L", "e", "e", "t", "C", "o", true, "d", true]

Explanation
StringIterator stringIterator = new StringIterator("L1e2t1C1o1d1e1");
stringIterator.next(); // return "L"
stringIterator.next(); // return "e"
stringIterator.next(); // return "e"
stringIterator.next(); // return "t"
stringIterator.next(); // return "C"
stringIterator.next(); // return "o"
stringIterator.hasNext(); // return True
stringIterator.next(); // return "d"
stringIterator.hasNext(); // return True

👨‍💻 Алгоритм: 1⃣Предварительная обработка Мы заранее создаем несжатую строку. Для этого проходим по данному сжатому строковому представлению и добавляем несжатые буквы для каждой сжатой буквы в результирующий строковый строитель res. Чтобы найти количество несжатых букв, мы проходим по данному сжатому строковому представлению. Когда находим букву, определяем следующее за ней число, используя десятичную арифметику. Таким образом, получаем два элемента (букву и количество), необходимые для формирования текущего фрагмента несжатой строки. 2⃣Операция next() Начинаем с проверки, есть ли еще несжатые буквы в строке. Если нет, hasNext() возвращает False, а next() возвращает пробел (' '). В противном случае возвращаем букву, на которую указывает ptr, указывающий на следующую букву для возврата. Перед возвратом буквы также обновляем ptr, чтобы указывать на следующую букву в res. 3⃣Операция hasNext() Если указатель ptr выходит за пределы массива res, это указывает на то, что больше несжатых букв нет. В этом случае возвращаем False. В противном случае возвращаем True. 😎 Решение:

public class StringIterator {
    private StringBuilder res = new StringBuilder();
    private int ptr = 0;

    public StringIterator(string s) {
        int i = 0;
        while (i < s.Length) {
            char ch = s[i++];
            int num = 0;
            while (i < s.Length && char.IsDigit(s[i])) {
                num = num * 10 + (s[i] - '0');
                i++;
            }
            for (int j = 0; j < num; j++)
                res.Append(ch);
        }
    }

    public char Next() {
        return !HasNext() ? ' ' : res[ptr++];
    }

    public bool HasNext() {
        return ptr != res.Length;
    }
}

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

Задача: 1305. All Elements in Two Binary Search Trees Сложность: medium Даны два бинарных дерева поиска root1 и root2. Вернуть список, содержащий все целые числа из обоих деревьев, отсортированные в порядке возрастания. Пример:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

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

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public IList<int> GetAllElements(TreeNode root1, TreeNode root2) {
        var stack1 = new Stack<TreeNode>();
        var stack2 = new Stack<TreeNode>();
        var output = new List<int>();

        while (root1 != null || root2 != null || stack1.Count > 0 || stack2.Count > 0) {
            while (root1 != null) {
                stack1.Push(root1);
                root1 = root1.left;
            }
            while (root2 != null) {
                stack2.Push(root2);
                root2 = root2.left;
            }
            if (stack2.Count == 0 || (stack1.Count > 0 && stack1.Peek().val <= stack2.Peek().val)) {
                root1 = stack1.Pop();
                output.Add(root1.val);
                root1 = root1.right;
            } else {
                root2 = stack2.Pop();
                output.Add(root2.val);
                root2 = root2.right;
            }
        }
        return output;
    }
}

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

Задача: 1059. All Paths from Source Lead to Destination Сложность: medium Учитывая ребра направленного графа, где edges[i] = [ai, bi] указывает на наличие ребра между вершинами ai и bi, и две вершины source и destination этого графа, определите, все ли пути, начинающиеся из source, заканчиваются в destination, то есть: существует ли хотя бы один путь из source в destination Если существует путь из source в node без исходящих ребер, то этот node равен destination. Количество возможных путей из source в destination - конечное число. Верните true тогда и только тогда, когда все пути из source ведут в destination. Пример:

Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
Output: false

👨‍💻 Алгоритм: 1⃣Построение графа и проверка путей: Построить граф на основе входных данных. Использовать поиск в глубину (DFS) для проверки наличия всех путей от вершины source до вершины destination. 2⃣Проверка конечности путей: Проверить, что из всех вершин, достижимых от source, либо исходят ребра, либо они являются вершиной destination. Убедиться, что из любой вершины, не являющейся destination, исходят хотя бы одно ребро. 3⃣Рекурсивная проверка конечности путей: Рекурсивно проверять, что все пути из source заканчиваются в destination, избегая циклов и проверяя конечность всех путей. 😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public bool LeadsToDestination(int n, int[][] edges, int source, int destination) {
        var graph = new Dictionary<int, List<int>>();
        foreach (var edge in edges) {
            if (!graph.ContainsKey(edge[0])) graph[edge[0]] = new List<int>();
            graph[edge[0]].Add(edge[1]);
        }
        
        var visited = new int[n];
        
        return Dfs(graph, visited, source, destination);
    }
    
    private bool Dfs(Dictionary<int, List<int>> graph, int[] visited, int node, int destination) {
        if (visited[node] != 0) return visited[node] == 2;
        if (!graph.ContainsKey(node)) return node == destination;
        visited[node] = 1;
        foreach (var neighbor in graph[node]) {
            if (!Dfs(graph, visited, neighbor, destination)) return false;
        }
        visited[node] = 2;
        return true;
    }
}

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

Задача: 650. 2 Keys Keyboard Сложность: medium На экране блокнота есть только один символ 'A'. Для каждого шага можно выполнить одну из двух операций над этим блокнотом: Copy All: скопировать все символы, присутствующие на экране (частичное копирование не допускается). Paste: Вы можете вставить символы, которые были скопированы в прошлый раз. Учитывая целое число n, верните минимальное количество операций, чтобы символ 'A' появился на экране ровно n раз. Пример:

Input: n = 3
Output: 3

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

public class Solution {
    public int MinSteps(int n) {
        if (n == 1) return 0;
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; j <= i / 2; j++) {
                if (i % j == 0) {
                    dp[i] = Math.Min(dp[i], dp[j] + i / j);
                }
            }
        }
        return dp[n];
    }
}

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

Задача: 372. Super Pow Сложность: medium Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива. Пример:

Input: a = 2, b = [3]
Output: 8

👨‍💻 Алгоритм: 1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди. 2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337. 3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337. 😎 Решение:

public class Solution {
    public int GetSum(int a, int b) {
        int x = System.Math.Abs(a), y = System.Math.Abs(b);
        if (x < y) return GetSum(b, a);
        int sign = a > 0 ? 1 : -1;

        if (a * b >= 0) {
            while (y != 0) {
                int carry = (x & y) << 1;
                x ^= y;
                y = carry;
            }
        } else {
            while (y != 0) {
                int borrow = ((~x) & y) << 1;
                x ^= y;
                y = borrow;
            }
        }
        return x * sign;
    }
}

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

Задача: 904. Fruit Into Baskets Сложность: medium Вы посещаете ферму, где в один ряд слева направо расположены фруктовые деревья. Деревья представлены целочисленным массивом fruits, где fruits[i] - это тип фрукта, который производит i-е дерево. Вы хотите собрать как можно больше фруктов. Однако у владельца есть строгие правила, которым вы должны следовать: у вас есть только две корзины, и каждая корзина может содержать только один тип фруктов. Количество фруктов в каждой корзине не ограничено. Начиная с любого дерева по вашему выбору, вы должны собрать ровно один фрукт с каждого дерева (включая начальное), двигаясь при этом вправо. Собранные фрукты должны поместиться в одну из ваших корзин. Как только вы достигнете дерева с фруктами, которые не могут поместиться в ваши корзины, вы должны остановиться. Учитывая целочисленный массив fruits, верните максимальное количество фруктов, которое вы можете собрать. Пример:

Input: fruits = [1,2,1]
Output: 3

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

using System;
using System.Collections.Generic;

public class Solution {
    public int TotalFruit(int[] fruits) {
        var basket = new Dictionary<int, int>();
        int left = 0, maxFruits = 0;

        for (int right = 0; right < fruits.Length; right++) {
            if (!basket.ContainsKey(fruits[right])) {
                basket[fruits[right]] = 0;
            }
            basket[fruits[right]]++;

            while (basket.Count > 2) {
                basket[fruits[left]]--;
                if (basket[fruits[left]] == 0) {
                    basket.Remove(fruits[left]);
                }
                left++;
            }

            maxFruits = Math.Max(maxFruits, right - left + 1);
        }

        return maxFruits;
    }
}

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

Задача: 340. Longest Substring with At Most K Distinct Characters Сложность: medium Дана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов. Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

👨‍💻 Алгоритм: 1⃣Инициализация Используйте два указателя (left и right) для отслеживания текущего окна в строке. Создайте словарь для отслеживания количества каждого символа в текущем окне. Инициализируйте переменные для хранения максимальной длины подстроки (max_length). 2⃣Раздвижение окна Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k. 3⃣Обновление максимальной длины На каждом шаге проверяйте и обновляйте максимальную длину подстроки, если текущее окно содержит не более k различных символов. В конце верните максимальную длину подстроки. 😎 Решение:

public class Solution {
    public int LengthOfLongestSubstringKDistinct(string s, int k) {
        int left = 0;
        int right = 0;
        Dictionary<char, int> charCount = new Dictionary<char, int>();
        int maxLength = 0;
        
        while (right < s.Length) {
            if (!charCount.ContainsKey(s[right])) {
                charCount[s[right]] = 0;
            }
            charCount[s[right]]++;
            
            while (charCount.Count > k) {
                charCount[s[left]]--;
                if (charCount[s[left]] == 0) {
                    charCount.Remove(s[left]);
                }
                left++;
            }
            maxLength = Math.Max(maxLength, right - left + 1);
            right++;
        }
        
        return maxLength;
    }
}

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

Задача: 867. Transpose Matrix Сложность: easy Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу. Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами. Пример:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]

👨‍💻 Алгоритм: 1⃣Инициализируйте новую матрицу ans с размерами C x R, где C — количество столбцов в исходной матрице, а R — количество строк. 2⃣Скопируйте каждую запись исходной матрицы в новую матрицу так, чтобы ans[c][r] = matrix[r][c]. 3⃣Верните матрицу ans. 😎 Решение:

public class Solution {
    public int[][] Transpose(int[][] A) {
        int R = A.Length, C = A[0].Length;
        int[][] ans = new int[C][];
        for (int c = 0; c < C; ++c) {
            ans[c] = new int[R];
            for (int r = 0; r < R; ++r)
                ans[c][r] = A[r][c];
        }
        return ans;
    }
}

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

Задача: 947. Most Stones Removed with Same Row or Column Сложность: medium Учитывая массив stones длины n, где stones[i] = [xi, yi] представляет местоположение i-го камня, верните наибольшее возможное количество камней, которые могут быть удалены. Пример:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

👨‍💻 Алгоритм: 1⃣Представить каждую строку и столбец как узлы в графе. 2⃣Создать связи между узлами для камней, которые находятся в той же строке или столбце. Использовать алгоритм поиска в глубину (DFS) или объединение-поиска (Union-Find), чтобы найти компоненты связности. 3⃣Количество камней, которые могут быть удалены, это общее количество камней минус количество компонентов связности. 😎 Решение:

public class Solution {
    public int RemoveStones(int[][] stones) {
        Dictionary<int, int> parent = new Dictionary<int, int>();
        
        int Find(int x) {
            if (!parent.ContainsKey(x)) parent[x] = x;
            if (parent[x] != x) parent[x] = Find(parent[x]);
            return parent[x];
        }
        
        void Union(int x, int y) {
            parent[Find(x)] = Find(y);
        }
        
        foreach (var stone in stones) {
            Union(stone[0], ~stone[1]);
        }
        
        HashSet<int> uniqueRoots = new HashSet<int>();
        foreach (var key in parent.Keys) {
            uniqueRoots.Add(Find(key));
        }
        
        return stones.Length - uniqueRoots.Count;
    }
}

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

Задача: 383. Ransom Note Сложность: easy Даны две строки ransomNote и magazine, верните true, если ransomNote можно составить, используя буквы из magazine, и false в противном случае. Каждая буква из magazine может быть использована в ransomNote только один раз. Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

public bool CanConstruct(string ransomNote, string magazine) {
    foreach (char c in ransomNote) {
        int index = magazine.IndexOf(c);
        if (index == -1) {
            return false;
        }
        magazine = magazine.Remove(index, 1);
    }
    return true;
}

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

Задача: 282. Expression Add Operators Сложность: hard Дана строка num, содержащая только цифры, и целое число target. Верните все возможные варианты вставки бинарных операторов '+', '-', и/или '*' между цифрами строки num так, чтобы результирующее выражение вычислялось в значение target. Учтите, что операнды в возвращаемых выражениях не должны содержать ведущих нулей. Пример:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

👨‍💻 Алгоритм: 1⃣Запускаем рекурсивный обход строк с учётом всех возможных разбиений чисел и вставок операторов. 2⃣Внутри рекурсии рассматривают 4 стороны: продолжить текущее число (без учета вставок оператора), вставить +, -, *. 3⃣Если дошли до конца строки и текущее значение выражения соответствует target, записываем выражение в результат. 😎 Решение:

using System;
using System.Collections.Generic;
using System.Text;

public class Solution {
    public List<string> answer;
    public string digits;
    public long target;

    public void Recurse(int index, long previousOperand, long currentOperand, long value, List<string> ops) {
        if (index == digits.Length) {
            if (value == target && currentOperand == 0) {
                StringBuilder sb = new StringBuilder();
                for (int i = 1; i < ops.Count; i++) {
                    sb.Append(ops[i]);
                }
                answer.Add(sb.ToString());
            }
            return;
        }

        currentOperand = currentOperand * 10 + (digits[index] - '0');
        string currentValRep = currentOperand.ToString();

        if (currentOperand > 0) {
            Recurse(index + 1, previousOperand, currentOperand, value, ops);
        }

        ops.Add("+");
        ops.Add(currentValRep);
        Recurse(index + 1, currentOperand, 0, value + currentOperand, ops);
        ops.RemoveAt(ops.Count - 1);
        ops.RemoveAt(ops.Count - 1);

        if (ops.Count > 0) {
            ops.Add("-");
            ops.Add(currentValRep);
            Recurse(index + 1, -currentOperand, 0, value - currentOperand, ops);
            ops.RemoveAt(ops.Count - 1);
            ops.RemoveAt(ops.Count - 1);

            ops.Add("*");
            ops.Add(currentValRep);
            Recurse(index + 1, currentOperand * previousOperand, 0, value - previousOperand + (currentOperand * previousOperand), ops);
            ops.RemoveAt(ops.Count - 1);
            ops.RemoveAt(ops.Count - 1);
        }
    }

    public IList<string> AddOperators(string num, int target) {
        if (num.Length == 0) {
            return new List<string>();
        }

        this.target = target;
        this.digits = num;
        this.answer = new List<string>();
        Recurse(0, 0, 0, 0, new List<string>());
        return answer;
    }
}

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

Задача: 733. Flood Fill Сложность: easy Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки. Пример:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

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

public class Solution {
    public int[][] FloodFill(int[][] image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        if (originalColor == color) {
            return image;
        }
        
        DFS(image, sr, sc, originalColor, color);
        return image;
    }
    
    private void DFS(int[][] image, int x, int y, int originalColor, int newColor) {
        if (x < 0 || x >= image.Length || y < 0 || y >= image[0].Length || image[x][y] != originalColor) {
            return;
        }
        image[x][y] = newColor;
        DFS(image, x + 1, y, originalColor, newColor);
        DFS(image, x - 1, y, originalColor, newColor);
        DFS(image, x, y + 1, originalColor, newColor);
        DFS(image, x, y - 1, originalColor, newColor);
    }
}

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

Задача: 371. Sum of Two Integers Сложность: medium Даны два целых числа a и b. Вернуть сумму этих двух чисел, не используя операторы + и -. Пример:

Input: a = 1, b = 2
Output: 3

👨‍💻 Алгоритм: 1⃣Упростите задачу до двух случаев: сумма или вычитание двух положительных целых чисел: x ± y, где x > y. Запомните знак результата. 2⃣Если нужно вычислить сумму: Пока перенос не равен нулю (y != 0): Текущий ответ без переноса равен XOR x и y: answer = x ^ y. Текущий перенос равен сдвинутому влево AND x и y: carry = (x & y) << 1. Подготовьтесь к следующему циклу: x = answer, y = carry. Верните x * sign. 3⃣Если нужно вычислить разность: Пока заимствование не равно нулю (y != 0): Текущий ответ без заимствования равен XOR x и y: answer = x ^ y. Текущее заимствование равно сдвинутому влево AND НЕ x и y: borrow = ((~x) & y) << 1. Подготовьтесь к следующему циклу: x = answer, y = borrow. Верните x * sign. 😎 Решение:

public class Solution {
    public int GetSum(int a, int b) {
        int x = System.Math.Abs(a), y = System.Math.Abs(b);
        if (x < y) return GetSum(b, a);
        int sign = a > 0 ? 1 : -1;

        if (a * b >= 0) {
            while (y != 0) {
                int carry = (x & y) << 1;
                x ^= y;
                y = carry;
            }
        } else {
            while (y != 0) {
                int borrow = ((~x) & y) << 1;
                x ^= y;
                y = borrow;
            }
        }
        return x * sign;
    }
}

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

Задача: 1275. Find Winner on a Tic Tac Toe Game Сложность: easy В игру "Крестики-нолики" играют два игрока A и B на сетке 3 x 3. Правила игры "Крестики-нолики" таковы: игроки по очереди помещают символы в пустые квадраты ' '. Первый игрок A всегда помещает символы "X", а второй игрок B - "O". Символы "X" и "O" всегда помещаются в пустые квадраты, а не в заполненные. Игра заканчивается, когда три одинаковых (непустых) символа заполняют любую строку, столбец или диагональ. Игра также заканчивается, если все клетки непустые. Больше ходов не может быть сыграно, если игра закончена. Учитывая двумерный целочисленный массив moves, где moves[i] = [rowi, coli] указывает, что i-й ход будет сыгран на сетке[rowi][coli]. верните победителя игры, если он существует (A или B). Если игра закончилась вничью, верните "Ничья". Если еще есть ходы для игры, верните "Pending". Можно предположить, что ходы действительны (т.е. соответствуют правилам игры в Крестики-нолики), сетка изначально пуста, и A будет играть первым. Пример:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"

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

public class Solution {
    public string Tictactoe(int[][] moves) {
        char[,] grid = new char[3,3];
        for (int i = 0; i < moves.Length; i++) {
            grid[moves[i][0], moves[i][1]] = (i % 2 == 0) ? 'X' : 'O';
        }

        for (int i = 0; i < 3; i++) {
            if (grid[i, 0] == grid[i, 1] && grid[i, 1] == grid[i, 2] && grid[i, 0] != '\0')
                return grid[i, 0] == 'X' ? "A" : "B";
            if (grid[0, i] == grid[1, i] && grid[1, i] == grid[2, i] && grid[0, i] != '\0')
                return grid[0, i] == 'X' ? "A" : "B";
        }

        if (grid[0, 0] == grid[1, 1] && grid[1, 1] == grid[2, 2] && grid[0, 0] != '\0')
            return grid[0, 0] == 'X' ? "A" : "B";
        if (grid[0, 2] == grid[1, 1] && grid[1, 1] == grid[2, 0] && grid[0, 2] != '\0')
            return grid[0, 2] == 'X' ? "A" : "B";

        return moves.Length == 9 ? "Draw" : "Pending";
    }
}

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

Задача: 368. Largest Divisible Subset Сложность: medium Дан набор различных положительных целых чисел nums. Вернуть наибольшее подмножество answer, такое что каждая пара (answer[i], answer[j]) элементов в этом подмножестве удовлетворяет условию: answer[i] % answer[j] == 0, или answer[j] % answer[i] == 0 Если существует несколько решений, вернуть любое из них. Пример:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

👨‍💻 Алгоритм: 1⃣Если число 8 может быть разделено на элемент X_i, то добавив число 8 к EDS(X_i), мы получим еще одно делимое подмножество, которое заканчивается на 8, согласно нашему следствию I. И это новое подмножество является потенциальным значением для EDS(8). Например, поскольку 8 % 2 == 0, то {2,8} может быть конечным значением для EDS(8), и аналогично для подмножества {2,4,8}, полученного из EDS(4). 2⃣Если число 8 не может быть разделено на элемент X_i, то можно быть уверенным, что значение EDS(X_i) не повлияет на EDS(8), согласно определению делимого подмножества. Например, подмножество EDS(7)={7} не имеет влияния на EDS(8). 3⃣Затем мы выбираем наибольшие новые подмножества, которые мы формируем с помощью EDS(X_i). В частности, подмножество {8} является допустимым кандидатом для EDS(8). И в гипотетическом случае, когда 8 не может быть разделено ни на один из предыдущих элементов, мы бы имели EDS(8)={8}. 😎 Решение:

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

public class Solution {
    public IList<int> LargestDivisibleSubset(int[] nums) {
        int n = nums.Length;
        if (n == 0) return new List<int>();

        Array.Sort(nums);
        List<List<int>> EDS = new List<List<int>>(new List<int>[n]);
        for (int i = 0; i < n; i++) {
            EDS[i] = new List<int>();
        }

        for (int i = 0; i < n; i++) {
            List<int> maxSubset = new List<int>();
            for (int k = 0; k < i; k++) {
                if (nums[i] % nums[k] == 0 && maxSubset.Count < EDS[k].Count) {
                    maxSubset = EDS[k];
                }
            }
            EDS[i] = new List<int>(maxSubset);
            EDS[i].Add(nums[i]);
        }

        List<int> ret = new List<int>();
        foreach (var subset in EDS) {
            if (ret.Count < subset.Count) {
                ret = subset;
            }
        }
        return ret;
    }
}

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