C# | LeetCode

#medium Задача: 654. Maximum Binary Tree Вам дан целочисленный массив nums без дубликатов. Из nums можно рекурсивно построить максимальное двоичное дерево, используя следующий алгоритм: создайте корневой узел, значение которого равно максимальному значению в nums. Рекурсивно постройте левое поддерево по префиксу подмассива слева от максимального значения. Рекурсивно постройте правое поддерево по суффиксу подмассива справа от максимального значения. Верните максимальное двоичное дерево, построенное из nums. Пример:

Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]

👨‍💻 Алгоритм: 1⃣Найдите максимальное значение в текущем подмассиве и создайте узел с этим значением. 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 {
    public TreeNode ConstructMaximumBinaryTree(int[] nums) {
        return Build(nums, 0, nums.Length);
    }

    private TreeNode Build(int[] nums, int l, int r) {
        if (l == r) return null;
        int maxIndex = Max(nums, l, r);
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = Build(nums, l, maxIndex);
        root.right = Build(nums, maxIndex + 1, r);
        return root;
    }

    private int Max(int[] nums, int l, int r) {
        int maxIndex = l;
        for (int i = l + 1; i < r; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}

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

#medium Задача: 655. Print Binary Tree Учитывая корень двоичного дерева, постройте строковую матрицу 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;
    }
}

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

#hard Задача: 656. Coin Path Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y. Пример:

Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]

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

using System;
using System.Collections.Generic;

public class Solution {
    public List<int> MinCostPath(int[] coins, int maxJump) {
        int n = coins.Length;
        if (coins[0] == -1) return new List<int>();
        
        int[] dp = new int[n];
        Array.Fill(dp, int.MaxValue);
        dp[0] = coins[0];
        List<int>[] path = new List<int>[n];
        for (int i = 0; i < n; i++) path[i] = new List<int>();
        path[0].Add(1);
        
        PriorityQueue<(int cost, int index), int> heap = new PriorityQueue<(int, int), int>();
        heap.Enqueue((coins[0], 0), coins[0]);
        
        while (heap.Count > 0) {
            var (currentCost, i) = heap.Dequeue();
            if (currentCost > dp[i]) continue;
            for (int k = 1; k <= maxJump; k++) {
                if (i + k < n && coins[i + k] != -1) {
                    int newCost = currentCost + coins[i + k];
                    if (newCost < dp[i + k] || (newCost == dp[i + k] && ComparePaths(path[i], path[i + k], i + k + 1))) {
                        dp[i + k] = newCost;
                        path[i + k] = new List<int>(path[i]);
                        path[i + k].Add(i + k + 1);
                        heap.Enqueue((newCost, i + k), newCost);
                    }
                }
            }
        }
        
        return dp[n - 1] == int.MaxValue ? new List<int>() : path[n - 1];
    }

    private bool ComparePaths(List<int> path1, List<int> path2, int newIndex) {
        List<int> newPath1 = new List<int>(path1);
        newPath1.Add(newIndex);
        return string.Join(",", newPath1).CompareTo(string.Join(",", path2)) < 0;
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        int[] coins = { 0, 2, 4, -1, 2, 5 };
        int maxJump = 2;
        var result = solution.MinCostPath(coins, maxJump);
    }
}

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

#medium Задача: 646. Maximum Length of Pair Chain Вам дан массив из n пар, где pairs[i] = [lefti, righti] и lefti < righti. Пара p2 = [c, d] следует за парой p1 = [a, b], если b < c. Таким образом можно построить цепочку пар. Верните самую длинную цепочку, которую можно составить. Вам не нужно использовать все заданные интервалы. Вы можете выбирать пары в любом порядке. Пример:

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

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

public class Solution {
    public int FindLongestChain(int[][] pairs) {
        Array.Sort(pairs, (a, b) => a[1] - b[1]);
        int currentEnd = int.MinValue;
        int count = 0;
        foreach (var pair in pairs) {
            if (currentEnd < pair[0]) {
                currentEnd = pair[1];
                count++;
            }
        }
        return count;
    }
}

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

#easy Задача: 645. Set Mismatch У вас есть набор целых чисел s, который изначально содержит все числа от 1 до n. К сожалению, из-за какой-то ошибки одно из чисел в s продублировалось в другое число в наборе, что привело к повторению одного числа и потере другого. Вам дан целочисленный массив nums, представляющий состояние данных в этом наборе после ошибки. Найдите число, которое встречается дважды, и число, которое отсутствует, и верните их в виде массива. Пример:

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

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

