Задача: 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;
    }
}

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

Задача: 106. Construct Binary Tree from Inorder and Postorder Traversal
Сложность: medium

Даны два массива целых чисел: inorder и postorder, где inorder — это массив обхода в глубину бинарного дерева слева направо, а postorder — это массив обхода в глубину после обработки всех потомков узла. Постройте и верните соответствующее бинарное дерево.

Пример:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

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

1⃣Создайте хэш-таблицу (hashmap) для хранения соответствия значений и их индексов в массиве обхода inorder.

2⃣Определите вспомогательную функцию helper, которая принимает границы левой и правой части текущего поддерева в массиве inorder. Эти границы используются для проверки, пусто ли поддерево. Если левая граница больше правой (in_left > in_right), то поддерево пустое и функция возвращает None.

3⃣Выберите последний элемент в массиве обхода postorder в качестве корня. Значение корня имеет индекс index в обходе inorder. Элементы от in_left до index - 1 принадлежат левому поддереву, а элементы от index + 1 до in_right — правому поддереву. Согласно логике обхода postorder, сначала рекурсивно строится правое поддерево helper(index + 1, in_right), а затем левое поддерево helper(in_left, index - 1). Возвращается корень.

😎 Решение:

public class Solution {
    int post_idx;
    int[] postorder;
    int[] inorder;
    Dictionary<int, int> idx_map = new Dictionary<int, int>();

    public TreeNode Helper(int in_left, int in_right) {
        if (in_left > in_right)
            return null;
        int root_val = postorder[post_idx];
        TreeNode root = new TreeNode(root_val);
        int index = idx_map[root_val];
        post_idx--;
        root.right = Helper(index + 1, in_right);
        root.left = Helper(in_left, index - 1);
        return root;
    }

    public TreeNode BuildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;
        this.inorder = inorder;
        post_idx = postorder.Length - 1;
        for (int idx = 0; idx < inorder.Length; idx++)
            idx_map[inorder[idx]] = idx;
        return Helper(0, inorder.Length - 1);
    }
}

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

Задача: 560. Subarray Sum Equals K
Сложность: easy

Дан массив целых чисел nums и целое число k, вернуть общее количество подмассивов, сумма которых равна k.

Подмассив - это непрерывная непустая последовательность элементов внутри массива.

Пример:

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

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

1⃣Самый простой метод - рассмотреть каждый возможный подмассив данного массива nums.

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

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

😎 Решение:

public class Solution {
    public int SubarraySum(int[] nums, int k) {
        int count = 0;
        for (int start = 0; start < nums.Length; start++) {
            for (int end = start + 1; end <= nums.Length; end++) {
                int sum = 0;
                for (int i = start; i < end; i++) {
                    sum += nums[i];
                }
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

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

Задача: 1260. Shift 2D Grid
Сложность: easy

Дана двумерная сетка размером m x n и целое число k. Требуется сдвинуть сетку k раз. За одну операцию сдвига: элемент в grid[i][j] перемещается в grid[i][j + 1]. Элемент в grid[i][n - 1] перемещается в grid[i + 1][0]. Элемент в grid[m - 1][n - 1] перемещается в grid[0][0]. Верните двумерную сетку после применения операции сдвига k раз.

Пример:

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

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

1⃣Преобразовать двумерную сетку в одномерный массив.

2⃣Выполнить сдвиг элементов в одномерном массиве.

3⃣Преобразовать одномерный массив обратно в двумерную сетку.

😎 Решение:

public class Solution {
    public IList<IList<int>> ShiftGrid(int[][] grid, int k) {
        int m = grid.Length;
        int n = grid[0].Length;
        int total = m * n;
        k = k % total;

        if (k == 0) {
            return grid;
        }

        int[] flatArray = new int[total];
        for (int i = 0; i < total; i++) {
            flatArray[i] = grid[i / n][i % n];
        }

        int[] newArray = new int[total];
        for (int i = 0; i < total; i++) {
            newArray[(i + k) % total] = flatArray[i];
        }

        var newGrid = new List<IList<int>>();
        for (int i = 0; i < m; i++) {
            var newRow = new List<int>();
            for (int j = 0; j < n; j++) {
                newRow.Add(newArray[i * n + j]);
            }
            newGrid.Add(newRow);
        }

        return newGrid;
    }
}

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

Задача: 905. Sort Array By Parity
Сложность: easy

Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию.

Пример:

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

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

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

2⃣Пройтись по массиву и добавить четные числа в один список, а нечетные в другой.

3⃣Объединить два списка и вернуть результат.

😎 Решение:

public class Solution {
    public int[] SortArrayByParity(int[] nums) {
        List<int> evens = new List<int>();
        List<int> odds = new List<int>();
        foreach (int num in nums) {
            if (num % 2 == 0) {
                evens.Add(num);
            } else {
                odds.Add(num);
            }
        }
        evens.AddRange(odds);
        return evens.ToArray();
    }
}

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

Задача: 686. Repeated String Match
Сложность: medium

Даны две строки a и b. Верните минимальное количество повторений строки a, чтобы строка b стала её подстрокой. Если сделать b подстрокой a невозможно, верните -1.

Обратите внимание: строка "abc", повторенная 0 раз, это "", повторенная 1 раз - "abc", повторенная 2 раза - "abcabc".

Пример:

Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.

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

1⃣ Найти минимальное количество повторений строки A, чтобы её длина стала больше или равна длине B. Это значение q = ceil(len(B) / len(A)).

2⃣Проверить, является ли B подстрокой строки A, повторенной q раз. Если да, вернуть q. Иначе, проверить строку A, повторенную (q+1) раз. Если B является подстрокой этой строки, вернуть q+1.

3⃣Если B не является подстрокой ни в одном из случаев, вернуть -1.

😎 Решение:

public class Solution {
    public int RepeatedStringMatch(string A, string B) {
        int q = 1;
        var S = new StringBuilder(A);
        while (S.Length < B.Length) {
            S.Append(A);
            q++;
        }
        if (S.ToString().Contains(B)) return q;
        if (S.Append(A).ToString().Contains(B)) return q + 1;
        return -1;
    }
}

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