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

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

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

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