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

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

Задача: 624. Maximum Distance in Arrays
Сложность: medium

Вам дано m массивов, где каждый массив отсортирован по возрастанию. Вы можете взять два целых числа из двух разных массивов (каждый массив выбирает одно) и вычислить расстояние. Мы определяем расстояние между двумя целыми числами a и b как их абсолютную разность |a - b|. Верните максимальное расстояние.

Пример:

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

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

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

2⃣Рассчитайте максимальное расстояние между минимальным и максимальным элементами.

3⃣Верните это максимальное расстояние.

😎 Решение:

public class Solution {
    public int MaxDistance(IList<IList<int>> arrays) {
        int minVal = arrays[0][0];
        int maxVal = arrays[0][arrays[0].Count - 1];
        int maxDistance = 0;
        
        for (int i = 1; i < arrays.Count; i++) {
            maxDistance = Math.Max(maxDistance, Math.Abs(arrays[i][arrays[i].Count - 1] - minVal), Math.Abs(arrays[i][0] - maxVal));
            minVal = Math.Min(minVal, arrays[i][0]);
            maxVal = Math.Max(maxVal, arrays[i][arrays[i].Count - 1]);
        }
        
        return maxDistance;
    }
}

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

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

Реализуйте класс BSTIterator, который представляет итератор по обходу бинарного дерева поиска (BST) в порядке in-order:

BSTIterator(TreeNode root): Инициализирует объект класса BSTIterator. Корень BST передается в качестве параметра конструктора. Указатель должен быть инициализирован на несуществующее число, меньшее любого элемента в BST.
boolean hasNext(): Возвращает true, если в обходе справа от указателя существует число, иначе возвращает false.
int next(): Перемещает указатель вправо, затем возвращает число на указателе.
Обратите внимание, что при инициализации указателя на несуществующее наименьшее число, первый вызов next() вернет наименьший элемент в BST.
Можно предположить, что вызовы next() всегда будут допустимы. То есть, при вызове next() в обходе всегда будет хотя бы одно следующее число.

Пример:

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // return 3
bSTIterator.next();    // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 20
bSTIterator.hasNext(); // return False

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

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

2⃣Мы обходим бинарное дерево поиска в порядке in-order и для каждого узла, который обрабатываем, добавляем его в наш массив узлов. Обратите внимание, что перед обработкой узла сначала нужно обработать (или рекурсивно вызвать) его левое поддерево, а после обработки узла — его правое поддерево.

3⃣Когда у нас будут все узлы в массиве, нам просто нужен указатель или индекс в этом массиве для реализации двух функций next и hasNext. Всякий раз, когда вызывается hasNext, мы просто проверяем, достиг ли индекс конца массива или нет. При вызове функции next мы просто возвращаем элемент, на который указывает индекс. Также, после вызова функции next, мы должны переместить индекс на один шаг вперед, чтобы имитировать прогресс нашего итератора.

😎 Решение:

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

public class BSTIterator {
    private List<int> nodesSorted;
    private int index;

    private void Inorder(TreeNode root) {
        if (root == null) return;
        Inorder(root.left);
        nodesSorted.Add(root.val);
        Inorder(root.right);
    }

    public BSTIterator(TreeNode root) {
        nodesSorted = new List<int>();
        index = -1;
        Inorder(root);
    }

    public int Next() {
        return nodesSorted[++index];
    }

    public bool HasNext() {
        return index + 1 < nodesSorted.Count;
    }
}

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

Задача: 643. Maximum Average Subarray I
Сложность: easy

Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.

Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000

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

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

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

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

😎 Решение:

public class Solution {
    public double FindMaxAverage(int[] nums, int k) {
        int currentSum = 0;
        for (int i = 0; i < k; i++) {
            currentSum += nums[i];
        }
        int maxSum = currentSum;
        
        for (int i = k; i < nums.Length; i++) {
            currentSum += nums[i] - nums[i - k];
            maxSum = Math.Max(maxSum, currentSum);
        }
        
        return (double)maxSum / k;
    }
}

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

Задача: 216. Combination Sum III
Сложность: medium

Найдите все допустимые комбинации k чисел, которые в сумме дают n, при условии, что:

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

Пример:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

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

