#medium
Задача: 565. Array Nesting

Дан массив целых чисел 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;
    }
}

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

#medium
Задача: 669. Trim a Binary Search Tree

Дано корневое дерево двоичного поиска и нижняя и верхняя границы как low и high. Обрежьте дерево так, чтобы все его элементы лежали в диапазоне [low, high]. Обрезка дерева не должна изменять относительную структуру элементов, которые останутся в дереве (то есть любой потомок узла должен оставаться потомком). Можно доказать, что существует единственный ответ.

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

Пример:

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

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

1⃣Если node.val > high, то обрезанное двоичное дерево должно находиться слева от узла.

2⃣Если node.val < low, то обрезанное двоичное дерево должно находиться справа от узла.

3⃣В противном случае обрезаем обе стороны дерева.

😎 Решение:

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

public class Solution {
    public TreeNode TrimBST(TreeNode root, int low, int high) {
        if (root == null) return null;
        if (root.val > high) return TrimBST(root.left, low, high);
        if (root.val < low) return TrimBST(root.right, low, high);
        root.left = TrimBST(root.left, low, high);
        root.right = TrimBST(root.right, low, high);
        return root;
    }
}

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

#medium
Задача: 309. Best Time to Buy and Sell Stock with Cooldown

Дан массив prices, где prices[i] — цена данной акции в i-й день.

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

После продажи акции вы не можете покупать акции на следующий день (т. е. необходимо один день подождать).

Пример:

Input: prices = [1]
Output: 0

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

1⃣Инициализация состояний
Используйте три состояния для отслеживания максимальной прибыли: hold: максимальная прибыль на данный день, если у вас есть акция. sold: максимальная прибыль на данный день, если вы продали акцию. cooldown: максимальная прибыль на данный день, если вы находитесь в периоде ожидания после продажи.

2⃣Обновление состояний
Итерируйте по каждому дню, обновляя состояния: hold: максимальная прибыль, если у вас есть акция на текущий день. sold: максимальная прибыль, если вы продаете акцию на текущий день. cooldown: максимальная прибыль, если вы находитесь в периоде ожидания на текущий день.

3⃣Определение максимальной прибыли
В конце итерации максимальная прибыль будет максимальным значением между состояниями sold и cooldown, так как hold состояние не может быть конечным состоянием для получения максимальной прибыли.

😎 Решение:

public class Solution {
    public int MaxProfit(int[] prices) {
        if (prices.Length == 0) return 0;
        
        int hold = -prices[0];
        int sold = 0;
        int cooldown = 0;
        
        for (int i = 1; i < prices.Length; i++) {
            int newHold = Math.Max(hold, cooldown - prices[i]);
            int newSold = hold + prices[i];
            int newCooldown = Math.Max(cooldown, sold);
            
            hold = newHold;
            sold = newSold;
            cooldown = newCooldown;
        }
        
        return Math.Max(sold, cooldown);
    }
}

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

#medium
Задача: 670. Maximum Swap

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

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

Пример:

Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

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

1⃣Сохраняем кандидатов как списки длины len(num). Для каждой пары позиций (i, j) выполняем обмен цифр, записываем кандидата, если он больше текущего ответа, затем возвращаем цифры обратно.

2⃣Проверяем, что не добавили ведущий ноль. Фактически, проверять это не нужно, так как изначальное число его не содержит.

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

😎 Решение:

public class Solution {
    public int MaximumSwap(int num) {
        char[] A = num.ToString().ToCharArray();
        char[] ans = (char[])A.Clone();
        for (int i = 0; i < A.Length; i++) {
            for (int j = i + 1; j < A.Length; j++) {
                char tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
                for (int k = 0; k < A.Length; k++) {
                    if (A[k] != ans[k]) {
                        if (A[k] > ans[k]) {
                            ans = (char[])A.Clone();
                        }
                        break;
                    }
                }
                A[j] = A[i];
                A[i] = tmp;
            }
        }
        return int.Parse(new string(ans));
    }
}

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

#medium
Задача: 310. Minimum Height Trees

Дерево — это неориентированный граф, в котором любые две вершины соединены ровно одним путем. Другими словами, любое связное граф без простых циклов является деревом.

