Задача: 1024. Video Stitching
Сложность: medium

Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается массивом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. Например, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. Верните минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если задача невыполнима, верните -1.

Пример:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3

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

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

2⃣Выбор клипов:
Используйте жадный алгоритм для выбора клипов. Начните с начальной точки 0 и двигайтесь вперед, выбирая клип, который может покрыть наибольший диапазон.
Если обнаруживается, что начальная точка текущего клипа больше текущей позиции, это означает, что клипы не могут покрыть промежуток, и нужно вернуть -1.

3⃣Проверка покрытия:
Продолжайте процесс, пока не покроете весь диапазон от 0 до T. Если в конце процесса достигнута или превышена точка T, верните количество использованных клипов, иначе верните -1.

😎 Решение:

public class Solution {
    public int VideoStitching(int[][] clips, int T) {
        Array.Sort(clips, (a, b) => a[0] == b[0] ? b[1].CompareTo(a[1]) : a[0].CompareTo(b[0]));
        int end = -1, end2 = 0, res = 0;
        
        foreach (var clip in clips) {
            if (end2 >= T || clip[0] > end2) break;
            if (end < clip[0] && clip[0] <= end2) {
                res++;
                end = end2;
            }
            end2 = Math.Max(end2, clip[1]);
        }
        return end2 >= T ? res : -1;
    }
}

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

Задача: 338. Counting Bits
Сложность: easy

Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.

Пример:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

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

1⃣Инициализация массива:
Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n.

2⃣Итерация и вычисление:
Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x.

3⃣Возврат результата:
Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n.

😎 Решение:

public class Solution {
    public int[] CountBits(int num) {
        int[] ans = new int[num + 1];
        for (int x = 1; x <= num; ++x) {
            ans[x] = ans[x & (x - 1)] + 1;
        }
        return ans;
    }
}

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

Задача: 1271. Hexspeak
Сложность: easy

Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR".

Пример:

Input: num = "257"
Output: "IOI"

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

1⃣Преобразуйте десятичное число в шестнадцатеричную строку в верхнем регистре.

2⃣Замените все вхождения цифры '0' на букву 'O', а цифры '1' на букву 'I'

3⃣Проверьте, что преобразованная строка содержит только допустимые символы. Если это так, верните строку, иначе верните "ERROR".

😎 Решение:

public class Solution {
    public string ToHexString(string num) {
        string hexStr = Convert.ToInt64(num).ToString("X").Replace('0', 'O').Replace('1', 'I');
        foreach (char c in hexStr) {
            if (!"ABCDEFIO".Contains(c)) {
                return "ERROR";
            }
        }
        return hexStr;
    }
}

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

Задача: 1323. Maximum 69 Number
Сложность: easy

Дано положительное целое число num, состоящее только из цифр 6 и 9.

Верните максимальное число, которое можно получить, изменив не более одной цифры (6 становится 9, а 9 становится 6).

Пример:

Input: num = 9669
Output: 9969
Explanation: 
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666.
The maximum number is 9969.

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

1⃣Преобразуйте входное целое число num в итерируемый и изменяемый объект num_obj.

2⃣Пройдитесь по num_obj и, если найдете цифру 6, замените её на 9 и прекратите итерацию.

3⃣Верните целое число, преобразованное из измененного num_obj.

😎 Решение:

public class Solution {
    public int Maximum69Number (int num) {
        char[] numArr = num.ToString().ToCharArray();
        for (int i = 0; i < numArr.Length; i++) {
            if (numArr[i] == '6') {
                numArr[i] = '9';
                break;
            }
        }
        return int.Parse(new string(numArr));
    }
}

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

Задача: 125. Valid Palindrome
Сложность: easy

Фраза является палиндромом, если после преобразования всех заглавных букв в строчные и удаления всех неалфавитно-цифровых символов она читается одинаково как слева направо, так и справа налево. Алфавитно-цифровые символы включают в себя буквы и цифры.