1⃣Инициализация и запуск рекурсивной функции:
Создайте вспомогательную функцию backtrack, которая принимает текущую оставшуюся сумму, размер комбинации k, текущую комбинацию, индекс следующего элемента для добавления и список результатов.
Инициализируйте пустые векторы для хранения текущей комбинации и всех возможных результатов.
Запустите функцию backtrack с начальными значениями: полной суммой n, размером комбинации k, пустой комбинацией, начальным индексом 0 и пустым списком результатов.

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

3⃣Возвращение результатов:
По завершении всех рекурсивных вызовов функция combinationSum3 возвращает список всех найденных комбинаций.

😎 Решение:

public class Solution {
    private void Backtrack(int remain, int k, List<int> comb, int nextStart, List<IList<int>> results) {
        if (remain == 0 && comb.Count == k) {
            results.Add(new List<int>(comb));
            return;
        } else if (remain < 0 || comb.Count == k) {
            return;
        }

        for (int i = nextStart; i < 9; i++) {
            comb.Add(i + 1);
            Backtrack(remain - i - 1, k, comb, i + 1, results);
            comb.RemoveAt(comb.Count - 1);
        }
    }

    public IList<IList<int>> CombinationSum3(int k, int n) {
        var results = new List<IList<int>>();
        var comb = new List<int>();
        Backtrack(n, k, comb, 0, results);
        return results;
    }
}

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

Задача: 1100. Find K-Length Substrings With No Repeated Characters
Сложность: medium

Дана строка s и целое число k. Верните количество подстрок в s длиной k, которые не содержат повторяющихся символов.

Пример:

Input: s = "havefunonleetcode", k = 5
Output: 6
Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.

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

1⃣Если k > 26, верните 0, так как не может быть строки длиной более 26 символов с уникальными символами. Для остальных случаев, где k <= 26, проверьте каждую подстроку длиной k на наличие повторяющихся символов.

2⃣Итерация по строке s от индекса 0 до n - k (включительно), где n - длина строки s:
Для каждого индекса i:
Инициализируйте флаг isUnique как true и массив частот размером 26 для подсчета частот каждого символа.
Итерируйте следующие k символов и увеличивайте частоту каждого встреченного символа в массиве частот.
Если частота любого символа становится больше 1, установите isUnique в false и прекратите итерацию.
Если после итерации по k символам флаг isUnique все еще равен true, увеличьте счетчик ответов на 1.

3⃣Верните количество подстрок без повторяющихся символов после итерации по всем индексам от 0 до n - k.

😎 Решение:

public class Solution {
    public int NumKLenSubstrNoRepeats(string s, int k) {
        if (k > 26) return 0;
        
        int answer = 0;
        int n = s.Length;
        
        for (int i = 0; i <= n - k; i++) {
            int[] freq = new int[26];
            bool isUnique = true;
            
            for (int j = i; j < i + k; j++) {
                freq[s[j] - 'a']++;
                
                if (freq[s[j] - 'a'] > 1) {
                    isUnique = false;
                    break;
                }
            }
            
            if (isUnique) answer++;
        }
        
        return answer;
    }
}

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

Задача: 323. Number of Connected Components in an Undirected Graph
Сложность: medium

У вас есть граф из n узлов. Вам дано целое число n и массив edges, где edges[i] = [ai, bi] указывает на наличие ребра между ai и bi в графе.

Верните количество связных компонентов в графе.

Пример:

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2

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

1⃣Создание списка смежности
Создайте список смежности, такой что adj[v] содержит все смежные вершины вершины v.

2⃣Инициализация посещенных узлов
Инициализируйте хэш-карту или массив visited для отслеживания посещенных вершин.

3⃣Подсчет компонентов
Определите счетчик и инициализируйте его нулем. Итерируйте по каждой вершине в edges, и если вершина еще не была посещена, начните DFS с этой вершины. Добавляйте каждую вершину, посещенную во время DFS, в visited. Каждый раз, когда начинается новый DFS, увеличивайте счетчик на один. В конце, счетчик будет содержать количество связных компонентов в неориентированном графе.

😎 Решение:

public class Solution {
    public int CountComponents(int n, int[][] edges) {
        var adj = new Dictionary<int, List<int>>();
        for (int i = 0; i < n; i++) adj[i] = new List<int>();
        foreach (var edge in edges) {
            adj[edge[0]].Add(edge[1]);
            adj[edge[1]].Add(edge[0]);
        }

        var visited = new HashSet<int>();
        int count = 0;

        void Dfs(int node) {
            var stack = new Stack<int>();
            stack.Push(node);
            while (stack.Count > 0) {
                var current = stack.Pop();
                if (visited.Add(current)) {
                    foreach (var neighbor in adj[current]) {
                        if (!visited.Contains(neighbor)) stack.Push(neighbor);
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (visited.Add(i)) {
                Dfs(i);
                count++;
            }
        }

        return count;
    }
}

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

Задача: 341. Flatten Nested List Iterator
Сложность: medium

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

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

NestedIterator(List<NestedInteger> nestedList) Инициализирует итератор вложенным списком nestedList.
int next() Возвращает следующий целый элемент вложенного списка.
boolean hasNext() Возвращает true, если в вложенном списке еще остались целые числа, и false в противном случае.

Пример:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

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

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

2⃣Метод next()
Возвращает следующий целый элемент из стека или очереди. Если текущий элемент является списком, развёртывайте его и добавляйте элементы в стек.

3⃣Метод hasNext()
Проверяет, есть ли в стеке или очереди оставшиеся целые элементы. Если на вершине стека находится список, развёртывайте его до тех пор, пока не встретится целый элемент.

😎 Решение:

public class NestedIterator {
    private Stack<NestedInteger> stack;
    
    public NestedIterator(IList<NestedInteger> nestedList) {
        stack = new Stack<NestedInteger>();
        Flatten(nestedList);
    }
    
    private void Flatten(IList<NestedInteger> nestedList) {
        for (int i = nestedList.Count - 1; i >= 0; i--) {
            stack.Push(nestedList[i]);
        }
    }
    
    public int Next() {
        return stack.Pop().GetInteger();
    }
    
    public bool HasNext() {
        while (stack.Count > 0 && !stack.Peek().IsInteger()) {
            Flatten(stack.Pop().GetList());
        }
        return stack.Count > 0;
    }
}

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

Задача: №16. 3Sum Closest
Сложность: medium

Учитывая целочисленный массив nums длины n и целочисленную цель, найдите три целых числа в nums, сумма которых наиболее близка к цели. Возвращает сумму трех целых чисел. Вы можете предположить, что каждый вход будет иметь ровно одно решение.

Пример:

Input: nums = [-1,2,1,-4], target = 1  
Output: 2  

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

1⃣Отсортировать массив и инициализировать переменные для отслеживания минимальной разницы.

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

3⃣Возвращать сумму, которая наиболее близка к target.

😎 Решение:

public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        Array.Sort(nums);
        int closestSum = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < nums.Length - 2; i++) {
            int left = i + 1, right = nums.Length - 1;
            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];

                if (Math.Abs(target - currentSum) < Math.Abs(target - closestSum)) {
                    closestSum = currentSum;
                }

                if (currentSum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return closestSum;
    }
}

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

Задача: 1015. Smallest Integer Divisible by K
Сложность: medium

Задано целое положительное число k, необходимо найти длину наименьшего целого положительного числа n, такого, что n делится на k, и n содержит только цифру 1. Верните длину n. Если такого n не существует, верните -1. Примечание: n может не поместиться в 64-битное знаковое целое число.

Пример:

Input: k = 1
Output: 1

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

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

2⃣Итеративное нахождение числа:
Используйте цикл, чтобы умножать num на 10 и добавлять 1 в каждой итерации, и каждый раз вычисляйте остаток от деления num на k.
Увеличивайте length на 1 в каждой итерации.
Если в какой-то итерации num % k == 0, верните length.

3⃣Проверка бесконечного цикла:
Если цикл длится слишком долго (например, 10^6 итераций), верните -1, чтобы предотвратить бесконечный цикл для случаев, когда решение не существует.

😎 Решение:

public class Solution {
    public int SmallestRepunitDivByK(int k) {
        int num = 1, length = 1;
        HashSet<int> seen = new HashSet<int>();
        
        while (num % k != 0) {
            if (seen.Contains(num % k)) {
                return -1;
            }
            seen.Add(num % k);
            num = (num * 10 + 1) % k;
            length++;
        }
        
        return length;
    }
}

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

Задача: 491. Non-decreasing Subsequences
Сложность: medium

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

Пример:

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

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

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

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

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

😎 Решение:

public class Solution {
    public IList<IList<int>> FindSubsequences(int[] nums) {
        var result = new HashSet<IList<int>>();
        var sequence = new List<int>();
        Backtrack(nums, 0, sequence, result);
        return result.ToList();
    }

