C# | LeetCode

Задача: 991. Broken Calculator Сложность: medium Имеется неисправный калькулятор, на экране которого изначально отображается целое число startValue. За одну операцию можно: Умножить число на экране на 2, или Вычесть 1 из числа на экране. Даны два целых числа startValue и target. Верните минимальное количество операций, необходимых для отображения target на калькуляторе. Пример:

Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

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

public class Solution {
    public int BrokenCalc(int startValue, int target) {
        int operations = 0;
        
        while (target > startValue) {
            operations++;
            if (target % 2 == 0) {
                target /= 2;
            } else {
                target += 1;
            }
        }
        
        return operations + (startValue - target);
    }
}

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

Задача: 687. Longest Univalue Path Сложность: medium Дано корень бинарного дерева, верните длину самого длинного пути, на котором все узлы имеют одинаковое значение. Этот путь может проходить через корень или не проходить. Длина пути между двумя узлами представлена количеством рёбер между ними. Пример:

Input: root = [5,4,5,1,1,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 5).

👨‍💻 Алгоритм: 1⃣Определить рекурсивную функцию solve(), принимающую текущий узел root и значение родительского узла parent. Если root равен NULL, вернуть 0. Рекурсивно вызвать solve() для левого и правого дочернего узлов, передав значение текущего узла как значение родительского узла. 2⃣Обновить переменную ans, если сумма значений для левого и правого узлов больше текущего значения ans. Если значение текущего узла равно значению родительского узла, вернуть max(left, right) + 1, иначе вернуть 0. 3⃣Вызвать solve() с корневым узлом и значением родительского узла -1. Вернуть максимальную длину пути ans.. 😎 Решение:

public class Solution {
    private int ans = 0;

    private int Solve(TreeNode root, int parent) {
        if (root == null) {
            return 0;
        }

        int left = Solve(root.left, root.val);
        int right = Solve(root.right, root.val);
        
        ans = Math.Max(ans, left + right);
        
        return root.val == parent ? Math.Max(left, right) + 1 : 0;
    }

    public int LongestUnivaluePath(TreeNode root) {
        Solve(root, -1);
        return ans;
    }
}

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

Почему вы не используете Битрикс24 CRM с AI-помощником? 1- не знал 2- забыл Рассказываем и напоминаем! ✅Битрикс24 CRM с AI помогает увеличивать продажи, работать с постоянными клиентами и сохранять все важные данные. AI-помощник CoPilot внутри сервиса расшифрует телефонные разговоры и автоматически заполнит карточки клиента в CRM. Битрикс24 можно использовать бесплатно для всех команд, независимо от их размера. ⚡Не тратьте время на рутину. Узнать больше #реклама 16+ bitrix24.ru О рекламодателе

Задача: 56. Merge Intervals Сложность: medium Дан массив интервалов intervals, где intervals[i] = [start_i, end_i]. Нужно объединить все перекрывающиеся интервалы и вернуть массив неперекрывающихся интервалов. Пример:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]  
Output: [[1,6],[8,10],[15,18]]  
Explanation: Так как `[1,3]` и `[2,6]` пересекаются, объединяем их в `[1,6]`.  

👨‍💻 Алгоритм: 1⃣Отсортировать интервалы по start. 2⃣Использовать List<int[]> merged, добавляя в него первый интервал. 3⃣Пройтись по остальным интервалам: - Если current.start <= lastMerged.end, объединить интервалы. - Иначе добавить current в merged. 4⃣Вернуть merged как int[][]. 😎 Решение:

public class Solution {
    public int[][] Merge(int[][] intervals) {
        if (intervals.Length == 0) return new int[0][];

        Array.Sort(intervals, (a, b) => a[0] - b[0]);
        List<int[]> merged = new List<int[]>();

        foreach (var interval in intervals) {
            if (merged.Count == 0 || merged[^1][1] < interval[0]) {
                merged.Add(interval);
            } else {
                merged[^1][1] = Math.Max(merged[^1][1], interval[1]);
            }
        }

        return merged.ToArray();
    }
}

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

