C# | LeetCode

Задача: 1376. Time Needed to Inform All Employees Сложность: medium В компании работает n сотрудников, каждому из которых присвоен уникальный идентификатор от 0 до n - 1. Руководитель компании имеет идентификатор headID. У каждого сотрудника есть один непосредственный начальник, указанный в массиве manager, где manager[i] — это непосредственный начальник i-го сотрудника, manager[headID] = -1. Также гарантируется, что отношения подчинения образуют древовидную структуру. Руководитель компании хочет сообщить всем сотрудникам компании срочную новость. Он сообщит своим непосредственным подчиненным, а они сообщат своим подчиненным и так далее, пока все сотрудники не узнают о срочной новости. i-й сотрудник нуждается в informTime[i] минутах, чтобы сообщить всем своим непосредственным подчиненным (т.е. через informTime[i] минут все его непосредственные подчиненные могут начать распространять новость). Верните количество минут, необходимых для того, чтобы сообщить всем сотрудникам о срочной новости. Пример:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

👨‍💻 Алгоритм: 1⃣Создайте список смежности adjList; индекс i будет хранить смежные узлы для сотрудника с идентификатором i. 2⃣Итерируйте по сотрудникам от 0 до N - 1, и для каждого сотрудника i добавляйте ребро manager[i] -> i, если manager[i] не равен -1. 3⃣Начните выполнение DFS с узла headID и временем 0 для каждого узла как curr. Обновите максимальное время maxTime, сравнив его с текущим временем. Итерируйте по смежным узлам curr и для каждого смежного узла выполните DFS с временем time + informTime[curr]. Когда DFS завершится, верните maxTime. 😎 Решение:

public class Solution {
    private int maxTime = int.MinValue;
    
    private void DFS(List<int>[] adjList, int[] informTime, int curr, int time) {
        maxTime = Math.Max(maxTime, time);
        foreach (int adjacent in adjList[curr]) {
            DFS(adjList, informTime, adjacent, time + informTime[curr]);
        }
    }
    
    public int NumOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        List<int>[] adjList = new List<int>[n];
        for (int i = 0; i < n; i++) {
            adjList[i] = new List<int>();
        }
        for (int i = 0; i < n; i++) {
            if (manager[i] != -1) {
                adjList[manager[i]].Add(i);
            }
        }
        DFS(adjList, informTime, headID, 0);
        return maxTime;
    }
}

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

Задача: 162. Find Peak Element Сложность: medium Пиковым элементом называется элемент, который строго больше своих соседей. Для массива целых чисел nums с индексацией с нуля найдите пиковый элемент и верните его индекс. Если в массиве несколько пиков, верните индекс любого из пиков. Вы можете представить, что nums[-1] = nums[n] = -∞. Другими словами, элемент всегда считается строго большим, чем сосед, находящийся за пределами массива. Необходимо написать алгоритм, который работает за время O(log n). Пример:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

👨‍💻 Алгоритм: 1⃣Начальная проверка: Определяем средний элемент массива mid как mid = low + (high - low) / 2. Это помогает предотвратить возможное переполнение при больших значениях индексов. 2⃣Определение направления поиска: Сравниваем элемент nums[mid] с его правым соседом nums[mid + 1]. Если nums[mid] меньше nums[mid + 1], это указывает на наличие восходящей последовательности, и мы двигаемся вправо, устанавливая low = mid + 1. Это потому, что пик гарантированно находится в правой части. Если nums[mid] больше nums[mid + 1], это указывает на наличие нисходящей последовательности, и пик находится либо в mid, либо слева от него, тогда устанавливаем high = mid. 3⃣Завершение поиска: Процесс продолжается до тех пор, пока low не станет равным high, что означает сужение поисковой области до одного элемента, который и является пиком, поскольку мы исключили все другие возможности. 😎 Решение:

public class Solution {
    public int FindPeakElement(int[] nums) {
        return Search(nums, 0, nums.Length - 1);
    }

    public int Search(int[] nums, int l, int r) {
        if (l == r)
            return l;
        int mid = (l + r) / 2;
        if (nums[mid] > nums[mid + 1])
            return Search(nums, l, mid);
        return Search(nums, mid + 1, r);
    }
}

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

