Задача: 814. Binary Tree Pruning
Сложность: medium

Дан корень бинарного дерева. Верните то же дерево, в котором удалены все поддеревья (данного дерева), не содержащие 1.

Поддерево узла node - это сам узел node и все узлы, являющиеся потомками node.

Пример:

Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

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

1⃣Используем функцию containsOne(node), которая сообщает, содержит ли поддерево в данном узле единицу, и обрезает все поддеревья, не содержащие единицу.

2⃣Например, если поддерево node.left не содержит единицу, то мы должны обрезать его через node.left = null.

3⃣Также нужно проверить родительский узел. Например, если дерево состоит из одного узла 0, то ответом будет пустое дерево.

😎 Решение:

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 PruneTree(TreeNode root) {
        return ContainsOne(root) ? root : null;
    }

    private bool ContainsOne(TreeNode node) {
        if (node == null) return false;

        bool leftContainsOne = ContainsOne(node.left);
        bool rightContainsOne = ContainsOne(node.right);

        if (!leftContainsOne) node.left = null;
        if (!rightContainsOne) node.right = null;

        return node.val == 1 || leftContainsOne || rightContainsOne;
    }
}

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

Задача: 509. Fibonacci Number
Сложность: easy

Числа Фибоначчи, обычно обозначаемые как F(n), образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.
Дано n, вычислите F(n).

Пример:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

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

1⃣Проверка начального условия
Если N <= 1, вернуть N.

2⃣Инициализация переменных
Инициализируйте current значением 0. Инициализируйте prev1 значением 1, что будет представлять fib(N-1) при вычислении текущего значения. Инициализируйте prev2 значением 0, что будет представлять fib(N-2) при вычислении текущего значения.

3⃣Итерация и вычисление
Итерация от 2 до N включительно. На каждой итерации: установите current как сумму prev1 и prev2. Обновите prev2 значением prev1. Обновите prev1 значением current. Вернуть значение current после завершения итерации.

😎 Решение:

public class Solution {
    public int Fib(int N) {
        if (N <= 1) return N;
        int current = 0, prev1 = 1, prev2 = 0;
        for (int i = 2; i <= N; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return current;
    }
}

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

Задача: 635. Design Log Storage System
Сложность: medium

Вам дается несколько журналов, где каждый журнал содержит уникальный идентификатор и временную метку. Временная метка - это строка, имеющая следующий формат: Год:Месяц:День:Час:Минута:Секунда, например, 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;
        }
    }
}

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

Задача: 736. Parse Lisp Expression
Сложность: hard

Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.

Пример:

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14

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

1⃣Определите функцию для оценки выражений.

2⃣Используйте рекурсивный подход для обработки различных типов выражений (let, add, mult, и переменных).

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

😎 Решение:

public class Solution {
    public int Evaluate(string expression) {
        return Evaluate(expression, new Dictionary<string, int>());
    }
    
    private int Evaluate(string expression, Dictionary<string, int> env) {
        if (expression[0] != '(') {
            return int.TryParse(expression, out var result) ? result : env[expression];
        }
        
        var tokens = Tokenize(expression);
        if (tokens[0] == "let") {
            for (int i = 1; i < tokens.Count - 2; i += 2) {
                env[tokens[i]] = Evaluate(tokens[i + 1], env);
            }
            return Evaluate(tokens[^1], env);
        } else if (tokens[0] == "add") {
            return Evaluate(tokens[1], env) + Evaluate(tokens[2], env);
        } else if (tokens[0] == "mult") {
            return Evaluate(tokens[1], env) * Evaluate(tokens[2], env);
        }
        return 0;
    }
    
    private List<string> Tokenize(string expression) {
        var tokens = new List<string>();
        var token = string.Empty;
        int parens = 0;
        foreach (var c in expression) {
            if (c == '(') {
                parens++;
                if (parens == 1) continue;
            } else if (c == ')') {
                parens--;
                if (parens == 0) {
                    tokens.AddRange(Tokenize(token));
                    token = string.Empty;
                    continue;
                }
            } else if (c == ' ' && parens == 1) {
                if (!string.IsNullOrEmpty(token)) {
                    tokens.Add(token);
                    token = string.Empty;
                }
                continue;
            }
            token += c;
        }
        if (!string.IsNullOrEmpty(token)) {
            tokens.Add(token);
        }
        return tokens;
    }
}

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