Для данной строки s верните true, если она является палиндромом, и false в противном случае.

Пример:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

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

1⃣Поскольку входная строка содержит символы, которые нам нужно игнорировать при проверке на палиндром, становится трудно определить реальную середину нашего палиндромического ввода.

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

3⃣Результирующий алгоритм прост:
1. Установите два указателя, один на каждом конце входной строки.
2. Если ввод является палиндромом, оба указателя должны указывать на эквивалентные символы в любой момент времени.
3. Если это условие не выполняется в какой-либо момент времени, мы прерываемся и возвращаемся раньше.
4. Мы можем просто игнорировать неалфавитно-цифровые символы, продолжая двигаться дальше.
5. Продолжайте перемещение внутрь, пока указатели не встретятся в середине.

😎 Решение:

public class Solution {
    public bool IsPalindrome(string s) {
        int i = 0;
        int j = s.Length - 1;
        while (i < j) {
            while (i < j && !Char.IsLetterOrDigit(s[i])) {
                i++;
            }

            while (i < j && !Char.IsLetterOrDigit(s[j])) {
                j--;
            }

            if (char.ToLower(s[i]) != char.ToLower(s[j]))
                return false;
            i++;
            j--;
        }

        return true;
    }
}

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

Задача: 1287. Element Appearing More Than 25% In Sorted Array
Сложность: easy

Дан массив целых чисел, отсортированный в неубывающем порядке. В этом массиве есть ровно одно число, которое встречается более чем в 25% случаев. Верните это число.

Пример:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

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

1⃣Инициализируйте хеш-таблицу counts и перебирайте каждый элемент в массиве arr, увеличивая counts[num] для каждого элемента num.

2⃣Установите target = arr.length / 4.

3⃣Перебирайте каждую пару ключ-значение в counts и, если значение > target, верните ключ. Код никогда не достигнет этой точки, так как гарантируется, что ответ существует; верните любое значение.

😎 Решение:

using System.Collections.Generic;

public class Solution {
    public int FindSpecialInteger(int[] arr) {
        Dictionary<int, int> counts = new Dictionary<int, int>();
        int target = arr.Length / 4;
        foreach (int num in arr) {
            if (!counts.ContainsKey(num)) {
                counts[num] = 0;
            }
            counts[num]++;
            if (counts[num] > target) {
                return num;
            }
        }
        return -1;
    }
}

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

Задача: 274. H-Index
Сложность: medium

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

Пример:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

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

1⃣Отсортировать массив цитирований по убыванию:
Отсортировать массив citations в порядке убывания, чтобы наибольшее количество цитирований было в начале массива.

2⃣Найти наибольшее значение i, для которого citations[i] > i:
Пройтись по отсортированному массиву и найти наибольшее значение i, для которого выполняется условие citations[i] > i.
Это значение будет индексом, при котором количество цитирований статьи больше индекса.

3⃣Рассчитать h-индекс:
h-индекс будет равен i + 1, где i - наибольшее значение, найденное на предыдущем шаге.

😎 Решение:

public class Solution {
    public int HIndex(int[] citations) {
        int n = citations.Length;
        int[] papers = new int[n + 1];
        foreach (int c in citations)
            papers[Math.Min(n, c)]++;
        int k = n;
        for (int s = papers[n]; k > s; s += papers[k])
            k--;
        return k;
    }
}

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

Задача: 950. Reveal Cards In Increasing Order
Сложность: medium

Вам дана колода целочисленных массивов. Имеется колода карт, в которой каждая карта имеет уникальное целое число. Целое число на i-й карте - deck[i]. Вы можете упорядочить колоду в любом порядке. Изначально все карты в одной колоде лежат лицевой стороной вниз (нераскрытыми). Вы будете выполнять следующие действия несколько раз, пока все карты не будут раскрыты: возьмите верхнюю карту колоды, раскройте ее и выньте из колоды. Если в колоде еще есть карты, положите следующую верхнюю карту колоды на дно колоды. Если еще есть нераскрытые карты, вернитесь к шагу 1. В противном случае остановитесь. Верните порядок колоды, при котором карты раскрываются в порядке возрастания. Обратите внимание, что первая запись в ответе считается верхом колоды.

