C# | LeetCode

Школьник + бесплатные курсы по ИТ = новые возможности Хотите прокачать мышление, научиться решать задачи по математике и информатике и познакомиться с ИТ? Бесплатные курсы для школьников в этом помогут. Занятия включают теорию и практические задачи, а само обучение не будет отнимать много времени - нужно 2-3 часа в неделю. После успешного прохождения одного из курсов вам выдадут сертификат - им можно пополнить портфолио. Чтобы начать учиться, выберите подходящую программу и оставьте заявку на сайте Т-Образования. Подать заявку #реклама 16+ education.tbank.ru О рекламодателе

#medium Задача: 325. Maximum Size Subarray Sum Equals k Дан целочисленный массив nums и целое число k. Верните максимальную длину подмассива, сумма которого равна k. Если такого подмассива не существует, верните 0. Пример:

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

👨‍💻 Алгоритм: 1⃣Инициализация переменных Инициализируйте prefixSum как 0 для отслеживания префиксной суммы nums. Инициализируйте longestSubarray как 0 для отслеживания самой длинной подмассы с суммой k. Инициализируйте хеш-карту indices для хранения префиксных сумм и их индексов. 2⃣Итерация по массиву На каждом индексе i, добавляйте nums[i] к prefixSum. Проверьте следующие условия: Если prefixSum == k, обновите longestSubarray как i + 1. Если prefixSum - k существует в indices, обновите longestSubarray, если текущая длина подмассива больше. Если текущий prefixSum еще не существует в indices, добавьте indices[prefixSum] = i. 3⃣Возврат результата Верните значение longestSubarray. 😎 Решение:

public class Solution {
    public int MaxSubArrayLen(int[] nums, int k) {
        int prefixSum = 0;
        int longestSubarray = 0;
        Dictionary<int, int> indices = new Dictionary<int, int>();
        
        for (int i = 0; i < nums.Length; i++) {
            prefixSum += nums[i];
            
            if (prefixSum == k) {
                longestSubarray = i + 1;
            }
            if (indices.ContainsKey(prefixSum - k)) {
                longestSubarray = Math.Max(longestSubarray, i - indices[prefixSum - k]);
            }
            if (!indices.ContainsKey(prefixSum)) {
                indices[prefixSum] = i;
            }
        }
        
        return longestSubarray;
    }
}

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

#medium Задача: 323. Number of Connected Components in an Undirected Graph У вас есть граф из n узлов. Вам дано целое число n и массив edges, где edges[i] = [ai, bi] указывает на наличие ребра между ai и bi в графе. Верните количество связных компонентов в графе. Пример:

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2

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