Задача: 932. Beautiful Array
Сложность: medium

Массив nums длины n красив, если: nums является перестановкой целых чисел в диапазоне [1, n]. Для каждого 0 <= i < j < n не существует индекса k с i < k < j, где 2 * nums[k] == nums[i] + nums[j]. Задано целое число n, верните любой красивый массив nums длины n. Для заданного n будет хотя бы один правильный ответ.

Пример:

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

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

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

2⃣Если длина массива равна 1, вернуть массив [1].
Разделить n на четные и нечетные индексы и создать массивы для них.

3⃣Объединить массивы, созданные для четных и нечетных индексов, в результирующий массив.

😎 Решение:

public class Solution {
    public int[] BeautifulArray(int n) {
        return Construct(n).ToArray();
    }
    
    private List<int> Construct(int n) {
        if (n == 1) return new List<int> { 1 };
        var odd = Construct((n + 1) / 2).Select(x => 2 * x - 1).ToList();
        var even = Construct(n / 2).Select(x => 2 * x).ToList();
        odd.AddRange(even);
        return odd;
    }
}

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

Задача: 1274. Number of Ships in a Rectangle
Сложность: hard

(Эта задача является интерактивной.) Каждый корабль находится в целочисленной точке моря, представленной картезианской плоскостью, и каждая целочисленная точка может содержать не более 1 корабля. У вас есть функция Sea.hasShips(topRight, bottomLeft), которая принимает две точки в качестве аргументов и возвращает true, если в прямоугольнике, представленном этими двумя точками, есть хотя бы один корабль, включая на границе. Учитывая две точки: правый верхний и левый нижний углы прямоугольника, верните количество кораблей в этом прямоугольнике. Гарантируется, что в прямоугольнике находится не более 10 кораблей. Решения, содержащие более 400 обращений к hasShips, будут оцениваться как "Неправильный ответ". Кроме того, любые решения, пытающиеся обойти судью, приведут к дисквалификации.

Пример:

Input: 
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3

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

1⃣Разделите текущий прямоугольник на четыре меньших прямоугольника

2⃣Рекурсивно проверьте наличие кораблей в каждом из четырех подпрямоугольников, используя функцию hasShips

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

😎 Решение:

public class Solution {
    public int CountShips(Sea sea, Point topRight, Point bottomLeft) {
        if (!sea.HasShips(topRight, bottomLeft)) {
            return 0;
        }
        if (topRight.x == bottomLeft.x && topRight.y == bottomLeft.y) {
            return 1;
        }
        int midX = (topRight.x + bottomLeft.x) / 2;
        int midY = (topRight.y + bottomLeft.y) / 2;
        return CountShips(sea, new Point(midX, midY), bottomLeft) +
               CountShips(sea, topRight, new Point(midX + 1, midY + 1)) +
               CountShips(sea, new Point(midX, topRight.y), new Point(bottomLeft.x, midY + 1)) +
               CountShips(sea, new Point(topRight.x, midY), new Point(midX + 1, bottomLeft.y));
    }
}

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

Задача: 1005. Maximize Sum Of Array After K Negations
Сложность: easy

Учитывая целочисленный массив nums и целое число k, измените массив следующим образом: выберите индекс i и замените nums[i] на -nums[i]. Вы должны применить этот процесс ровно k раз. Вы можете выбрать один и тот же индекс i несколько раз. Верните наибольшую возможную сумму массива после его модификации таким образом.

Пример:

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

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

1⃣Сортировка массива:
Отсортируйте массив nums по возрастанию, чтобы наибольшее количество раз менять самые маленькие (отрицательные) значения на их противоположные.

2⃣Модификация массива:
Пройдитесь по отсортированному массиву и замените k наименьших значений на их противоположные (умножьте на -1). Если встретите 0, прекратите дальнейшие изменения, так как изменение 0 на -0 не имеет смысла.

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

😎 Решение:

public class Solution {
    public int LargestSumAfterKNegations(int[] nums, int k) {
        Array.Sort(nums);
        
        for (int i = 0; i < nums.Length; i++) {
            if (k > 0 && nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        
        if (k % 2 == 1) {
            Array.Sort(nums);
            nums[0] = -nums[0];
        }
        
        return nums.Sum();
    }
}

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

Задача: 929. Unique Email Addresses
Сложность: easy

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: emails = ["[email protected]","[email protected]","[email protected]"]
Output: 2

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

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

2⃣Для каждого адреса в emails:
Разделить адрес на локальное и доменное имя по символу '@'.
Обработать локальное имя:
Удалить все точки '.'.
Обрезать часть после символа '+'.
Объединить обработанное локальное имя и доменное имя.
Добавить результат в множество уникальных адресов.

3⃣Вернуть количество уникальных адресов в множестве.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int NumUniqueEmails(string[] emails) {
        var uniqueEmails = new HashSet<string>();
        foreach (var email in emails) {
            var parts = email.Split('@');
            var local = parts[0].Split('+')[0].Replace(".", "");
            uniqueEmails.Add($"{local}@{parts[1]}");
        }
        return uniqueEmails.Count;
    }
}

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

Задача: 169. Majority Element
Сложность: easy

Дан массив nums размера n, верните элемент большинства.

Элемент большинства — это элемент, который встречается более чем ⌊n / 2⌋ раз. Можно предположить, что элемент большинства всегда существует в массиве.

Пример:

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

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

1⃣Использование HashMap для подсчета:
Создайте HashMap для отслеживания количества каждого элемента в массиве.

2⃣Подсчет вхождений элементов:
Пройдите по массиву nums, увеличивая счетчик в HashMap для каждого элемента.

3⃣Поиск элемента большинства:
Определите элемент большинства, просмотрев HashMap и найдя ключ с максимальным значением, которое должно быть больше ⌊n / 2⌋

😎 Решение:

public class Solution {
    private Dictionary<int, int> countNums(int[] nums) {
        var counts = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (!counts.ContainsKey(num)) {
                counts.Add(num, 1);
            } else {
                counts[num]++;
            }
        }

        return counts;
    }

    public int MajorityElement(int[] nums) {
        var counts = countNums(nums);

        foreach (var count in counts) {
            if (count.Value > nums.Length / 2)
                return count.Key;
        }

        return 0;
    }
}

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

Задача: 600. Non-negative Integers without Consecutive Ones
Сложность: hard

Дано положительное целое число n, верните количество чисел в диапазоне [0, n], бинарные представления которых не содержат последовательных единиц.

Пример:

Input: n = 5
Output: 5
Explanation:
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 

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

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

2⃣Чтобы проверить, существует ли 1 на позиции x (считая от младшего значащего бита), в текущем числе n, поступаем следующим образом. Сдвигаем двоичную 1 x−1 раз влево, чтобы получить число y, которое имеет 1 только на x-й позиции. Логическое И числа n и y даст результат 1 только если n содержит 1 на позиции x.

3⃣В конце подсчитываем и возвращаем количество чисел в диапазоне [0, n], не содержащих последовательных единиц.

😎 Решение:

public class Solution {
    public int FindIntegers(int num) {
        int count = 0;
        for (int i = 0; i <= num; i++) {
            if (Check(i)) {
                count++;
            }
        }
        return count;
    }

    public bool Check(int n) {
        int i = 31;
        while (i > 0) {
            if ((n & (1 << i)) != 0 && (n & (1 << (i - 1))) != 0) {
                return false;
            }
            i--;
        }
        return true;
    }
}

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

Задача: 1370. Increasing Decreasing String
Сложность: easy

Дана строка s. Переставьте символы строки, используя следующий алгоритм:

Выберите наименьший символ из s и добавьте его к результату.
Выберите наименьший символ из s, который больше последнего добавленного символа, и добавьте его.
Повторяйте шаг 2, пока не сможете выбрать больше символов.
Выберите наибольший символ из s и добавьте его к результату.
Выберите наибольший символ из s, который меньше последнего добавленного символа, и добавьте его.
Повторяйте шаг 5, пока не сможете выбрать больше символов.
Повторяйте шаги с 1 по 6, пока не выберете все символы из s.
На каждом этапе, если наименьший или наибольший символ появляется более одного раза, вы можете выбрать любое его вхождение и добавить его к результату.

Верните результирующую строку после сортировки s с помощью этого алгоритма.

