Задача: 1004. Max Consecutive Ones III
Сложность: medium

Если задан двоичный массив nums и целое число k, верните максимальное количество последовательных 1 в массиве, если можно перевернуть не более k 0.

Пример:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6

👨‍💻 Алгоритм:

1⃣Инициализация оконного подхода:
Используйте два указателя для создания скользящего окна. Инициализируйте левый указатель в начале массива, правый указатель будет двигаться по массиву. Создайте переменную для подсчета количества нулей в текущем окне.

2⃣Перемещение правого указателя и обновление окна:
Перемещайте правый указатель по массиву, обновляя количество нулей в текущем окне. Если количество нулей превышает k, сдвиньте левый указатель вправо до тех пор, пока количество нулей снова не станет допустимым (меньше или равно k).

3⃣Подсчет максимального количества последовательных единиц:
На каждом шаге обновляйте максимальное количество последовательных единиц, сравнивая текущую длину окна (разница между правым и левым указателями) с текущим максимумом.

😎 Решение:

public class Solution {
    public int LongestOnes(int[] nums, int k) {
        int left = 0, maxOnes = 0, zeroCount = 0;

        for (int right = 0; right < nums.Length; right++) {
            if (nums[right] == 0) {
                zeroCount++;
            }

            while (zeroCount > k) {
                if (nums[left] == 0) {
                    zeroCount--;
                }
                left++;
            }

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

        return maxOnes;
    }
}

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

Задача: 273. Integer to English Words
Сложность: hard

Преобразуйте неотрицательное целое число num в его словесное представление на английском языке.

Пример:

Input: num = 123
Output: "One Hundred Twenty Three"

👨‍💻 Алгоритм:

1⃣Обработка чисел до 20 и кратных 10 до 90:
Создать массивы или словари для чисел от 1 до 19 и для кратных 10 от 20 до 90.
Если число попадает в эти диапазоны, сразу вернуть соответствующее словесное представление.

2⃣Обработка сотен, тысяч, миллионов и миллиардов:
Разделить число на группы по три цифры (единицы, тысячи, миллионы, миллиарды).
Для каждой группы сформировать словесное представление с использованием рекурсивной функции для чисел от 1 до 999.

3⃣Формирование окончательного результата:
Собрать словесное представление всех групп, добавив соответствующие суффиксы (тысячи, миллионы, миллиарды).
Соединить все части в одну строку, удалив лишние пробелы.

😎 Решение:

public class Solution {
    private string[] belowTwenty = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private string[] tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    private string[] thousands = {"", "Thousand", "Million", "Billion"};

    public string NumberToWords(int num) {
        if (num == 0) return "Zero";
        int i = 0;
        string result = "";
        
        while (num > 0) {
            if (num % 1000 != 0) {
                result = Helper(num % 1000) + thousands[i] + " " + result;
            }
            num /= 1000;
            i++;
        }
        return result.Trim();
    }

