Задача: 1342. Number of Steps to Reduce a Number to Zero
Сложность: easy

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

На каждом шаге, если текущее число четное, его нужно разделить на 2, в противном случае, вы должны вычесть из него 1.

Пример:

Input: num = 14
Output: 6
Explanation: 
Step 1) 14 is even; divide by 2 and obtain 7. 
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3. 
Step 4) 3 is odd; subtract 1 and obtain 2. 
Step 5) 2 is even; divide by 2 and obtain 1. 
Step 6) 1 is odd; subtract 1 and obtain 0.

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

1⃣На каждом шаге проверяйте, четное ли текущее число, используя оператор остатка от деления (%). Если число четное (number % 2 == 0), разделите его на 2.

2⃣Если число нечетное (number % 2 == 1), вычтите из него 1.

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

😎 Решение:

public int NumberOfSteps(int num) {
    int steps = 0;
    while (num != 0) {
        if (num % 2 == 0) {
            num /= 2;
        } else {
            num -= 1;
        }
        steps++;
    }
    return steps;
}

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

Завтра последний день!

Успей купить пожизненный easyoffer PRO - по цене 1 года

Покупаешь один раз — пользуешься всю жизнь.

👉 Акция до 31 марта: https://easyoffer.ru/pro

Задача: 305. Number of Islands II
Сложность: hard

Дан пустой двумерный бинарный массив grid размером m x n. Этот массив представляет собой карту, где 0 означает воду, а 1 — сушу. Изначально все ячейки массива — водные (т.е. все ячейки содержат 0).
Вы можете выполнить операцию "добавить землю", которая превращает воду в указанной позиции в сушу. Вам дан массив positions, где positions[i] = [ri, ci] — позиция (ri, ci), в которой следует выполнить i-ю операцию.
Верните массив целых чисел answer, где answer[i] — количество островов после превращения ячейки (ri, ci) в сушу.
Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Вы можете считать, что все четыре края сетки окружены водой.

Пример:

Input: m = 1, n = 1, positions = [[0,0]]
Output: [1]

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

1⃣Инициализация:
Создайте массивы x[] = { -1, 1, 0, 0 } и y[] = { 0, 0, -1, 1 }, которые будут использоваться для нахождения соседей ячейки.
Создайте экземпляр UnionFind, например, dsu(m * n). Инициализируйте всех родителей значением -1. Используйте объединение по рангу, инициализируйте все ранги значением 0. Наконец, инициализируйте count = 0.
Создайте список целых чисел answer, где answer[i] будет хранить количество островов, образованных после превращения ячейки positions[i] в сушу.

2⃣Обработка позиций:
Итерация по массиву positions. Для каждой позиции в positions:
Выполните линейное отображение, чтобы преобразовать двумерную позицию ячейки в landPosition = position[0] * n + position[1].
Используйте операцию addLand(landPosition), чтобы добавить landPosition как узел в граф. Эта функция также увеличит count.
Итерация по каждому соседу позиции. Соседа можно определить с помощью neighborX = position[0] + x[i] и neighborY = position[1] + y[i], где neighborX — координата X, а neighborY — координата Y соседней ячейки. Выполните линейное отображение соседней ячейки с помощью neighborPosition = neighborX * n + neighborY. Теперь, если на neighborPosition есть суша, т.е. isLand(neighborPosition) возвращает true, выполните объединение neighborPosition и landPosition. В объединении уменьшите count на 1.

3⃣Определение количества островов:
Выполните операцию numberOfIslands, которая возвращает количество островов, образованных после превращения позиции в сушу. Добавьте это значение в answer.
Верните answer.

😎 Решение

public class UnionFind {
    private int[] parent, rank;
    private int count;
    public UnionFind(int size) { parent = new int[size]; rank = new int[size]; Array.Fill(parent, -1); count = 0; }
    public void AddLand(int x) { if (parent[x] < 0) { parent[x] = x; count++; } }
    public bool IsLand(int x) { return parent[x] >= 0; }
    public int NumberOfIslands() { return count; }
    public int Find(int x) { return parent[x] != x ? parent[x] = Find(parent[x]) : x; }
    public void UnionSet(int x, int y) { int xset = Find(x), yset = Find(y); if (xset != yset) {
        if (rank[xset] < rank[yset]) parent[xset] = yset; else { parent[yset] = xset; if (rank[xset] == rank[yset]) rank[xset]++; } count--; } }
}