Пример:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

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

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

3⃣Проверка завершения:
Повторяйте шаги 2 и 3, пока не будут добавлены все символы из строки s в result.

😎 Решение:

public class Solution {
    public string SortString(string s) {
        int[] charCount = new int[26];
        foreach (char c in s) {
            charCount[c - 'a']++;
        }
        
        var result = new System.Text.StringBuilder();
        while (result.Length < s.Length) {
            for (char c = 'a'; c <= 'z'; c++) {
                if (charCount[c - 'a'] > 0) {
                    result.Append(c);
                    charCount[c - 'a']--;
                }
            }
            for (char c = 'z'; c >= 'a'; c--) {
                if (charCount[c - 'a'] > 0) {
                    result.Append(c);
                    charCount[c - 'a']--;
                }
            }
        }
        
        return result.ToString();
    }
}

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

Задача: 249. Group Shifted Strings
Сложность: medium

Выполните следующие операции сдвига на строке:

Правый сдвиг: замените каждую букву следующей буквой английского алфавита, где 'z' заменяется на 'a'. Например, "abc" можно сдвинуть вправо на "bcd" или "xyz" можно сдвинуть вправо на "yza".
Левый сдвиг: замените каждую букву предыдущей буквой английского алфавита, где 'a' заменяется на 'z'. Например, "bcd" можно сдвинуть влево на "abc" или "yza" можно сдвинуть влево на "xyz".
Мы можем продолжать сдвигать строку в обоих направлениях, чтобы сформировать бесконечную последовательность сдвигов.

Например, сдвиньте "abc", чтобы сформировать последовательность: ... <-> "abc" <-> "bcd" <-> ... <-> "xyz" <-> "yza" <-> .... <-> "zab" <-> "abc" <-> ...
Вам дан массив строк strings, сгруппируйте все strings[i], которые принадлежат одной и той же последовательности сдвигов. Ответ можно вернуть в любом порядке.

Пример:

Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"]

Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]

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

1⃣Переберите строки, и для каждой строки найдите ее хэш-значение, сдвигая все символы так, чтобы строка начиналась с 'a'. Значение сдвига равно позиции первого символа строки, и каждый символ сдвигается на это значение с учетом модуля 26.

2⃣Сопоставьте оригинальную строку с найденным хэш-значением в карте mapHashToList, добавляя оригинальную строку в список, соответствующий ее хэш-значению.

3⃣Переберите mapHashToList и сохраните список для каждого ключа в карте в массив ответа groups.

😎 Решение:

using System;
using System.Collections.Generic;
using System.Text;

public class Solution {
    private char ShiftLetter(char letter, int shift) {
        return (char) ((letter - shift + 26) % 26 + 'a');
    }
    
    private string GetHash(string s) {
        int shift = s[0];
        StringBuilder hashKey = new StringBuilder();
        
        foreach (char letter in s) {
            hashKey.Append(ShiftLetter(letter, shift));
        }
        
        return hashKey.ToString();
    }
    
    public IList<IList<string>> GroupStrings(IList<string> strings) {
        var mapHashToList = new Dictionary<string, IList<string>>();
        
        foreach (string str in strings) {
            string hashKey = GetHash(str);
            if (!mapHashToList.ContainsKey(hashKey)) {
                mapHashToList[hashKey] = new List<string>();
            }
            mapHashToList[hashKey].Add(str);
        }
        
        var groups = new List<IList<string>>();
        foreach (var pair in mapHashToList) {
            groups.Add(pair.Value);
        }
        
        return groups;
    }
}

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

Задача: 1160. Find Words That Can Be Formed by Characters
Сложность: easy

Вам дан массив строк words и строка chars.

Строка считается хорошей, если она может быть составлена из символов chars (каждый символ может быть использован только один раз).

Верните сумму длин всех хороших строк в words.

Пример:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

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

1⃣Создайте хеш-таблицу counts, которая будет записывать частоту каждого символа в chars. Инициализируйте переменную ans = 0.

2⃣Итерируйте по каждому слову в words. Создайте хеш-таблицу wordCount, которая будет записывать частоту каждого символа в слове. Установите good = true. Итерируйте по каждому ключу c в wordCount. Пусть freq = wordCount[c]. Если counts[c] < freq, установите good = false и прервите цикл.