    private string Helper(int num) {
        if (num == 0) return "";
        else if (num < 20) return belowTwenty[num] + " ";
        else if (num < 100) return tens[num / 10] + " " + Helper(num % 10);
        else return belowTwenty[num / 100] + " Hundred " + Helper(num % 100);
    }
}

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

Задача: 1279. Traffic Light Controlled Intersection
Сложность: easy

Здесь есть пересечение двух дорог. Первая дорога - это дорога A, по которой автомобили движутся с севера на юг в направлении 1 и с юга на север в направлении 2. Вторая дорога - дорога B, по которой машины едут с запада на восток в направлении 3 и с востока на запад в направлении 4. На каждой дороге перед перекрестком есть светофор. Зеленый означает, что автомобили могут пересекать перекресток в обоих направлениях. Красный означает, что автомобили в обоих направлениях не могут пересекать перекресток и должны ждать, пока загорится зеленый свет. Светофор не может гореть зеленым одновременно на обеих дорогах. Это значит, что когда на дороге А горит зеленый свет, на дороге Б он красный, а когда на дороге Б горит зеленый свет, на дороге А он красный.
Изначально на дороге A горит зеленый сигнал светофора, а на дороге B - красный. Когда на одной дороге горит зеленый свет, все автомобили могут пересекать перекресток в обоих направлениях, пока на другой дороге не загорится зеленый.Два автомобиля, движущиеся по разным дорогам, не должны пересекать перекресток одновременно. Разработайте систему управления светофором на этом перекрестке без тупиков. Реализуйте функцию void carArrived(carId, roadId, direction, turnGreen, crossCar), где: carId - идентификатор автомобиля, который приехал. roadId - идентификатор дороги, по которой едет автомобиль.
direction - направление движения автомобиля. turnGreen - функция, которую можно вызвать, чтобы переключить светофор на зеленый свет на текущей дороге. crossCar - функция, которую можно вызвать, чтобы позволить текущему автомобилю пересечь перекресток. Ваш ответ считается правильным, если он позволяет избежать тупика на перекрестке.Переключение светофора на зеленый свет на дороге, где он уже был зеленым, считается неправильным ответом.

Пример:

Input: cars = [1,2,3,4,5], directions = [2,4,3,3,1], arrivalTimes = [10,20,30,40,40]
Output: [
"Car 1 Has Passed Road A In Direction 2",    // Traffic light on road A is green, car 1 can cross the intersection.
"Traffic Light On Road B Is Green",          // Car 2 requests green light for road B.
"Car 2 Has Passed Road B In Direction 4",    // Car 2 crosses as the light is green on road B now.
"Car 3 Has Passed Road B In Direction 3",    // Car 3 crosses as the light is green on road B now.
"Traffic Light On Road A Is Green",          // Car 5 requests green light for road A.
"Car 5 Has Passed Road A In Direction 1",    // Car 5 crosses as the light is green on road A now.
"Traffic Light On Road B Is Green",          // Car 4 requests green light for road B. Car 4 blocked until car 5 crosses and then traffic light is green on road B.
"Car 4 Has Passed Road B In Direction 3"     // Car 4 crosses as the light is green on road B now.
]

👨‍💻 Алгоритм:

1⃣Если на дороге, по которой едет автомобиль, уже зеленый свет, вызываем функцию crossCar.

2⃣Если на дороге, по которой едет автомобиль, красный свет, вызываем функцию turnGreen, чтобы переключить свет на зеленый, и затем вызываем функцию crossCar.

3⃣Обеспечиваем, что функции turnGreen и crossCar вызываются атомарно для предотвращения гонок и тупиков

😎 Решение:

using System;
using System.Threading;

public class TrafficLight {
    private int greenRoad = 1;
    private readonly object lockObj = new object();

    public void CarArrived(
        int carId,
        int roadId,
        int direction,
        Action turnGreen,
        Action crossCar
    ) {
        lock (lockObj) {
            if (greenRoad != roadId) {
                turnGreen();
                greenRoad = roadId;
            }
            crossCar();
        }
    }
}

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

Задача: 1053. Previous Permutation With One Swap
Сложность: medium

Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].

Пример:

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

👨‍💻 Алгоритм:

1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.

2⃣Пройди по массиву, используя скользящее окно для учета эффекта от техники.

3⃣Найди максимальное количество дополнительных удовлетворенных покупателей, которые можно получить, используя технику на k минут подряд.

😎 Решение:

public class Solution {
    public int[] PrevPermOpt1(int[] arr) {
        int n = arr.Length;
        int i;
        for (i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                break;
            }
        }
        if (i == -1) {
            return arr;
        }
        
        int j;
        for (j = n - 1; j > i; j--) {
            if (arr[j] < arr[i] && (j == n - 1 || arr[j] != arr[j + 1])) {
                break;
            }
        }
        
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        
        return arr;
    }
}

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

Задача: 1356. Sort Integers by The Number of 1 Bits
Сложность: easy

Дан целочисленный массив arr. Отсортируйте целые числа в массиве по возрастанию числа единиц в их двоичном представлении, а в случае, если у двух или более чисел одинаковое количество единиц, отсортируйте их по возрастанию.

Верните массив после сортировки.