Задача: 1426. Counting Elements Сложность: easy Дан целочисленный массив arr, посчитайте, сколько элементов x в нем есть таких, что x + 1 также находится в arr. Если в arr есть дубликаты, считайте их отдельно. Пример:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

👨‍💻 Алгоритм: 1⃣Создайте вспомогательную функцию для проверки, содержится ли элемент в массиве. 2⃣Итерируйте по каждому элементу массива и используйте вспомогательную функцию для проверки, содержится ли элемент x + 1 в массиве. 3⃣Увеличьте счетчик, если x + 1 найден, и верните значение счетчика. 😎 Решение:

public class Solution {
    public int CountElements(int[] arr) {
        int count = 0;
        foreach (int x in arr) {
            if (IntegerInArray(arr, x + 1)) {
                count++;
            }
        }
        return count;
    }
    
    public bool IntegerInArray(int[] arr, int target) {
        foreach (int x in arr) {
            if (x == target) {
                return true;
            }
        }
        return false;
    }
}

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

Задача: 1016. Binary String With Substrings Representing 1 To N Сложность: medium Если задана двоичная строка s и положительное целое число n, верните true, если двоичное представление всех целых чисел в диапазоне [1, n] является подстрокой s, или false в противном случае. Подстрока - это непрерывная последовательность символов в строке. Пример:

Input: s = "0110", n = 3
Output: true

👨‍💻 Алгоритм: 1⃣Генерация двоичных строк: Для каждого числа в диапазоне [1, n] сгенерируйте его двоичное представление. 2⃣Проверка подстрок: Проверьте, является ли каждое из двоичных представлений подстрокой строки s. 3⃣Возврат результата: Если все двоичные представления являются подстроками строки s, верните true. В противном случае, верните false. 😎 Решение:

public class Solution {
    public bool QueryString(string s, int n) {
        for (int i = 1; i <= n; i++) {
            string binary = Convert.ToString(i, 2);
            if (!s.Contains(binary)) {
                return false;
            }
        }
        return true;
    }
}

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

📺 База 1000+ реальных собеседований На программиста, тестировщика, аналитика, проджекта и другие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

#medium Задача: 311. Sparse Matrix Multiplication Сложность: medium Даны две разреженные матрицы mat1 размером m x k и mat2 размером k x n. Верните результат перемножения матриц mat1 x mat2. Вы можете предположить, что умножение всегда возможно. Пример:

Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]
Output: [[7,0,0],[-7,0,3]]

👨‍💻 Алгоритм: 1⃣Инициализация результирующей матрицы Создайте результирующую матрицу result размером m x n, заполненную нулями. 2⃣Хранение ненулевых элементов Пройдите по каждой строке матрицы mat1 и сохраните индексы и значения ненулевых элементов в хеш-карте mat1_map. Пройдите по каждой колонке матрицы mat2 и сохраните индексы и значения ненулевых элементов в хеш-карте mat2_map. 3⃣Вычисление произведения Для каждой строки i в mat1 и для каждой колонки j в mat2: Если в mat1_map есть ненулевой элемент в строке i и в mat2_map есть ненулевой элемент в колонке j с одинаковым индексом k, добавьте произведение этих элементов к result[i][j]. 😎 Решение:

public class Solution {
    public int[][] Multiply(int[][] mat1, int[][] mat2) {
        int n = mat1.Length;
        int k = mat1[0].Length;
        int m = mat2[0].Length;

        int[][] ans = new int[n][];
        for (int i = 0; i < n; i++) {
            ans[i] = new int[m];
        }

        for (int rowIndex = 0; rowIndex < n; rowIndex++) {
            for (int elementIndex = 0; elementIndex < k; elementIndex++) {
                if (mat1[rowIndex][elementIndex] != 0) {
                    for (int colIndex = 0; colIndex < m; colIndex++) {
                        ans[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex];
                    }
                }
            }
        }

        return ans;
    }
}

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