На easyoffer 2.0 появится: База тестовых заданий 🟠Тестовые задания для разных грейдов 🟠Фильтрация тестовых заданий по технологиям и компаниям Когда я только начинал учиться на программиста, я постоянно выдумывал себе задачи для практики и тратил на это много времени. Но только в момент поиска работы я столкнулся с тестовыми заданиями, и понял насколько круто они прокачивают навыки. Нужно было еще на этапе обучения пробовать их делать. Все компании стараются составить тестовое задание "под себя", это дает большой выбор в тематике задач и технологий. На easyoffer 2.0 вы сможете отфильтровать тестовые задания по навыкам/грейдам и найти те, что подходят лично вам для практики. В течение 1-2 дней я объявлю о краудфандинг кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки и смогут попасть на закрытое бета-тестирование. А первые 150 донатеров получать особо-выгодную цену и бонус. 🚀 Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Партнёрская программа рекрутинга в Яндекс Еду Станьте партнёром Яндекс Еды по привлечению курьеров и получите кучу преимуществ: 💰Платим до 47 000 ₽ за успешного кандидата 📞Поддержка на всех этапах 📅Свободное расписание 📊Удобные инструменты для работы Приводите новых курьеров и получайте в среднем 250 000 ₽ в месяц! Зарегистрироваться #реклама eda.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 32. Longest Valid Parentheses Сложность: hard Дана строка, содержащая только символы '(' и ')'. Верните длину самой длинной подстроки с корректными (правильно сформированными) скобками. Пример:

Input: s = "(()"  
Output: 2  

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

public class Solution {
    public int LongestValidParentheses(string s) {
        Stack<int> stack = new Stack<int>();
        stack.Push(-1);
        int maxLen = 0;

        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '(') {
                stack.Push(i);
            } else {
                stack.Pop();
                if (stack.Count == 0) {
                    stack.Push(i);
                } else {
                    maxLen = Math.Max(maxLen, i - stack.Peek());
                }
            }
        }

        return maxLen;
    }
}

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

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

Задача: 1337. The K Weakest Rows in a Matrix Сложность: easy Вам дана бинарная матрица размером m x n mat, состоящая из 1 (представляющих солдат) и 0 (представляющих гражданских лиц). Солдаты расположены перед гражданскими лицами. То есть, все 1 будут расположены слева от всех 0 в каждой строке. Строка i слабее строки j, если выполнено одно из следующих условий: Количество солдат в строке i меньше, чем в строке j. Обе строки имеют одинаковое количество солдат, но i < j. Верните индексы k самых слабых строк в матрице, упорядоченных от самой слабой к самой сильной. Пример:

Input: mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
Output: [2,0,3]
Explanation: 
The number of soldiers in each row is: 
- Row 0: 2 
- Row 1: 4 
- Row 2: 1 
- Row 3: 2 
- Row 4: 5 
The rows ordered from weakest to strongest are [2,0,3,1,4].

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

public class Solution {
    public int[] KWeakestRows(int[][] mat, int k) {
        int m = mat.Length;
        int n = mat[0].Length;

        var pairs = new List<(int strength, int index)>();

        for (int i = 0; i < m; i++) {
            int strength = 0;
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) break;
                strength++;
            }
            pairs.Add((strength, i));
        }

        pairs.Sort((a, b) => {
            if (a.strength == b.strength) return a.index - b.index;
            return a.strength - b.strength;
        });

        int[] indexes = new int[k];
        for (int i = 0; i < k; i++) {
            indexes[i] = pairs[i].index;
        }
        return indexes;
    }
}

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

Задача: 40. Combination Sum II Сложность: medium Дан массив candidates и целое число target. Нужно найти все уникальные комбинации чисел из candidates, сумма которых равна target. Каждое число можно использовать только один раз. Решение не должно содержать повторяющихся комбинаций. Пример:

Input: candidates = [10,1,2,7,6,1,5], target = 8  
Output:  
[  
 [1,1,6],  
 [1,2,5],  
 [1,7],  
 [2,6]  
]  

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