public class Solution {
    public int[] FindErrorNums(int[] nums) {
        int n = nums.Length;
        HashSet<int> numSet = new HashSet<int>();
        int duplicate = -1;
        foreach (int num in nums) {
            if (!numSet.Add(num)) {
                duplicate = num;
            }
        }
        int missing = (n * (n + 1)) / 2 - numSet.Sum();
        return new int[] { duplicate, missing };
    }
}

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

– Помощь с pet-проектом – Составление roadmap – Общая консультация – Проведение код-ревью и mock-собеседования – Помощь с трудоустройством Все это и многое другое может Ментор. Он обеспечит вам необходимый boost, ускорит и упростит вход в IT. 🔥 Здесь размещен список менторов, и многие из них предлагают бесплатную первую консультацию

#hard Задача: 644. Maximum Average Subarray II Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого больше или равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5. Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000

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

public class Solution {
    public double FindMaxAverage(int[] nums, int k) {
        int currSum = nums.Take(k).Sum();
        int maxSum = currSum;
        for (int i = k; i < nums.Length; i++) {
            currSum += nums[i] - nums[i - k];
            if (currSum > maxSum) {
                maxSum = currSum;
            }
        }
        return (double)maxSum / k;
    }
}

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

#easy Задача: 643. Maximum Average Subarray I Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5. Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000

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

public class Solution {
    public double FindMaxAverage(int[] nums, int k) {
        int currentSum = 0;
        for (int i = 0; i < k; i++) {
            currentSum += nums[i];
        }
        int maxSum = currentSum;
        
        for (int i = k; i < nums.Length; i++) {
            currentSum += nums[i] - nums[i - k];
            maxSum = Math.Max(maxSum, currentSum);
        }
        
        return (double)maxSum / k;
    }
}

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

#hard Задача: 568. Maximum Vacation Days LeetCode хочет предоставить одному из своих лучших сотрудников возможность путешествовать по n городам для сбора задач по алгоритмам. Однако, как говорится, "делу время, потехе час". Вы можете брать отпуска в некоторых конкретных городах и неделях. Ваша задача — спланировать поездку, чтобы максимально увеличить количество дней отпуска, которые вы сможете взять, соблюдая при этом определенные правила и ограничения. Правила и ограничения: Вы можете путешествовать только между n городами, обозначенными индексами от 0 до n-1. Изначально вы находитесь в городе с индексом 0 в понедельник. Города связаны рейсами. Рейсы представлены матрицей n x n, называемой flights, представляющей статус авиалинии от города i до города j. Если рейса из города i в город j нет, flights[i][j] == 0; иначе flights[i][j] == 1. Также для всех i выполняется flights[i][i] == 0. У вас есть k недель (каждая неделя состоит из семи дней) для путешествий. Вы можете летать не более одного раза в день и можете летать только утром каждого понедельника. Время полета настолько короткое, что его влияние не учитывается. Для каждого города у вас есть ограниченные дни отпуска в разные недели, заданные матрицей n x k, называемой days. Значение days[i][j] представляет максимальное количество дней отпуска, которые вы можете взять в городе i на неделе j. Даны две матрицы flights и days, верните максимальное количество дней отпуска, которые вы можете взять в течение k недель. Пример:

Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation:
One of the best strategies is:
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day.
(Although you start at city 0, we could also fly to and start at other cities since it is Monday.)
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week : stay at city 2, and play 3 days and work 4 days.
Ans = 6 + 3 + 3 = 12.

👨‍💻 Алгоритм: 1⃣Использовать функцию dfs (поиск в глубину), которая возвращает количество отпускных дней, которые можно взять, начиная с текущего города cur_city и текущей недели weekno. В каждом вызове функции проходить по всем городам и находить все города, которые связаны с текущим городом. Такой город обозначен 1 в соответствующей позиции flights[cur_city][i]. 2⃣Для текущего города можно либо остаться в нем, либо поехать в связанный город. Обозначим город, в который меняется расположение, как j. После смены города нужно найти количество отпускных дней, которые можно взять, начиная с нового города и с новой недели. Это количество отпускных дней можно представить как: days[j][weekno] + dfs(flights, days, j, weekno + 1). 3⃣Для текущего города необходимо найти максимальное количество отпускных дней, выбирая различные города в качестве следующего местоположения. Из всех вариантов отпускных дней выбираем максимальное значение, которое и будет возвращено для каждого вызова функции dfs. 😎 Решение:

