Задача: 99. Recover Binary Search Tree
Сложность: medium

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

Пример:

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

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

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

2⃣Определите два поменянных местами элемента x и y в почти отсортированном массиве за линейное время.

3⃣Повторно пройдите по дереву. Измените значение x на y и значение y на x.

😎 Решение:

public class Solution {
    private void Inorder(TreeNode root, List<int> nums) {
        if (root == null)
            return;
        Inorder(root.left, nums);
        nums.Add(root.val);
        Inorder(root.right, nums);
    }

    private int[] FindTwoSwapped(List<int> nums) {
        int n = nums.Count;
        int x = -1, y = -1;
        bool swappedFirstOccurrence = false;
        for (int i = 0; i < n - 1; ++i) {
            if (nums[i + 1] < nums[i]) {
                y = nums[i + 1];
                if (!swappedFirstOccurrence) {
                    x = nums[i];
                    swappedFirstOccurrence = true;
                } else {
                    break;
                }
            }
        }

        return new int[] { x, y };
    }

    private void Recover(TreeNode r, int count, int x, int y) {
        if (r != null) {
            if (r.val == x || r.val == y) {
                r.val = r.val == x ? y : x;
                if (--count == 0)
                    return;
            }

            Recover(r.left, count, x, y);
            Recover(r.right, count, x, y);
        }
    }

    public void RecoverTree(TreeNode root) {
        List<int> nums = new List<int>();
        Inorder(root, nums);
        int[] swapped = FindTwoSwapped(nums);
        Recover(root, 2, swapped[0], swapped[1]);
    }
}

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

Задача: 66. Plus One
Сложность: easy

Вам дано большое число, представленное в виде массива целых чисел digits, где каждый элемент digits[i] — это i-я цифра числа. Цифры расположены в порядке от старшей к младшей слева направо. Большое число не содержит ведущих нулей.

Увеличьте большое число на один и верните результирующий массив цифр.

Пример:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

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

1⃣Проходим по входному массиву, начиная с конца массива.

2⃣Устанавливаем все девятки на конце массива в ноль. Если мы встречаем цифру, не равную девяти, увеличиваем её на один. Работа выполнена — возвращаем массив цифр.

3⃣Мы здесь, потому что все цифры были равны девяти. Теперь они все установлены в ноль. Затем мы добавляем цифру 1 в начало остальных цифр и возвращаем результат.

😎 Решение:

public class Solution {
    public int[] PlusOne(int[] digits) {
        int n = digits.Length;
        for (int idx = n - 1; idx >= 0; --idx) {
            if (digits[idx] == 9) {
                digits[idx] = 0;
            } else {
                digits[idx]++;
                return digits;
            }
        }
        int[] newDigits = new int[n + 1];
        newDigits[0] = 1;
        return newDigits;
    }
}

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

Задача: 1197. Minimum Knight Moves
Сложность: medium

На бесконечной шахматной доске с координатами от -бесконечности до +бесконечности у вас есть конь на клетке [0, 0].
У коня есть 8 возможных ходов. Каждый ход представляет собой два квадрата в кардинальном направлении, затем один квадрат в ортогональном направлении.

Верните минимальное количество шагов, необходимых для перемещения коня на клетку [x, y]. Гарантируется, что ответ существует.

Пример:

Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

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

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

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

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

😎 Решение:

public class Solution {
    public int MinKnightMoves(int x, int y) {
        int[][] offsets = new int[][] {
            new int[] {1, 2}, new int[] {2, 1}, new int[] {2, -1}, new int[] {1, -2},
            new int[] {-1, -2}, new int[] {-2, -1}, new int[] {-2, 1}, new int[] {-1, 2}
        };
        
        var originQueue = new Queue<int[]>();
        originQueue.Enqueue(new int[] {0, 0, 0});
        var originDistance = new Dictionary<string, int> {{"0,0", 0}};
        
        var targetQueue = new Queue<int[]>();
        targetQueue.Enqueue(new int[] {x, y, 0});
        var targetDistance = new Dictionary<string, int> {{$"{x},{y}", 0}};
        
        while (true) {
            var origin = originQueue.Dequeue();
            var originKey = $"{origin[0]},{origin[1]}";
            if (targetDistance.ContainsKey(originKey)) {
                return origin[2] + targetDistance[originKey];
            }
            
            var target = targetQueue.Dequeue();
            var targetKey = $"{target[0]},{target[1]}";
            if (originDistance.ContainsKey(targetKey)) {
                return target[2] + originDistance[targetKey];
            }
            
            foreach (var offset in offsets) {
                var nextOrigin = new int[] {origin[0] + offset[0], origin[1] + offset[1], origin[2] + 1};
                var nextOriginKey = $"{nextOrigin[0]},{nextOrigin[1]}";
                if (!originDistance.ContainsKey(nextOriginKey)) {
                    originQueue.Enqueue(nextOrigin);
                    originDistance[nextOriginKey] = nextOrigin[2];
                }
                
                var nextTarget = new int[] {target[0] + offset[0], target[1] + offset[1], target[2] + 1};
                var nextTargetKey = $"{nextTarget[0]},{nextTarget[1]}";
                if (!targetDistance.ContainsKey(nextTargetKey)) {
                    targetQueue.Enqueue(nextTarget);
                    targetDistance[nextTargetKey] = nextTarget[2];
                }
            }
        }
    }
}

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

Задача: 312. Burst Balloons
Сложность: hard

Дано 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];
    }
}

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

Задача: 1003. Check If Word Is Valid After Substitutions
Сложность: medium

Дана строка s, определите, является ли она допустимой. Строка s допустима, если, начиная с пустой строки t = "", вы можете преобразовать t в s, выполнив следующую операцию любое количество раз: вставить строку "abc" в любую позицию в t. Более формально, t становится tleft + "abc" + tright, где t == tleft + tright. Обратите внимание, что tleft и tright могут быть пустыми. Верните true, если s - допустимая строка, иначе верните false.

Пример:

Input: s = "aabcbc"
Output: true

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

1⃣Проверка допустимости длины строки:
Проверьте, что длина строки s кратна 3. Если нет, верните false.

2⃣Использование стека для проверки:
Инициализируйте пустой стек. Проходите по каждому символу строки s.
Если текущий символ является 'c', проверьте, что два предыдущих символа в стеке - это 'b' и 'a' соответственно. Если это так, удалите 'b' и 'a' из стека. Если нет, верните false.
Если текущий символ не 'c', добавьте его в стек.

3⃣Проверка остатка стека:
В конце, если стек пуст, верните true. Иначе верните false.

😎 Решение:

public class Solution {
    public bool IsValid(string s) {
        if (s.Length % 3 != 0) return false;

        Stack<char> stack = new Stack<char>();
        foreach (char ch in s) {
            if (ch == 'c') {
                if (stack.Count < 2 || stack.Pop() != 'b' || stack.Pop() != 'a') {
                    return false;
                }
            } else {
                stack.Push(ch);
            }
        }

        return stack.Count == 0;
    }
}

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

Ура, друзья! Изиоффер переходит в публичное бета-тестирование!

🎉 Что нового:
🟢Анализ IT собеседований на основе 4500+ реальных интервью
🟢Вопросы из собеседований с вероятностью встречи
🟢Видео-примеры ответов на вопросы от Senior, Middle, Junior грейдов
🟢Пример лучшего ответа
🟢Задачи из собеседований
🟢Тестовые задания
🟢Примеры собеседований
🟢Фильтрация всего контента по грейдам, компаниям
🟢Тренажер подготовки к собеседованию на основе интервальных повторений и флеш карточек
🟡Тренажер "Реальное собеседование" с сценарием вопросов из реальных собеседований (скоро)
🟢Автоотклики на HeadHunter
🟢Закрытое сообщество easyoffer


💎 Акция в честь открытия для первых 500 покупателей:
🚀 Скидка 50% на PRO тариф на 1 год (15000₽ → 7500₽)

🔥 Акция уже стартовала! 👉 https://easyoffer.ru/pro

Задача: 153. Find Minimum in Rotated Sorted Array
Сложность: medium

Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,2,4,5,6,7] может стать:

[4,5,6,7,0,1,2], если он был повернут 4 раза.
[0,1,2,4,5,6,7], если он был повернут 7 раз.
Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Для данного отсортированного и повернутого массива nums с уникальными элементами верните минимальный элемент этого массива.

Вы должны написать алгоритм, который работает за время O(log n).