public class Solution {
    public IList<int> NumIslands2(int m, int n, int[][] positions) {
        var dsu = new UnionFind(m * n);
        int[] x = { -1, 1, 0, 0 }, y = { 0, 0, -1, 1 };
        var answer = new List<int>();
        foreach (var pos in positions) {
            int land = pos[0] * n + pos[1];
            dsu.AddLand(land);
            for (int i = 0; i < 4; ++i) {
                int nx = pos[0] + x[i], ny = pos[1] + y[i], neighbor = nx * n + ny;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && dsu.IsLand(neighbor)) dsu.UnionSet(land, neighbor);
            }
            answer.Add(dsu.NumberOfIslands());
        }
        return answer;
    }
}

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

Задача: 656. Coin Path
Сложность: hard

Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y.

Пример:

Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]

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

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

2⃣Храните путь до каждого индекса для отслеживания наименьшего лексикографического пути.

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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public List<int> MinCostPath(int[] coins, int maxJump) {
        int n = coins.Length;
        if (coins[0] == -1) return new List<int>();
        
        int[] dp = new int[n];
        Array.Fill(dp, int.MaxValue);
        dp[0] = coins[0];
        List<int>[] path = new List<int>[n];
        for (int i = 0; i < n; i++) path[i] = new List<int>();
        path[0].Add(1);
        
        PriorityQueue<(int cost, int index), int> heap = new PriorityQueue<(int, int), int>();
        heap.Enqueue((coins[0], 0), coins[0]);
        
        while (heap.Count > 0) {
            var (currentCost, i) = heap.Dequeue();
            if (currentCost > dp[i]) continue;
            for (int k = 1; k <= maxJump; k++) {
                if (i + k < n && coins[i + k] != -1) {
                    int newCost = currentCost + coins[i + k];
                    if (newCost < dp[i + k] || (newCost == dp[i + k] && ComparePaths(path[i], path[i + k], i + k + 1))) {
                        dp[i + k] = newCost;
                        path[i + k] = new List<int>(path[i]);
                        path[i + k].Add(i + k + 1);
                        heap.Enqueue((newCost, i + k), newCost);
                    }
                }
            }
        }
        
        return dp[n - 1] == int.MaxValue ? new List<int>() : path[n - 1];
    }

    private bool ComparePaths(List<int> path1, List<int> path2, int newIndex) {
        List<int> newPath1 = new List<int>(path1);
        newPath1.Add(newIndex);
        return string.Join(",", newPath1).CompareTo(string.Join(",", path2)) < 0;
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        int[] coins = { 0, 2, 4, -1, 2, 5 };
        int maxJump = 2;
        var result = solution.MinCostPath(coins, maxJump);
    }
}

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

Задача: 537. Complex Number Multiplication
Сложность: medium

Комплексное число можно представить в виде строки в формате "real+imaginaryi", где:
real — это действительная часть и является целым числом в диапазоне [-100, 100].
imaginary — это мнимая часть и является целым числом в диапазоне [-100, 100].
i^2 == -1.
Даны два комплексных числа num1 и num2 в виде строк, верните строку комплексного числа, представляющую их произведение.

Пример:

Input: num1 = "1+1i", num2 = "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

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

1⃣ Извлечение реальной и мнимой частей:
Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'.

2⃣ Вычисление произведения:
Переведите извлечённые части в целые числа.
Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay).

3⃣ Формирование строки результата:
Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её.

😎 Решение:

public class Solution {
    public string ComplexNumberMultiply(string a, string b) {
        var x = a.Split(new char[] { '+', 'i' });
        var y = b.Split(new char[] { '+', 'i' });
        int a_real = int.Parse(x[0]);
        int a_img = int.Parse(x[1]);
        int b_real = int.Parse(y[0]);
        int b_img = int.Parse(y[1]);
        int realPart = a_real * b_real - a_img * b_img;
        int imaginaryPart = a_real * b_img + a_img * b_real;
        return realPart + "+" + imaginaryPart + "i";
    }
}

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

Задача: 1216. Valid Palindrome III
Сложность: hard

Дана строка s и целое число k. Верните true, если s является k-палиндромом.
Строка является k-палиндромом, если её можно преобразовать в палиндром, удалив из неё не более k символов.

Пример:

Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.

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