public class Solution {
    public int MaxVacationDays(int[][] flights, int[][] days) {
        int n = flights.Length, k = days[0].Length;
        int[][] memo = new int[n][];
        for (int i = 0; i < n; i++) {
            memo[i] = new int[k];
            Array.Fill(memo[i], -1);
        }
        return Dfs(flights, days, memo, 0, 0);
    }

    private int Dfs(int[][] flights, int[][] days, int[][] memo, int curCity, int weekNo) {
        int n = flights.Length, k = days[0].Length;
        if (weekNo == k) return 0;
        if (memo[curCity][weekNo] != -1) return memo[curCity][weekNo];
        int maxVac = 0;
        for (int nextCity = 0; nextCity < n; nextCity++) {
            if (curCity == nextCity || flights[curCity][nextCity] == 1) {
                maxVac = Math.Max(maxVac, days[nextCity][weekNo] + Dfs(flights, days, memo, nextCity, weekNo + 1));
            }
        }
        memo[curCity][weekNo] = maxVac;
        return maxVac;
    }
}

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

📺 Уникальная база IT собеседований 370+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

#medium Задача: 641. Design Circular Deque Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае. Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

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

public class MyCircularDeque {
    private int[] deque;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    public MyCircularDeque(int k) {
        capacity = k;
        deque = new int[k];
        front = 0;
        rear = 0;
        size = 0;
    }

    public bool InsertFront(int value) {
        if (IsFull()) return false;
        front = (front - 1 + capacity) % capacity;
        deque[front] = value;
        size++;
        return true;
    }

    public bool InsertLast(int value) {
        if (IsFull()) return false;
        deque[rear] = value;
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }

    public bool DeleteFront() {
        if (IsEmpty()) return false;
        front = (front + 1) % capacity;
        size--;
        return true;
    }

    public bool DeleteLast() {
        if (IsEmpty()) return false;
        rear = (rear - 1 + capacity) % capacity;
        size--;
        return true;
    }

    public int GetFront() {
        if (IsEmpty()) return -1;
        return deque[front];
    }

    public int GetRear() {
        if (IsEmpty()) return -1;
        return deque[(rear - 1 + capacity) % capacity];
    }

    public bool IsEmpty() {
        return size == 0;
    }

    public bool IsFull() {
        return size == capacity;
    }
}

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

#medium Задача: 567. Permutation in String Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае. Другими словами, верните true, если одна из перестановок s1 является подстрокой s2. Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

👨‍💻 Алгоритм: 1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2. 2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1. 3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false. 😎 Решение:

public class Solution {
    public bool CheckInclusion(string s1, string s2) {
        int s1Len = s1.Length, s2Len = s2.Length;
        if (s1Len > s2Len) return false;
        
        int[] s1Count = new int[26];
        int[] s2Count = new int[26];
        
        for (int i = 0; i < s1Len; i++) {
            s1Count[s1[i] - 'a']++;
            s2Count[s2[i] - 'a']++;
        }
        
        for (int i = 0; i < s2Len - s1Len; i++) {
            if (s1Count.SequenceEqual(s2Count)) return true;
            s2Count[s2[i] - 'a']--;
            s2Count[s2[i + s1Len] - 'a']++;
        }
        
        return s1Count.SequenceEqual(s2Count);
    }
}

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

#easy Задача: 566. Reshape the Matrix В MATLAB есть удобная функция под названием reshape, которая может преобразовать матрицу размером m x n в новую матрицу с другим размером r x c, сохраняя исходные данные. Вам дана матрица m x n mat и два целых числа r и c, представляющие количество строк и столбцов желаемой преобразованной матрицы. Преобразованная матрица должна быть заполнена всеми элементами исходной матрицы в том же порядке обхода строк, в котором они были. Если операция преобразования с заданными параметрами возможна и допустима, выведите новую преобразованную матрицу; в противном случае выведите исходную матрицу. Пример:

Input: mat = [[1,2],[3,4]], r = 1, c = 4
Output: [[1,2,3,4]]

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