Пример:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

👨‍💻 Алгоритм:

1⃣Создание функции для подсчета единиц:
Создайте функцию, которая принимает целое число и возвращает количество единиц в его двоичном представлении.

2⃣Сортировка массива:
Используйте встроенную функцию сортировки, передавая ей пользовательскую функцию сравнения, которая использует количество единиц в двоичном представлении чисел для сортировки. Если количество единиц одинаковое, используйте само число для сортировки.

3⃣Возврат отсортированного массива:
Верните отсортированный массив.

😎 Решение:

using System;
using System.Linq;

public class Solution {
    public int[] SortByBits(int[] arr) {
        return arr.OrderBy(x => Convert.ToString(x, 2).Count(c => c == '1')).ThenBy(x => x).ToArray();
    }
}

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

Задача: 281. Zigzag Iterator
Сложность: medium

Даны два вектора целых чисел v1 и v2, реализуйте итератор, который возвращает их элементы поочередно.

Реализуйте класс ZigzagIterator:
ZigzagIterator(List<int> v1, List<int> v2) инициализирует объект с двумя векторами v1 и v2.
boolean hasNext() возвращает true, если в итераторе еще есть элементы, и false в противном случае.
int next() возвращает текущий элемент итератора и перемещает итератор к следующему элементу.

Пример:

Input: v1 = [1,2], v2 = [3,4,5,6]
Output: [1,3,2,4,5,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].

👨‍💻 Алгоритм:

1⃣Инициализация: сохраняем оба списка в переменных vectorsи добавляем по очереди индексы тех, у кого есть элементы.

2⃣Метод Next: извлекаем текущий элемент по индексам из очереди, если есть следующий в этом списке — добавляем в очередь.

3⃣Метод HasNext: проверяем, пуста очередь. Если нет — возвращаем истину.

😎 Решение:

using System.Collections.Generic;

public class ZigzagIterator {
    private List<List<int>> vectors = new List<List<int>>();
    private Queue<KeyValuePair<int, int>> queue = new Queue<KeyValuePair<int, int>>();

    public ZigzagIterator(List<int> v1, List<int> v2) {
        vectors.Add(v1);
        vectors.Add(v2);
        for (int i = 0; i < vectors.Count; i++) {
            if (vectors[i].Count > 0) {
                queue.Enqueue(new KeyValuePair<int, int>(i, 0));
            }
        }
    }

    public int Next() {
        var pointer = queue.Dequeue();
        int vecIndex = pointer.Key;
        int elemIndex = pointer.Value;
        int nextElemIndex = elemIndex + 1;
        if (nextElemIndex < vectors[vecIndex].Count) {
            queue.Enqueue(new KeyValuePair<int, int>(vecIndex, nextElemIndex));
        }
        return vectors[vecIndex][elemIndex];
    }

    public bool HasNext() {
        return queue.Count > 0;
    }
}

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

Задача: 536. Construct Binary Tree from String
Сложность: medium

Вам нужно построить бинарное дерево из строки, состоящей из круглых скобок и целых чисел.

Весь ввод представляет собой бинарное дерево. Он содержит целое число, за которым следуют ноль, одна или две пары круглых скобок. Целое число представляет значение корня, а пара круглых скобок содержит дочернее бинарное дерево с той же структурой.

Вы всегда начинаете строить левый дочерний узел родителя сначала, если он существует.

Пример:

Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]

👨‍💻 Алгоритм:

1⃣ Извлечение числа:
Определите функцию getNumber, которая извлекает целое число из текущей строки, начиная с указанного индекса. Учтите знак числа, если он есть.

2⃣ Построение поддерева:
Определите рекурсивную функцию str2treeInternal, которая принимает строку и текущий индекс в качестве входных данных и возвращает пару: узел TreeNode и следующий индекс для обработки.
Внутри функции извлеките значение для корневого узла текущего поддерева, создайте узел, а затем рекурсивно постройте левое и правое поддеревья, если они существуют.

3⃣ Основная функция:
Определите основную функцию str2tree, которая вызывает рекурсивную функцию str2treeInternal и возвращает построенное дерево.