Пример:

Input: deck = [17,13,11,2,3,5,7]
Output: [2,13,3,11,5,17,7]

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

1⃣Создать индексы карт в порядке, в котором они будут раскрываться.

2⃣Отсортировать колоду карт по возрастанию.

3⃣Заполнить результат раскрытия карт по ранее созданным индексам.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int[] DeckRevealedIncreasing(int[] deck) {
        int n = deck.Length;
        Queue<int> index = new Queue<int>();
        for (int i = 0; i < n; i++) {
            index.Enqueue(i);
        }
        
        Array.Sort(deck);
        int[] result = new int[n];
        
        foreach (int card in deck) {
            result[index.Dequeue()] = card;
            if (index.Count > 0) {
                index.Enqueue(index.Dequeue());
            }
        }
        
        return result;
    }
}

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

Задача: 139. Word Break
Сложность: medium

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

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

Пример:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

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

1⃣Инициализация структур данных:
Преобразуйте wordDict в множество words для быстрой проверки вхождения.
Инициализируйте очередь queue начальным значением 0 (индекс начала строки) и множество seen для отслеживания посещённых индексов.

2⃣Обход в ширину (BFS):
Пока очередь не пуста, извлекайте первый элемент из очереди, обозначающий начальную позицию start.
Если start равен длине строки s, возвращайте true, так как достигнут конец строки, и строку можно разделить на слова из словаря.
Итерируйте end от start + 1 до s.length включительно. Для каждого end, проверьте, посещён ли он уже.

3⃣Проверка подстроки и обновление структур:
Проверьте подстроку начиная с start и заканчивая перед end. Если подстрока находится в множестве words, добавьте end в очередь и отметьте его в seen как посещённый.
Если BFS завершается и конечный узел не достигнут, возвращайте false.

😎 Решение:

public class Solution {
    public bool WordBreak(string s, IList<string> wordDict) {
        HashSet<string> words = new HashSet<string>(wordDict);
        Queue<int> queue = new Queue<int>();
        bool[] seen = new bool[s.Length + 1];
        queue.Enqueue(0);
        while (queue.Count != 0) {
            int start = queue.Dequeue();
            if (start == s.Length) {
                return true;
            }

            for (int end = start + 1; end <= s.Length; end++) {
                if (seen[end]) {
                    continue;
                }

                if (words.Contains(s.Substring(start, end - start))) {
                    queue.Enqueue(end);
                    seen[end] = true;
                }
            }
        }

        return false;
    }
}

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

Задача: 1022. Sum of Root To Leaf Binary Numbers
Сложность: easy

Вам дан корень двоичного дерева, в котором каждый узел имеет значение 0 или 1. Каждый путь от корня к листьям представляет собой двоичное число, начиная со старшего бита. Например, если путь 0 -> 1 -> 1 -> 0 -> 1, то в двоичном виде это может представлять 01101, что равно 13. Для всех листьев дерева рассмотрите числа, представленные путем от корня к этому листу. Верните сумму этих чисел. Тестовые примеры генерируются таким образом, чтобы ответ помещался в 32-битовое целое число.

Пример:

Input: root = [1,0,1,0,1,0,1]
Output: 22

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

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

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

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

😎 Решение:

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

public class Solution {
    public int SumRootToLeaf(TreeNode root) {
        return Dfs(root, 0);
    }
    
    private int Dfs(TreeNode node, int currentValue) {
        if (node == null) return 0;
        currentValue = (currentValue << 1) | node.val;
        if (node.left == null && node.right == null) return currentValue;
        return Dfs(node.left, currentValue) + Dfs(node.right, currentValue);
    }
}

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