public class Solution {
    public int[][] MatrixReshape(int[][] mat, int r, int c) {
        int m = mat.Length, n = mat[0].Length;
        if (m * n != r * c) {
            return mat;
        }
        int[][] reshapedMatrix = new int[r][];
        for (int i = 0; i < r; i++) {
            reshapedMatrix[i] = new int[c];
        }
        int row = 0, col = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                reshapedMatrix[row][col] = mat[i][j];
                col++;
                if (col == c) {
                    col = 0;
                    row++;
                }
            }
        }
        return reshapedMatrix;
    }
}

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

#medium Задача: 640. Solve the Equation Решите заданное уравнение и верните значение 'x' в виде строки "x=#value". Уравнение содержит только операции '+', '-', переменную 'x' и ее коэффициент. Вы должны вернуть "No solution", если для уравнения нет решения, или "Infinite solutions", если для уравнения существует бесконечное количество решений. Если для уравнения существует ровно одно решение, мы убеждаемся, что значение 'x' является целым числом. Пример:

Input: s = "*"
Output: 9

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

using System;
using System.Text.RegularExpressions;

public class Solution {
    public string SolveEquation(string equation) {
        string[] sides = equation.Split('=');
        int[] left = Parse(sides[0]);
        int[] right = Parse(sides[1]);
        
        int coeff = left[0] - right[0];
        int constPart = right[1] - left[1];
        
        if (coeff == 0) {
            return constPart == 0 ? "Infinite solutions" : "No solution";
        }
        return "x=" + (constPart / coeff);
    }

    private int[] Parse(string s) {
        int coeff = 0, constPart = 0, sign = 1, num = 0;
        int i = 0;
        while (i < s.Length) {
            if (s[i] == '+') {
                sign = 1;
                i++;
            } else if (s[i] == '-') {
                sign = -1;
                i++;
            } else if (char.IsDigit(s[i])) {
                num = 0;
                while (i < s.Length && char.IsDigit(s[i])) {
                    num = num * 10 + (s[i] - '0');
                    i++;
                }
                if (i < s.Length && s[i] == 'x') {
                    coeff += sign * num;
                    i++;
                } else {
                    constPart += sign * num;
                }
            } else if (s[i] == 'x') {
                coeff += sign;
                i++;
            }
        }
        return new int[]{coeff, constPart};
    }
}

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

#hard Задача: 639. Decode Ways II Сообщение, содержащее буквы от A-Z, может быть закодировано в цифры с помощью следующего отображения: 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" Чтобы декодировать закодированное сообщение, все цифры должны быть сгруппированы, а затем снова преобразованы в буквы с помощью обратного отображения (может быть несколько способов). Например, "11106" может быть преобразовано в: "AAJF" с группировкой (1 1 10 6) "KJF" с группировкой (11 10 6) Обратите внимание, что группировка (1 11 06) недействительна, поскольку "06" не может быть преобразовано в "F", так как "6" отличается от "06". В дополнение к вышеуказанным преобразованиям кодированное сообщение может содержать символ "*", который может представлять любую цифру от "1" до "9" ("0" исключается). Например, кодированное сообщение "1*" может представлять любое из кодированных сообщений "11", "12", "13", "14", "15", "16", "17", "18" или "19". Декодирование "1*" эквивалентно декодированию любого из кодированных сообщений, которые оно может представлять. Если задана строка s, состоящая из цифр и символов '*', верните количество способов ее декодирования. Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Пример:

Input: s = "*"
Output: 9

👨‍💻 Алгоритм: 1⃣Инициализация Создайте массив dp, где dp[i] представляет количество способов декодирования подстроки s[0:i]. Установите начальные значения dp[0] = 1 (пустая строка имеет один способ декодирования). 2⃣Обход строки Используйте цикл для обхода строки и вычисления количества способов декодирования для каждого символа, включая обработку символа '*'. 3⃣Модульное вычисление Поскольку количество способов декодирования может быть большим, вычисляйте результаты по модулю 10^9 + 7. 😎 Решение:

using System;

public class Solution {
    public int NumDecodings(string s) {
        const int MOD = 1000000007;
        int n = s.Length;
        long[] dp = new long[n + 1];
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            if (s[i - 1] == '*') {
                dp[i] = 9 * dp[i - 1];
            } else if (s[i - 1] != '0') {
                dp[i] = dp[i - 1];
            }

            if (i > 1) {
                if (s[i - 2] == '*') {
                    if (s[i - 1] == '*') {
                        dp[i] += 15 * dp[i - 2];
                    } else if (s[i - 1] <= '6') {
                        dp[i] += 2 * dp[i - 2];
                    } else {
                        dp[i] += dp[i - 2];
                    }
                } else if (s[i - 2] == '1') {
                    if (s[i - 1] == '*') {
                        dp[i] += 9 * dp[i - 2];
                    } else {
                        dp[i] += dp[i - 2];
                    }
                } else if (s[i - 2] == '2') {
                    if (s[i - 1] == '*') {
                        dp[i] += 6 * dp[i - 2];
                    } else if (s[i - 1] <= '6') {
                        dp[i] += dp[i - 2];
                    }
                }
            }

            dp[i] %= MOD;
        }

