C# | LeetCode

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

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

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

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