1⃣Инициализируйте двухмерный массив memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Определите функцию isValidPalindrome, которая будет возвращать минимальное количество удалений для создания палиндрома в подстроке от индекса i до j.

2⃣Реализуйте базовые случаи для функции isValidPalindrome: если i равно j, то это уже палиндром, если i и j - соседние индексы, то возвращается 1, если символы не совпадают. Если значение для пары индексов уже рассчитано, то возвращается сохраненное значение из memo.

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

😎 Решение:

public class Solution {
    private int[,] memo;

    private int IsValidPalindromeHelper(char[] s, int i, int j) {
        if (i == j) return 0;
        if (i == j - 1) return s[i] != s[j] ? 1 : 0;
        if (memo[i, j] != -1) return memo[i, j];
        if (s[i] == s[j]) {
            memo[i, j] = IsValidPalindromeHelper(s, i + 1, j - 1);
        } else {
            memo[i, j] = 1 + Math.Min(IsValidPalindromeHelper(s, i + 1, j), IsValidPalindromeHelper(s, i, j - 1));
        }
        return memo[i, j];
    }

    public bool IsValidPalindrome(string s, int k) {
        int n = s.Length;
        memo = new int[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                memo[i, j] = -1;
            }
        }
        return IsValidPalindromeHelper(s.ToCharArray(), 0, n - 1) <= k;
    }
}

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

Задача: 1001. Grid Illumination
Сложность: hard

Имеется двумерная сетка размером n x n, в каждой ячейке которой есть лампа, изначально выключенная. Вам дан двумерный массив позиций ламп lamps, где lamps[i] = [rowi, coli] означает, что лампа в ячейке grid[rowi][coli] включена. Даже если одна и та же лампа указана несколько раз, она включена. Когда лампа включена, она освещает свою ячейку и все остальные ячейки в той же строке, столбце или диагонали. Вам также дан другой двумерный массив queries, где queries[j] = [rowj, colj]. Для j-го запроса определите, освещена ли сетка[rowj][colj] или нет. После ответа на j-й запрос выключите лампу в сетке[rowj][colj] и 8 соседних ламп, если они существуют. Лампа является смежной, если ее ячейка имеет общую сторону или угол с сеткой[rowj][colj]. Верните массив целых чисел ans, где ans[j] должно быть 1, если ячейка в j-м запросе была освещена, или 0, если лампа не была освещена.

Пример:

Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]

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

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

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

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

😎 Решение:

public class Solution {
    public int[] GridIllumination(int n, int[][] lamps, int[][] queries) {
        var lamps_on = new HashSet<(int, int)>();
        var rows = new Dictionary<int, int>();
        var cols = new Dictionary<int, int>();
        var diag1 = new Dictionary<int, int>();
        var diag2 = new Dictionary<int, int>();

        foreach (var lamp in lamps) {
            int r = lamp[0], c = lamp[1];
            var key = (r, c);
            if (lamps_on.Contains(key)) continue;
            lamps_on.Add(key);
            if (!rows.ContainsKey(r)) rows[r] = 0;
            if (!cols.ContainsKey(c)) cols[c] = 0;
            if (!diag1.ContainsKey(r - c)) diag1[r - c] = 0;
            if (!diag2.ContainsKey(r + c)) diag2[r + c] = 0;
            rows[r]++;
            cols[c]++;
            diag1[r - c]++;
            diag2[r + c]++;
        }

        var directions = new (int, int)[] {(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)};
        var result = new int[queries.Length];

        for (int i = 0; i < queries.Length; i++) {
            int r = queries[i][0], c = queries[i][1];
            if (rows.ContainsKey(r) && rows[r] > 0 || cols.ContainsKey(c) && cols[c] > 0 || diag1.ContainsKey(r - c) && diag1[r - c] > 0 || diag2.ContainsKey(r + c) && diag2[r + c] > 0) {
                result[i] = 1;
            } else {
                result[i] = 0;
            }

            foreach (var dir in directions) {
                int nr = r + dir.Item1, nc = c + dir.Item2;
                var key = (nr, nc);
                if (lamps_on.Contains(key)) {
                    lamps_on.Remove(key);
                    rows[nr]--;
                    cols[nc]--;
                    diag1[nr - nc]--;
                    diag2[nr + nc]--;
                }
            }
        }

        return result;
    }
}

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