3⃣Если good = true, добавьте длину слова к ans. Верните ans.

😎 Решение:

public class Solution {
    public int CountCharacters(string[] words, string chars) {
        var counts = new Dictionary<char, int>();
        foreach (var c in chars) {
            if (!counts.ContainsKey(c)) {
                counts[c] = 0;
            }
            counts[c]++;
        }
        
        int ans = 0;
        foreach (var word in words) {
            var wordCount = new Dictionary<char, int>();
            foreach (var c in word) {
                if (!wordCount.ContainsKey(c)) {
                    wordCount[c] = 0;
                }
                wordCount[c]++;
            }
            
            bool good = true;
            foreach (var kv in wordCount) {
                if (counts.GetValueOrDefault(kv.Key, 0) < kv.Value) {
                    good = false;
                    break;
                }
            }
            
            if (good) {
                ans += word.Length;
            }
        }
        
        return ans;
    }
}

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

Задача: 124. Binary Tree Maximum Path Sum
Сложность: hard

Вам дан массив prices, где prices[i]— это цена акции в i-й день.
Найдите источник прибыли , которую можно получить, совершив не более двух транзакций.​ Важно : нельзя уча.
Важно: нельзя участвовать в нескольких транзакциях одновременно — нужно сначала продать , прежде чем покупать снова.

Пример:

Input: prices = [3,3,5,0,0,3,1,4] Output: 6алго

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

1⃣Пройдите массив слева направо, отслеживая минимальную цену и создавая массив leftProfits, где leftProfits[i]— максимальная прибыль от одной транзакции до дня i.

2⃣Пройдите по массиву справа налево, отслеживая дефекты цены и изменяя массив rightProfits, где rightProfits[i]— максимальная прибыль от одной транзакции со дня iдо конца.

3⃣Для каждого дня iпосчитайте сумму leftProfits[i] + rightProfits[i + 1]и найдите наибольшее значение этой суммы.

😎 Решение:

public class Solution {
    public int MaxProfit(int[] prices) {
        int length = prices.Length;
        if (length <= 1)
            return 0;
        int leftMin = prices[0];
        int rightMax = prices[length - 1];
        int[] leftProfits = new int[length];
        int[] rightProfits = new int[length + 1];
        for (var l = 1; l < length; ++l) {
            leftProfits[l] = Math.Max(leftProfits[l - 1], prices[l] - leftMin);
            leftMin = Math.Min(leftMin, prices[l]);
            int r = length - 1 - l;
            rightProfits[r] =
                Math.Max(rightProfits[r + 1], rightMax - prices[r]);
            rightMax = Math.Max(rightMax, prices[r]);
        }

        var maxProfit = 0;
        for (var i = 0; i < length; ++i)
            maxProfit =
                Math.Max(maxProfit, leftProfits[i] + rightProfits[i + 1]);
        return maxProfit;
    }
}

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

Задача: 1345. Jump Game IV
Сложность: hard

Дан массив целых чисел arr, изначально вы находитесь на первом индексе массива.

За один шаг вы можете прыгнуть с индекса i на индекс:

- i + 1, где: i + 1 < arr.length.
- i - 1, где: i - 1 >= 0.
- j, где: arr[i] == arr[j] и i != j.

Вернуть минимальное количество шагов, чтобы достичь последнего индекса массива.

Обратите внимание, что нельзя прыгать за пределы массива в любой момент времени.

Пример:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

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

1⃣Построить граф, где ключи - значения из массива, а значения - списки индексов этих значений. Начать с первого индекса, добавив его в очередь текущего слоя и инициализировать набор посещенных индексов.

2⃣Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя.

3⃣Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь.

😎 Решение:

public class Solution {
    public int MinJumps(int[] arr) {
        int n = arr.Length;
        if (n <= 1) {
            return 0;
        }

        var graph = new Dictionary<int, List<int>>();
        for (int i = 0; i < n; i++) {
            if (!graph.ContainsKey(arr[i])) {
                graph[arr[i]] = new List<int>();
            }
            graph[arr[i]].Add(i);
        }

        var curs = new List<int> { 0 };
        var visited = new HashSet<int> { 0 };
        int step = 0;

        while (curs.Count > 0) {
            var nex = new List<int>();

            foreach (var node in curs) {
                if (node == n - 1) {
                    return step;
                }

                foreach (var child in graph[arr[node]]) {
                    if (!visited.Contains(child)) {
                        visited.Add(child);
                        nex.Add(child);
                    }
                }

                graph[arr[node]].Clear();

                if (node + 1 < n && !visited.Contains(node + 1)) {
                    visited.Add(node + 1);
                    nex.Add(node + 1);
                }
                if (node - 1 >= 0 && !visited.Contains(node - 1)) {
                    visited.Add(node - 1);
                    nex.Add(node - 1);
                }
            }

            curs = nex;
            step++;
        }

        return -1;
    }
}

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

Задача: 501. Find Mode in Binary Search Tree
Сложность: easy

Дано корень бинарного дерева поиска (BST) с дубликатами. Необходимо вернуть все моды (т.е. самые часто встречающиеся элементы) в этом дереве.
Если в дереве более одной моды, верните их в любом порядке.

Предположим, что BST определяется следующим образом:
Левое поддерево узла содержит только узлы с ключами, меньшими или равными ключу этого узла.
Правое поддерево узла содержит только узлы с ключами, большими или равными ключу этого узла.
Оба поддерева также должны быть бинарными деревьями поиска.

Пример:

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

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

1⃣Обход дерева
Выполните обход дерева (inorder DFS) с использованием рекурсивной функции dfs, чтобы пройти по всем узлам дерева. На каждом узле добавьте node.val в список values.

2⃣Поиск мод
Инициализируйте переменные maxStreak, currStreak, currNum как 0 и пустой список ans. Пройдите по списку values. Для каждого числа num: если num равно currNum, увеличьте currStreak. Иначе, установите currStreak равным 1, а currNum равным num. Если currStreak больше maxStreak, обновите maxStreak и сбросьте ans. Если currStreak равен maxStreak, добавьте num в ans.

3⃣Возврат результата
Верните список ans.

😎 Решение:

public class Solution {
    public int[] FindMode(TreeNode root) {
        var values = new List<int>();
        Dfs(root, values);
        
        int maxStreak = 0, currStreak = 0, currNum = 0;
        var ans = new List<int>();
        
        foreach (int num in values) {
            if (num == currNum) {
                currStreak++;
            } else {
                currStreak = 1;
                currNum = num;
            }
            
            if (currStreak > maxStreak) {
                ans.Clear();
                ans.Add(num);
                maxStreak = currStreak;
            } else if (currStreak == maxStreak) {
                ans.Add(num);
            }
        }
        
        return ans.ToArray();
    }
    
    private void Dfs(TreeNode node, List<int> values) {
        if (node == null) return;
        Dfs(node.left, values);
        values.Add(node.val);
        Dfs(node.right, values);
    }
}

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

Задача: 949. Largest Time for Given Digits
Сложность: medium

Учитывая массив arr из 4 цифр, найдите самое позднее 24-часовое время, которое можно составить, используя каждую цифру ровно один раз. 24-часовое время имеет формат "ЧЧ:ММ", где ЧЧ - от 00 до 23, а ММ - от 00 до 59. Самое раннее 24-часовое время - 00:00, а самое позднее - 23:59. Верните самое позднее 24-часовое время в формате "HH:MM". Если не удается определить действительное время, возвращается пустая строка.

Пример:

Input: arr = [1,2,3,4]
Output: "23:41"

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

1⃣Перебрать все возможные перестановки массива arr.

2⃣Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время.
Найти самое позднее допустимое время среди всех перестановок.

3⃣Алгоритм
Перебрать все возможные перестановки массива arr.
Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время.
Найти самое позднее допустимое время среди всех перестановок.
Вернуть найденное время в формате "HH
". Если допустимое время не найдено, вернуть пустую строку.

😎 Решение:

public class Solution {
    public string LargestTimeFromDigits(int[] arr) {
        Array.Sort(arr);
        int maxTime = -1;
        
        do {
            int hours = arr[0] * 10 + arr[1];
            int minutes = arr[2] * 10 + arr[3];
            if (hours < 24 && minutes < 60) {
                maxTime = Math.Max(maxTime, hours * 60 + minutes);
            }
        } while (NextPermutation(arr));
        
        if (maxTime == -1) {
            return "";
        }
        
        return String.Format("{0:D2}:{1:D2}", maxTime / 60, maxTime % 60);
    }
    