Задача: 616. Add Bold Tag in String Сложность: medium Вам дана строка s и массив строк words. Вы должны добавить закрытую пару полужирных тегов <b> и </b>, чтобы обернуть подстроки в s, которые существуют в words. Если две такие подстроки пересекаются, вы должны обернуть их вместе только одной парой закрытых полужирных тегов. Если две подстроки, обернутые полужирными тегами, идут подряд, вы должны объединить их. Верните s после добавления полужирных тегов. Пример:

Input: s = "abcxyz123", words = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"

👨‍💻 Алгоритм: 1⃣Найдите все позиции вхождений подстрок из words в строку s и пометьте эти позиции для выделения тегами <b> и </b>. 2⃣Пройдитесь по помеченным позициям, чтобы определить области, которые нужно обернуть в полужирные теги, слияя пересекающиеся и смежные области. 3⃣Постройте новую строку s, добавляя теги <b> и </b> в определенные позиции. 😎 Решение:

public class Solution {
    public string AddBoldTag(string s, string[] words) {
        int n = s.Length;
        bool[] bold = new bool[n];
        
        foreach (var word in words) {
            int start = s.IndexOf(word);
            while (start != -1) {
                for (int i = start; i < start + word.Length; i++) {
                    bold[i] = true;
                }
                start = s.IndexOf(word, start + 1);
            }
        }
        
        var result = new StringBuilder();
        int j = 0;
        while (j < n) {
            if (bold[j]) {
                result.Append("<b>");
                while (j < n && bold[j]) {
                    result.Append(s[j]);
                    j++;
                }
                result.Append("</b>");
            } else {
                result.Append(s[j]);
                j++;
            }
        }
        
        return result.ToString();
    }
}

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

Задача: 974. Subarray Sums Divisible by K Сложность: medium Дан целочисленный массив nums и целое число k. Верните количество непустых подмассивов, сумма которых делится на k. Подмассив — это непрерывная часть массива. Пример:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка. Инициализируйте prefixMod = 0 для хранения остатка от суммы элементов до текущего индекса при делении на k. Инициализируйте result = 0 для хранения количества подмассивов, сумма которых делится на k. Инициализируйте массив modGroups длиной k, где modGroups[R] хранит количество подмассивов с остатком R. Установите modGroups[0] = 1. 2⃣Итерирование по массиву. Для каждого элемента массива nums вычислите новый prefixMod как (prefixMod + nums[i] % k + k) % k, чтобы избежать отрицательных значений. Увеличьте result на значение modGroups[prefixMod], чтобы добавить количество подмассивов с текущим остатком. Увеличьте значение modGroups[prefixMod] на 1 для будущих совпадений. 3⃣Возврат результата. Верните значение result, которое содержит количество подмассивов, сумма которых делится на k. 😎 Решение:

public class Solution {
    public int SubarraysDivByK(int[] nums, int k) {
        int prefixMod = 0, result = 0;
        int[] modGroups = new int[k];
        modGroups[0] = 1;

        foreach (int num in nums) {
            prefixMod = (prefixMod + num % k + k) % k;
            result += modGroups[prefixMod];
            modGroups[prefixMod]++;
        }

        return result;
    }
}

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

Задача: 141. Linked List Cycle Сложность: easy Дана переменная head, которая является началом связного списка. Определите, содержит ли связный список цикл. Цикл в связном списке существует, если существует узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла. Обратите внимание, что pos не передается в качестве параметра. Верните true, если в связном списке есть цикл. В противном случае верните false. Пример:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

👨‍💻 Алгоритм: 1⃣Инициализация структуры данных: Создайте хеш-таблицу (или множество) для хранения ссылок на узлы, чтобы отслеживать уже посещённые узлы. 2⃣Обход списка: Перемещайтесь по связному списку, начиная с головы (head), и проверяйте каждый узел по очереди. 3⃣Проверка на цикл: Если текущий узел равен null, это означает, что вы достигли конца списка, и список не имеет циклов. В этом случае верните false. Если текущий узел уже содержится в хеш-таблице, это означает, что вы вернулись к ранее посещённому узлу, и, следовательно, в списке присутствует цикл. Верните true. Если ни одно из этих условий не выполнено, добавьте текущий узел в хеш-таблицу и продолжите обход списка. 😎 Решение:

public class Solution {
    public bool HasCycle(ListNode head) {
        HashSet<ListNode> nodesSeen = new HashSet<ListNode>();
        ListNode current = head;
        while (current != null) {
            if (nodesSeen.Contains(current)) {
                return true;
            }

            nodesSeen.Add(current);
            current = current.next;
        }

        return false;
    }
}

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

Задача: 1074. Number of Submatrices That Sum to Target Сложность: hard Дана матрица и целевое значение. Верните количество непустых подматриц, сумма элементов которых равна целевому значению. Подматрица x1, y1, x2, y2 — это набор всех ячеек matrix[x][y] с x1 <= x <= x2 и y1 <= y <= y2. Две подматрицы (x1, y1, x2, y2) и (x1', y1', x2', y2') различны, если у них есть какая-то различающаяся координата: например, если x1 != x1'. Пример:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

👨‍💻 Алгоритм: 1⃣Инициализируйте результат: count = 0. Вычислите количество строк: r = len(matrix) и количество столбцов: c = len(matrix[0]). Вычислите двумерную префиксную сумму ps, выделив еще одну строку и еще один столбец для нулевых значений. 2⃣Итерируйте по строкам: r1 от 1 до r и r2 от r1 до r. Внутри этого двойного цикла фиксируйте левые и правые границы строк и инициализируйте хэш-таблицу для хранения префиксных сумм. Итерируйте по столбцам от 1 до c + 1, вычислите текущую префиксную сумму 1D curr_sum и увеличьте count на количество матриц, сумма которых равна target. 3⃣Добавьте текущую префиксную сумму 1D в хэш-таблицу. Когда все итерации завершены, верните count. 😎 Решение:

public class Solution {
    public int NumSubmatrixSumTarget(int[][] matrix, int target) {
        int r = matrix.Length, c = matrix[0].Length;
        int[,] ps = new int[r + 1, c + 1];
        
        for (int i = 1; i <= r; ++i) {
            for (int j = 1; j <= c; ++j) {
                ps[i, j] = ps[i - 1, j] + ps[i, j - 1] - ps[i - 1, j - 1] + matrix[i - 1][j - 1];
            }
        }
        
        int count = 0;
        
        for (int r1 = 1; r1 <= r; ++r1) {
            for (int r2 = r1; r2 <= r; ++r2) {
                Dictionary<int, int> h = new Dictionary<int, int>();
                h[0] = 1;
                for (int col = 1; col <= c; ++col) {
                    int currSum = ps[r2, col] - ps[r1 - 1, col];
                    if (h.ContainsKey(currSum - target)) {
                        count += h[currSum - target];
                    }
                    if (h.ContainsKey(currSum)) {
                        h[currSum]++;
                    } else {
                        h[currSum] = 1;
                    }
                }
            }
        }
        
        return count;
    }
}

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

Задача: 1416. Restore The Array Сложность: hard Программа должна была напечатать массив целых чисел. Программа забыла напечатать пробелы, и массив напечатан как строка цифр s, и всё, что мы знаем, это что все числа в массиве были в диапазоне [1, k] и в массиве нет ведущих нулей. Учитывая строку s и целое число k, верните количество возможных массивов, которые могут быть напечатаны как s с использованием упомянутой программы. Так как ответ может быть очень большим, верните его по модулю 10^9 + 7. Пример:

Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]

👨‍💻 Алгоритм: 1⃣Создать массив dp размера m + 1, чтобы хранить значения dfs(x). 2⃣Для получения значения dfs(start), если dp[start] не равно нулю, вернуть его значение. Иначе: Если s[start] == 0, вернуть 0. Если start = m, вернуть 1. Инициализировать count = 0, чтобы считать количество возможных массивов. Перебрать все возможные конечные индексы end, и если s[start ~ end] представляет допустимое число, продолжить рекурсивный вызов dfs(end + 1) и обновить count как count += dfs(end + 1). Обновить dp[start] значением dfs(start). 3⃣Вернуть dfs(0). 😎 Решение:

public class Solution {
    private int mod = 1_000_000_007;

    private int Dfs(int[] dp, int start, string s, int k) {
        if (dp[start] != 0) return dp[start];
        if (start == s.Length) return 1;
        if (s[start] == '0') return 0;

        long count = 0;
        for (int end = start; end < s.Length; ++end) {
            string currNumber = s.Substring(start, end - start + 1);
            if (long.Parse(currNumber) > k) break;
            count = (count + Dfs(dp, end + 1, s, k)) % mod;
        }

        dp[start] = (int)count;
        return (int)count;
    }

    public int NumberOfArrays(string s, int k) {
        int[] dp = new int[s.Length + 1];
        return Dfs(dp, 0, s, k);
    }
}

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

Задача: 167. Two Sum II - Input Array Is Sorted Сложность: medium Дан массив целых чисел numbers, индексированный с 1, который уже отсортирован в неубывающем порядке. Найдите два числа так, чтобы их сумма составляла заданное целевое число. Пусть эти два числа будут numbers[index1] и numbers[index2], где 1 <= index1 < index2 <= numbers.length. Верните индексы этих двух чисел, index1 и index2, увеличенные на один, в виде массива из двух элементов [index1, index2]. Тесты генерируются таким образом, что существует ровно одно решение. Нельзя использовать один и тот же элемент дважды. Ваше решение должно использовать только константное дополнительное пространство. Пример:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

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

public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        int low = 0;
        int high = numbers.Length - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return new int[] { low + 1, high + 1 };
            } else if (sum < target) {
                ++low;
            } else {
                --high;
            }
        }
        return new int[] { -1, -1 };
    }
}

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

Задача: 856. Score of Parentheses Сложность: medium Дана строка s, состоящая из сбалансированных скобок, верните счёт строки. Счёт сбалансированной строки скобок основывается на следующих правилах: "()" имеет счёт 1. AB имеет счёт A + B, где A и B — сбалансированные строки скобок. (A) имеет счёт 2 * A, где A — сбалансированная строка скобок. Пример:

Input: s = "()"
Output: 1

👨‍💻 Алгоритм: 1⃣Назовём сбалансированную строку примитивной, если её нельзя разделить на две непустые сбалансированные строки. 2⃣Отслеживая баланс (количество открывающих скобок минус количество закрывающих скобок), мы можем разделить строку S на примитивные подстроки S = P_1 + P_2 + ... + P_n. Тогда, по определению, score(S) = score(P_1) + score(P_2) + ... + score(P_n). 3⃣Для каждой примитивной подстроки (S[i], S[i+1], ..., S[k]), если длина строки равна 2, то её счёт равен 1. В противном случае, счёт равен удвоенному счёту подстроки (S[i+1], S[i+2], ..., S[k-1]). 😎 Решение:

public class Solution {
    public int ScoreOfParentheses(string S) {
        return F(S, 0, S.Length);
    }

    private int F(string S, int i, int j) {
        int ans = 0, bal = 0;

        for (int k = i; k < j; ++k) {
            bal += S[k] == '(' ? 1 : -1;
            if (bal == 0) {
                if (k - i == 1) ans++;
                else ans += 2 * F(S, i + 1, k);
                i = k + 1;
            }
        }

        return ans;
    }
}

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

Задача: 136. Single Number Сложность: easy Дан непустой массив целых чисел nums, в котором каждый элемент встречается дважды, кроме одного. Найдите этот единственный элемент. Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство. Пример:

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

👨‍💻 Алгоритм: 1⃣Переберите все элементы в массиве nums. 2⃣Если какое-то число в nums новое для массива, добавьте его. 3⃣Если какое-то число уже есть в массиве, удалите его. 😎 Решение:

public class Solution {
    public int SingleNumber(int[] nums) {
        List<int> no_duplicate_list = new List<int>();
        foreach (int i in nums) {
            if (!no_duplicate_list.Contains(i)) {
                no_duplicate_list.Add(i);
            } else {
                no_duplicate_list.Remove(i);
            }
        }

        return no_duplicate_list[0];
    }
}

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