Дано дерево из n узлов, помеченных от 0 до n - 1, и массив из n - 1 ребер, где edges[i] = [ai, bi] указывает на наличие неориентированного ребра между узлами ai и bi в дереве. Вы можете выбрать любой узел дерева в качестве корня. Когда вы выбираете узел x в качестве корня, дерево имеет высоту h. Среди всех возможных корневых деревьев те, которые имеют минимальную высоту (то есть min(h)), называются деревьями с минимальной высотой (MHT).

Верните список всех меток корней MHT. Вы можете вернуть ответ в любом порядке.

Высота корневого дерева — это количество ребер на самом длинном нисходящем пути между корнем и листом.

Пример:

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

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

1⃣Создание списка смежности
Создайте список смежности, представляющий граф.

2⃣Удаление листьев
Начните с удаления всех листьев. Лист — это узел с одной гранью. В каждой итерации удаляйте текущие листья и обновляйте список смежности. Новые листья будут вершинами, которые стали листьями после удаления предыдущих листьев.

3⃣Повторение процесса
Повторяйте процесс до тех пор, пока не останется два или менее узлов. Эти узлы будут корнями деревьев с минимальной высотой (MHT).

😎 Решение:

public class Solution {
    public IList<int> FindMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return new List<int> { 0 };
        
        var adj = new List<HashSet<int>>();
        for (int i = 0; i < n; i++) adj.Add(new HashSet<int>());
        foreach (var edge in edges) {
            adj[edge[0]].Add(edge[1]);
            adj[edge[1]].Add(edge[0]);
        }
        
        var leaves = new List<int>();
        for (int i = 0; i < n; i++) {
            if (adj[i].Count == 1) leaves.Add(i);
        }
        
        int remainingNodes = n;
        while (remainingNodes > 2) {
            remainingNodes -= leaves.Count;
            var newLeaves = new List<int>();
            foreach (var leaf in leaves) {
                var neighbor = adj[leaf].First();
                adj[neighbor].Remove(leaf);
                if (adj[neighbor].Count == 1) newLeaves.Add(neighbor);
            }
            leaves = newLeaves;
        }
        
        return leaves;
    }
}

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

#medium
Задача: 672. Bulb Switcher II

Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:

Кнопка 1: Переключает состояние всех лампочек.
Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).
Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).
Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).
Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.

Даны два целых числа n и presses, вернуть количество различных возможных состояний после выполнения всех presses нажатий кнопок.

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

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

1⃣Рассчитаем возможные множества остатков: то есть какие множества c_i = f_i (mod 2) возможны.

2⃣Так как c_i ≡ f_i и c_i ≤ f_i, если ∑f_i ≠ ∑c_i, или если ∑f_i < ∑c_i, это невозможно. В противном случае это возможно простым построением: выполните операции, указанные c_i, затем выполните операцию номер 1 с четным числом оставшихся операций.

3⃣Для каждого возможного множества остатков симулируем и запоминаем, как будут выглядеть первые 6 лампочек, сохраняя это в структуре Set. В конце возвращаем размер этого множества.

😎 Решение:

public class Solution {
    public int FlipLights(int n, int m) {
        var seen = new HashSet<int>();
        n = Math.Min(n, 6);
        int shift = Math.Max(0, 6 - n);
        for (int cand = 0; cand < 16; ++cand) {
            int bcount = Convert.ToString(cand, 2).Count(c => c == '1');
            if (bcount % 2 == m % 2 && bcount <= m) {
                int lights = 0;
                if (((cand >> 0) & 1) > 0) lights ^= 0b111111 >> shift;
                if (((cand >> 1) & 1) > 0) lights ^= 0b010101 >> shift;
                if (((cand >> 2) & 1) > 0) lights ^= 0b101010 >> shift;
                if (((cand >> 3) & 1) > 0) lights ^= 0b100100 >> shift;
                seen.Add(lights);
            }
        }
        return seen.Count;
    }
}

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

#medium
Задача: 311. Sparse Matrix Multiplication

Даны две разреженные матрицы 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;
    }
}

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

#medium
Задача: 673. Number of Longest Increasing Subsequence

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

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

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

1⃣Объявите два массива динамического программирования length и count, и инициализируйте их значениями length[i]=1 и count[i]=1. Итерируйте i от 0 до n−1. Для каждого i итерируйте j от 0 до i−1 и, если nums[j] < nums[i], обновите length[i] и count[i] в зависимости от значений length[j] и count[j].

2⃣Найдите максимальное значение в массиве length и сохраните его в переменной maxLength. Инициализируйте переменную result = 0.

3⃣Итерируйте i от 0 до n−1 и, если length[i] = maxLength, добавьте count[i] к result. Верните result.