public class Solution {
    public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
        Array.Sort(candidates);
        List<IList<int>> results = new List<IList<int>>();
        Backtrack(candidates, target, 0, new List<int>(), results);
        return results;
    }

    private void Backtrack(int[] candidates, int remain, int start, List<int> comb, List<IList<int>> results) {
        if (remain == 0) {
            results.Add(new List<int>(comb));
            return;
        }

        for (int i = start; i < candidates.Length; i++) {
            if (i > start && candidates[i] == candidates[i - 1]) continue; // Пропуск дубликатов

            if (candidates[i] > remain) break; // Оптимизация: остановка, если число больше оставшейся суммы

            comb.Add(candidates[i]);
            Backtrack(candidates, remain - candidates[i], i + 1, comb, results);
            comb.RemoveAt(comb.Count - 1);
        }
    }
}

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по AI! Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 342. Power of Four Сложность: easy Дано целое число n. Верните true, если оно является степенью числа четыре. В противном случае верните false. Целое число n является степенью числа четыре, если существует целое число x такое, что n == 4^x. Пример:

Input: n = 16
Output: true

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

public class Solution {
    public bool IsPowerOfFour(int n) {
        if (n <= 0) return false;
        double log_n_base_4 = Math.Log(n) / Math.Log(4);
        return log_n_base_4 == Math.Floor(log_n_base_4);
    }
}

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

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

На easyoffer 2.0 появится: Тренажер "Реальное собеседование" 🟠 Сценарии вопросов из реального собеседования 🟠Возможность подготовиться к собеседованию в конкретную компанию 🟠Итоговая статистика (прошёл/не прошёл) Сценарий вопросов взят из реального собеседования. То есть вы тренируетесь на тех вопросах, которые действительно задавались в компании X. Уже в начале следующей недели стартует краудфандинг кампания, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки. Первые 150 донатеров получать особо-выгодную цену и бонус. Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Задача: 1335. Minimum Difficulty of a Job Schedule Сложность: hard Вы хотите составить расписание списка заданий на d дней. Задания зависят друг от друга (т.е. чтобы выполнить задание i, вы должны закончить все задания j, где 0 <= j < i). Вы должны выполнять как минимум одно задание каждый день. Сложность расписания заданий — это сумма сложностей каждого дня из d дней. Сложность дня — это максимальная сложность задания, выполненного в этот день. Вам дан массив целых чисел jobDifficulty и целое число d. Сложность i-го задания равна jobDifficulty[i]. Верните минимальную сложность расписания заданий. Если вы не можете найти расписание для заданий, верните -1. Пример:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 

👨‍💻 Алгоритм: 1⃣Определение состояния: Индекс i (индекс первой задачи на сегодняшний день в массиве jobDifficulty) и день d (количество оставшихся дней) будут определять состояние динамического программирования. min_diff(i, d) обозначает минимальную сложность при начале с i-й задачи с оставшимися d днями. min_diff(0, d) будет окончательным ответом, так как он представляет начало с начала массива задач и завершение всех задач за ровно d дней. 2⃣Функция перехода состояния: Задача с индексом j будет первой задачей на следующий день, следовательно, задачи, которые должны быть завершены сегодня, это все задачи с индексами между i и j, то есть jobDifficulty[i ]. Поскольку сложность дня — это максимальная сложность выполненной в этот день задачи, к сумме сложностей задач будет добавляться максимум из jobDifficulty[i ]. Формулируем функцию перехода состояния следующим образом: min_diff(i, d) = min_diff(j, d - 1) + max(jobDifficulty[i ]) для всех j > i. 3⃣Базовый случай: Когда остается только 1 день, необходимо завершить все незавершенные задачи в этот день и увеличить сложность расписания задач на максимальную сложность этих задач. 😎 Решение:

public class Solution {
    public int MinDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.Length;
        if (n < d) {
            return -1;
        }

        int[][] mem = new int[n][];
        for (int i = 0; i < n; i++) {
            mem[i] = new int[d + 1];
            for (int j = 0; j <= d; j++) {
                mem[i][j] = -1;
            }
        }