Задача: 1428. Leftmost Column with at Least a One
Сложность: medium

Строково-отсортированная бинарная матрица означает, что все элементы равны 0 или 1, и каждая строка матрицы отсортирована в неубывающем порядке.
Дана строково-отсортированная бинарная матрица binaryMatrix, верните индекс (начиная с 0) самого левого столбца, содержащего 1. Если такого индекса не существует, верните -1.
Вы не можете напрямую обращаться к бинарной матрице. Вы можете получить доступ к матрице только через интерфейс BinaryMatrix:
- BinaryMatrix.get(row, col) возвращает элемент матрицы с индексом (row, col) (начиная с 0).
- BinaryMatrix.dimensions() возвращает размеры матрицы в виде списка из 2 элементов [rows, cols], что означает, что матрица имеет размер rows x cols.

Отправки, делающие более 1000 вызовов к BinaryMatrix.get, будут оценены как неправильный ответ. Кроме того, любые решения, пытающиеся обойти проверку, будут дисквалифицированы.

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

Пример:

Input: mat = [[0,0],[0,1]]
Output: 1

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

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

2⃣Повторяйте поиск до тех пор, пока указатели не выйдут за границы матрицы:
Если текущий элемент равен 0, сдвигайте указатель строки вниз.
Если текущий элемент равен 1, сдвигайте указатель столбца влево.

3⃣Если указатель столбца остается на последнем столбце, значит, все элементы матрицы равны 0, и верните -1. В противном случае верните индекс самого левого столбца с 1.

😎 Решение:

public class Solution {
    public int LeftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        IList<int> dimensions = binaryMatrix.Dimensions();
        int rows = dimensions[0];
        int cols = dimensions[1];
        
        int currentRow = 0;
        int currentCol = cols - 1;
        
        while (currentRow < rows && currentCol >= 0) {
            if (binaryMatrix.Get(currentRow, currentCol) == 0) {
                currentRow++;
            } else {
                currentCol--;
            }
        }
        
        return (currentCol == cols - 1) ? -1 : currentCol + 1;
    }
}

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

Задача: 154. Find Minimum in Rotated Sorted Array II
Сложность: hard

Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,4,4,5,6,7] может стать:

[4,5,6,7,0,1,4], если он был повернут 4 раза.
[0,1,4,4,5,6,7], если он был повернут 7 раз.
Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

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

Необходимо максимально уменьшить количество операций.

Пример:

Input: nums = [1,3,5]
Output: 1

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

1⃣Сравнение с правой границей:
В классическом бинарном поиске мы бы сравнивали элемент в середине (nums[mid]) с искомым значением. В нашем случае мы сравниваем его с элементом, на который указывает правый указатель (nums[high]).

2⃣Обновление указателей:
Если элемент в середине находится в той же половине массива, что и элемент на правой границе (nums[mid] > nums[high]), минимальный элемент должен находиться в левой половине от mid. Следовательно, сдвигаем правый указатель на позицию mid.
Если nums[mid] < nums[high], это указывает, что минимальный элемент находится в правой половине или равен mid. Сдвигаем правый указатель на mid.
Если nums[mid] == nums[high], мы не можем быть уверены, в какой половине находится минимальный элемент из-за наличия дубликатов. В этом случае безопасно сдвинуть правый указатель на один шаг влево (high = high - 1), чтобы сузить область поиска без пропуска возможного минимального элемента.

3⃣Итерация до сужения диапазона поиска:
Продолжаем процесс, пока левый указатель не встретится с правым. В конечном итоге правый указатель укажет на минимальный элемент массива после всех поворотов.

😎 Решение:

public class Solution {
    public int FindMin(int[] nums) {
        int low = 0, high = nums.Length - 1;

        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high])
                high = pivot;
            else if (nums[pivot] > nums[high])
                low = pivot + 1;
            else
                high -= 1;
        }

        return nums[low];
    }
}

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

Задача: 442. Find All Duplicates in an Array
Сложность: medium

Дан целочисленный массив nums длины n, где все целые числа nums находятся в диапазоне [1, n], и каждое число появляется один или два раза. Верните массив всех чисел, которые появляются дважды.

Вы должны написать алгоритм, который работает за время O(n) и использует только постоянное дополнительное пространство.

Пример:

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

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

1⃣Когда мы итерируемся по элементам входного массива, мы можем просто искать любое другое вхождение текущего элемента в оставшейся части массива.

2⃣Поскольку элемент может появляться только один или два раза, нам не нужно беспокоиться о получении дубликатов элементов, которые появляются дважды: Случай I: Если элемент встречается в массиве только один раз, при поиске его в остальной части массива ничего не найдется. Случай II: Если элемент встречается дважды, вы найдете второе вхождение элемента в оставшейся части массива. Когда вы наткнетесь на второе вхождение в более поздней итерации, это будет аналогично случаю I (поскольку больше вхождений этого элемента в оставшейся части массива не будет).

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

😎 Решение:

public class Solution {
    public IList<int> FindDuplicates(int[] nums) {
        List<int> ans = new List<int>();
        
        for (int i = 0; i < nums.Length; i++)
            for (int j = i + 1; j < nums.Length; j++) {
                if (nums[j] == nums[i]) {
                    ans.Add(nums[i]);
                    break;
                }
            }
        
        return ans;
    }
}

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

Задача: 352. Data Stream as Disjoint Intervals
Сложность: hard

Дано поступление данных из последовательности неотрицательных целых чисел a1, a2, ..., an, необходимо обобщить увиденные числа в виде списка непересекающихся интервалов.

Реализуйте класс SummaryRanges:

SummaryRanges() Инициализирует объект с пустым потоком.
void addNum(int value) Добавляет целое число в поток.
int[][] getIntervals() Возвращает обобщение текущих чисел в потоке в виде списка непересекающихся интервалов [starti, endi]. Ответ должен быть отсортирован по starti.

Пример:

Input
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Output
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

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

1⃣Используйте SortedSet<int>, чтобы автоматически сохранять отдельные элементы в отсортированном виде.

2⃣AddNum(value)— просто добавить элемент в SortedSet, дубликаты автоматически теряются.

3⃣GetIntervals()—
проходим поSortedSet
если текущий элемент продолжает текущий интервал ( value == right + 1) — расширение его
в противном случае сохраняем текущий интервал и начинаем новый
после цикла добавление последней интервала

😎 Решение:

using System;
using System.Collections.Generic;

public class SummaryRanges {
    private SortedSet<int> values;

    public SummaryRanges() {
        values = new SortedSet<int>();
    }

    public void AddNum(int value) {
        values.Add(value);
    }

    public List<int[]> GetIntervals() {
        var intervals = new List<int[]>();
        if (values.Count == 0) {
            return intervals;
        }

        int left = -1, right = -1;
        foreach (var value in values) {
            if (left < 0) {
                left = right = value;
            } else if (value == right + 1) {
                right = value;
            } else {
                intervals.Add(new int[] { left, right });
                left = right = value;
            }
        }
        intervals.Add(new int[] { left, right });
        return intervals;
    }
}

// Example usage
public class Program {
    public static void Main() {
        SummaryRanges sr = new SummaryRanges();
        sr.AddNum(1);
        sr.AddNum(3);
        sr.AddNum(7);
        sr.AddNum(2);
        sr.AddNum(6);
        List<int[]> intervals = sr.GetIntervals();
        foreach (var interval in intervals) {
            Console.WriteLine($"{interval[0]} {interval[1]}");
        }
    }
}

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

Задача: 753. Cracking the Safe
Сложность: medium

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

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