😎 Решение:

public class Solution {
    public int FindNumberOfLIS(int[] nums) {
        int n = nums.Length;
        int[] length = new int[n];
        int[] count = new int[n];
        Array.Fill(length, 1);
        Array.Fill(count, 1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (length[j] + 1 > length[i]) {
                        length[i] = length[j] + 1;
                        count[i] = 0;
                    }
                    if (length[j] + 1 == length[i]) {
                        count[i] += count[j];
                    }
                }
            }
        }

        int maxLength = length.Max();
        int result = 0;

        for (int i = 0; i < n; i++) {
            if (length[i] == maxLength) {
                result += count[i];
            }
        }

        return result;
    }
}

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

#easy
Задача: 674. Longest Continuous Increasing Subsequence

Дан неотсортированный массив целых чисел nums, верните длину самой длинной непрерывной возрастающей подпоследовательности (т.е. подмассива). Подпоследовательность должна быть строго возрастающей.

Непрерывная возрастающая подпоследовательность определяется двумя индексами l и r (l < r) так, что она имеет вид [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] и для каждого l <= i < r выполняется nums[i] < nums[i + 1].

Пример:

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.

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

1⃣Каждая (непрерывная) возрастающая подпоследовательность не пересекается, и граница каждой такой подпоследовательности возникает, когда nums[i-1] >= nums[i]. В этом случае начинается новая возрастающая подпоследовательность с nums[i], и мы сохраняем такой i в переменной anchor.

2⃣Например, если nums = [7, 8, 9, 1, 2, 3], то anchor начинается с 0 (nums[anchor] = 7) и затем устанавливается на anchor = 3 (nums[anchor] = 1). Независимо от значения anchor, мы записываем кандидата на ответ длиной i - anchor + 1, длина подмассива nums[anchor], nums[anchor+1], ..., nums[i], и наш ответ обновляется соответствующим образом.

3⃣Возвращаем максимальную длину найденной непрерывной возрастающей подпоследовательности.

😎 Решение:

public class Solution {
    public int FindLengthOfLCIS(int[] nums) {
        int ans = 0, anchor = 0;
        for (int i = 0; i < nums.Length; ++i) {
            if (i > 0 && nums[i-1] >= nums[i]) anchor = i;
            ans = Math.Max(ans, i - anchor + 1);
        }
        return ans;
    }
}

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

#hard
Задача: 675. Cut Off Trees for Golf Event

Вам необходимо срубить все деревья в лесу для проведения гольф-мероприятия. Лес представлен в виде матрицы m x n. В этой матрице:

- 0 означает, что ячейка непроходима.
- 1 представляет собой пустую проходимую ячейку.
- Число больше 1 представляет собой дерево в ячейке, и это число обозначает высоту дерева.

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

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

Начиная с точки (0, 0), верните минимальное количество шагов, необходимых для того, чтобы срубить все деревья. Если невозможно срубить все деревья, верните -1.

Примечание: Входные данные сформированы так, что нет двух деревьев с одинаковой высотой, и нужно срубить как минимум одно дерево.

Пример:

Input: forest = [[1,2,3],[0,0,4],[7,6,5]]
Output: 6
Explanation: Following the path above allows you to cut off the trees from shortest to tallest in 6 steps.

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

1⃣Начиная с (0, 0), для каждого дерева в порядке возрастания высоты будем вычислять расстояние от текущего местоположения до следующего дерева (и перемещаться туда), добавляя это расстояние к ответу.

2⃣Формулируем задачу как предоставление функции расстояния dist(forest, sr, sc, tr, tc), которая вычисляет расстояние от точки (sr, sc) до цели (tr, tc) с учетом препятствий, где dist[i][j] == 0. (Эта функция расстояния вернет -1, если путь невозможен.)

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

😎 Решение:

public class Solution {
    public int CutOffTree(IList<IList<int>> forest) {
        var trees = new List<(int height, int r, int c)>();
        for (int r = 0; r < forest.Count; ++r) {
            for (int c = 0; c < forest[r].Count; ++c) {
                if (forest[r][c] > 1) {
                    trees.Add((forest[r][c], r, c));
                }
            }
        }
        trees.Sort((a, b) => a.height.CompareTo(b.height));

        int sr = 0, sc = 0, ans = 0;
        foreach (var tree in trees) {
            int tr = tree.r, tc = tree.c;
            int d = Dist(forest, sr, sc, tr, tc);
            if (d < 0) return -1;
            ans += d;
            sr = tr;
            sc = tc;
        }
        return ans;
    }