Пример:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

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

1⃣Нахождение середины массива:
Определите элемент, находящийся посередине массива.

2⃣Определение направления поиска:
Если элемент в середине больше первого элемента массива, это означает, что точка перегиба (минимальный элемент) находится справа от середины.
Если элемент в середине меньше первого элемента массива, это указывает на то, что точка перегиба находится слева от середины.

3⃣Остановка поиска при нахождении точки перегиба:
Поиск прекращается, когда найдена точка перегиба, когда выполняется одно из двух условий:
nums[mid] > nums[mid + 1] – следовательно, mid+1 является наименьшим элементом.
nums[mid - 1] > nums[mid] – следовательно, mid является наименьшим элементом.

😎 Решение:

public class Solution {
    public int FindMin(int[] nums) {
        if (nums.Length == 1) {
            return nums[0];
        }
        int left = 0, right = nums.Length - 1;

        if (nums[right] > nums[0]) {
            return nums[0];
        }

        while (right >= left) {
          
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                return nums[mid + 1];
            }

            if (nums[mid - 1] > nums[mid]) {
                return nums[mid];
            }
            if (nums[mid] > nums[0]) {
                left = mid + 1;
            } else {
                               right = mid - 1;
            }
        }

        return Int32.MaxValue;
    }
}

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

Задача: 208. Implement Trie (Prefix Tree)
Сложность: medium

Trie (произносится как "трай") или префиксное дерево — это древовидная структура данных, используемая для эффективного хранения и поиска ключей в наборе строк. Существует множество применений этой структуры данных, таких как автозаполнение и проверка орфографии.

Реализуйте класс Trie:
Trie() инициализирует объект trie.
void insert(String word) вставляет строку word в trie.
boolean search(String word) возвращает true, если строка word есть в trie (то есть была вставлена ранее), и false в противном случае.
boolean startsWith(String prefix) возвращает true, если есть ранее вставленная строка word, которая имеет префикс prefix, и false в противном случае.

Пример:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

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

1⃣Инициализация и вставка в Trie:
Создайте класс Trie, который включает в себя метод insert(String word) для добавления строк в Trie.
Метод insert инициализирует текущий узел как корень и проходит по каждому символу строки. Если текущий узел не содержит символа, создайте новый узел. В конце отметьте последний узел как конец слова.

2⃣Поиск строки в Trie:
Создайте метод search(String word), который использует вспомогательный метод searchPrefix(String word) для поиска строки или префикса в Trie.
В методе searchPrefix начните с корневого узла и для каждого символа строки перемещайтесь к следующему узлу. Если на каком-то этапе узел не содержит текущего символа, верните null. В противном случае, в конце строки верните текущий узел.

3⃣Проверка наличия префикса в Trie:
Создайте метод startsWith(String prefix), который также использует метод searchPrefix(String prefix).
Метод startsWith вызывает searchPrefix и возвращает true, если возвращаемый узел не равен null, что указывает на наличие префикса в Trie.

😎 Решение:

public class TrieNode {
    private TrieNode[] links = new TrieNode[26];
    private bool isEnd;

    public bool ContainsKey(char ch) {
        return links[ch - 'a'] != null;
    }

    public TrieNode Get(char ch) {
        return links[ch - 'a'];
    }

    public void Put(char ch, TrieNode node) {
        links[ch - 'a'] = node;
    }

    public void SetEnd() {
        isEnd = true;
    }

    public bool IsEnd() {
        return isEnd;
    }
}

public class Trie {
    private TrieNode root = new TrieNode();

    public void Insert(string word) {
        TrieNode node = root;
        foreach (char ch in word) {
            if (!node.ContainsKey(ch)) {
                node.Put(ch, new TrieNode());
            }
            node = node.Get(ch);
        }
        node.SetEnd();
    }

    private TrieNode SearchPrefix(string word) {
        TrieNode node = root;
        foreach (char ch in word) {
            if (node.ContainsKey(ch)) {
                node = node.Get(ch);
            } else {
                return null;
            }
        }
        return node;
    }

    public bool Search(string word) {
        TrieNode node = SearchPrefix(word);
        return node != null && node.IsEnd();
    }

    public bool StartsWith(string prefix) {
        return SearchPrefix(prefix) != null;
    }
}

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