        return (int)dp[n];
    }
}

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

#medium Задача: 638. Shopping Offers В магазине LeetCode Store есть n предметов для продажи. Каждый товар имеет свою цену. Однако существуют специальные предложения, и специальное предложение состоит из одного или нескольких различных видов товаров с распродажной ценой. Вам дан целочисленный массив price, где price[i] - цена i-го товара, и целочисленный массив needs, где needs[i] - количество штук i-го товара, который вы хотите купить. Вам также дан массив special, где special[i] имеет размер n + 1, где special[i][j] - количество штук j-го товара в i-м предложении, а special[i][n] (т.е., Возвращает наименьшую цену, которую вы можете заплатить за определенный товар из заданных, где вы могли бы оптимально использовать специальные предложения. Вам не разрешается покупать больше товаров, чем вы хотите, даже если это снизит общую цену. Вы можете использовать любое из специальных предложений столько раз, сколько захотите. Пример:

Input: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
Output: 14

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

public class Solution {
    public int ShoppingOffers(IList<int> price, IList<IList<int>> special, IList<int> needs) {
        var memo = new Dictionary<string, int>();
        return Dfs(price, special, needs, memo);
    }

    private int Dfs(IList<int> price, IList<IList<int>> special, IList<int> needs, Dictionary<string, int> memo) {
        string key = Serialize(needs);
        if (memo.ContainsKey(key)) {
            return memo[key];
        }

        int minPrice = 0;
        for (int i = 0; i < needs.Count; i++) {
            minPrice += needs[i] * price[i];
        }

        foreach (var offer in special) {
            var newNeeds = new List<int>();
            bool valid = true;
            for (int i = 0; i < needs.Count; i++) {
                if (needs[i] < offer[i]) {
                    valid = false;
                    break;
                }
                newNeeds.Add(needs[i] - offer[i]);
            }
            if (valid) {
                minPrice = Math.Min(minPrice, offer[needs.Count] + Dfs(price, special, newNeeds, memo));
            }
        }

        memo[key] = minPrice;
        return minPrice;
    }

    private string Serialize(IList<int> needs) {
        return string.Join(",", needs);
    }
}

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка для вас и 3-х ваших близких 30 дней бесплатно. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте сейчас❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

#easy Задача: 637. Average of Levels in Binary Tree Учитывая корень бинарного дерева, верните среднее значение узлов на каждом уровне в виде массива. Принимаются ответы в пределах 10-5 от фактического ответа. Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]

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

using System;
using System.Collections.Generic;

public class Solution {
    public IList<double> AverageOfLevels(TreeNode root) {
        var result = new List<double>();
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);

        while (queue.Count > 0) {
            long sum = 0;
            int count = queue.Count;
            for (int i = 0; i < count; i++) {
                var node = queue.Dequeue();
                sum += node.val;
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            result.Add((double)sum / count);
        }

        return result;
    }
}

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

#medium Задача: 636. Exclusive Time of Functions На однопоточном процессоре выполняется программа, содержащая n функций. Каждая функция имеет уникальный ID от 0 до n-1. Вызовы функций хранятся в стеке вызовов: когда начинается вызов функции, ее ID заталкивается в стек, а когда вызов функции заканчивается, ее ID выгружается из стека. Функция, чей идентификатор находится в верхней части стека, является текущей выполняемой функцией. Каждый раз, когда функция запускается или завершается, мы пишем лог с идентификатором, началом или завершением и меткой времени. Вам предоставляется список logs, где logs[i] представляет собой i-е сообщение лога, отформатированное как строка "{function_id}:{"start" | "end"}:{timestamp}". Например, "0:start:3" означает, что вызов функции с идентификатором 0 начался в начале временной метки 3, а "1:end:2" означает, что вызов функции с идентификатором 1 завершился в конце временной метки 2. Обратите внимание, что функция может быть вызвана несколько раз, возможно, рекурсивно. Исключительное время функции - это сумма времен выполнения всех вызовов функции в программе. Например, если функция вызывается дважды, причем один вызов выполняется за 2 единицы времени, а другой - за 1 единицу, то эксклюзивное время равно 2 + 1 = 3. Верните эксклюзивное время каждой функции в массив, где значение по i-му индексу представляет собой эксклюзивное время для функции с идентификатором i. Пример:

Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3,4]

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