    private int Dist(IList<IList<int>> forest, int sr, int sc, int tr, int tc) {
        // Implement the distance function here
        return 0;
    }
}

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

#hard
Задача: 312. Burst Balloons

Дано n воздушных шаров, пронумерованных от 0 до n - 1. Каждый шарик окрашен в число, представленное массивом nums. Вам нужно лопнуть все шарики.

Если вы лопаете шарик i, вы получите nums[i - 1] * nums[i] * nums[i + 1] монет. Если i - 1 или i + 1 выходит за границы массива, то считайте, что там находится шарик с числом 1.

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

Пример:

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

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

1⃣Инициализация и подготовка данных
Добавьте по одному шару с числом 1 в начало и конец массива nums, чтобы упростить обработку граничных случаев. Определите функцию dp(left, right), которая будет возвращать максимальное количество монет, если лопнуть все шары на интервале [left, right] включительно.

2⃣Вычисление значений для всех интервалов
Для каждого интервала [left, right] и каждого индекса i в этом интервале: Вычислите максимальные монеты, которые можно получить, сначала лопая все шары кроме i, а затем лопая i. Обновите dp(left, right) максимальной суммой этих монет.

3⃣Возврат результата
Верните значение dp(1, n - 2), которое будет содержать максимальное количество монет, которое можно собрать, лопнув все шары с умом, исключая добавленные нами шары.

😎 Решение:

public class Solution {
    public int MaxCoins(int[] nums) {
        int n = nums.Length;
        int[] newNums = new int[n + 2];
        newNums[0] = 1;
        newNums[n + 1] = 1;
        Array.Copy(nums, 0, newNums, 1, n);
        
        int[,] dp = new int[n + 2, n + 2];
        
        for (int length = 2; length < n + 2; length++) {
            for (int left = 0; left < n + 2 - length; left++) {
                int right = left + length;
                for (int i = left + 1; i < right; i++) {
                    dp[left, right] = Math.Max(dp[left, right],
                                               newNums[left] * newNums[i] * newNums[right] + dp[left, i] + dp[i, right]);
                }
            }
        }
        
        return dp[0, n + 1];
    }
}

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

#medium
Задача: 313. Super Ugly Number

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

Дано целое число n и массив целых чисел primes. Верните n-е супер некрасивое число.

Гарантируется, что n-е супер некрасивое число помещается в 32-битное знаковое целое число.

Пример:

Input: n = 12, primes = [2,7,13,19]
Output: 32
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].

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

1⃣Инициализация
Создайте массив ugly_numbers длиной n для хранения супер некрасивых чисел. Создайте массив indices длиной primes для отслеживания позиций в массиве ugly_numbers. Создайте массив next_ugly длиной primes для хранения следующего возможного супер некрасивого числа для каждого простого числа из primes.

2⃣Генерация супер некрасивых чисел
Установите первое значение в ugly_numbers как 1. Повторяйте до тех пор, пока не заполните массив ugly_numbers: Найдите минимальное значение в массиве next_ugly и добавьте его в ugly_numbers. Обновите соответствующий индекс в indices и пересчитайте значение в next_ugly.

3⃣Возврат результата
Верните последнее значение в массиве ugly_numbers, которое будет n-м супер некрасивым числом.

😎 Решение:

public class Solution {
    public int NthSuperUglyNumber(int n, int[] primes) {
        int[] ugly_numbers = new int[n];
        int[] indices = new int[primes.Length];
        int[] next_ugly = (int[])primes.Clone();
        ugly_numbers[0] = 1;
        
        for (int i = 1; i < n; i++) {
            int next_val = next_ugly.Min();
            ugly_numbers[i] = next_val;
            
            for (int j = 0; j < primes.Length; j++) {
                if (next_val == next_ugly[j]) {
                    indices[j]++;
                    next_ugly[j] = ugly_numbers[indices[j]] * primes[j];
                }
            }
        }
        
        return ugly_numbers[n - 1];
    }
}

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

#medium
Задача: 633. Sum of Square Numbers

Учитывая целое неотрицательное число c, решите, существуют ли два целых числа a и b такие, что a2 + b2 = c.

Пример:

Input: c = 5
Output: true

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