Задача: 1035. Uncrossed Lines
Сложность: medium

Вам даны два целочисленных массива nums1 и nums2. Запишем целые числа nums1 и nums2 (в том порядке, в котором они даны) на двух отдельных горизонтальных линиях. Мы можем провести соединительные линии: прямую линию, соединяющую два числа nums1[i] и nums2[j] так, что: nums1[i] == nums2[j], и проведенная линия не пересекает никакую другую соединительную (негоризонтальную) линию. Обратите внимание, что соединительная линия не может пересекаться даже в конечных точках (т.е, каждое число может принадлежать только одной соединительной линии). Верните максимальное количество соединительных линий, которые мы можем нарисовать таким образом.

Пример:

Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2

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

1⃣Определение задачи как задачи о нахождении наибольшей общей подпоследовательности (LCS):
Эта задача является классической задачей динамического программирования, где нам нужно найти максимальную длину наибольшей общей подпоследовательности (LCS) между nums1 и nums2.

2⃣Построение таблицы динамического программирования:
Создайте двумерный массив dp, где dp[i][j] будет представлять длину наибольшей общей подпоследовательности для подмассивов nums1[0..i-1] и nums2[0..j-1].
Инициализируйте первый ряд и первый столбец нулями, так как если один из массивов пуст, LCS также будет пустым.

3⃣Заполнение таблицы динамического программирования:
Пройдите по элементам массивов nums1 и nums2. Если текущие элементы совпадают, увеличьте значение ячейки dp[i][j] на 1 от диагонального значения dp[i-1][j-1]. Если не совпадают, установите значение ячейки dp[i][j] как максимальное из значений dp[i-1][j] и dp[i][j-1].
Результат будет находиться в ячейке dp[nums1.length][nums2.length].

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int[][] AllCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        var cells = new List<(int, int, int)>();
        
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                int distance = Math.Abs(r - rCenter) + Math.Abs(c - cCenter);
                cells.Add((distance, r, c));
            }
        }
        
        cells.Sort((a, b) => a.Item1.CompareTo(b.Item1));
        
        var result = new List<int[]>();
        foreach (var cell in cells) {
            result.Add(new int[] { cell.Item2, cell.Item3 });
        }
        
        return result.ToArray();
    }
}

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

Задача: 1237. Find Positive Integer Solution for a Given Equation
Сложность: medium

Если дана вызываемая функция f(x, y) со скрытой формулой и значением z, выполните обратную разработку формулы и верните все пары целых положительных чисел x и y, в которых f(x,y) == z. Пары можно возвращать в любом порядке. Хотя точная формула скрыта, функция является монотонно возрастающей, т.е.Например: f(x, y) < f(x + 1, y) f(x, y) < f(x, y + 1) Интерфейс функции определяется следующим образом: interface CustomFunction { public: // Возвращает некоторое положительное целое число f(x, y) для двух положительных целых чисел x и y на основе формулы.
int f(int x, int y); }; Мы будем оценивать ваше решение следующим образом: у судьи есть список из 9 скрытых реализаций CustomFunction, а также способ сгенерировать ключ ответа из всех допустимых пар для определенного z. Судья получит два входа: function_id (чтобы определить, с какой реализацией тестировать ваш код) и целевое z. Судья вызовет ваш findSolution и сравнит ваши результаты с ключом ответа. Если ваши результаты совпадут с ключом ответа, ваше решение будет принято.

Пример:

Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]

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

1⃣Начнем с =1 x=1 и 𝑦=1000 y=1000 (предполагаем максимальное значение y).

2⃣Перемещение указателей:
Если 𝑓(𝑥,𝑦)=𝑧
f(x,y)=z, добавляем пару (𝑥,𝑦)(x,y) в результат и увеличиваем x.

3⃣Повторяем шаги до тех пор, пока
𝑥≤1000 x≤1000 и 𝑦≥1y≥1.

😎 Решение:

using System.Collections.Generic;

public class CustomFunction {
    public int f(int x, int y) {}
}

public class Solution {
    public IList<IList<int>> FindSolution(CustomFunction customfunction, int z) {
        var result = new List<IList<int>>();
        int x = 1;
        int y = 1000;
        
        while (x <= 1000 && y >= 1) {
            int value = customfunction.f(x, y);
            if (value == z) {
                result.Add(new List<int> { x, y });
                x++;
            } else if (value < z) {
                x++;
            } else {
                y--;
            }
        }
        
        return result;
    }
}

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