😎 Решение:

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

public class Solution {
    public TreeNode Str2Tree(string s) {
        return Str2TreeInternal(s, 0).Item1;
    }
    
    private Tuple<int, int> GetNumber(string s, int index) {
        bool isNegative = false;
        if (s[index] == '-') {
            isNegative = true;
            index++;
        }
        int number = 0;
        while (index < s.Length && char.IsDigit(s[index])) {
            number = number * 10 + (s[index] - '0');
            index++;
        }
        return Tuple.Create(isNegative ? -number : number, index);
    }

    private Tuple<TreeNode, int> Str2TreeInternal(string s, int index) {
        if (index == s.Length) return Tuple.Create<TreeNode, int>(null, index);
        
        var numberData = GetNumber(s, index);
        int value = numberData.Item1;
        index = numberData.Item2;
        
        TreeNode node = new TreeNode(value);
        
        if (index < s.Length && s[index] == '(') {
            var leftData = Str2TreeInternal(s, index + 1);
            node.left = leftData.Item1;
            index = leftData.Item2;
        }

        if (index < s.Length && s[index] == '(') {
            var rightData = Str2TreeInternal(s, index + 1);
            node.right = rightData.Item1;
            index = rightData.Item2;
        }
        
        return Tuple.Create(node, index < s.Length && s[index] == ')' ? index + 1 : index);
    }
}

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

Задача: 1049. Last Stone Weight II
Сложность: medium

Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два любых камня и разбиваем их вместе. Предположим, что камни имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y приобретает новый вес y - x. В конце игры остается не более одного камня. Верните наименьший возможный вес оставшегося камня. Если камней не осталось, верните 0.

Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

👨‍💻 Алгоритм:

1⃣Используй метод динамического программирования, чтобы проверить, можно ли разделить камни на две группы с равной суммой.

2⃣Определи, какие веса можно достичь, используя половину суммы всех камней.

3⃣Найди наибольшую достижимую сумму, которая меньше или равна половине общей суммы, и верни разницу между общей суммой и удвоенной этой суммой.Верни максимальную длину среди всех цепочек.

😎 Решение:

public class Solution {
    public int LastStoneWeightII(int[] stones) {
        int totalSum = stones.Sum();
        int halfSum = totalSum / 2;
        int[] dp = new int[halfSum + 1];

        foreach (var stone in stones) {
            for (int j = halfSum; j >= stone; j--) {
                dp[j] = Math.Max(dp[j], dp[j - stone] + stone);
            }
        }

        return totalSum - 2 * dp[halfSum];
    }
}

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

Задача: 233. Number of Digit One
Сложность: hard

Дано целое число n, посчитайте общее количество единиц, встречающихся во всех неотрицательных числах, меньших или равных n.

Пример:

Input: n = 13
Output: 6

👨‍💻 Алгоритм:

1⃣Итерация по степеням 10: Итеративно увеличивайте значение i от 1 до n, увеличивая i в 10 раз на каждом шаге. Это позволяет анализировать каждую цифру числа n.

2⃣Подсчет групповых единиц: Для каждой итерации добавляйте (n / (i * 10)) * i к счетчику countr, что представляет собой количество единиц, встречающихся в группах размера i после каждого интервала (i * 10).

3⃣Добавление дополнительных единиц: Для каждой итерации добавляйте min(max((n % (i * 10)) - i + 1, 0), i) к счетчику countr, что представляет собой дополнительные единицы, зависящие от цифры на позиции i.

😎 Решение:

public class Solution {
    public int CountDigitOne(int n) {
        int countr = 0;
        for (long i = 1; i <= n; i *= 10) {
            long divider = i * 10;
            countr += (n / divider) * i + Math.Min(Math.Max(n % divider - i + 1, 0), i);
        }
        return countr;
    }
}

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

Задача: 297. Serialize and Deserialize Binary Tree
Сложность: hard

Сериализация — это процесс преобразования структуры данных или объекта в последовательность битов, чтобы их можно было сохранить в файле или буфере памяти или передать по сетевому соединению для последующего восстановления в той же или другой компьютерной среде.