    private bool NextPermutation(int[] arr) {
        int n = arr.Length;
        int i = n - 2;
        while (i >= 0 && arr[i] >= arr[i + 1]) {
            i--;
        }
        if (i < 0) {
            return false;
        }
        int j = n - 1;
        while (arr[j] <= arr[i]) {
            j--;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        Array.Reverse(arr, i + 1, n - i - 1);
        return true;
    }
}

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

Задача: 435. Non-overlapping Intervals
Сложность: medium

Дан массив интервалов intervals, где intervals[i] = [starti, endi]. Верните минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались.

Пример:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

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

1⃣Отсортируйте интервалы по времени окончания.

2⃣Инициализируйте переменную ответа ans = 0 и целое число k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, например, INT_MIN.

3⃣Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. Верните ans.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int EraseOverlapIntervals(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));
        int ans = 0;
        int k = int.MinValue;
        
        foreach (var interval in intervals) {
            int x = interval[0];
            int y = interval[1];
            if (x >= k) {
                k = y;
            } else {
                ans++;
            }
        }
        
        return ans;
    }
}

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

Задача: 205. Isomorphic Strings
Сложность: easy

Даны две строки s и t, определите, являются ли они изоморфными.

Две строки s и t являются изоморфными, если символы в s могут быть заменены для получения t.

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

Пример:

Input: s = "egg", t = "add"
Output: true

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

1⃣Определите два словаря: mapping_s_t для отображения символов из строки s в символы строки t, и mapping_t_s для отображения символов из строки t в символы строки s.

2⃣Итеративно пройдитесь по символам строк s и t. Для каждого символа c1 из s и соответствующего c2 из t, если c1 нет в mapping_s_t и c2 нет в mapping_t_s, добавьте соответствующие отображения; если одно из отображений существует, проверьте, соответствует ли оно ожидаемому значению.

3⃣Если в процессе проверки какое-либо отображение неверно, верните false. Если все проверки пройдены успешно, верните true после окончания итерации по строкам.

😎 Решение:

public class Solution {
    public bool IsIsomorphic(string s, string t) {
        int[] mappingStoT = new int[256];
        int[] mappingTtoS = new int[256];

        for (int i = 0; i < s.Length; ++i) {
            char c1 = s[i];
            char c2 = t[i];

            if (mappingStoT[c1] == 0 && mappingTtoS[c2] == 0) {
                mappingStoT[c1] = c2;
                mappingTtoS[c2] = c1;
            } else if (!(mappingStoT[c1] == c2 && mappingTtoS[c2] == c1)) {
                return false;
            }
        }

        return true;
    }
}

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

Задача: 366. Find Leaves of Binary Tree
Сложность: medium

Дан корень бинарного дерева, соберите узлы дерева следующим образом:
Соберите все листовые узлы.
Удалите все листовые узлы.
Повторяйте, пока дерево не станет пустым.

Пример:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

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

1⃣Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -1.

2⃣Сохранить пары (высота, значение) для всех узлов и отсортировать их по высоте.

3⃣Организовать узлы по высоте и вернуть результат.

😎 Решение:

using System;
using System.Collections.Generic;

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

public class Solution {
    private List<Tuple<int, int>> pairs = new List<Tuple<int, int>>();

    private int GetHeight(TreeNode node) {
        if (node == null) return -1;
        int leftHeight = GetHeight(node.left);
        int rightHeight = GetHeight(node.right);
        int currHeight = Math.Max(leftHeight, rightHeight) + 1;
        pairs.Add(new Tuple<int, int>(currHeight, node.val));
        return currHeight;
    }

    public IList<IList<int>> FindLeaves(TreeNode root) {
        GetHeight(root);
        pairs.Sort((a, b) => a.Item1.CompareTo(b.Item1));
        IList<IList<int>> solution = new List<IList<int>>();
        int currentHeight = -1;
        foreach (var pair in pairs) {
            if (pair.Item1 != currentHeight) {
                solution.Add(new List<int>());
                currentHeight = pair.Item1;
            }
            solution[solution.Count - 1].Add(pair.Item2);
        }
        return solution;
    }
}

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