Задача: 240. Search a 2D Matrix II
Сложность: medium

Напишите эффективный алгоритм, который ищет значение target в матрице целых чисел размером m на n. У этой матрицы есть следующие свойства:

Целые числа в каждой строке отсортированы по возрастанию слева направо.
Целые числа в каждом столбце отсортированы по возрастанию сверху вниз.

Пример:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

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

1⃣Проверка матрицы: Перед началом поиска убедитесь, что матрица не пуста и не содержит null.

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

3⃣Бинарный поиск и завершение: Продолжайте бинарный поиск до тех пор, пока не исчерпаете все диагонали (в этом случае возвращается False) или пока не найдете целевое значение (в этом случае возвращается True). Функция бинарного поиска должна уметь работать как с рядами, так и с колонками матрицы.

😎 Решение:

public class Solution {
    private bool BinarySearch(int[,] matrix, int target, int start, bool vertical) {
        int lo = start;
        int hi = vertical ? matrix.GetLength(1) - 1 : matrix.GetLength(0) - 1;

        while (hi >= lo) {
            int mid = (lo + hi) / 2;
            int value = vertical ? matrix[start, mid] : matrix[mid, start];
            if (value < target) {
                lo = mid + 1;
            } else if (value > target) {
                hi = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }

    public bool SearchMatrix(int[,] matrix, int target) {
        if (matrix == null || matrix.Length == 0) return false;

        int shorterDim = Math.Min(matrix.GetLength(0), matrix.GetLength(1));
        for (int i = 0; i < shorterDim; i++) {
            if (BinarySearch(matrix, target, i, true) || BinarySearch(matrix, target, i, false)) {
                return true;
            }
        }
        return false;
    }
}

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

Задача: 328. Odd Even Linked List
Сложность: medium

Дан заголовок односвязного списка. Сгруппируйте все узлы с нечетными индексами вместе, а затем узлы с четными индексами, и верните упорядоченный список.

Первый узел считается нечетным, второй узел — четным и так далее.

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

Вы должны решить задачу с дополнительной сложностью по памяти O(1) и временной сложностью O(n).

Пример:

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

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

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

2⃣Разделение списка:
Используйте цикл для прохождения списка, перенаправляя нечетные узлы в oddList, а четные узлы в evenList. Обновляйте указатели odd и even в процессе итерации.

3⃣Соединение списков:
После окончания цикла соедините конец нечетного списка с началом четного списка, используя указатель evenHead.

😎 Решение:

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode OddEvenList(ListNode head) {
        if (head == null) return null;
        ListNode odd = head, even = head.next, evenHead = even;
        
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}

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

Задача: 322. Coin Change
Сложность: medium

Дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег.

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

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

Пример:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

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

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

2⃣Функция backtracking
Внутри функции backtracking для каждой монеты из массива coins:
Проверьте все возможные количества монет данного номинала (от 0 до максимального количества, которое можно использовать без превышения amount). Для каждой комбинации монет обновите сумму и вызовите функцию рекурсивно для проверки оставшейся суммы. Если текущая комбинация дает меньшую сумму монет, обновите минимальное количество монет.

3⃣Возврат результата
Если комбинация, дающая сумму amount, найдена, верните минимальное количество монет, иначе верните -1.

😎 Решение:

public class Solution {
    public int CoinChange(int[] coins, int amount) {
        return CoinChange(0, coins, amount);
    }

    private int CoinChange(int idxCoin, int[] coins, int amount) {
        if (amount == 0) return 0;
        if (idxCoin < coins.Length && amount > 0) {
            int maxVal = amount / coins[idxCoin];
            int minCost = int.MaxValue;
            for (int x = 0; x <= maxVal; x++) {
                if (amount >= x * coins[idxCoin]) {
                    int res = CoinChange(idxCoin + 1, coins, amount - x * coins[idxCoin]);
                    if (res != -1)
                        minCost = Math.Min(minCost, res + x);
                }
            }
            return minCost == int.MaxValue ? -1 : minCost;
        }
        return -1;
    }
}

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

Задача: 775. Global and Local Inversions
Сложность: medium

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

Число глобальных инверсий — это количество различных пар (i, j), где:

0 <= i < j < n
nums[i] > nums[j]
Число локальных инверсий — это количество индексов i, где:

0 <= i < n - 1
nums[i] > nums[i + 1]
Верните true, если количество глобальных инверсий равно количеству локальных инверсий.

Пример:

Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.

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

1⃣Локальная инверсия также является глобальной инверсией. Таким образом, нам нужно проверить, есть ли в нашей перестановке какие-либо нелокальные инверсии (A[i] > A[j], i < j) с j - i > 1.

2⃣Для этого мы можем перебрать каждый индекс i и проверить, есть ли индекс j, такой что j > i + 1 и nums[i] > nums[j]. Если такой индекс найден, это будет означать наличие нелокальной инверсии.

3⃣Если для всех индексов i условие выше не выполняется, это значит, что количество глобальных инверсий равно количеству локальных инверсий, и мы возвращаем true. В противном случае, если хотя бы одна нелокальная инверсия найдена, мы возвращаем false.

😎 Решение:

public class Solution {
    public bool IsIdealPermutation(int[] A) {
        int N = A.Length;
        for (int i = 0; i < N; ++i)
            for (int j = i + 2; j < N; ++j)
                if (A[i] > A[j]) return false;
        return true;
    }
}

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

Задача: 27. Remove Element
Сложность: easy

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

Учитывайте количество элементов в nums, которые не равны val be k. Чтобы вас приняли, вам необходимо сделать следующее:
- Измените массив nums так, чтобы первые k элементов nums содержали элементы, не равные val. Остальные элементы nums не важны, как и размер nums.
- Вернуть k.

Пример:

Input: nums = [3,2,2,3], val = 3  
Output: 2  

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

1⃣Создать указатель i для записи элементов, не равных val.

2⃣Перебрать массив nums, копируя элементы, отличные от val, на место i, с последующим увеличением i.

3⃣Вернуть i как количество оставшихся элементов.

😎 Решение:

public class Solution {
    public int RemoveElement(int[] nums, int val) {
        int i = 0;
        for (int j = 0; j < nums.Length; j++) {
            if (nums[j] != val) {
                nums[i++] = nums[j];
            }
        }
        return i;
    }
}

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

Задача: 31. Next Permutation
Сложность: medium

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

Пример:

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

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

1⃣Найти первый элемент справа, который меньше следующего (nums[i] < nums[i+1]).

2⃣Найти наибольший элемент справа, который больше nums[i], и поменять их местами.

3⃣Перевернуть оставшуюся часть массива после i для минимальной лексикографической перестановки.

😎 Решение:

public class Solution {
    public void NextPermutation(int[] nums) {
        int i = nums.Length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) i--;

        if (i >= 0) {
            int j = nums.Length - 1;
            while (nums[j] <= nums[i]) j--;
            Swap(nums, i, j);
        }

        Reverse(nums, i + 1);
    }

    private void Reverse(int[] nums, int start) {
        int i = start, j = nums.Length - 1;
        while (i < j) Swap(nums, i++, j--);
    }

    private void Swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

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

Задача: 1055. Shortest Way to Form String
Сложность: medium

Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.

Пример:

Input: source = "abc", target = "abcbc"
Output: 2

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

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

2⃣Перебирай символы строки source, пока не найдешь совпадающий символ в target.
Если ты прошел всю строку source и не нашел все символы target, увеличь счетчик количества подпоследовательностей и начни снова с начала source.

3⃣Повтори шаги 2 и 3 до тех пор, пока не пройдешь всю строку target.

😎 Решение:

public class Solution {
    public int MinSubsequences(string source, string target) {
        int subsequencesCount = 0;
        int targetIndex = 0;

        while (targetIndex < target.Length) {
            int sourceIndex = 0;
            subsequencesCount++;
            int startIndex = targetIndex;

            while (sourceIndex < source.Length && targetIndex < target.Length) {
                if (source[sourceIndex] == target[targetIndex]) {
                    targetIndex++;
                }
                sourceIndex++;
            }

            if (targetIndex == startIndex) {
                return -1;
            }
        }

        return subsequencesCount;
    }
}

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

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

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

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

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

Пример:

Input: nestedList = [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's with a weight of 1, one 2 with a weight of 2.
1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8

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

1⃣Инициализировать первый уровень BFS-дерева, добавив все элементы из входного nestedList в очередь.

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

3⃣Когда очередь станет пустой, вернуть значение (maxDepth + 1) * sumOfElements - sumOfProducts.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int DepthSumInverse(IList<NestedInteger> nestedList) {
        var queue = new Queue<NestedInteger>(nestedList);
        int depth = 1, maxDepth = 0, sumOfElements = 0, sumOfProducts = 0;

        while (queue.Count > 0) {
            int size = queue.Count;
            maxDepth = Math.Max(maxDepth, depth);

            for (int i = 0; i < size; i++) {
                var nested = queue.Dequeue();

                if (nested.IsInteger()) {
                    int value = nested.GetInteger();
                    sumOfElements += value;
                    sumOfProducts += value * depth;
                } else {
                    foreach (var ni in nested.GetList()) queue.Enqueue(ni);
                }
            }
            depth++;
        }
        return (maxDepth + 1) * sumOfElements - sumOfProducts;
    }
}

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

Задача: 629. K Inverse Pairs Array
Сложность: hard

Для целочисленного массива nums инверсная пара - это пара целых чисел [i, j], где 0 <= i < j < nums.length и nums[i] > nums[j]. Учитывая два целых числа n и k, верните количество различных массивов, состоящих из чисел от 1 до n, в которых существует ровно k инверсных пар. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.

Пример:

Input: n = 3, k = 0
Output: 1

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

1⃣Инициализация
Создайте двумерный массив dp размером [n+1][k+1] и установите начальное значение dp[0][0] = 1. Остальные значения установите в 0.

2⃣Заполнение DP-таблицы
Используйте два вложенных цикла для заполнения таблицы DP. Внешний цикл перебирает длину массива i от 1 до n, а внутренний цикл перебирает количество инверсий j от 0 до k. Если j == 0, то dp[i][j] = 1. В противном случае обновляйте dp[i][j] с учетом всех возможных позиций вставки нового элемента в массив длины i-1.

3⃣Возвращение результата
Результатом будет значение dp[n][k].

😎 Решение:

public class Solution {
    public int KInversePairs(int n, int k) {
        int MOD = 1000000007;
        int[,] dp = new int[n + 1, k + 1];
        dp[0, 0] = 1;

        for (int i = 1; i <= n; i++) {
            dp[i, 0] = 1;
            for (int j = 1; j <= k; j++) {
                dp[i, j] = (dp[i, j - 1] + dp[i - 1, j]) % MOD;
                if (j >= i) {
                    dp[i, j] = (dp[i, j] - dp[i - 1, j - i] + MOD) % MOD;
                }
            }
        }

        return dp[n, k];
    }
}

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

Задача: 1199. Minimum Time to Build Blocks
Сложность: hard

Вам дан список блоков, где blocks[i] = t означает, что на строительство i-го блока требуется t единиц времени. Блок может быть построен только одним рабочим.
Рабочий может либо разделиться на двух рабочих (количество рабочих увеличивается на одного), либо построить блок и уйти домой. Оба решения требуют некоторого времени.
Время, затраченное на разделение одного рабочего на двух, задано целым числом split. Обратите внимание, что если два рабочих разделяются одновременно, они разделяются параллельно, поэтому затраты времени будут равны split.

Выведите минимальное время, необходимое для строительства всех блоков.

Изначально есть только один рабочий.

Пример:

Input: blocks = [1,2,3], split = 1
Output: 4
Explanation: Split 1 worker into 2, then assign the first worker to the last block and split the second worker into 2.
Then, use the two unassigned workers to build the first two blocks.
The cost is 1 + max(3, 1 + max(1, 2)) = 4.

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

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

2⃣Обработка кучи:
Пока в куче больше одного элемента:
- извлеките минимальное значение из кучи, обозначим его как x.
- извлеките следующее минимальное значение из кучи, обозначим его как y.
- создайте новое время строительства, которое равно split + y, и вставьте его обратно в кучу.

3⃣Возврат результата:
Когда в куче останется только одно значение, оно и будет минимальным временем, необходимым для строительства всех блоков.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int MinBuildTime(int[] blocks, int split) {
        PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
        foreach (var block in blocks) {
            pq.Enqueue(block, block);
        }
        
        while (pq.Count > 1) {
            int x = pq.Dequeue();
            int y = pq.Dequeue();
            pq.Enqueue(split + y, split + y);
        }
        
        return pq.Dequeue();
    }
}

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

Задача: 1247. Minimum Swaps to Make Strings Equal
Сложность: hard

Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.

Пример:

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

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

1⃣Подсчет несоответствующих пар:
Пройдите по строкам s1 и s2, чтобы подсчитать количество пар xy и yx. Пара xy возникает, когда s1[i] равно 'x', а s2[i] равно 'y'. Пара yx возникает, когда s1[i] равно 'y', а s2[i] равно 'x'.

2⃣Проверка четности:
Если сумма количества пар xy и yx нечетная, то невозможно сделать строки равными, поскольку каждая замена уменьшает сумму несоответствующих пар на 2. В этом случае верните -1.

3⃣Вычисление минимального количества замен:
Если количество пар xy четное и количество пар yx четное, то каждые две пары xy и каждые две пары yx можно обменять за один ход. Поэтому минимальное количество замен равно xy // 2 + yx // 2.
Если количество пар xy нечетное и количество пар yx нечетное, то мы можем обменять одну пару xy и одну пару yx за два хода. Поэтому минимальное количество замен равно xy // 2 + yx // 2 + 2.

😎 Решение:

public class Solution {
    public int MinimumSwap(string s1, string s2) {
        int xy = 0, yx = 0;
        for (int i = 0; i < s1.Length; i++) {
            if (s1[i] == 'x' && s2[i] == 'y') {
                xy++;
            } else if (s1[i] == 'y' && s2[i] == 'x') {
                yx++;
            }
        }
        if ((xy + yx) % 2 != 0) {
            return -1;
        }
        return xy / 2 + yx / 2 + (xy % 2) * 2;
    }
}

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

Задача: 71. Simplify Path
Сложность: medium

Дан абсолютный путь в стиле Unix. Необходимо преобразовать его в канонический, представляющий лишние слэши, .(текущую директорию) и ..(возврат на уровень выше).

Пример:

Input: path = "/home/"

Output: "/home"

Explanation:

The trailing slash should be removed.

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

1⃣Разбить путь /и обработать каждую деталь: колонки .и пустые строки .

2⃣При ..удалении последнего элемента из стеки, если он есть.

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

😎 Решение:

public class Solution {
    public string SimplifyPath(string path) {
        Stack<string> stack = new Stack<string>();
        string[] components = path.Split('/');
        foreach (string directory in components) {
            if (directory.Equals(".") || directory.Length == 0) {
                continue;
            } else if (directory.Equals("..")) {
                if (stack.Any()) {
                    stack.Pop();
                }
            } else {
                stack.Push(directory);
            }
        }

        StringBuilder result = new StringBuilder();
        foreach (string dir in stack.Reverse()) {
            result.Append("/");
            result.Append(dir);
        }

        return result.Length > 0 ? result.ToString() : "/";
    }
}

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

Задача: 598. Range Addition II
Сложность: Easy

Вам дана матрица M размером m x n, инициализированная нулями, и массив операций ops, где ops[i] = [ai, bi] означает, что значение M[x][y] должно быть увеличено на единицу для всех 0 <= x < ai и 0 <= y < bi.

Подсчитайте и верните количество максимальных чисел в матрице после выполнения всех операций.

Пример:

Input: m = 3, n = 3, ops = [[2,2],[3,3]]
Output: 4
Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.

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

1⃣Все операции выполняются на прямоугольной подматрице изначальной матрицы M, заполненной нулями, с верхним левым углом в точке (0,0) и нижним правым углом для операции [i,j] в точке (i,j).

2⃣Максимальный элемент будет тем, на который выполнены все операции. Максимальные элементы будут находиться в области пересечения прямоугольников, представляющих операции. Для определения этой области нужно найти нижний правый угол пересекающейся области (x,y), который равен (min(op[0]), min(op[1])).

3⃣Количество элементов, находящихся в области пересечения, определяется как произведение координат x и y.

😎 Решение:

public class Solution {
    public int MaxCount(int m, int n, int[][] ops) {
        int minA = m;
        int minB = n;
        foreach (var op in ops) {
            minA = Math.Min(minA, op[0]);
            minB = Math.Min(minB, op[1]);
        }
        return minA * minB;
    }
}

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