Разработайте алгоритм для сериализации и десериализации бинарного дерева. Нет ограничений на то, как ваш алгоритм сериализации/десериализации должен работать. Вам нужно просто гарантировать, что бинарное дерево может быть сериализовано в строку, и эта строка может быть десериализована в исходную структуру дерева.

Уточнение: формат ввода/вывода такой же, как в LeetCode для сериализации бинарного дерева. Вам не обязательно придерживаться этого формата, так что будьте креативны и придумайте свои подходы.

Пример:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

👨‍💻 Алгоритм:

1⃣Сериализация дерева:
Используйте рекурсивный обход дерева в порядке root -> left subtree -> right subtree.
Для каждого узла добавляйте его значение в строку сериализации. Если узел пустой, добавляйте "None".

2⃣Пример:
Начните с корня, узел 1, строка сериализации становится "1,".
Переходите к левому поддереву с корнем 2, строка сериализации становится "1,2,".
Для узла 2, посетите его левый узел 3 ("1,2,3,None,None,") и правый узел 4 ("1,2,3,None,None,4,None,None").
Возвращайтесь к корню 1 и посетите его правое поддерево, узел 5 ("1,2,3,None,None,4,None,None,5,None,None,").

3⃣Десериализация строки:
Разделите строку на список значений.
Используйте рекурсивную функцию для создания узлов дерева, извлекая значения из списка и восстанавливая структуру дерева. Если значение "None", узел пустой.

😎 Решение:

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 Codec {
    private void Rserialize(TreeNode root, StringBuilder str) {
        if (root == null) {
            str.Append("null,");
        } else {
            str.Append(root.val).Append(",");
            Rserialize(root.left, str);
            Rserialize(root.right, str);
        }
    }

    public string Serialize(TreeNode root) {
        StringBuilder str = new StringBuilder();
        Rserialize(root, str);
        return str.ToString();
    }

    private TreeNode Rdeserialize(Queue<string> data) {
        if (data.Peek() == "null") {
            data.Dequeue();
            return null;
        }

        TreeNode root = new TreeNode(int.Parse(data.Dequeue()));
        root.left = Rdeserialize(data);
        root.right = Rdeserialize(data);
        return root;
    }

    public TreeNode Deserialize(string data) {
        Queue<string> dataArray = new Queue<string>(data.Split(','));
        return Rdeserialize(dataArray);
    }
}

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

Задача: 524. Longest Word in Dictionary through Deleting
Сложность: medium

Даны строка s и массив строк dictionary. Верните самую длинную строку из dictionary, которую можно сформировать, удаляя некоторые символы из данной строки s. Если возможных результатов несколько, верните самое длинное слово с наименьшим лексикографическим порядком. Если возможного результата нет, верните пустую строку.

Пример:

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

👨‍💻 Алгоритм:

1⃣Инициализируйте переменную для хранения самой длинной строки, соответствующей критериям. Пройдите по каждой строке x в неотсортированном массиве dictionary и проверьте, является ли x подпоследовательностью строки s.

2⃣Если строка x является подпоследовательностью, сравните её с текущей самой длинной строкой по длине. Если длина x больше или равна длине текущей самой длинной строки и она меньше текущей строки в лексикографическом порядке (если равны по длине), обновите текущую самую длинную строку.

3⃣После рассмотрения всех строк в dictionary, верните найденную строку. Если ни одна строка не подошла, верните пустую строку.

😎 Решение:

public class Solution {
    public bool IsSubsequence(string x, string y) {
        int j = 0;
        for (int i = 0; i < y.Length && j < x.Length; i++) {
            if (x[j] == y[i]) {
                j++;
            }
        }
        return j == x.Length;
    }

    public string FindLongestWord(string s, IList<string> d) {
        string maxStr = "";
        foreach (string str in d) {
            if (IsSubsequence(str, s)) {
                if (str.Length > maxStr.Length || (str.Length == maxStr.Length && string.Compare(str, maxStr) < 0)) {
                    maxStr = str;
                }
            }
        }
        return maxStr;
    }
}

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

