Задача: 1396. Design Underground System
Сложность: medium

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

Реализуйте класс UndergroundSystem:
- void checkIn(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, регистрируется на станции stationName в момент времени t.
Пассажир может быть зарегистрирован только в одном месте в одно и то же время.
- void checkOut(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, покидает станцию stationName в момент времени t.
- double getAverageTime(string startStation, string endStation)
Возвращает среднее время, необходимое для поездки от startStation до endStation.
Среднее время вычисляется на основе всех предыдущих временных интервалов поездок от startStation до endStation, которые происходили непосредственно, т.е. регистрация на startStation с последующим выходом на endStation.
Время, необходимое для поездки от startStation до endStation, может отличаться от времени поездки от endStation до startStation.
Перед вызовом getAverageTime будет как минимум один пассажир, который уже совершил поездку от startStation до endStation.
Вы можете предположить, что все вызовы методов checkIn и checkOut являются последовательными. Если пассажир регистрируется в момент времени t1, а затем выходит в момент времени t2, то t1 < t2. Все события происходят в хронологическом порядке.

Пример:

Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]
Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]
Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // Customer 2 "Leyton" -> "Paradise" in 30-21 = 9

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

1⃣При регистрации на входе сохраняем информацию о начале пути (станция и время) в словаре checkInData.

2⃣При регистрации на выходе извлекаем информацию о начале пути из checkInData, вычисляем время поездки и обновляем статистику для маршрута в journeyData.

3⃣Для получения среднего времени поездки по заданному маршруту извлекаем статистику из journeyData и вычисляем среднее значение.

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

Задача: 1359. Count All Valid Pickup and Delivery Options
Сложность: hard

Дано n заказов, каждый из которых состоит из услуги забора и доставки.

Посчитайте все возможные допустимые последовательности забора/доставки, такие что доставка(i) всегда идет после забора(i).

Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

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

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

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

3⃣Возвращение результата:
Верните результат для n заказов, применяя модуль 10^9 + 7 для предотвращения переполнения.

😎 Решение:

public class Solution {
    public int CountOrders(int n) {
        int MOD = 1_000_000_007;
        long[] dp = new long[n + 1];
        dp[0] = 1;
        
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] * (2 * i - 1) * i % MOD;
        }
        
        return (int) dp[n];
    }
}

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

Задача: 1502. Can Make Arithmetic Progression From Sequence
Сложность: easy

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

Дан массив чисел arr, верните true, если массив можно переставить так, чтобы он образовал арифметическую прогрессию. В противном случае верните false.

Пример:

Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

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

1⃣Отсортируйте массив arr.

2⃣Запишите разницу первой пары элементов: diff = arr[1] - arr[0].

3⃣Итерируйтесь по отсортированному массиву начиная с i = 2, проверяя, равна ли разница каждой пары элементов значению diff. Если нет, верните False. Если итерация завершена без нахождения различий, верните True.

😎 Решение:

public class Solution {
    public bool CanMakeArithmeticProgression(int[] arr) {
        Array.Sort(arr);
        int diff = arr[1] - arr[0];
        
        for (int i = 2; i < arr.Length; ++i) {
            if (arr[i] - arr[i - 1] != diff) {
                return false;
            }
        }
        
        return true;
    }
}

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

Задача: 485. Max Consecutive Ones
Сложность: Easy

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

Пример:

Input: nums = [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.

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

1⃣Поддерживайте счетчик для подсчета единиц и увеличивайте его на 1 при встрече единицы.

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

3⃣В конце верните максимальное значение.

😎 Решение:

public class Solution {
    public int FindMaxConsecutiveOnes(int[] nums) {
        int count = 0;
        int maxCount = 0;
        foreach (int num in nums) {
            if (num == 1) {
                count += 1;
            } else {
                maxCount = Math.Max(maxCount, count);
                count = 0;
            }
        }
        return Math.Max(maxCount, count);
    }
}

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

Задача: 832. Flipping an Image
Сложность: easy

Дано бинарное изображение размером n x n, необходимо перевернуть изображение по горизонтали, затем инвертировать его и вернуть результат.
Перевернуть изображение по горизонтали означает, что каждая строка изображения будет развернута.
Например, переворот строки [1,1,0] по горизонтали дает [0,1,1].
Инвертировать изображение означает, что каждый 0 заменяется на 1, а каждый 1 заменяется на 0.
Например, инверсия строки [0,1,1] дает [1,0,0].

Пример:

Input: image = [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

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

1⃣Переверните каждую строку по горизонтали, обменяв элементы слева направо и наоборот.

2⃣Инвертируйте каждую строку, заменив каждый 0 на 1 и каждый 1 на 0.

3⃣Верните преобразованное изображение.

😎 Решение:

public class Solution {
    public int[][] FlipAndInvertImage(int[][] A) {
        int C = A[0].Length;

        foreach (var row in A) {
            for (int i = 0; i < (C + 1) / 2; ++i) {
                int tmp = row[i] ^ 1;
                row[i] = row[C - 1 - i] ^ 1;
                row[C - 1 - i] = tmp;
            }
        }

        return A;
    }
}

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

Задача: 1245. Tree Diameter
Сложность: medium

Диаметр дерева - это количество ребер в самом длинном пути в этом дереве. Имеется неориентированное дерево из n узлов, помеченных от 0 до n - 1. Вам дан двумерный массив edges, где edges.length == n - 1 и edges[i] = [ai, bi] означает, что между узлами ai и bi в дереве есть неориентированное ребро. Верните диаметр дерева.

Пример:

Input: edges = [[0,1],[0,2]]
Output: 2

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

1⃣Построение графа:
Используем представление графа в виде списка смежности.

2⃣Поиск самой удаленной вершины (DFS1):
Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее.

3⃣Поиск диаметра (DFS2):
Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId):
Устанавливаем счет игрока в 0.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int TreeDiameter(int[][] edges) {
        if (edges.Length == 0) return 0;

        var graph = new Dictionary<int, List<int>>();
        foreach (var edge in edges) {
            if (!graph.ContainsKey(edge[0])) graph[edge[0]] = new List<int>();
            if (!graph.ContainsKey(edge[1])) graph[edge[1]] = new List<int>();
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }

        int farthestNode = 0;

        int Dfs(int node, int parent) {
            int maxDepth = 0;
            foreach (var neighbor in graph[node]) {
                if (neighbor != parent) {
                    int depth = Dfs(neighbor, node);
                    if (depth + 1 > maxDepth) {
                        maxDepth = depth + 1;
                        farthestNode = neighbor;
                    }
                }
            }
            return maxDepth;
        }

        Dfs(0, -1);
        int startNode = farthestNode;

        Dfs(startNode, -1);
        return Dfs(farthestNode, -1);
    }
}

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

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

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

Вы должны построить множество s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ...} при соблюдении следующего правила:

Первый элемент в s[k] начинается с выбора элемента nums[k] с индексом k.
Следующий элемент в s[k] должен быть nums[nums[k]], затем nums[nums[nums[k]]], и так далее.
Мы прекращаем добавлять элементы непосредственно перед тем, как в s[k] появится дубликат.

Верните длину самого длинного множества s[k].

Пример:

Input: nums = [5,4,0,3,1,6,2]
Output: 4
Explanation: 
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

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

1⃣Создайте массив для отслеживания посещенных элементов.

2⃣Для каждого элемента в nums, если он не посещен, начните формирование множества s[k], последовательно переходя по элементам, пока не встретится уже посещенный элемент.

3⃣Обновите максимальную длину найденного множества.

😎 Решение:

public class Solution {
    public int ArrayNesting(int[] nums) {
        bool[] visited = new bool[nums.Length];
        int maxLength = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            if (!visited[i]) {
                int start = i;
                int count = 0;
                while (!visited[start]) {
                    visited[start] = true;
                    start = nums[start];
                    count++;
                }
                maxLength = Math.Max(maxLength, count);
            }
        }
        