Задача: 1272. Remove Interval Сложность: medium Множество вещественных чисел можно представить как объединение нескольких несовпадающих интервалов, где каждый интервал имеет вид [a, b). Вещественное число x входит в множество, если один из его интервалов [a, b) содержит x (то есть a <= x < b). Вам дан отсортированный список непересекающихся интервалов, представляющих множество вещественных чисел, как описано выше, где intervals[i] = [ai, bi] представляет интервал [ai, bi). Вам также дан еще один интервал toBeRemoved. Верните набор вещественных чисел с интервалом toBeRemoved, удаленным из intervals. Другими словами, верните набор вещественных чисел, каждый x в котором находится в интервале, но не в toBeRemoved. Вашим ответом должен быть отсортированный список непересекающихся интервалов, как описано выше. Пример:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

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

using System;
using System.Collections.Generic;

public class Solution {
    public IList<IList<double>> RemoveInterval(IList<IList<double>> intervals, IList<double> toBeRemoved) {
        var result = new List<IList<double>>();
        foreach (var interval in intervals) {
            if (interval[0] < toBeRemoved[0]) {
                result.Add(new List<double> { interval[0], Math.Min(interval[1], toBeRemoved[0]) });
            }
            if (interval[1] > toBeRemoved[1]) {
                result.Add(new List<double> { Math.Max(interval[0], toBeRemoved[1]), interval[1] });
            }
        }
        return result;
    }
}

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

Задача: 413. Arithmetic Slices Сложность: medium Целочисленный массив называется арифметическим, если он состоит не менее чем из трех элементов и если разность между любыми двумя последовательными элементами одинакова. Например, [1,3,5,7,9], [7,7,7] и [3,-1,-5,-9] являются арифметическими последовательностями. Если задан целочисленный массив nums, верните количество арифметических подмассивов массива nums. Подмассив - это непрерывная подпоследовательность массива. Пример:

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

👨‍💻 Алгоритм: 1⃣Пройдите по массиву, инициализируя два указателя: начальный и текущий. Начните с первой пары элементов. 2⃣Для каждой пары элементов проверяйте, сохраняется ли разность между последовательными элементами. Если да, увеличивайте длину текущей арифметической последовательности. Если нет, сбрасывайте начальную позицию и начинайте новую последовательность. 3⃣Суммируйте количество найденных арифметических подмассивов, учитывая, что для каждого арифметического подмассива длины len, количество таких подмассивов равно (len - 2). 😎 Решение:

public class Solution {
    public int NumberOfArithmeticSlices(int[] nums) {
        if (nums.Length < 3) return 0;
        int count = 0;
        int currentLength = 0;
        for (int i = 2; i < nums.Length; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                currentLength++;
                count += currentLength;
            } else {
                currentLength = 0;
            }
        }
        return count;
    }
}

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

Задача: 922. Sort Array By Parity II Сложность: medium Дан массив целых чисел nums, половина целых чисел в нем нечетные, а другая половина - четные. Отсортируйте массив так, чтобы во всех случаях, когда nums[i] нечетный, i был нечетным, а во всех случаях, когда nums[i] четный, i был четным. Верните любой массив ответов, удовлетворяющий этому условию. Пример:

Input: nums = [4,2,5,7]
Output: [4,5,2,7]

👨‍💻 Алгоритм: 1⃣Инициализировать два указателя even_idx и odd_idx для отслеживания позиций четных и нечетных индексов соответственно. 2⃣Пройти по массиву nums и для каждого элемента: Если элемент четный, поместить его на позицию even_idx и увеличить even_idx на 2. Если элемент нечетный, поместить его на позицию odd_idx и увеличить odd_idx на 2. 3⃣Вернуть отсортированный массив. 😎 Решение:

public class Solution {
    public int[] SortArrayByParityII(int[] nums) {
        int[] result = new int[nums.Length];
        int evenIdx = 0;
        int oddIdx = 1;
        
        foreach (int num in nums) {
            if (num % 2 == 0) {
                result[evenIdx] = num;
                evenIdx += 2;
            } else {
                result[oddIdx] = num;
                oddIdx += 2;
            }
        }
        
        return result;
    }
}

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