public class Solution {
    public int CountComponents(int n, int[][] edges) {
        var adj = new Dictionary<int, List<int>>();
        for (int i = 0; i < n; i++) adj[i] = new List<int>();
        foreach (var edge in edges) {
            adj[edge[0]].Add(edge[1]);
            adj[edge[1]].Add(edge[0]);
        }

        var visited = new HashSet<int>();
        int count = 0;

        void Dfs(int node) {
            var stack = new Stack<int>();
            stack.Push(node);
            while (stack.Count > 0) {
                var current = stack.Pop();
                if (visited.Add(current)) {
                    foreach (var neighbor in adj[current]) {
                        if (!visited.Contains(neighbor)) stack.Push(neighbor);
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (visited.Add(i)) {
                Dfs(i);
                count++;
            }
        }

        return count;
    }
}

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

Мастер-класс по Python для школьников. Бесплатно! Онлайн-урок от ведущего ИТ ВУЗа страны - Университета Иннополис для учеников 6-11 классов. 👍Бесплатно! ✅Познакомим с профессией тестировщика. ✅Научим проверять программы, находить баги. ✅На практике отработаем использование инструментов и методов тестирования. ⚡Ваш ребёнок за один час создаст автоматический тест на языке программирования Python и сможет использовать полученные знания в дальнейшем! Для участия важно знание основ программирования на Python. Помогите ребёнку освоить востребованную профессию. Регистрируйтесь! Зарегистрироваться #реклама 16+ progmatica.innopolis.university О рекламодателе

#medium Задача: 406. Queue Reconstruction by Height Вам дан массив людей, people, которые являются атрибутами некоторых людей в очереди (не обязательно по порядку). Каждый people[i] = [hi, ki] представляет собой человека ростом hi, перед которым стоят ровно ki других людей, чей рост больше или равен hi. Реконструируйте и верните очередь, представленную входным массивом people. Возвращаемая очередь должна быть отформатирована как массив queue, где queue[j] = [hj, kj] - это атрибуты j-го человека в очереди (queue[0] - человек, находящийся в начале очереди). Пример:

Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

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

using System;
using System.Collections.Generic;

public class Solution {
    public int[][] ReconstructQueue(int[][] people) {
        Array.Sort(people, (a, b) => a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        List<int[]> result = new List<int[]>();
        foreach (var person in people) {
            result.Insert(person[1], person);
        }
        return result.ToArray();
    }
}

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

#medium Задача: 322. Coin Change Дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег. Верните минимальное количество монет, необходимых для составления этой суммы. Если эту сумму невозможно составить с помощью комбинации монет, верните -1. Вы можете предположить, что у вас есть неограниченное количество монет каждого типа. Пример:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

👨‍💻 Алгоритм: 1⃣Инициализация и вызов функции backtracking Инициализируйте переменные для хранения минимального количества монет и вызовите функцию backtracking с начальными параметрами. 2⃣Функция backtracking Внутри функции backtracking для каждой монеты из массива coins: Проверьте все возможные количества монет данного номинала (от 0 до максимального количества, которое можно использовать без превышения amount). Для каждой комбинации монет обновите сумму и вызовите функцию рекурсивно для проверки оставшейся суммы. Если текущая комбинация дает меньшую сумму монет, обновите минимальное количество монет. 3⃣Возврат результата Если комбинация, дающая сумму amount, найдена, верните минимальное количество монет, иначе верните -1. 😎 Решение:

public class Solution {
    public int CoinChange(int[] coins, int amount) {
        return CoinChange(0, coins, amount);
    }

    private int CoinChange(int idxCoin, int[] coins, int amount) {
        if (amount == 0) return 0;
        if (idxCoin < coins.Length && amount > 0) {
            int maxVal = amount / coins[idxCoin];
            int minCost = int.MaxValue;
            for (int x = 0; x <= maxVal; x++) {
                if (amount >= x * coins[idxCoin]) {
                    int res = CoinChange(idxCoin + 1, coins, amount - x * coins[idxCoin]);
                    if (res != -1)
                        minCost = Math.Min(minCost, res + x);
                }
            }
            return minCost == int.MaxValue ? -1 : minCost;
        }
        return -1;
    }
}

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

ТОП-10 Курсов по Программированию ⚡Tutortop — маркетплейс курсов №1 по количеству школ-партнеров, курсов и реальных отзывов студентов. ✅Хотите стать программистом, но не знаете с какого языка начать? Помогаем разобраться в самых популярных и востребованных языках программирования. Подарок в конце подборки! Выбрать #реклама 16+ tutortop.ru О рекламодателе

#easy Задача: 405. Convert a Number to Hexadecimal Если задано целое число num, верните строку, представляющую его шестнадцатеричное представление. Для отрицательных целых чисел используется метод дополнения до двух. Все буквы в строке ответа должны быть строчными, и в ответе не должно быть никаких ведущих нулей, кроме самого нуля. Примечание: Вам не разрешается использовать какие-либо встроенные библиотечные методы для непосредственного решения этой задачи. Пример:

Input: num = 26
Output: "1a"

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

public class Solution {
    public string ToHex(int num) {
        if (num == 0) return "0";
        char[] hexChars = "0123456789abcdef".ToCharArray();
        uint n = (uint)num;
        StringBuilder result = new StringBuilder();
        while (n > 0) {
            result.Append(hexChars[n % 16]);
            n /= 16;
        }
        char[] charArray = result.ToString().ToCharArray();
        Array.Reverse(charArray);
        return new string(charArray);
    }
}

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

#easy Задача: 543. Diameter of Binary Tree Учитывая корень бинарного дерева, вернуть длину диаметра дерева. Диаметр бинарного дерева — это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень. Длина пути между двумя узлами представлена числом ребер между ними. Пример:

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

👨‍💻 Алгоритм: 1⃣Инициализируйте целочисленную переменную diameter для отслеживания самого длинного пути, найденного с помощью DFS. 2⃣Реализуйте рекурсивную функцию longestPath, которая принимает TreeNode в качестве входных данных и рекурсивно исследует дерево: Если узел равен None, вернуть 0. Рекурсивно исследовать левые и правые дочерние узлы, возвращая длины путей leftPath и rightPath. Если сумма leftPath и rightPath больше текущего diameter, обновить diameter. Вернуть большее из leftPath и rightPath плюс 1. 3⃣Вызвать longestPath с root. 😎 Решение:

public class Solution {
    private int diameter;
    
    public int DiameterOfBinaryTree(TreeNode root) {
        diameter = 0;
        LongestPath(root);
        return diameter;
    }
    
    private int LongestPath(TreeNode node) {
        if (node == null) return 0;
        
        int leftPath = LongestPath(node.left);
        int rightPath = LongestPath(node.right);
        
        diameter = Math.Max(diameter, leftPath + rightPath);
        
        return Math.Max(leftPath, rightPath) + 1;
    }
}

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

#medium Задача: 320. Generalized Abbreviation Обобщенная аббревиатура слова может быть построена путем замены любых неперекрывающихся и несмежных подстрок на их соответствующие длины. Например, "abcde" можно сократить следующим образом: "a3e" ("bcd" заменено на "3") "1bcd1" ("a" и "e" заменены на "1") "5" ("abcde" заменено на "5") "abcde" (без замены подстрок) Однако следующие аббревиатуры недействительны: "23" ("ab" заменено на "2" и "cde" заменено на "3") недействительно, так как выбранные подстроки смежные. "22de" ("ab" заменено на "2" и "bc" заменено на "2") недействительно, так как выбранные подстроки перекрываются. Дано слово word, верните список всех возможных обобщенных аббревиатур слова. Верните ответ в любом порядке. Пример:

Input: word = "a"
Output: ["1","a"]

👨‍💻 Алгоритм: 1⃣Создание битовых масок Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур. 2⃣Генерация аббревиатур Для числа x просканируйте его бит за битом, чтобы определить, какие символы следует сохранить, а какие - сократить. Если бит равен 1, сохраните соответствующий символ, если 0 - замените его на счетчик. 3⃣Перебор всех комбинаций Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1. 😎 Решение:

public class Solution {
    public IList<string> GenerateAbbreviations(string word) {
        var ans = new List<string>();
        for (int x = 0; x < (1 << word.Length); ++x)
            ans.Add(Abbr(word, x));
        return ans;
    }

    private string Abbr(string word, int x) {
        var builder = new StringBuilder();
        int k = 0, n = word.Length;
        for (int i = 0; i < n; ++i, x >>= 1) {
            if ((x & 1) == 0) {
                if (k != 0) {
                    builder.Append(k);
                    k = 0;
                }
                builder.Append(word[i]);
            } else {
                ++k;
            }
        }
        if (k != 0) builder.Append(k);
        return builder.ToString();
    }
}

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

#medium Задача: 319. Bulb Switcher Есть n лампочек, которые изначально выключены. Сначала вы включаете все лампочки, затем выключаете каждую вторую лампочку. На третьем раунде вы переключаете каждую третью лампочку (включаете, если она выключена, или выключаете, если она включена). На i-ом раунде вы переключаете каждую i-ую лампочку. На n-ом раунде вы переключаете только последнюю лампочку. Верните количество лампочек, которые будут включены после n раундов. Пример:

Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off]. 
So you should return 1 because there is only one bulb is on.
Explanation: The two words can be "abcw", "xtfn".

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

public class Solution {
    public int BulbSwitch(int n) {
        return (int) Math.Sqrt(n);
    }
}

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

Тахеометры по выгодным ценам В наличии весь спектр тахометров для проведения геодезических работ. Большой шоурум в Москве. Обращайтесь к нам и получайте профессиональные решения для всех Ваших задач. При покупке оборудования Вы получаете бесплатное обучение по эксплуатации геодезического оборудования и круглосуточную техническую поддержку. Наши специалисты помогут с выбором и организуют бесплатный демонстрационный показ в день обращения. Они также проведут обучение по правилам эксплуатации прибора. Осуществляем доставку в любой город России. Гарантируем качество оборудования и услуг. Узнать больше #реклама fgeo.ru О рекламодателе

#medium Задача: 318. Maximum Product of Word Lengths Дан массив строк words, верните максимальное значение произведения длины word[i] на длину word[j], где два слова не имеют общих букв. Если таких двух слов не существует, верните 0. Пример:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

👨‍💻 Алгоритм: 1⃣Предварительная обработка масок и длин Вычислите битовые маски для всех слов и сохраните их в массиве masks. Сохраните длины всех слов в массиве lens. 2⃣Сравнение слов и проверка общих букв Сравните каждое слово с каждым последующим словом. Если два слова не имеют общих букв (проверка с использованием масок: (masks[i] & masks[j]) == 0), обновите максимальное произведение maxProd. 3⃣Возврат результата Верните максимальное значение произведения maxProd. 😎 Решение:

public class Solution {
    public int MaxProduct(string[] words) {
        int n = words.Length;
        int[] masks = new int[n];
        int[] lens = new int[n];
        
        for (int i = 0; i < n; i++) {
            int bitmask = 0;
            foreach (char ch in words[i]) {
                bitmask |= 1 << (ch - 'a');
            }
            masks[i] = bitmask;
            lens[i] = words[i].Length;
        }
        
        int maxVal = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    maxVal = Math.Max(maxVal, lens[i] * lens[j]);
                }
            }
        }
        return maxVal;
    }
}

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