public class Solution {
    public string CrackSafe(int n, int k) {
        var seen = new HashSet<string>();
        var result = new StringBuilder();

        string startNode = new string('0', n - 1);
        Dfs(startNode, k, seen, result);

        result.Append(startNode);
        return result.ToString();
    }

    private void Dfs(string node, int k, HashSet<string> seen, StringBuilder result) {
        for (int x = 0; x < k; x++) {
            string neighbor = node + x;
            if (!seen.Contains(neighbor)) {
                seen.Add(neighbor);
                Dfs(neighbor.Substring(1), k, seen, result);
                result.Append(x);
            }
        }
    }
}

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

Задача: 217. Contains Duplicate
Сложность: easy

Дан массив целых чисел nums. Верните true, если любое значение появляется в массиве хотя бы дважды, и верните false, если каждый элемент уникален.

Пример:

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

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

1⃣Отсортируйте массив nums по возрастанию.

2⃣Итерируйте по отсортированному массиву и сравнивайте каждое число с следующим.

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

😎 Решение:

public bool ContainsDuplicate(int[] nums) {
    Array.Sort(nums);
    for (int i = 0; i < nums.Length - 1; ++i) {
        if (nums[i] == nums[i + 1]) {
            return true;
        }
    }
    return false;
}

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

Задача: 959. Regions Cut By Slashes
Сложность: medium

n x n сетка состоит из квадратов размером 1 x 1, где каждый квадрат 1 x 1 содержит '/', '', или пустое пространство ' '. Эти символы делят квадрат на смежные области.

Дана сетка grid, представленная в виде строкового массива. Верните количество областей.

Обратите внимание, что обратные слеши экранированы, поэтому '' представлен как '\'.

Пример:

Input: grid = [" /","/ "]
Output: 2

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

1⃣Создайте 4*N*N узлов для каждой ячейки сетки и соедините их в соответствии с описанием.

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

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

😎 Решение:

public class DSU {
    int[] parent;
    public DSU(int N) {
        parent = new int[N];
        for (int i = 0; i < N; ++i)
            parent[i] = i;
    }
    public int Find(int x) {
        if (parent[x] != x) parent[x] = Find(parent[x]);
        return parent[x];
    }
    public void Union(int x, int y) {
        parent[Find(x)] = Find(y);
    }
}

public class Solution {
    public int RegionsBySlashes(string[] grid) {
        int N = grid.Length;
        DSU dsu = new DSU(4 * N * N);
        
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                int root = 4 * (r * N + c);
                char val = grid[r][c];
                
                if (val != '\\') {
                    dsu.Union(root + 0, root + 1);
                    dsu.Union(root + 2, root + 3);
                }
                if (val != '/') {
                    dsu.Union(root + 0, root + 2);
                    dsu.Union(root + 1, root + 3);
                }
                
                if (r + 1 < N) {
                    dsu.Union(root + 3, (root + 4 * N) + 0);
                }
                if (r - 1 >= 0) {
                    dsu.Union(root + 0, (root - 4 * N) + 3);
                }
                if (c + 1 < N) {
                    dsu.Union(root + 2, (root + 4) + 1);
                }
                if (c - 1 >= 0) {
                    dsu.Union(root + 1, (root - 4) + 2);
                }
            }
        }
        
        int ans = 0;
        for (int x = 0; x < 4 * N * N; ++x) {
            if (dsu.Find(x) == x) {
                ++ans;
            }
        }
        
        return ans;
    }
}

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

Задача: 146. LRU Cache
Сложность: medium

Реализуйте класс LRUCache:
LRUCache(int capacity) - инициализирует LRU-кэш с положительным размером capacity.
int get(int key) - возвращает значение по ключу, если ключ существует, в противном случае возвращает -1.
void put(int key, int value) - обновляет значение по ключу, если ключ существует. В противном случае добавляет пару ключ-значение в кэш. Если количество ключей превышает установленную емкость после этой операции, удаляет наименее недавно использованный ключ.