1⃣Проверка границ
Проверьте, если c меньше 0, немедленно верните false, так как сумма квадратов двух целых чисел не может быть отрицательной.

2⃣Инициализация указателей
Используйте два указателя a и b. Инициализируйте a на 0 и b на значение квадратного корня из c. Поиск решения: Используйте цикл для поиска a и b, таких что a^2 + b^2 == c: Если a^2 + b^2 равно c, верните true. Если a^2 + b^2 меньше c, увеличьте a на 1. Если a^2 + b^2 больше c, уменьшите b на 1.

3⃣Возвращение результата
Если цикл завершится без нахождения подходящих a и b, верните false.

😎 Решение:

import kotlin.math.sqrt

class Solution {
    fun judgeSquareSum(c: Int): Boolean {
        var a = 0
        var b = sqrt(c.toDouble()).toInt()
        while (a <= b) {
            val total = a * a + b * b
            if (total == c) {
                return true
            } else if (total < c) {
                a++
            } else {
                b--
            }
        }
        return false
    }
}

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

#medium
Задача: 1801. Number of Orders in the Backlog

Дан двумерный целочисленный массив orders, где каждый элемент orders[i] = [pricei, amounti, orderTypei] обозначает, что было размещено amounti заказов типа orderTypei по цене pricei. Тип заказа orderTypei может быть:

- 0, если это партия заказов на покупку, или
- 1, если это партия заказов на продажу.

Обратите внимание, что orders[i] представляет собой партию из amounti независимых заказов с одинаковой ценой и типом. Все заказы, представленные orders[i], будут размещены перед всеми заказами, представленными orders[i+1] для всех допустимых i.

Существует список невыполненных заказов (backlog), который изначально пуст. При размещении заказа происходит следующее:

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

Верните общее количество заказов в списке невыполненных заказов после размещения всех заказов из входных данных. Поскольку это число может быть большим, верните его по модулю 10^9 + 7.

Пример:

Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
Output: 6

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

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

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

3⃣Подсчитайте общее количество оставшихся заказов в списке и верните его по модулю 10^9 + 7.

😎 Решение:

public class Solution {
    public int GetNumberOfBacklogOrders(int[][] orders) {
        int MOD = 1_000_000_007;
        var buyOrders = new PriorityQueue<(int price, int amount), int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        var sellOrders = new PriorityQueue<(int price, int amount), int>();

        foreach (var order in orders) {
            int price = order[0], amount = order[1], orderType = order[2];
            var primaryQueue = orderType == 0 ? sellOrders : buyOrders;
            var secondaryQueue = orderType == 0 ? buyOrders : sellOrders;
            bool isBuyOrder = orderType == 0;

            while (amount > 0 && primaryQueue.Count > 0 && 
                   (isBuyOrder ? primaryQueue.Peek().price <= price : primaryQueue.Peek().price >= price)) {
                var topOrder = primaryQueue.Dequeue();
                int executedAmount = Math.Min(amount, topOrder.amount);
                amount -= executedAmount;
                if (topOrder.amount > executedAmount) {
                    primaryQueue.Enqueue((topOrder.price, topOrder.amount - executedAmount), topOrder.price);
                }
            }
            if (amount > 0) {
                secondaryQueue.Enqueue((price, amount), price);
            }
        }

        return (int)((SumOrders(buyOrders) + SumOrders(sellOrders)) % MOD);
    }

    private long SumOrders(PriorityQueue<(int price, int amount), int> queue) {
        long total = 0;
        while (queue.Count > 0) {
            total += queue.Dequeue().amount;
        }
        return total;
    }
}

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

#medium
Задача: 634. Find the Derangement of An Array

В комбинаторной математике отклонение - это перестановка элементов множества таким образом, что ни один элемент не оказывается на прежнем месте. Вам дано целое число n. Изначально имеется массив, состоящий из n целых чисел от 1 до n в порядке возрастания, верните количество отклонений, которые он может породить. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.

Пример:

Input: n = 3
Output: 2

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

1⃣Инициализация массива для хранения результатов
Создайте массив dp для хранения количества отклонений для каждого значения от 0 до n. Установите начальные значения: dp[0] = 1 и dp[1] = 0.

2⃣Вычисление количества отклонений
Используйте динамическое программирование для вычисления количества отклонений для каждого значения от 2 до n. Формула для вычисления: dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD.

3⃣Возвращение результата
Верните значение dp[n], которое будет количеством отклонений для n элементов, по модулю 10^9 + 7.