    private void Backtrack(int[] nums, int index, List<int> sequence, HashSet<IList<int>> result) {
        if (index == nums.Length) {
            if (sequence.Count >= 2) {
                result.Add(new List<int>(sequence));
            }
            return;
        }
        if (sequence.Count == 0 || sequence[sequence.Count - 1] <= nums[index]) {
            sequence.Add(nums[index]);
            Backtrack(nums, index + 1, sequence, result);
            sequence.RemoveAt(sequence.Count - 1);
        }
        Backtrack(nums, index + 1, sequence, result);
    }
}

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

Задача: 232. Implement Queue using Stacks
Сложность: easy

Реализуйте очередь (FIFO) с использованием только двух стеков. Реализованная очередь должна поддерживать все функции обычной очереди (push, peek, pop и empty).

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

void push(int x) добавляет элемент x в конец очереди.
int pop() удаляет элемент из начала очереди и возвращает его.
int peek() возвращает элемент из начала очереди.
boolean empty() возвращает true, если очередь пуста, и false в противном случае.

Пример:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

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

1⃣Добавление элемента: Для метода push(int x) переместите все элементы из стека s1 в стек s2. Добавьте элемент x в стек s2. Затем переместите все элементы обратно из стека s2 в стек s1. Если стек s1 пуст, обновите переменную front значением x.

2⃣Удаление и проверка первого элемента: Для метода pop() удалите элемент из начала очереди, извлекая верхний элемент из стека s1. Обновите переменную front на новый верхний элемент стека s1, если он не пуст. Для метода peek() верните значение переменной front, так как она всегда хранит первый элемент очереди.

3⃣Проверка на пустоту: Для метода empty() верните результат проверки, является ли стек s1 пустым.

😎 Решение:

public class MyQueue {
    private Stack<int> s1 = new Stack<int>();
    private Stack<int> s2 = new Stack<int>();
    private int front;

    public void Push(int x) {
        if (s1.Count == 0)
            front = x;
        while (s1.Count != 0)
            s2.Push(s1.Pop());
        s2.Push(x);
        while (s2.Count != 0)
            s1.Push(s2.Pop());
    }

    public int Pop() {
        int res = s1.Pop();
        if (s1.Count != 0)
            front = s1.Peek();
        return res;
    }

    public bool Empty() {
        return s1.Count == 0;
    }