        return maxLength;
    }
}

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

Задача: 1087. Brace Expansion
Сложность: medium

Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.

Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.

Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.

Пример:

Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

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

1⃣Вызовите функцию findAllWords(String, Integer) с данной строкой s и значением startPos равным 0. startPos представляет текущую позицию в строке s. Если строка, которую нужно рассмотреть, пуста (startPos == s.length()), верните список, содержащий пустую строку.

2⃣Вызовите функцию storeFirstOptions с строкой s, целым числом startPos и пустым списком firstOptions. Найдите набор символов, начиная с позиции startPos, и сохраните их в списке firstOptions. Это может быть один символ или все символы между скобками. Отсортируйте список firstOptions. Верните обновленное значение startPos, которое теперь указывает на первый индекс следующей группы символов в строке s, которую мы будем рассматривать. Сохраните это значение в переменной remStringStartPos. Сделайте рекурсивный вызов функции findAllWords(String, Integer) с строкой s и remStringStartPos. Сохраните возвращенный список слов в переменной wordsWithRemString.

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

😎 Решение:

public class Solution {
    private int StoreFirstOptions(string s, int startPos, List<char> firstOptions) {
        if (s[startPos] != '{') {
            firstOptions.Add(s[startPos]);
        } else {
            startPos++;
            while (s[startPos] != '}') {
                if (char.IsLower(s[startPos])) {
                    firstOptions.Add(s[startPos]);
                }
                startPos++;
            }
            firstOptions.Sort();
        }
        return startPos + 1;
    }

    private List<string> FindAllWords(string s, int startPos) {
        if (startPos == s.Length) {
            return new List<string> { "" };
        }

        List<char> firstOptions = new List<char>();
        int remStringStartPos = StoreFirstOptions(s, startPos, firstOptions);
        List<string> wordsWithRemString = FindAllWords(s, remStringStartPos);

        List<string> expandedWords = new List<string>();
        foreach (char c in firstOptions) {
            foreach (string word in wordsWithRemString) {
                expandedWords.Add(c + word);
            }
        }
        return expandedWords;
    }

    public List<string> Expand(string s) {
        return FindAllWords(s, 0);
    }
}

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

Задача: 566. Reshape the Matrix
Сложность: easy

В MATLAB есть удобная функция под названием reshape, которая может преобразовать матрицу размером m x n в новую матрицу с другим размером r x c, сохраняя исходные данные.

Вам дана матрица m x n mat и два целых числа r и c, представляющие количество строк и столбцов желаемой преобразованной матрицы.

Преобразованная матрица должна быть заполнена всеми элементами исходной матрицы в том же порядке обхода строк, в котором они были.

Если операция преобразования с заданными параметрами возможна и допустима, выведите новую преобразованную матрицу; в противном случае выведите исходную матрицу.

Пример:

Input: mat = [[1,2],[3,4]], r = 1, c = 4
Output: [[1,2,3,4]]

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

1⃣Проверить, можно ли преобразовать матрицу с заданными параметрами r и c. Это возможно, если произведение m * n равно произведению r * c. Если преобразование невозможно, вернуть исходную матрицу.

2⃣Создать новый массив для хранения преобразованной матрицы. Перебрать все элементы исходной матрицы и вставить их в новый массив в порядке обхода строк.

3⃣Вернуть преобразованную матрицу, если преобразование возможно, иначе вернуть исходную матрицу.

😎 Решение:

public class Solution {
    public int[][] MatrixReshape(int[][] mat, int r, int c) {
        int m = mat.Length, n = mat[0].Length;
        if (m * n != r * c) {
            return mat;
        }
        int[][] reshapedMatrix = new int[r][];
        for (int i = 0; i < r; i++) {
            reshapedMatrix[i] = new int[c];
        }
        int row = 0, col = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                reshapedMatrix[row][col] = mat[i][j];
                col++;
                if (col == c) {
                    col = 0;
                    row++;
                }
            }
        }
        return reshapedMatrix;
    }
}

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