Функции get и put должны выполняться за среднее время O(1).

Пример:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

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

1⃣Метод добавления узла в конец связного списка (add):
Получите текущий узел в конце списка, это "реальный" хвост: tail.prev, обозначим его как previousEnd.
Вставьте node после previousEnd, установив previousEnd.next = node.
Настройте указатели узла: node.prev = previousEnd и node.next = tail.
Обновите tail.prev = node, делая node новым "реальным" хвостом списка.

2⃣Метод удаления узла из связного списка (remove):
Узел node должен быть удален из списка. Для этого определите узлы nextNode = node.next и prevNode = node.prev.
Чтобы удалить node, переназначьте prevNode.next = nextNode и nextNode.prev = prevNode, эффективно исключая node из списка.
Это превратит, например, последовательность A <-> B <-> C в A <-> C, где prevNode = A и nextNode = C.

3⃣Методы get и put:
get(int key): Проверьте, существует ли ключ в хэш-карте. Если нет, верните -1. Иначе, получите узел, связанный с ключом, переместите его в конец списка с помощью remove(node) и add(node). Верните node.val.
put(int key, int value): Если ключ уже существует, найдите соответствующий узел и удалите его методом remove. Создайте новый узел с key и value, добавьте его в хэш-карту и в конец списка методом add(node). Если размер кэша превышает установленную емкость после добавления, удалите самый редко используемый узел (который находится в голове списка после фиктивного узла head), затем удалите соответствующий ключ из хэш-карты.

😎 Решение:

public class Node {
    public int key { get; set; }
    public int value { get; set; }
    public Node next { get; set; }
    public Node prev { get; set; }

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

public class LRUCache {
    private int capacity;
    private Dictionary<int, Node> dic;
    private Node head;
    private Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dic = new Dictionary<int, Node>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    public int Get(int key) {
        if (!dic.ContainsKey(key)) {
            return -1;
        }

        Node node = dic[key];
        Remove(node);
        Add(node);
        return node.value;
    }

    public void Put(int key, int value) {
        if (dic.ContainsKey(key)) {
            Node oldNode = dic[key];
            Remove(oldNode);
        }

        Node node = new Node(key, value);
        dic[key] = node;
        Add(node);
        if (dic.Count > capacity) {
            Node nodeToDelete = head.next;
            Remove(nodeToDelete);
            dic.Remove(nodeToDelete.key);
        }
    }

    private void Add(Node node) {
        Node previousEnd = tail.prev;
        previousEnd.next = node;
        node.prev = previousEnd;
        node.next = tail;
        tail.prev = node;
    }