😎 Решение:

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

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

#medium
Задача: 635. Design Log Storage System

Вам дается несколько журналов, где каждый журнал содержит уникальный идентификатор и временную метку. Временная метка - это строка, имеющая следующий формат: Год:Месяц:День:Час:Минута:Секунда, например, 2017:01:01:23:59:59. Все домены - десятичные числа с нулевым добавлением. Реализация класса LogSystem: LogSystem() Инициализирует объект LogSystem. void put(int id, string timestamp) Сохраняет заданный журнал (id, timestamp) в вашей системе хранения.
int[] retrieve(string start, string end, string granularity) Возвращает идентификаторы журналов, временные метки которых находятся в диапазоне от start до end включительно. start и end имеют тот же формат, что и timestamp, а granularity означает, насколько точным должен быть диапазон (т. е. с точностью до дня, минуты и т. д.). Например, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", а granularity = "Day" означает, что нам нужно найти журналы в диапазоне от 1 января 2017 года до 2 января 2017 года включительно, а час, минуту и секунду для каждой записи журнала можно игнорировать.

Пример:

Input
["LogSystem", "put", "put", "put", "retrieve", "retrieve"]
[[], [1, "2017:01:01:23:59:59"], [2, "2017:01:01:22:59:59"], [3, "2016:01:01:00:00:00"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour"]]
Output
[null, null, null, null, [3, 2, 1], [2, 1]]

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

1⃣Инициализация и хранение журналов
Реализуйте метод put, который будет сохранять журнал с заданным id и timestamp в системе хранения.

2⃣Формирование диапазона
Реализуйте метод retrieve, который будет формировать диапазон временных меток на основе заданного start, end и granularity.

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

😎 Решение:

using System;
using System.Collections.Generic;

public class LogSystem {
    private List<LogEntry> logs;

    public LogSystem() {
        logs = new List<LogEntry>();
    }

    public void Put(int id, string timestamp) {
        logs.Add(new LogEntry(id, timestamp));
    }

    public IList<int> Retrieve(string start, string end, string granularity) {
        int index = GetGranularityIndex(granularity);
        string startPrefix = start.Substring(0, index);
        string endPrefix = end.Substring(0, index);

        List<int> result = new List<int>();
        foreach (var log in logs) {
            string timestampPrefix = log.Timestamp.Substring(0, index);
            if (startPrefix.CompareTo(timestampPrefix) <= 0 && timestampPrefix.CompareTo(endPrefix) <= 0) {
                result.Add(log.Id);
            }
        }
        return result;
    }

    private int GetGranularityIndex(string granularity) {
        switch (granularity) {
            case "Year": return 4;
            case "Month": return 7;
            case "Day": return 10;
            case "Hour": return 13;
            case "Minute": return 16;
            case "Second": return 19;
            default: return 19;
        }
    }

    private class LogEntry {
        public int Id { get; }
        public string Timestamp { get; }

        public LogEntry(int id, string timestamp) {
            Id = id;
            Timestamp = timestamp;
        }
    }
}

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

#medium
Задача: 636. Exclusive Time of Functions

На однопоточном процессоре выполняется программа, содержащая n функций. Каждая функция имеет уникальный ID от 0 до n-1. Вызовы функций хранятся в стеке вызовов: когда начинается вызов функции, ее ID заталкивается в стек, а когда вызов функции заканчивается, ее ID выгружается из стека. Функция, чей идентификатор находится в верхней части стека, является текущей выполняемой функцией. Каждый раз, когда функция запускается или завершается, мы пишем лог с идентификатором, началом или завершением и меткой времени. Вам предоставляется список logs, где logs[i] представляет собой i-е сообщение лога, отформатированное как строка "{function_id}:{"start" | "end"}:{timestamp}". Например, "0:start:3" означает, что вызов функции с идентификатором 0 начался в начале временной метки 3, а "1:end:2" означает, что вызов функции с идентификатором 1 завершился в конце временной метки 2. Обратите внимание, что функция может быть вызвана несколько раз, возможно, рекурсивно. Исключительное время функции - это сумма времен выполнения всех вызовов функции в программе. Например, если функция вызывается дважды, причем один вызов выполняется за 2 единицы времени, а другой - за 1 единицу, то эксклюзивное время равно 2 + 1 = 3. Верните эксклюзивное время каждой функции в массив, где значение по i-му индексу представляет собой эксклюзивное время для функции с идентификатором i.

Пример:

Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3,4]

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

1⃣Парсинг логов
Пройдитесь по каждому логу, чтобы распознать действие (start или end) и идентификатор функции вместе с временной меткой.

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

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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int[] ExclusiveTime(int n, IList<string> logs) {
        Stack<int> stack = new Stack<int>();
        int[] times = new int[n];
        int prevTime = 0;
        
        foreach (string log in logs) {
            string[] parts = log.Split(':');
            int fid = int.Parse(parts[0]);
            string type = parts[1];
            int time = int.Parse(parts[2]);
            
            if (type == "start") {
                if (stack.Count > 0) {
                    times[stack.Peek()] += time - prevTime;
                }
                stack.Push(fid);
                prevTime = time;
            } else {
                times[stack.Pop()] += time - prevTime + 1;
                prevTime = time + 1;
            }
        }
        
        return times;
    }
}

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

