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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#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;
    }
}

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

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

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

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

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

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

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

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

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

Задача: 1009. Complement of Base 10 Integer
Сложность: easy

Дополнение целого числа - это целое число, которое получается, если перевернуть все 0 в 1 и все 1 в 0 в его двоичном представлении. Например, целое число 5 - это "101" в двоичном представлении, а его дополнение - "010", то есть целое число 2. Если задано целое число n, верните его дополнение.

Пример:

Input: n = 5
Output: 2

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

1⃣Определение длины двоичного представления:
Найдите длину двоичного представления числа n.

2⃣Создание маски:
Создайте маску, которая состоит из всех единиц и имеет ту же длину, что и двоичное представление числа n.

3⃣Вычисление дополнения:
Примените побитовую операцию XOR между числом n и маской, чтобы получить дополнение числа.

😎 Решение:

public class Solution {
    public int FindComplement(int num) {
        int length = (int)Math.Log(num, 2) + 1;
        int mask = (1 << length) - 1;
        return num ^ mask;
    }
}

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

Задача: 417. Pacific Atlantic Water Flow
Сложность: medium

Имеется прямоугольный остров размером m x n, который граничит с Тихим и Атлантическим океанами. Тихий океан касается левого и верхнего краев острова, а Атлантический океан - правого и нижнего краев. Остров разбит на сетку квадратных ячеек. Вам дана целочисленная матрица heights размером m x n, где heights[r][c] - высота над уровнем моря клетки с координатами (r, c). На острове выпадает много осадков, и дождевая вода может стекать в соседние клетки прямо на север, юг, восток и запад, если высота соседней клетки меньше или равна высоте текущей клетки. Вода может течь из любой клетки, прилегающей к океану, в океан. Верните двумерный список координат сетки result, где result[i] = [ri, ci] означает, что дождевая вода может течь из клетки (ri, ci) как в Тихий, так и в Атлантический океаны.

Пример:

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

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

1⃣Определите две матрицы для отслеживания клеток, из которых вода может течь в Тихий и Атлантический океаны, используя поиск в глубину (DFS) или поиск в ширину (BFS), начиная с границ, примыкающих к каждому океану.

2⃣Выполните поиск для каждого океана, обновляя матрицы достижимости.

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

😎 Решение:

public class Solution {
    public IList<IList<int>> PacificAtlantic(int[][] heights) {
        int m = heights.Length;
        int n = heights[0].Length;
        bool[][] pacific = new bool[m][];
        bool[][] atlantic = new bool[m][];
        for (int i = 0; i < m; i++) {
            pacific[i] = new bool[n];
            atlantic[i] = new bool[n];
        }
        int[][] directions = new int[][] { new int[] {-1, 0}, new int[] {1, 0}, new int[] {0, -1}, new int[] {0, 1} };
        
        for (int i = 0; i < m; i++) {
            Dfs(i, 0, pacific, heights, directions);
            Dfs(i, n - 1, atlantic, heights, directions);
        }
        for (int j = 0; j < n; j++) {
            Dfs(0, j, pacific, heights, directions);
            Dfs(m - 1, j, atlantic, heights, directions);
        }
        
        IList<IList<int>> result = new List<IList<int>>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.Add(new List<int> { i, j });
                }
            }
        }
        return result;
    }
    
    private void Dfs(int r, int c, bool[][] ocean, int[][] heights, int[][] directions) {
        ocean[r][c] = true;
        foreach (int[] dir in directions) {
            int nr = r + dir[0];
            int nc = c + dir[1];
            if (nr >= 0 && nc >= 0 && nr < heights.Length && nc < heights[0].Length && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                Dfs(nr, nc, ocean, heights, directions);
            }
        }
    }
}

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

Задача: 1044. Longest Duplicate Substring
Сложность: hard

Учитывая строку s, рассмотрите все дублированные подстроки: (смежные) подстроки s, которые встречаются 2 или более раз.Вхождения могут перекрываться. Верните любую дублированную подстроку, которая имеет наибольшую возможную длину.Если в s нет дублирующейся подстроки, ответом будет "".