    public int Peek() {
        return front;
    }
}

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

Задача: 859. Buddy Strings
Сложность: easy

Даны две строки s и goal. Верните true, если вы можете поменять местами две буквы в s так, чтобы результат был равен goal, в противном случае верните false.

Обмен буквами определяется как взятие двух индексов i и j (нумерация с 0), таких что i != j, и обмен символов в s[i] и s[j].

Например, обмен символов на индексах 0 и 2 в строке "abcd" приводит к "cbad".

Пример:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

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

1⃣Если количество символов в строках s и goal разное, возвращаем false. Если s == goal, используем хеш-таблицу или массив из 26 элементов для хранения частоты каждого символа в строке s. Если какой-либо символ встречается более одного раза, можно поменять местами две одинаковые буквы, возвращаем true. Иначе возвращаем false.

2⃣Иначе, если s != goal, инициализируем firstIndex и secondIndex значениями -1 для хранения индексов символов в строке s, которые отличаются от символов в строке goal на тех же индексах. Итерируем по каждому индексу i в строке s: если символы s[i] и goal[i] разные, сохраняем текущий индекс. Если firstIndex == -1, обновляем firstIndex = i. Если firstIndex != -1, но secondIndex == -1, обновляем secondIndex = i. Если оба индекса уже обновлены, возвращаем false.

3⃣Если обновлен только firstIndex, возвращаем false. Иначе, все символы обеих строк одинаковы, кроме двух индексов. Поэтому s[firstIndex] должен быть равен goal[secondIndex], и s[secondIndex] должен быть равен goal[firstIndex], чтобы строки стали равны после обмена.

😎 Решение:

public class Solution {
    public bool BuddyStrings(string s, string goal) {
        if (s.Length != goal.Length) return false;
        if (s == goal) {
            var freq = new int[26];
            foreach (var ch in s) {
                if (++freq[ch - 'a'] > 1) return true;
            }
            return false;
        }

        int firstIndex = -1, secondIndex = -1;
        for (int i = 0; i < s.Length; ++i) {
            if (s[i] != goal[i]) {
                if (firstIndex == -1) firstIndex = i;
                else if (secondIndex == -1) secondIndex = i;
                else return false;
            }
        }

        return secondIndex != -1 &&
               s[firstIndex] == goal[secondIndex] &&
               s[secondIndex] == goal[firstIndex];
    }
}

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

Задача: 1140. Stone Game II
Сложность: medium

Алиса и Боб продолжают свои игры с кучами камней. Есть несколько куч, расположенных в ряд, и в каждой куче положительное количество камней piles[i]. Цель игры - закончить с наибольшим количеством камней.
Алиса и Боб ходят по очереди, начиная с Алисы. Изначально M = 1.
В свой ход каждый игрок может взять все камни из первых X оставшихся куч, где 1 <= X <= 2M. Затем, мы устанавливаем M = max(M, X).
Игра продолжается до тех пор, пока все камни не будут взяты.
Предполагая, что Алиса и Боб играют оптимально, верните максимальное количество камней, которые может получить Алиса.

Пример:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. 
Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. 
In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

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

1⃣Создать рекурсивную функцию f, которая принимает три параметра: p (игрок), i (индекс текущей кучи),
и m (максимальное количество куч, которые можно взять за ход).
Если i равен длине массива кучи, вернуть 0 (базовый случай рекурсии). Если значение уже вычислено ранее (dp[p][i][m] != -1), вернуть его.

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

3⃣Итеративно обновлять значение res в зависимости от того, чей ход, и обновлять значения в dp[p][i][m]. В конце вернуть res.

😎 Решение:

public class Solution {
    public int StoneGameII(int[] piles) {
        int[][][] dp = new int[2][][];
        for (int i = 0; i < 2; i++) {
            dp[i] = new int[piles.Length + 1][];
            for (int j = 0; j <= piles.Length; j++) {
                dp[i][j] = new int[piles.Length + 1];
                for (int k = 0; k <= piles.Length; k++) {
                    dp[i][j][k] = -1;
                }
            }
        }
        
        int f(int p, int i, int m) {
            if (i == piles.Length) return 0;
            if (dp[p][i][m] != -1) return dp[p][i][m];
            int res = p == 1 ? 1000000 : -1;
            int s = 0;
            for (int x = 1; x <= Math.Min(2 * m, piles.Length - i); x++) {
                s += piles[i + x - 1];
                if (p == 0) {
                    res = Math.Max(res, s + f(1, i + x, Math.Max(m, x)));
                } else {
                    res = Math.Min(res, f(0, i + x, Math.Max(m, x)));
                }
            }
            return dp[p][i][m] = res;
        }
        
        return f(0, 0, 1);
    }
}

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

Задача: 1151. Minimum Swaps to Group All 1's Together
Сложность: medium

Дан бинарный массив data, необходимо вернуть минимальное количество перестановок, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте массива.

Пример:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

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

1⃣Используем два указателя, left и right, чтобы поддерживать скользящее окно длиной ones и проверяем каждый фрагмент массива data, подсчитывая количество единиц в нем (cnt_one) и запоминая максимальное значение max_one.

2⃣Пока окно скользит по массиву data, поддерживаем его длину равной ones.

3⃣Обновляем количество единиц в окне, добавляя новую границу data[right] и вычитая левую границу data[left].

😎 Решение:

public class Solution {
    public int MinSwaps(int[] data) {
        int ones = data.Sum();
        int cnt_one = 0, max_one = 0;
        int left = 0, right = 0;

        while (right < data.Length) {
            cnt_one += data[right++];
            if (right - left > ones) {
                cnt_one -= data[left++];
            }
            max_one = Math.Max(max_one, cnt_one);
        }
        return ones - max_one;
    }
}

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