Задача: 1481. Least Number of Unique Integers after K Removals
Сложность: medium

Дан массив целых чисел arr и целое число k. Найдите минимальное количество уникальных целых чисел после удаления ровно k элементов.

Пример:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

👨‍💻 Алгоритм:

1⃣Инициализация и построение частотного массива:
Создайте хеш-таблицу для отслеживания частот элементов массива arr.
Итеративно увеличивайте частоту элементов в хеш-таблице.

2⃣Сортировка и удаление элементов:
Создайте массив частот и заполните его значениями из хеш-таблицы.
Отсортируйте массив частот.
Инициализируйте переменную для отслеживания числа удаленных элементов и итеративно добавляйте частоты, пока количество удаленных элементов не превысит k.

3⃣Возвращение результата:
Если количество удаленных элементов превысило k, верните оставшееся количество уникальных элементов.
Если все элементы были удалены, верните 0.

😎 Решение:

public class Solution {
    public int FindLeastNumOfUniqueInts(int[] arr, int k) {
        var freqMap = new Dictionary<int, int>();
        foreach (var num in arr) {
            if (freqMap.ContainsKey(num)) {
                freqMap[num]++;
            } else {
                freqMap[num] = 1;
            }
        }
        
        var frequencies = new List<int>(freqMap.Values);
        frequencies.Sort();
        
        int elementsRemoved = 0;
        for (int i = 0; i < frequencies.Count; i++) {
            elementsRemoved += frequencies[i];
            if (elementsRemoved > k) {
                return frequencies.Count - i;
            }
        }
        
        return 0;
    }
}

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

Задача: 776. Split BST
Сложность: medium

Дан корень бинарного дерева поиска (BST) и целое число target, разделите дерево на два поддерева, где первое поддерево содержит узлы, которые меньше или равны значению target, а второе поддерево содержит узлы, которые больше значения target. Не обязательно, чтобы дерево содержало узел со значением target.

Кроме того, большая часть структуры исходного дерева должна сохраниться. Формально, для любого потомка c с родителем p в исходном дереве, если они оба находятся в одном поддереве после разделения, то узел c все еще должен иметь родителя p.

Верните массив из двух корней двух поддеревьев в порядке.

Пример:

Input: root = [4,2,6,1,3,5,7], target = 2
Output: [[2,1],[4,3,6,null,null,5,7]]

👨‍💻 Алгоритм:

1⃣Базовый случай: Если корень равен null, верните массив, содержащий два указателя null. Это необходимо для обработки случая, когда дерево пустое.

2⃣Проверьте, больше ли значение корня целевого значения. Если да, рекурсивно разделите левое поддерево, вызвав splitBST(root->left, target). Прикрепите правую часть разделенного к левому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень.

3⃣Если значение корня меньше или равно целевому значению, рекурсивно разделите правое поддерево, вызвав splitBST(root->right, target). Прикрепите левую часть разделенного к правому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень.

😎 Решение:

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

public class Solution {
    public TreeNode[] SplitBST(TreeNode root, int target) {
        if (root == null) {
            return new TreeNode[]{null, null};
        }

        if (root.val > target) {
            TreeNode[] left = SplitBST(root.left, target);
            root.left = left[1];
            return new TreeNode[]{left[0], root};
        } else {
            TreeNode[] right = SplitBST(root.right, target);
            root.right = right[0];
            return new TreeNode[]{root, right[1]};
        }
    }
}

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

Задача: 811. Subdomain Visit Count
Сложность: medium

Веб-сайт с доменом "discuss.leetcode.com" состоит из различных поддоменов. На верхнем уровне у нас есть "com", на следующем уровне - "leetcode.com", и на самом нижнем уровне - "discuss.leetcode.com". Когда мы посещаем домен, такой как "discuss.leetcode.com", мы также автоматически посещаем родительские домены "leetcode.com" и "com".

Домен с парным счетчиком - это домен, который имеет один из двух форматов "rep d1.d2.d3" или "rep d1.d2", где rep - это количество посещений домена, а d1.d2.d3 - это сам домен.