using System;
using System.Collections.Generic;

public class Solution {
    public int[] ExclusiveTime(int n, IList<string> logs) {
        Stack<int> stack = new Stack<int>();
        int[] times = new int[n];
        int prevTime = 0;
        
        foreach (string log in logs) {
            string[] parts = log.Split(':');
            int fid = int.Parse(parts[0]);
            string type = parts[1];
            int time = int.Parse(parts[2]);
            
            if (type == "start") {
                if (stack.Count > 0) {
                    times[stack.Peek()] += time - prevTime;
                }
                stack.Push(fid);
                prevTime = time;
            } else {
                times[stack.Pop()] += time - prevTime + 1;
                prevTime = time + 1;
            }
        }
        
        return times;
    }
}

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

#medium Задача: 635. Design Log Storage System Вам дается несколько журналов, где каждый журнал содержит уникальный идентификатор и временную метку. Временная метка - это строка, имеющая следующий формат: Год:Месяц:День:Час:Минута:Секунда, например, 2017:01:01:23:59:59. Все домены - десятичные числа с нулевым добавлением. Реализация класса LogSystem: LogSystem() Инициализирует объект LogSystem. void put(int id, string timestamp) Сохраняет заданный журнал (id, timestamp) в вашей системе хранения. int[] retrieve(string start, string end, string granularity) Возвращает идентификаторы журналов, временные метки которых находятся в диапазоне от start до end включительно. start и end имеют тот же формат, что и timestamp, а granularity означает, насколько точным должен быть диапазон (т. е. с точностью до дня, минуты и т. д.). Например, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", а granularity = "Day" означает, что нам нужно найти журналы в диапазоне от 1 января 2017 года до 2 января 2017 года включительно, а час, минуту и секунду для каждой записи журнала можно игнорировать. Пример:

Input
["LogSystem", "put", "put", "put", "retrieve", "retrieve"]
[[], [1, "2017:01:01:23:59:59"], [2, "2017:01:01:22:59:59"], [3, "2016:01:01:00:00:00"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour"]]
Output
[null, null, null, null, [3, 2, 1], [2, 1]]

👨‍💻 Алгоритм: 1⃣Инициализация и хранение журналов Реализуйте метод put, который будет сохранять журнал с заданным id и timestamp в системе хранения. 2⃣Формирование диапазона Реализуйте метод retrieve, который будет формировать диапазон временных меток на основе заданного start, end и granularity. 3⃣Фильтрация и возврат результатов Используйте сформированный диапазон для фильтрации журналов и возврата идентификаторов тех журналов, чьи временные метки попадают в этот диапазон. 😎 Решение:

using System;
using System.Collections.Generic;

public class LogSystem {
    private List<LogEntry> logs;

    public LogSystem() {
        logs = new List<LogEntry>();
    }

    public void Put(int id, string timestamp) {
        logs.Add(new LogEntry(id, timestamp));
    }

    public IList<int> Retrieve(string start, string end, string granularity) {
        int index = GetGranularityIndex(granularity);
        string startPrefix = start.Substring(0, index);
        string endPrefix = end.Substring(0, index);

        List<int> result = new List<int>();
        foreach (var log in logs) {
            string timestampPrefix = log.Timestamp.Substring(0, index);
            if (startPrefix.CompareTo(timestampPrefix) <= 0 && timestampPrefix.CompareTo(endPrefix) <= 0) {
                result.Add(log.Id);
            }
        }
        return result;
    }

    private int GetGranularityIndex(string granularity) {
        switch (granularity) {
            case "Year": return 4;
            case "Month": return 7;
            case "Day": return 10;
            case "Hour": return 13;
            case "Minute": return 16;
            case "Second": return 19;
            default: return 19;
        }
    }

    private class LogEntry {
        public int Id { get; }
        public string Timestamp { get; }

        public LogEntry(int id, string timestamp) {
            Id = id;
            Timestamp = timestamp;
        }
    }
}

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