#hard Задача: 317. Shortest Distance from All Buildings Дана сетка m x n, содержащая значения 0, 1 или 2, где: каждое 0 обозначает пустую землю, по которой можно свободно проходить, каждое 1 обозначает здание, через которое нельзя пройти, каждое 2 обозначает препятствие, через которое нельзя пройти. Вы хотите построить дом на пустой земле, чтобы он достиг всех зданий с минимальным суммарным расстоянием. Можно перемещаться только вверх, вниз, влево и вправо. Верните минимальное суммарное расстояние для такого дома. Если построить такой дом невозможно согласно указанным правилам, верните -1. Суммарное расстояние — это сумма расстояний между домами друзей и точкой встречи. Пример:

Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7

👨‍💻 Алгоритм: 1⃣Инициализация и запуск BFS Для каждой пустой ячейки (0) в сетке grid запустите BFS, обходя все соседние ячейки в 4 направлениях, которые не заблокированы и не посещены, отслеживая расстояние от начальной ячейки. 2⃣Обработка BFS и обновление расстояний При достижении здания (1) увеличьте счетчик достигнутых домов housesReached и суммарное расстояние distanceSum на текущее расстояние. Если housesReached равно общему количеству зданий, верните суммарное расстояние. Если BFS не может достигнуть всех домов, установите значение каждой посещенной пустой ячейки в 2, чтобы не запускать новый BFS из этих ячеек, и верните INT_MAX. 3⃣Обновление и возврат минимального расстояния Обновите минимальное расстояние (minDistance) после каждого вызова BFS. Если возможно достигнуть все дома из любой пустой ячейки, верните найденное минимальное расстояние. В противном случае, верните -1. 😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    private int Bfs(int[][] grid, int row, int col, int totalHouses) {
        int[][] dirs = { new int[] { 1, 0 }, new int[] { -1, 0 }, new int[] { 0, 1 }, new int[] { 0, -1 } };
        int rows = grid.Length, cols = grid[0].Length, distanceSum = 0, housesReached = 0, steps = 0;
        Queue<int[]> q = new Queue<int[]>();
        q.Enqueue(new int[] { row, col });
        bool[,] vis = new bool[rows, cols];
        vis[row, col] = true;

        while (q.Count > 0 && housesReached != totalHouses) {
            int size = q.Count;
            while (size-- > 0) {
                int[] curr = q.Dequeue();
                int r = curr[0], c = curr[1];
                if (grid[r][c] == 1) {
                    distanceSum += steps;
                    housesReached++;
                    continue;
                }
                foreach (var dir in dirs) {
                    int nr = r + dir[0], nc = c + dir[1];
                    if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && !vis[nr, nc] && grid[nr][nc] != 2) {
                        vis[nr, nc] = true;
                        q.Enqueue(new int[] { nr, nc });
                    }
                }
            }
            steps++;
        }

        if (housesReached != totalHouses) {
            for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (grid[r][c] == 0 && vis[r, c]) grid[r][c] = 2;
            return int.MaxValue;
        }
        return distanceSum;
    }

    public int ShortestDistance(int[][] grid) {
        int minDistance = int.MaxValue, rows = grid.Length, cols = grid[0].Length, totalHouses = 0;
        foreach (var row in grid) foreach (var cell in row) if (cell == 1) totalHouses++;
        for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (grid[r][c] == 0) minDistance = Math.Min(minDistance, Bfs(grid, r, c, totalHouses));
        return minDistance == int.MaxValue ? -1 : minDistance;
    }
}

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

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