        return MinDiff(0, d, jobDifficulty, mem);
    }

    private int MinDiff(int i, int daysRemaining, int[] jobDifficulty, int[][] mem) {
        if (mem[i][daysRemaining] != -1) {
            return mem[i][daysRemaining];
        }

        if (daysRemaining == 1) {
            int res = 0;
            for (int j = i; j < jobDifficulty.Length; j++) {
                res = Math.Max(res, jobDifficulty[j]);
            }
            return res;
        }

        int result = int.MaxValue;
        int dailyMaxJobDiff = 0;
        for (int j = i; j < jobDifficulty.Length - daysRemaining + 1; j++) {
            dailyMaxJobDiff = Math.Max(dailyMaxJobDiff, jobDifficulty[j]);
            result = Math.Min(result, dailyMaxJobDiff + MinDiff(j + 1, daysRemaining - 1, jobDifficulty, mem));
        }
        mem[i][daysRemaining] = result;
        return result;
    }
}

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

⚡️ Айтишник из «VISION» скупил курсы айти школ и выложил гигабайты материалов к себе Каждый найдет что-то по душе: 1202 ГБ — Python 1811 ГБ — Frontend 1100 ГБ — C / C++ / C# 804 ГБ — Java 411 ГБ — SQL & БД 309 ГБ — DevOps 998 ГБ — ИБ & Хакинг 773 ГБ — Kotlin / Swift 189 ГБ — PHP 201 ГБ — GoLang 170 ГБ — Rust 167 ГБ — QA / Тестирование 310 ГБ — 1C + Лицензии 495 ГБ — Машинное обучение 704 ГБ — Аналитика Данных 991 ГБ — Дизайн Материалы в закрепе, постоянно пополняются👆🏻

Битрикс24 💻Один онлайн-сервис для совместной работы. 📱10+ инструментов. ✅0 денег. Счастливые сотрудники. Прибыльный бизнес. Регистрируйтесь и забирайте себе Зарегистрироваться #реклама 16+ office-online.bitrix24.ru О рекламодателе

Задача: 988. Smallest String Starting From Leaf Сложность: medium Дан корень бинарного дерева, где каждый узел имеет значение в диапазоне [0, 25], представляющее буквы от 'a' до 'z'. Верните лексикографически наименьшую строку, которая начинается с листа этого дерева и заканчивается у корня. Напоминаем, что любая более короткая префиксная строка является лексикографически меньшей. Например, "ab" лексикографически меньше, чем "aba". Лист узла - это узел, у которого нет потомков. Пример:

Input: root = [0,1,2,3,4,3,4]
Output: "dba"

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

public class Solution {
    private string ans = "~";

    public string SmallestFromLeaf(TreeNode root) {
        Dfs(root, new StringBuilder());
        return ans;
    }

    private void Dfs(TreeNode node, StringBuilder path) {
        if (node == null) return;
        path.Append((char) (node.val + 'a'));
        if (node.left == null && node.right == null) {
            var s = new string(path.ToString().Reverse().ToArray());
            if (string.Compare(s, ans) < 0) {
                ans = s;
            }
        }
        Dfs(node.left, path);
        Dfs(node.right, path);
        path.Remove(path.Length - 1, 1);
    }
}

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

На easyoffer 2.0 появится новый раздел: Задачи с собеседований 🟠Задачи на Алгоритмические, Live-coding и System Design из реальных собеседований 🟠Вероятность встретить ту или иную задачу 🟠Возможность подготовиться к задачам конкретной компании Есть много сайтов, на которых можно тренироваться решать задачи, но у них у всех одна проблема – сами задачи люди просто выдумывают. На easyoffer 2.0 вы сможете готовиться к live-coding и system design секциям на основе задач из реальных собеседований. Вы можете найдете самые частые задачи и сделаете упор на их решение. Считаные дни остались до старта краудфандинговой кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки, а те кто поддержат проект раньше других ито дешевле + получат существенный бонус. Следите за стартом 👉 в этом телеграм канале.

Нанимаете аутсорс, подрядчиков, фрилансеров? Попробуйте Битрикс24 Коллабы – платформа для эффективной работы с подрядчиками. Тут обсуждения превращаются в задачи, а видео созвон можно собрать одной кнопкой. Любой проект можно разложить по полочкам с понятным ТЗ и обозначенными сроками. Работайте в Битрикс24 и создавайте Коллабы с подрядчиками. Начать #реклама 16+ collabs.bitrix24.ru О рекламодателе