#easy
Задача: 637. Average of Levels in Binary Tree

Учитывая корень бинарного дерева, верните среднее значение узлов на каждом уровне в виде массива. Принимаются ответы в пределах 10-5 от фактического ответа.

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]

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

1⃣Обход дерева
Используйте обход в ширину (BFS) для обхода каждого уровня дерева.

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

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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public IList<double> AverageOfLevels(TreeNode root) {
        var result = new List<double>();
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);

        while (queue.Count > 0) {
            long sum = 0;
            int count = queue.Count;
            for (int i = 0; i < count; i++) {
                var node = queue.Dequeue();
                sum += node.val;
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            result.Add((double)sum / count);
        }

        return result;
    }
}

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

#medium
Задача: 638. Shopping Offers

В магазине LeetCode Store есть n предметов для продажи. Каждый товар имеет свою цену. Однако существуют специальные предложения, и специальное предложение состоит из одного или нескольких различных видов товаров с распродажной ценой. Вам дан целочисленный массив price, где price[i] - цена i-го товара, и целочисленный массив needs, где needs[i] - количество штук i-го товара, который вы хотите купить. Вам также дан массив special, где special[i] имеет размер n + 1, где special[i][j] - количество штук j-го товара в i-м предложении, а special[i][n] (т.е., Возвращает наименьшую цену, которую вы можете заплатить за определенный товар из заданных, где вы могли бы оптимально использовать специальные предложения. Вам не разрешается покупать больше товаров, чем вы хотите, даже если это снизит общую цену. Вы можете использовать любое из специальных предложений столько раз, сколько захотите.

Пример:

Input: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
Output: 14

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

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

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

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

😎 Решение:

public class Solution {
    public int ShoppingOffers(IList<int> price, IList<IList<int>> special, IList<int> needs) {
        var memo = new Dictionary<string, int>();
        return Dfs(price, special, needs, memo);
    }

    private int Dfs(IList<int> price, IList<IList<int>> special, IList<int> needs, Dictionary<string, int> memo) {
        string key = Serialize(needs);
        if (memo.ContainsKey(key)) {
            return memo[key];
        }

        int minPrice = 0;
        for (int i = 0; i < needs.Count; i++) {
            minPrice += needs[i] * price[i];
        }

        foreach (var offer in special) {
            var newNeeds = new List<int>();
            bool valid = true;
            for (int i = 0; i < needs.Count; i++) {
                if (needs[i] < offer[i]) {
                    valid = false;
                    break;
                }
                newNeeds.Add(needs[i] - offer[i]);
            }
            if (valid) {
                minPrice = Math.Min(minPrice, offer[needs.Count] + Dfs(price, special, newNeeds, memo));
            }
        }

        memo[key] = minPrice;
        return minPrice;
    }

    private string Serialize(IList<int> needs) {
        return string.Join(",", needs);
    }
}

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

#hard
Задача: 639. Decode Ways II

Сообщение, содержащее буквы от A-Z, может быть закодировано в цифры с помощью следующего отображения: 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" Чтобы декодировать закодированное сообщение, все цифры должны быть сгруппированы, а затем снова преобразованы в буквы с помощью обратного отображения (может быть несколько способов). Например, "11106" может быть преобразовано в: "AAJF" с группировкой (1 1 10 6) "KJF" с группировкой (11 10 6) Обратите внимание, что группировка (1 11 06) недействительна, поскольку "06" не может быть преобразовано в "F", так как "6" отличается от "06". В дополнение к вышеуказанным преобразованиям кодированное сообщение может содержать символ "*", который может представлять любую цифру от "1" до "9" ("0" исключается). Например, кодированное сообщение "1*" может представлять любое из кодированных сообщений "11", "12", "13", "14", "15", "16", "17", "18" или "19". Декодирование "1*" эквивалентно декодированию любого из кодированных сообщений, которые оно может представлять. Если задана строка s, состоящая из цифр и символов '*', верните количество способов ее декодирования. Поскольку ответ может быть очень большим, верните его по модулю 109 + 7.

Пример:

Input: s = "*"
Output: 9

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

1⃣Инициализация
Создайте массив dp, где dp[i] представляет количество способов декодирования подстроки s[0:i]. Установите начальные значения dp[0] = 1 (пустая строка имеет один способ декодирования).

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

3⃣Модульное вычисление
Поскольку количество способов декодирования может быть большим, вычисляйте результаты по модулю 10^9 + 7.

😎 Решение:

using System;

public class Solution {
    public int NumDecodings(string s) {
        const int MOD = 1000000007;
        int n = s.Length;
        long[] dp = new long[n + 1];
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            if (s[i - 1] == '*') {
                dp[i] = 9 * dp[i - 1];
            } else if (s[i - 1] != '0') {
                dp[i] = dp[i - 1];
            }

            if (i > 1) {
                if (s[i - 2] == '*') {
                    if (s[i - 1] == '*') {
                        dp[i] += 15 * dp[i - 2];
                    } else if (s[i - 1] <= '6') {
                        dp[i] += 2 * dp[i - 2];
                    } else {
                        dp[i] += dp[i - 2];
                    }
                } else if (s[i - 2] == '1') {
                    if (s[i - 1] == '*') {
                        dp[i] += 9 * dp[i - 2];
                    } else {
                        dp[i] += dp[i - 2];
                    }
                } else if (s[i - 2] == '2') {
                    if (s[i - 1] == '*') {
                        dp[i] += 6 * dp[i - 2];
                    } else if (s[i - 1] <= '6') {
                        dp[i] += dp[i - 2];
                    }
                }
            }

            dp[i] %= MOD;
        }

        return (int)dp[n];
    }
}

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