#medium Задача: 316. Remove Duplicate Letters Дана строка s, удалите повторяющиеся буквы так, чтобы каждая буква появилась один раз и только один раз. Вы должны сделать так, чтобы результат был наименьшим в лексикографическом порядке среди всех возможных результатов. Пример:

Input: s = "bcabc"
Output: "abc"

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

public class Solution {
    public string RemoveDuplicateLetters(string s) {
        var stack = new Stack<char>();
        var seen = new HashSet<char>();
        var lastOccurrence = new Dictionary<char, int>();
        for (int i = 0; i < s.Length; i++) {
            lastOccurrence[s[i]] = i;
        }

        for (int i = 0; i < s.Length; i++) {
            char c = s[i];
            if (!seen.Contains(c)) {
                while (stack.Count > 0 && c < stack.Peek() && i < lastOccurrence[stack.Peek()]) {
                    seen.Remove(stack.Pop());
                }
                seen.Add(c);
                stack.Push(c);
            }
        }
        return new string(stack.Reverse().ToArray());
    }
}

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

#easy Задача: 404. Sum of Left Leaves Если задан корень бинарного дерева, верните сумму всех левых листьев. Лист - это узел, не имеющий детей. Левый лист - это лист, который является левым ребенком другого узла. Пример:

Input: root = [3,9,20,null,null,15,7]
Output: 24

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