Например, "9001 discuss.leetcode.com" - это домен с парным счетчиком, указывающий на то, что discuss.leetcode.com был посещен 9001 раз.
Дан массив доменов с парными счетчиками cpdomains, верните массив доменов с парными счетчиками для каждого поддомена во входных данных. Вы можете вернуть ответ в любом порядке.

Пример:

Input: cpdomains = ["9001 discuss.leetcode.com"]
Output: ["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
Explanation: We only have one website domain: "discuss.leetcode.com".
As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

👨‍💻 Алгоритм:

1⃣Следуем указаниям из условия задачи.

2⃣Для адреса вида a.b.c, подсчитываем a.b.c, b.c и c. Для адреса вида x.y, подсчитываем x.y и y.

3⃣Для подсчета этих строк используем хеш-таблицу. Для разделения строк на требуемые части используем библиотечные функции split.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public IList<string> SubdomainVisits(string[] cpdomains) {
        var ans = new Dictionary<string, int>();
        foreach (var domain in cpdomains) {
            var parts = domain.Split(' ');
            var count = int.Parse(parts[0]);
            var frags = parts[1].Split('.');
            for (int i = 0; i < frags.Length; i++) {
                var subdomain = string.Join(".", frags, i, frags.Length - i);
                if (ans.ContainsKey(subdomain)) {
                    ans[subdomain] += count;
                } else {
                    ans[subdomain] = count;
                }
            }
        }
        var res = new List<string>();
        foreach (var entry in ans) {
            res.Add($"{entry.Value} {entry.Key}");
        }
        return res;
    }
}

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

Задача: 761. Special Binary String
Сложность: hard

Специальные двоичные строки - это двоичные строки, обладающие следующими двумя свойствами: количество 0 равно количеству 1. Каждый префикс двоичной строки имеет не меньше 1, чем 0. Вам дана специальная двоичная строка s. Ход состоит в выборе двух последовательных, непустых специальных подстрок s и их обмене. Две строки являются последовательными, если последний символ первой строки находится ровно на один индекс раньше первого символа второй строки. Верните лексикографически наибольшую результирующую строку, возможную после применения указанных операций над строкой.

Пример:

Input: s = "11011000"
Output: "11100100"

👨‍💻 Алгоритм:

1⃣Определите, что специальная двоичная строка можно разбить на несколько специальных подстрок.

2⃣Рекурсивно примените к каждой подстроке этот алгоритм, чтобы найти лексикографически наибольшую строку.

3⃣Сортируйте полученные подстроки в лексикографическом порядке по убыванию и объединяйте их.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public string MakeLargestSpecial(string s) {
        int count = 0, i = 0;
        List<string> substrs = new List<string>();
        for (int j = 0; j < s.Length; j++) {
            count += s[j] == '1' ? 1 : -1;
            if (count == 0) {
                substrs.Add("1" + MakeLargestSpecial(s.Substring(i + 1, j - i - 1)) + "0");
                i = j + 1;
            }
        }
        substrs.Sort((a, b) => string.Compare(b, a, StringComparison.Ordinal));
        return string.Join("", substrs);
    }
}

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

Задача: 394. Decode String
Сложность: medium

Дана закодированная строка, вернуть её декодированную версию.

Правило кодирования следующее: k[закодированная_строка], где закодированная_строка внутри квадратных скобок повторяется ровно k раз. Обратите внимание, что k гарантированно является положительным целым числом.

Можно предположить, что входная строка всегда допустима; нет лишних пробелов, квадратные скобки корректно сформированы и т.д. Более того, можно предположить, что исходные данные не содержат никаких цифр, и что цифры используются только для обозначения количества повторений, k. Например, не будет таких входных данных, как 3a или 2[4].

Тестовые случаи сгенерированы так, что длина выходной строки никогда не превысит 105.

Пример:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

👨‍💻 Алгоритм:

1⃣Проходите по строке s и обрабатывайте каждый символ. Если текущий символ не является закрывающей скобкой ], поместите его в стек.