    private void Remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

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

Задача: 1472. Design Browser History
Сложность: medium

У вас есть браузер с одной вкладкой, где вы начинаете на домашней странице и можете посетить другой URL, вернуться назад на определённое количество шагов в истории или переместиться вперёд на определённое количество шагов в истории.

Реализуйте класс BrowserHistory:
BrowserHistory(string homepage) Инициализирует объект с домашней страницей браузера.
void visit(string url) Посещает URL с текущей страницы. Это очищает всю историю вперёд.
string back(int steps) Перемещает на steps шагов назад в истории. Если вы можете вернуться только на x шагов в истории, а steps > x, вы вернётесь только на x шагов. Возвращает текущий URL после перемещения назад в истории на не более чем steps шагов.
string forward(int steps) Перемещает на steps шагов вперёд в истории. Если вы можете переместиться только на x шагов вперёд в истории, а steps > x, вы переместитесь только на x шагов. Возвращает текущий URL после перемещения вперёд в истории на не более чем steps шагов.

Пример:

Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // You are in "leetcode.com". Visit "google.com"
browserHistory.visit("facebook.com");     // You are in "google.com". Visit "facebook.com"
browserHistory.visit("youtube.com");      // You are in "facebook.com". Visit "youtube.com"
browserHistory.back(1);                   // You are in "youtube.com", move back to "facebook.com" return "facebook.com"
browserHistory.back(1);                   // You are in "facebook.com", move back to "google.com" return "google.com"
browserHistory.forward(1);                // You are in "google.com", move forward to "facebook.com" return "facebook.com"
browserHistory.visit("linkedin.com");     // You are in "facebook.com". Visit "linkedin.com"
browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.

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

1⃣Инициализация:
Создайте класс BrowserHistory с двумя стеками (history и future) и строковой переменной current для хранения текущего URL. Инициализируйте current с домашней страницей.

2⃣Посещение URL:
Метод visit(url) сохраняет текущий URL в стеке history, устанавливает url как текущий и очищает стек future.

3⃣Навигация назад и вперед:
Метод back(steps) перемещает текущий URL в стек future и извлекает URL из стека history, пока шаги не будут исчерпаны или стек history не станет пустым.
Метод forward(steps) перемещает текущий URL в стек history и извлекает URL из стека future, пока шаги не будут исчерпаны или стек future не станет пустым.

😎 Решение:

using System.Collections.Generic;

public class BrowserHistory {
    private Stack<string> history;
    private Stack<string> future;
    private string current;

    public BrowserHistory(string homepage) {
        history = new Stack<string>();
        future = new Stack<string>();
        current = homepage;
    }
    
    public void Visit(string url) {
        history.Push(current);
        current = url;
        future.Clear();
    }
    
    public string Back(int steps) {
        while (steps > 0 && history.Count > 0) {
            future.Push(current);
            current = history.Pop();
            steps--;
        }
        return current;
    }
    
    public string Forward(int steps) {
        while (steps > 0 && future.Count > 0) {
            history.Push(current);
            current = future.Pop();
            steps--;
        }
        return current;
    }
}

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

Задача: 645. Set Mismatch
Сложность: easy

У вас есть набор целых чисел s, который изначально содержит все числа от 1 до n. К сожалению, из-за какой-то ошибки одно из чисел в s продублировалось в другое число в наборе, что привело к повторению одного числа и потере другого. Вам дан целочисленный массив nums, представляющий состояние данных в этом наборе после ошибки. Найдите число, которое встречается дважды, и число, которое отсутствует, и верните их в виде массива.

Пример:

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

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

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

2⃣Определите отсутствующее число, используя сумму чисел от 1 до n и текущую сумму массива.

3⃣Верните дублированное и отсутствующее числа в виде массива.

😎 Решение:

public class Solution {
    public int[] FindErrorNums(int[] nums) {
        int n = nums.Length;
        HashSet<int> numSet = new HashSet<int>();
        int duplicate = -1;
        foreach (int num in nums) {
            if (!numSet.Add(num)) {
                duplicate = num;
            }
        }
        int missing = (n * (n + 1)) / 2 - numSet.Sum();
        return new int[] { duplicate, missing };
    }
}

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

Задача: 1207. Unique Number of Occurrences
Сложность: easy

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

Пример:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

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

1⃣Сохраните частоты элементов массива arr в хэш-таблице freq.

2⃣Итерируйтесь по хэш-таблице freq и вставьте частоты всех уникальных элементов массива arr в хэш-набор freqSet.

3⃣Верните true, если размер хэш-набора freqSet равен размеру хэш-таблицы freq, иначе верните false.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public bool UniqueOccurrences(int[] arr) {
        Dictionary<int, int> freq = new Dictionary<int, int>();
        foreach (int num in arr) {
            if (freq.ContainsKey(num)) {
                freq[num]++;
            } else {
                freq[num] = 1;
            }
        }
        HashSet<int> freqSet = new HashSet<int>(freq.Values);
        return freq.Count == freqSet.Count;
    }
}

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