Пример:

Input: s = "banana"
Output: "ana"

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

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

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

3⃣Хеширование с помощью функции rolling hash:
Rolling hash позволяет быстро вычислять хеши подстрок фиксированной длины и сравнивать их для поиска дубликатов.

😎 Решение:

public class Solution {
    public string LongestDupSubstring(string s) {
        int left = 1, right = s.Length;
        string result = "";
        while (left < right) {
            int mid = (left + right) / 2;
            string dup = Search(s, mid);
            if (dup != null) {
                result = dup;
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return result;
    }

    private string Search(string s, int length) {
        HashSet<string> seen = new HashSet<string>();
        for (int i = 0; i <= s.Length - length; i++) {
            string sub = s.Substring(i, length);
            if (seen.Contains(sub)) {
                return sub;
            }
            seen.Add(sub);
        }
        return null;
    }
}

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

Задача: 956. Tallest Billboard
Сложность: hard

Вы устанавливаете рекламный щит и хотите, чтобы он имел наибольшую высоту. У рекламного щита будет две стальные опоры, по одной с каждой стороны. Каждая стальная опора должна быть одинаковой высоты. Вам дается набор стержней, которые можно сварить вместе. Например, если у вас есть стержни длиной 1, 2 и 3, вы можете сварить их вместе, чтобы получилась опора длиной 6. Верните наибольшую возможную высоту вашей рекламной установки. Если вы не можете установить рекламный щит, верните 0.

Пример:

Input: rods = [1,2,3,6]
Output: 6

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

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

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

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

😎 Решение:

public class Solution {
    public int MinDeletionSize(string[] strs) {
        int n = strs.Length;
        int m = strs[0].Length;
        bool[] deleteCount = new bool[m];
        
        bool IsSorted() {
            for (int i = 0; i < n - 1; i++) {
                for (int j = 0; j < m; j++) {
                    if (deleteCount[j]) continue;
                    if (strs[i][j] > strs[i + 1][j]) return false;
                    if (strs[i][j] < strs[i + 1][j]) break;
                }
            }
            return true;
        }
        
        while (!IsSorted()) {
            for (int j = 0; j < m; j++) {
                if (deleteCount[j]) continue;
                for (int i = 0; i < n - 1; i++) {
                    if (strs[i][j] > strs[i + 1][j]) {
                        deleteCount[j] = true;
                        break;
                    }
                }
                if (deleteCount[j]) break;
            }
        }
        
        int count = 0;
        foreach (bool del in deleteCount) {
            if (del) count++;
        }
        return count;
    }
}

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

Задача: 1372. Longest ZigZag Path in a Binary Tree
Сложность: medium

Вам дан корень бинарного дерева.

Зигзагообразный путь для бинарного дерева определяется следующим образом:

Выберите любой узел в бинарном дереве и направление (вправо или влево).
Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу.
Измените направление с вправо на влево или с влево на вправо.
Повторяйте второй и третий шаги, пока не сможете двигаться по дереву.
Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0).

Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве.

Пример:

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

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

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

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

3⃣Рекурсивный вызов для левого и правого дочерних узлов:
Рекурсивно вызывайте функцию dfs для левого и правого дочерних узлов с обновленными параметрами длины и направления.

😎 Решение:

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

public class Solution {
    private int maxLength = 0;

    public int LongestZigZag(TreeNode root) {
        Dfs(root, true, 0);
        Dfs(root, false, 0);
        return maxLength;
    }

    private void Dfs(TreeNode node, bool isLeft, int length) {
        if (node == null) return;
        maxLength = Math.Max(maxLength, length);
        if (isLeft) {
            Dfs(node.left, false, length + 1);
            Dfs(node.right, true, 1);
        } else {
            Dfs(node.right, true, length + 1);
            Dfs(node.left, false, 1);
        }
    }
}

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