Задача: 713. Subarray Product Less Than K
Сложность: medium

Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k.

Пример:

Input: nums = [10,5,2,6], k = 100
Output: 8

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

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

2⃣Перемещайте правый указатель по массиву и умножайте текущий элемент на текущее произведение. Если произведение становится больше или равно k, перемещайте левый указатель, уменьшая произведение до тех пор, пока оно снова не станет меньше k.

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

😎 Решение:

public class Solution {
    public int NumSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int product = 1, count = 0, left = 0;
        for (int right = 0; right < nums.Length; right++) {
            product *= nums[right];
            while (product >= k) {
                product /= nums[left];
                left++;
            }
            count += right - left + 1;
        }
        return count;
    }
}

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

Задача: 423. Reconstruct Original Digits from English
Сложность: medium

Дана строка s, содержащая неупорядоченное английское представление цифр от 0 до 9, верните цифры в порядке возрастания.

Пример:

Input: s = "owoztneoer"
Output: "012"

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

1⃣Подсчитайте количество каждого символа в строке s с помощью хэш-таблицы или массива, чтобы определить количество каждого символа.

2⃣Используйте уникальные символы, присутствующие только в одном числе (например, 'z' для 0, 'w' для 2, 'u' для 4, 'x' для 6, 'g' для 8), чтобы определить количество этих цифр в строке. Затем определите количество остальных цифр, вычитая уже найденные цифры.

3⃣Соберите найденные цифры в строку в порядке возрастания и верните результат.

😎 Решение:

public class Solution {
    public string OriginalDigits(string s) {
        int[] count = new int[26];
        foreach (char letter in s) {
            count[letter - 'a']++;
        }

        int[] out = new int[10];
        out[0] = count['z' - 'a'];
        out[2] = count['w' - 'a'];
        out[4] = count['u' - 'a'];
        out[6] = count['x' - 'a'];
        out[8] = count['g' - 'a'];
        out[3] = count['h' - 'a'] - out[8];
        out[5] = count['f' - 'a'] - out[4];
        out[7] = count['s' - 'a'] - out[6];
        out[9] = count['i' - 'a'] - out[5] - out[6] - out[8];
        out[1] = count['n' - 'a'] - out[7] - 2 * out[9];

        StringBuilder output = new StringBuilder();
        for(int i = 0; i < 10; i++)
            for (int j = 0; j < out[i]; j++)
                output.Append(i);
        return output.ToString();
    }
}

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

Задача: 186. Reverse Words in a String II
Сложность: medium

Дан массив символов s, переверните порядок слов.

Слово определяется как последовательность символов, не являющихся пробелами. Слова в s будут разделены одним пробелом.

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

Пример:

Input: s = ["a"]
Output: ["a"]

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

1⃣Перевернуть всю строку: применить функцию reverse, которая переворачивает весь массив символов от начала до конца.

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

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

😎 Решение:

public class Solution {
    public void ReverseWords(char[] s) {
        Array.Reverse(s);
        int start = 0, end = 0, n = s.Length;

        while (start < n) {
            while (end < n && s[end] != ' ') end++;
            Array.Reverse(s, start, end - start);
            end++;
            start = end;
        }
    }
}

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

Задача: 339. Nested List Weight Sum
Сложность: medium

Вам дан вложенный список целых чисел nestedList. Каждый элемент либо целое число, либо список, элементы которого также могут быть целыми числами или другими списками.

Глубина целого числа — это количество списков, в которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значения каждого целого числа, установленные в его глубину.

Верните сумму каждого целого числа в nestedList, умноженного на его глубину.

Пример:

Input: nestedList = [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.

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

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

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

3⃣Возврат результата:
Возвращайте общую сумму на каждом уровне рекурсии. Основная функция возвращает итоговую сумму.

😎 Решение:

public class Solution {
    public int DepthSum(IList<NestedInteger> nestedList) {
        return Dfs(nestedList, 1);
    }
    
    private int Dfs(IList<NestedInteger> list, int depth) {
        int total = 0;
        foreach (var nested in list) {
            if (nested.IsInteger()) {
                total += nested.GetInteger() * depth;
            } else {
                total += Dfs(nested.GetList(), depth + 1);
            }
        }
        return total;
    }
}

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

Задача: 379. Design Phone Directory
Сложность: medium

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

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

PhoneDirectory(int maxNumbers) Инициализирует телефонный справочник с количеством доступных слотов maxNumbers.
int get() Предоставляет номер, который никому не назначен. Возвращает -1, если номера недоступны.
bool check(int number) Возвращает true, если слот доступен, и false в противном случае.
void release(int number) Перераспределяет или освобождает номер слота.

Пример:

Input
["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"]
[[3], [], [], [2], [], [2], [2], [2]]
Output
[null, 0, 1, true, 2, false, null, true]

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

1⃣Инициализировать массив isSlotAvailable размером maxNumbers, установив значение true во всех индексах.

2⃣Метод get(): Проходить по массиву isSlotAvailable. Если найдется true на каком-либо индексе, установить isSlotAvailable[i] = false и вернуть i. Если доступных слотов нет, вернуть -1.
Метод check(number): Вернуть значение isSlotAvailable[number].

3⃣Метод release(number): Установить isSlotAvailable[number] = true.

😎 Решение:

using System;

public class PhoneDirectory {
    private bool[] isSlotAvailable;

    public PhoneDirectory(int maxNumbers) {
        isSlotAvailable = new bool[maxNumbers];
        for (int i = 0; i < maxNumbers; i++) {
            isSlotAvailable[i] = true;
        }
    }

    public int Get() {
        for (int i = 0; i < isSlotAvailable.Length; i++) {
            if (isSlotAvailable[i]) {
                isSlotAvailable[i] = false;
                return i;
            }
        }
        return -1;
    }

    public bool Check(int number) {
        return isSlotAvailable[number];
    }

    public void Release(int number) {
        isSlotAvailable[number] = true;
    }
}

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

Задача: 630. Course Schedule III
Сложность: hard

Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти.

Пример:

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3

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

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

2⃣Проход по курсам
Используйте приоритетную очередь (max-heap) для отслеживания продолжительности пройденных курсов.

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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int ScheduleCourse(int[][] courses) {
        Array.Sort(courses, (a, b) => a[1].CompareTo(b[1]));
        var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        int time = 0;

        foreach (var course in courses) {
            time += course[0];
            maxHeap.Enqueue(course[0], course[0]);
            if (time > course[1]) {
                time -= maxHeap.Dequeue();
            }
        }

        return maxHeap.Count;
    }
}

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

Задача: 906. Super Palindromes
Сложность: hard

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

Пример:

Input: left = "4", right = "1000"
Output: 4

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

1⃣Найти все палиндромы до корня из right.

2⃣Проверить, являются ли квадраты этих палиндромов палиндромами и лежат ли в диапазоне [left, right].

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

😎 Решение:

public class Solution {
    private bool IsPalindrome(long x) {
        string s = x.ToString();
        char[] arr = s.ToCharArray();
        Array.Reverse(arr);
        return s == new string(arr);
    }

    public int SuperpalindromesInRange(string left, string right) {
        long leftNum = long.Parse(left);
        long rightNum = long.Parse(right);
        int count = 0;

        for (int i = 1; i < 100000; i++) {
            string s = i.ToString();
            long palin1 = long.Parse(s + new string(s.Reverse().ToArray()));
            long palin2 = long.Parse(s + new string(s.Reverse().Skip(1).ToArray()));

            if (palin1 * palin1 > rightNum) {
                break;
            }
            if (palin1 * palin1 >= leftNum && IsPalindrome(palin1 * palin1)) {
                count++;
            }
            if (palin2 * palin2 >= leftNum && palin2 * palin2 <= rightNum && IsPalindrome(palin2 * palin2)) {
                count++;
            }
        }

        return count;
    }
}

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