Задача: 28. Find the Index of the First Occurrence in a String Сложность: easy Учитывая две строки needle и haystack, верните индекс первого вхождения needle в haystack или -1, если needle не является частью haystack. Пример:

Input: haystack = "sadbutsad", needle = "sad"  
Output: 0  

👨‍💻 Алгоритм: 1⃣Использовать два указателя i и j для прохода по haystack и needle. 2⃣Применить алгоритм KMP с использованием массива LPS (longest prefix suffix) для оптимального поиска. 3⃣Вернуть индекс первого вхождения needle или -1, если needle не найден. 😎 Решение:

public class Solution {
    public int StrStr(string haystack, string needle) {
        int i = 0, j = 0;
        int[] lps = BuildLPS(needle);
        
        while (i < haystack.Length) {
            if (haystack[i] == needle[j]) {
                i++;
                j++;
                if (j == needle.Length) return i - j;
            } else {
                if (j > 0) j = lps[j - 1];
                else i++;
            }
        }
        
        return -1;
    }
    
    private int[] BuildLPS(string needle) {
        int[] lps = new int[needle.Length];
        int i = 0;

        for (int j = 1; j < needle.Length;) {
            if (needle[i] == needle[j]) {
                lps[j++] = ++i;
            } else {
                if (i > 0) i = lps[i - 1];
                else j++;
            }
        }

        return lps;
    }
}

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

⚡️ В сети начали массово сливать курсы и книги известных онлайн школ по айти Вот отсортированная база с тонной материала (постепенно пополняется): (363 видео, 87 книги) — Python (415 видео, 68 книги) — Frontend (143 видео, 33 книги) — ИБ/Хакинг (352 видео, 89 книги) — С/С++/C# (343 видео, 87 книги) — Java/QA (176 видео, 32 книги) — Git/Linux (174 видео, 91 книги) — DevOps (167 видео, 53 книги) — PHP/1С (227 видео, 83 книги) — SQL/БД (114 видео, 77 книги) — Сисадмин (107 видео, 43 книги) — BA/SA (181 видео, 32 книги) — Go/Rust (167 видео, 43 книги) — Kotlin/Swift (112 видео, 24 книги) — Flutter (137 видео, 93 книги) — DS/ML (113 видео, 82 книги) — GameDev (183 видео, 37 книги) — Дизайн (136 видео, 33 книги) — PM/HR Скачивать ничего не нужно — все выложили в Telegram

Задача: 405. Convert a Number to Hexadecimal Сложность: easy Если задано целое число num, верните строку, представляющую его шестнадцатеричное представление. Для отрицательных целых чисел используется метод дополнения до двух. Все буквы в строке ответа должны быть строчными, и в ответе не должно быть никаких ведущих нулей, кроме самого нуля. Примечание: Вам не разрешается использовать какие-либо встроенные библиотечные методы для непосредственного решения этой задачи. Пример:

Input: num = 26
Output: "1a"

👨‍💻 Алгоритм: 1⃣Определите, является ли число отрицательным. Если да, преобразуйте его в положительное число с помощью метода дополнения до двух. Для этого прибавьте к числу 2^32 и используйте битовую операцию И с маской 0xFFFFFFFF. 2⃣Создайте строку с шестнадцатеричными символами. Последовательно делите число на 16 и добавляйте соответствующий символ к результату, пока число не станет равным нулю. 3⃣Переверните строку результата и удалите ведущие нули, если они есть. Если строка пустая, верните "0". 😎 Решение:

public class Solution {
    public string ToHex(int num) {
        if (num == 0) return "0";
        char[] hexChars = "0123456789abcdef".ToCharArray();
        uint n = (uint)num;
        StringBuilder result = new StringBuilder();
        while (n > 0) {
            result.Append(hexChars[n % 16]);
            n /= 16;
        }
        char[] charArray = result.ToString().ToCharArray();
        Array.Reverse(charArray);
        return new string(charArray);
    }
}

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