public class Solution {
    public int SumOfLeftLeaves(TreeNode root) {
        return Dfs(root, false);
    }
    
    private int Dfs(TreeNode node, bool isLeft) {
        if (node == null) return 0;
        if (node.left == null && node.right == null) return isLeft ? node.val : 0;
        return Dfs(node.left, true) + Dfs(node.right, false);
    }
}

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

Москвич 3 – надежно для вас и ваших увлечений Современный городской кроссовер Москвич 3. Ежемесячный платеж 17 500 рублей. Подробности уточняйте на официальном сайте moskvich.ru. Перейти на сайт Финансовые услуги оказывает: АО "Авто Финанс Банк", ПАО "Совкомбанк". #реклама moskvich.ru О рекламодателе

#hard Задача: 403. Frog Jump Если задана строка num, представляющая неотрицательное целое число num, и целое число k, верните наименьшее возможное целое число после удаления k цифр из num. Пример:

Input: stones = [0,1,3,5,6,8,12,17]
Output: true

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

public class Solution {
    public bool CanCross(int[] stones) {
        var dp = new Dictionary<int, HashSet<int>>();
        foreach (var stone in stones) {
            dp[stone] = new HashSet<int>();
        }
        dp[0].Add(0);
        
        foreach (var stone in stones) {
            foreach (var jump in dp[stone]) {
                for (int step = jump - 1; step <= jump + 1; step++) {
                    if (step > 0 && dp.ContainsKey(stone + step)) {
                        dp[stone + step].Add(step);
                    }
                }
            }
        }
        
        return dp[stones[stones.Length - 1]].Count > 0;
    }
}

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