Задача: 1228. Missing Number In Arithmetic Progression
Сложность: easy

В массиве arr значения находились в арифметической прогрессии: значения arr[i + 1] - arr[i] равны для всех 0 <= i < arr.length - 1.

Из массива arr было удалено значение, которое не было первым или последним значением в массиве.

Дан массив arr, вернуть удаленное значение.

Пример:

Input: arr = [5,7,11,13]
Output: 9
Explanation: The previous array was [5,7,9,11,13].

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

1⃣Рассчитать разность difference между элементами арифметической прогрессии.

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

3⃣Вернуть первое ожидаемое значение, которое не совпадает с текущим значением в массиве.

😎 Решение:

public class Solution {
    public int MissingNumber(int[] arr) {
        int n = arr.Length;
        int difference = (arr[n - 1] - arr[0]) / n;
        int expected = arr[0];

        foreach (int val in arr) {
            if (val != expected) {
                return expected;
            }
            expected += difference;
        }
        return expected;
    }
}

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

Задача: 1425. Constrained Subsequence Sum
Сложность: hard

Дан целочисленный массив nums и целое число k, верните максимальную сумму непустой подпоследовательности этого массива, такую, что для любых двух последовательных целых чисел в подпоследовательности nums[i] и nums[j], где i < j, выполняется условие j - i <= k.

Подпоследовательность массива получается путем удаления некоторого количества элементов (может быть ноль) из массива, оставляя оставшиеся элементы в их исходном порядке.

Пример:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

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

1⃣Инициализируйте очередь queue и массив dp той же длины, что и nums.

2⃣Итерируйте i по индексам nums:
Если i минус первый элемент queue больше k, удалите элемент из начала queue.
Установите dp[i] как dp[queue.front()] + nums[i]. Если queue пуст, используйте 0 вместо dp[queue.front()].
Пока dp[queue.back()] меньше dp[i], удаляйте элементы с конца queue.
Если dp[i] > 0, добавьте i в конец queue.

3⃣Верните максимальное значение в массиве dp.

😎 Решение:

public class Solution {
    public int ConstrainedSubsetSum(int[] nums, int k) {
        Deque<int> queue = new LinkedList<int>();
        int[] dp = new int[nums.Length];
        int maxSum = int.MinValue;
        
        for (int i = 0; i < nums.Length; i++) {
            if (queue.Count > 0 && i - queue.First.Value > k) {
                queue.RemoveFirst();
            }
            
            dp[i] = (queue.Count > 0 ? dp[queue.First.Value] : 0) + nums[i];
            
            while (queue.Count > 0 && dp[queue.Last.Value] < dp[i]) {
                queue.RemoveLast();
            }
            
            if (dp[i] > 0) {
                queue.AddLast(i);
            }
            
            maxSum = Math.Max(maxSum, dp[i]);
        }
        
        return maxSum;
    }
}

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

Задача: 583. Delete Operation for Two Strings
Сложность: medium

Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми.

На одном шаге можно удалить ровно один символ в любой строке.

Пример:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

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

1⃣ Инициализация массива:
Создайте одномерный массив dp для хранения минимального количества удалений, необходимых для уравнивания строк word1 и word2.

2⃣ Заполнение массива:
Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки.

3⃣ Обновление и результат:
Скопируйте временный массив temp обратно в dp после обработки каждой строки. В конце верните значение из dp, представляющее минимальное количество удалений.

😎 Решение:

public class Solution {
    public int MinDistance(string word1, string word2) {
        int m = word1.Length;
        int n = word2.Length;
        int[] dp = new int[n + 1];

        for (int i = 0; i <= m; i++) {
            int[] temp = new int[n + 1];
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) {
                    temp[j] = i + j;
                } else if (word1[i - 1] == word2[j - 1]) {
                    temp[j] = dp[j - 1];
                } else {
                    temp[j] = 1 + Math.Min(dp[j], temp[j - 1]);
                }
            }
            dp = temp;
        }

        return dp[n];
    }
}

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

Задача: 446. Arithmetic Slices II - Subsequence
Сложность: hard

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

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

Например, [1, 3, 5, 7, 9], [7, 7, 7, 7] и [3, -1, -5, -9] являются арифметическими последовательностями.
Например, [1, 1, 2, 5, 7] не является арифметической последовательностью.
Подпоследовательность массива - это последовательность, которая может быть образована путем удаления некоторых элементов (возможно, ни одного) из массива.

Например, [2, 5, 10] является подпоследовательностью [1, 2, 1, 2, 4, 1, 5, 10].
Тестовые случаи сгенерированы таким образом, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [2,4,6,8,10]
Output: 7
Explanation: All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

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

1⃣Мы можем использовать поиск в глубину (DFS) для генерации всех подпоследовательностей.

2⃣Мы можем проверить, является ли подпоследовательность арифметической, согласно ее определению.

3⃣Возвращаем количество всех арифметических подпоследовательностей.

😎 Решение:

public class Solution {
    private int n;
    private int ans;

    private void Dfs(int dep, int[] A, List<long> cur) {
        if (dep == n) {
            if (cur.Count < 3) return;
            for (int i = 1; i < cur.Count; i++) {
                if (cur[i] - cur[i - 1] != cur[1] - cur[0]) return;
            }
            ans++;
            return;
        }
        Dfs(dep + 1, A, cur);
        cur.Add(A[dep]);
        Dfs(dep + 1, A, cur);
        cur.RemoveAt(cur.Count - 1);
    }

    public int NumberOfArithmeticSlices(int[] A) {
        n = A.Length;
        ans = 0;
        Dfs(0, A, new List<long>());
        return ans;
    }
}

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

Задача: 1178. Number of Valid Words for Each PuzzleHardTopicsHint
Сложность: hard

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

Слово содержит первую букву головоломки.
Каждая буква в слове присутствует в головоломке.
Например, если головоломка "abcdefg", то допустимыми словами являются "faced", "cabbage" и "baggage", а недопустимыми словами являются "beefed" (не включает 'a') и "based" (включает 's', которой нет в головоломке).

Верните массив answer, где answer[i] - это количество слов в данном списке слов words, которые допустимы относительно головоломки puzzles[i].

Пример:

Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0,1,3,2,0]

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

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

2⃣Подсчитайте количество допустимых слов для каждой головоломки. Для каждой головоломки в списке puzzles:
Преобразуйте ее в битовую маску ее символов. Итерируйте по каждой возможной подмаске, содержащей первую букву головоломки (puzzle[i][0]). Слово является допустимым для головоломки, если его битовая маска совпадает с одной из подмасок головоломки.

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

😎 Решение:

public class Solution {
    private int Bitmask(string word) {
        int mask = 0;
        foreach (char letter in word) {
            mask |= 1 << (letter - 'a');
        }
        return mask;
    }

    public IList<int> FindNumOfValidWords(string[] words, string[] puzzles) {
        var wordCount = new Dictionary<int, int>();
        foreach (var word in words) {
            int mask = Bitmask(word);
            if (!wordCount.ContainsKey(mask)) {
                wordCount[mask] = 0;
            }
            wordCount[mask]++;
        }

        var result = new List<int>();
        foreach (var puzzle in puzzles) {
            int first = 1 << (puzzle[0] - 'a');
            int count = wordCount.ContainsKey(first) ? wordCount[first] : 0;
            int mask = Bitmask(puzzle.Substring(1));
            for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
                count += wordCount.ContainsKey(submask | first) ? wordCount[submask | first] : 0;
            }
            result.Add(count);
        }
        return result;
    }
}

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