Задача: 1354. Construct Target Array With Multiple Sums
Сложность: hard

Дан массив целых чисел target длины n. Начав с массива arr, состоящего из n единиц, вы можете выполнить следующую процедуру:

Пусть x будет суммой всех элементов, находящихся в вашем массиве.
Выберите индекс i так, чтобы 0 <= i < n, и установите значение arr в индексе i равным x.
Вы можете повторять эту процедуру столько раз, сколько потребуется.
Верните true, если возможно построить массив target из arr, в противном случае верните false.

Пример:

Input: target = [8,5]
Output: true

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

1⃣Использование максимальной кучи (Max Heap) для отслеживания максимальных значений в target:
Сначала необходимо инициализировать кучу с максимальным приоритетом, чтобы всегда иметь доступ к наибольшему элементу в массиве target.
Вычислить сумму всех элементов в target и сохранить ее.

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

3⃣Повторение цикла до достижения результата:
Повторять шаг 2 до тех пор, пока не будут выполнены условия выхода из цикла (возврат true или false).

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public bool IsPossible(int[] target) {
        var pq = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
        long total = 0;
        foreach (var num in target) {
            total += num;
            pq.Enqueue(num, num);
        }
        
        while (pq.Peek() > 1) {
            int maxVal = pq.Dequeue();
            total -= maxVal;
            if (maxVal < total || total == 0 || maxVal % total == 0) return false;
            pq.Enqueue(maxVal % total, maxVal % total);
            total += pq.Peek();
        }
        return true;
    }
}

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

Задача: 480. Sliding Window Median
Сложность: Hard

Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, среднего значения не существует, поэтому медианой считается среднее значение двух средних чисел.

Например, если arr = [2, 3, 4], медиана равна 3.
Например, если arr = [1, 2, 3, 4], медиана равна (2 + 3) / 2 = 2.5.

Вам дан целочисленный массив nums и целое число k. Существует скользящее окно размера k, которое перемещается от самого левого края массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.

Верните массив медиан для каждого окна в исходном массиве. Ответы с точностью до 10^-5 будут приниматься.

Пример:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation: 
Window position                Median
---------------                -----
[1  3  -1] -3  5  3  6  7        1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7        3
 1  3  -1  -3 [5  3  6] 7        5
 1  3  -1  -3  5 [3  6  7]       6

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

1⃣Сохраняйте числа в контейнере окна размера k, выполняя следующие операции: Вставка входящего элемента. Удаление выходящего элемента.

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

3⃣ Поддерживайте окно в отсортированном состоянии до и после операций вставки и удаления.

😎 Решение:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<double> MedianSlidingWindow(int[] nums, int k) {
        List<double> medians = new List<double>();

        for (int i = 0; i + k <= nums.Length; i++) {
            int[] window = new int[k];
            Array.Copy(nums, i, window, 0, k);
            Array.Sort(window);

            if (k % 2 == 1) {
                medians.Add(window[k / 2]);
            } else {
                medians.Add((window[k / 2 - 1] + window[k / 2]) / 2.0);
            }
        }

        return medians;
    }
}

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

Задача: 716. Max Stack
Сложность: hard

Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова.

Пример:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

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

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

2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека.

3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно.

😎 Решение:

public class MaxStack {

    private Stack<int> stack;
    private Stack<int> maxStack;

    public MaxStack() {
        stack = new Stack<int>();
        maxStack = new Stack<int>();
    }

    public void Push(int x) {
        stack.Push(x);
        if (maxStack.Count == 0 || x >= maxStack.Peek()) {
            maxStack.Push(x);
        }
    }

    public int Pop() {
        int x = stack.Pop();
        if (x == maxStack.Peek()) {
            maxStack.Pop();
        }
        return x;
    }

    public int Top() {
        return stack.Peek();
    }

    public int PeekMax() {
        return maxStack.Peek();
    }

    public int PopMax() {
        int maxVal = maxStack.Pop();
        Stack<int> buffer = new Stack<int>();
        while (stack.Peek() != maxVal) {
            buffer.Push(stack.Pop());
        }
        stack.Pop();
        while (buffer.Count > 0) {
            Push(buffer.Pop());
        }
        return maxVal;
    }
}

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