2⃣Если текущий символ является закрывающей скобкой ], начните декодировать последнюю пройденную строку. Извлекайте из стека символы, пока следующий символ не станет открывающей скобкой [, и добавляйте каждый символ (a-z) к decodedString. Затем извлеките открывающую скобку [ из стека и извлекайте символы, пока следующий символ является цифрой (0-9), чтобы собрать число k.

3⃣Декодируйте шаблон k[decodedString], помещая decodedString в стек k раз. После того как вся строка будет пройдена, извлеките результат из стека и верните его.

😎 Решение:

public class Solution {
    public string DecodeString(string s) {
        Stack<char> stack = new Stack<char>();
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == ']') {
                string decodedString = "";
                while (stack.Peek() != '[') {
                    decodedString = stack.Pop() + decodedString;
                }
                stack.Pop();
                int baseValue = 1;
                int k = 0;
                while (stack.Count > 0 && char.IsDigit(stack.Peek())) {
                    k = k + (stack.Pop() - '0') * baseValue;
                    baseValue *= 10;
                }
                while (k != 0) {
                    for (int j = decodedString.Length - 1; j >= 0; j--) {
                        stack.Push(decodedString[j]);
                    }
                    k--;
                }
            } else {
                stack.Push(s[i]);
            }
        }
        string result = "";
        while (stack.Count > 0) {
            result = stack.Pop() + result;
        }
        return result;
    }
}

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

Задача: 203. Remove Linked List Elements
Сложность: easy

Для заданного начала связного списка и целого числа val удалите все узлы связного списка, у которых Node.val равно val, и верните новое начало списка.

Пример:

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

👨‍💻 Алгоритм:

1⃣Инициализируйте сторожевой узел как ListNode(0) и установите его новым началом: sentinel.next = head. Инициализируйте два указателя для отслеживания текущего узла и его предшественника: curr и prev.

2⃣Пока curr не является нулевым указателем, сравните значение текущего узла со значением для удаления. Если значения равны, удалите текущий узел: prev.next = curr.next, иначе установите предшественника равным текущему узлу. Переместитесь к следующему узлу: curr = curr.next.

3⃣Верните sentinel.next.

😎 Решение:

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode DeleteNode(ListNode head, int value) {
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
        ListNode prev = sentinel, curr = head;

        while (curr != null) {
            if (curr.val == value) {
                prev.next = curr.next;
            } else {
                prev = curr;
            }
            curr = curr.next;
        }
        return sentinel.next;
    }
}

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

Задача: 931. Minimum Falling Path Sum
Сложность: medium

Если задан массив целых чисел n x n, верните минимальную сумму любого падающего пути через матрицу. Падающий путь начинается с любого элемента в первой строке и выбирает элемент в следующей строке, который находится либо прямо под ним, либо по диагонали слева/справа. В частности, следующим элементом из позиции (row, col) будет (row + 1, col - 1), (row + 1, col) или (row + 1, col + 1).

Пример:

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

👨‍💻 Алгоритм:

1⃣Использовать динамическое программирование для хранения минимальных сумм падающих путей для каждой позиции.

2⃣Инициализировать dp массив копией первой строки исходной матрицы.
Пройти по каждой строке, обновляя dp массив на основе значений из предыдущей строки.

3⃣Вернуть минимальное значение в последней строке dp массива.

😎 Решение:

public class Solution {
    public int MinFallingPathSum(int[][] matrix) {
        int n = matrix.Length;
        int[] dp = (int[])matrix[0].Clone();
        
        for (int i = 1; i < n; i++) {
            int[] newDp = new int[n];
            for (int j = 0; j < n; j++) {
                newDp[j] = matrix[i][j] + Math.Min(dp[j], Math.Min(j > 0 ? dp[j - 1] : int.MaxValue, j < n - 1 ? dp[j + 1] : int.MaxValue));
            }
            dp = newDp;
        }
        
        int minSum = int.MaxValue;
        foreach (int sum in dp) {
            minSum = Math.Min(minSum, sum);
        }
        return minSum;
    }
}

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