#medium
Задача: 640. Solve the Equation

Решите заданное уравнение и верните значение 'x' в виде строки "x=#value". Уравнение содержит только операции '+', '-', переменную 'x' и ее коэффициент. Вы должны вернуть "No solution", если для уравнения нет решения, или "Infinite solutions", если для уравнения существует бесконечное количество решений. Если для уравнения существует ровно одно решение, мы убеждаемся, что значение 'x' является целым числом.

Пример:

Input: s = "*"
Output: 9

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

1⃣Разделение уравнения
Разделите уравнение на левую и правую части относительно знака равенства '='.

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

3⃣Решение уравнения
Используйте уравнение вида ax + b = cx + d, чтобы решить для 'x'. Если коэффициенты 'x' равны и числовые значения равны, уравнение имеет бесконечное количество решений. Если коэффициенты 'x' равны, но числовые значения различны, решения нет. В противном случае вычислите значение 'x'.

😎 Решение:

using System;
using System.Text.RegularExpressions;

public class Solution {
    public string SolveEquation(string equation) {
        string[] sides = equation.Split('=');
        int[] left = Parse(sides[0]);
        int[] right = Parse(sides[1]);
        
        int coeff = left[0] - right[0];
        int constPart = right[1] - left[1];
        
        if (coeff == 0) {
            return constPart == 0 ? "Infinite solutions" : "No solution";
        }
        return "x=" + (constPart / coeff);
    }

    private int[] Parse(string s) {
        int coeff = 0, constPart = 0, sign = 1, num = 0;
        int i = 0;
        while (i < s.Length) {
            if (s[i] == '+') {
                sign = 1;
                i++;
            } else if (s[i] == '-') {
                sign = -1;
                i++;
            } else if (char.IsDigit(s[i])) {
                num = 0;
                while (i < s.Length && char.IsDigit(s[i])) {
                    num = num * 10 + (s[i] - '0');
                    i++;
                }
                if (i < s.Length && s[i] == 'x') {
                    coeff += sign * num;
                    i++;
                } else {
                    constPart += sign * num;
                }
            } else if (s[i] == 'x') {
                coeff += sign;
                i++;
            }
        }
        return new int[]{coeff, constPart};
    }
}

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