Задача: 907. Sum of Subarray Minimums
Сложность: medium

Учитывая массив целых чисел arr, найдите сумму min(b), где b находится в каждом (смежном) подмассиве arr. Поскольку ответ может быть большим, верните ответ по модулю 109 + 7.

Пример:

Input: arr = [3,1,2,4]
Output: 17

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

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

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

3⃣Вычислить сумму минимальных значений для всех подмассивов и вернуть результат по модулю 10^9 + 7.

😎 Решение:

public class Solution {
    public int SumSubarrayMins(int[] arr) {
        const int MOD = 1_000_000_007;
        int n = arr.Length;
        int[] left = new int[n];
        int[] right = new int[n];
        Stack<int> stack = new Stack<int>();

        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && arr[stack.Peek()] > arr[i]) {
                stack.Pop();
            }
            left[i] = stack.Count == 0 ? i + 1 : i - stack.Peek();
            stack.Push(i);
        }

        stack.Clear();

        for (int i = n - 1; i >= 0; i--) {
            while (stack.Count > 0 && arr[stack.Peek()] >= arr[i]) {
                stack.Pop();
            }
            right[i] = stack.Count == 0 ? n - i : stack.Peek() - i;
            stack.Push(i);
        }

        long result = 0;
        for (int i = 0; i < n; i++) {
            result = (result + (long)arr[i] * left[i] * right[i]) % MOD;
        }

        return (int)result;
    }
}

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

Задача: 1133. Largest Unique Number
Сложность: easy

Вам Дан целочисленный массив nums, верните наибольшее целое число, которое встречается только один раз. Если ни одно целое число не встречается один раз, верните -1.

Пример:

Input: nums = [5,7,3,9,4,9,8,3,1]
Output: 8
Explanation: The maximum integer in the array is 9 but it is repeated. The number 8 occurs only once, so it is the answer.

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

1⃣Создайте хеш-таблицу для хранения количества каждого числа в массиве.

2⃣Пройдите по массиву и заполните хеш-таблицу количеством каждого числа.

3⃣Инициализируйте результат значением -1. Пройдите по хеш-таблице и если значение ключа равно 1, установите результат равным максимальному значению между ключом и текущим результатом. Верните результат.

😎 Решение:

public class Solution {
    public int LargestUniqueNumber(int[] nums) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        
        foreach (int num in nums) {
            if (count.ContainsKey(num)) {
                count[num]++;
            } else {
                count[num] = 1;
            }
        }
        
        int result = -1;
        foreach (var entry in count) {
            if (entry.Value == 1) {
                result = Math.Max(result, entry.Key);
            }
        }
        
        return result;
    }
}

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

Задача: 784. Letter Case Permutation
Сложность: medium

Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве.

Пример:

Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

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

1⃣Если следующий символ c является буквой, то мы удвоим все слова в нашем текущем ответе, и добавим lowercase(c) к каждому слову в первой половине, и uppercase(c) к каждому слову во второй половине.

2⃣Если c является цифрой, мы добавим его к каждому слову.

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

😎 Решение:

public class Solution {
    public IList<string> LetterCasePermutation(string S) {
        var ans = new List<List<char>> { new List<char>() };

        foreach (var c in S) {
            int n = ans.Count;
            if (char.IsLetter(c)) {
                for (int i = 0; i < n; i++) {
                    var current = new List<char>(ans[i]);
                    ans.Add(current);
                    ans[i].Add(char.ToLower(c));
                    ans[n + i].Add(char.ToUpper(c));
                }
            } else {
                for (int i = 0; i < n; i++) {
                    ans[i].Add(c);
                }
            }
        }

        return ans.Select(list => new string(list.ToArray())).ToList();
    }
}

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

Задача: 465. Optimal Account Balancing
Сложность: medium

Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.

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

Пример:

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2

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

1⃣Создать хеш-таблицу для хранения чистого баланса каждого человека.

2⃣Собрать все ненулевые чистые балансы в массив balance_list.

3⃣Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]:
Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1.
Если cur = n, вернуть 0.
В противном случае установить cost на большое значение, например, inf.
Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0,
Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur].
Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1).
Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат).
Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации.
Вернуть cost, когда итерация завершена. Вернуть dfs(0).

😎 Решение:

public class Solution {
    private List<int> creditList;
    
    public int MinTransfers(int[][] transactions) {
        var creditMap = new Dictionary<int, int>();
        foreach (var t in transactions) {
            if (!creditMap.ContainsKey(t[0])) creditMap[t[0]] = 0;
            if (!creditMap.ContainsKey(t[1])) creditMap[t[1]] = 0;
            creditMap[t[0]] += t[2];
            creditMap[t[1]] -= t[2];
        }
        
        creditList = new List<int>();
        foreach (var amount in creditMap.Values) {
            if (amount != 0) {
                creditList.Add(amount);
            }
        }
        
        int n = creditList.Count;
        return Dfs(0, n);
    }
    
    private int Dfs(int cur, int n) {
        while (cur < n && creditList[cur] == 0) {
            cur++;
        }
    
        if (cur == n) {
            return 0;
        }
        
        int cost = int.MaxValue;
        for (int nxt = cur + 1; nxt < n; nxt++) {
            if (creditList[nxt] * creditList[cur] < 0) {
                creditList[nxt] += creditList[cur];
                cost = Math.Min(cost, 1 + Dfs(cur + 1, n));
                creditList[nxt] -= creditList[cur];
            }
        }
        
        return cost;
    }
}

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

Задача: 839. Similar String Groups
Сложность: hard

Две строки, X и Y, считаются похожими, если либо они идентичны, либо мы можем сделать их эквивалентными, поменяв местами не более двух букв (в разных позициях) в строке X.

Например, "tars" и "rats" похожи (замена на позициях 0 и 2), и "rats" и "arts" похожи, но "star" не похожа на "tars", "rats" или "arts".
Эти строки образуют две связанные группы по сходству: {"tars", "rats", "arts"} и {"star"}. Обратите внимание, что "tars" и "arts" находятся в одной группе, хотя они не похожи друг на друга. Формально, каждая группа такова, что слово находится в группе, если и только если оно похоже хотя бы на одно другое слово в группе.

Вам дан список строк strs, где каждая строка в списке является анаграммой каждой другой строки в списке. Сколько групп существует?

Пример:

Input: strs = ["tars","rats","arts","star"]
Output: 2

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

1⃣Создайте переменную n, хранящую количество слов в strs, и создайте экземпляр UnionFind размера n.

2⃣Для любых двух слов на индексах i и j, которые ведут себя как узлы, проверьте, являются ли слова strs[i] и strs[j] похожими, и выполните операции find и union для объединения различных компонентов в один, если слова похожи.

3⃣Верните количество оставшихся групп.

😎 Решение:

public class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; ++i) {
            parent[i] = i;
        }
    }

    public int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }

    public void Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}

public class Solution {
    public bool IsSimilar(string a, string b) {
        int diff = 0;
        for (int i = 0; i < a.Length; ++i) {
            if (a[i] != b[i]) {
                diff++;
            }
        }
        return diff == 0 || diff == 2;
    }

    public int NumSimilarGroups(string[] strs) {
        int n = strs.Length;
        UnionFind dsu = new UnionFind(n);
        int count = n;

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (IsSimilar(strs[i], strs[j]) && dsu.Find(i) != dsu.Find(j)) {
                    count--;
                    dsu.Union(i, j);
                }
            }
        }

        return count;
    }
}

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

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

Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.

Пример:

Input: num1 = "11", num2 = "123"
Output: "134"

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

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

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

3⃣Верните третье максимальное число, если оно существует, иначе верните первое максимальное число.

😎 Решение:

public class Solution {
    public int ThirdMax(int[] nums) {
        int? first = null;
        int? second = null;
        int? third = null;
        
        foreach (int num in nums) {
            if (num == first || num == second || num == third) {
                continue;
            }
            if (first == null || num > first) {
                third = second;
                second = first;
                first = num;
            } else if (second == null || num > second) {
                third = second;
                second = num;
            } else if (third == null || num > third) {
                third = num;
            }
        }
        
        return third ?? first.Value;
    }
}

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

Задача: 38. Count and Say
Сложность: medium

Последовательность "считай и скажи" (countAndSay) строится рекурсивно:

- countAndSay(1) = "1"
- countAndSay(n) — это кодирование длин серий из countAndSay(n - 1).

Пример кодирования длин серий (RLE):
- "3322251" → "23321511"

Для заданного n верните n-й элемент последовательности.

Пример:

Input: n = 4  
Output: "1211"  

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

1⃣Начать с s = "1".

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

3⃣Вернуть итоговую строку.

😎 Решение:

public class Solution {
    public string CountAndSay(int n) {
        string s = "1";
        for (int i = 0; i < n - 1; i++) {
            StringBuilder current = new StringBuilder();
            for (int j = 0; j < s.Length; j++) {
                int count = 1;
                while (j < s.Length - 1 && s[j] == s[j + 1]) {
                    j++;
                    count++;
                }
                current.Append(count).Append(s[j]);
            }
            s = current.ToString();
        }
        return s;
    }
}

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

Задача: 899. Orderly Queue
Сложность: hard

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

Пример:

Input: s = "cba", k = 1
Output: "acb"

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

1⃣Если k равно 1, найти лексикографически наименьшую строку путем вращения строки и поиска минимального варианта.

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

3⃣Вернуть результат.

😎 Решение:

using System;
using System.Linq;

public class Solution {
    public string OrderlyQueue(string s, int k) {
        if (k == 1) {
            string minString = s;
            for (int i = 1; i < s.Length; i++) {
                string rotated = s.Substring(i) + s.Substring(0, i);
                if (rotated.CompareTo(minString) < 0) {
                    minString = rotated;
                }
            }
            return minString;
        } else {
            return new string(s.OrderBy(c => c).ToArray());
        }
    }
}

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

Задача: 820. Short Encoding of Words
Сложность: medium

Допустимым кодированием массива слов является любая опорная строка s и массив индексов indices, такие что:

words.length == indices.length
Опорная строка s заканчивается символом '#'.
Для каждого индекса indices[i], подстрока строки s, начинающаяся с indices[i] и заканчивающаяся (но не включительно) следующим символом '#', равна words[i].
Дан массив слов, верните длину самой короткой возможной опорной строки s для любого допустимого кодирования слов.

Пример:

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"

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

1⃣Поскольку слово имеет не более 6 собственных суффиксов (так как words[i].length <= 7), давайте итерироваться по всем из них. Для каждого собственного суффикса мы попытаемся удалить его из нашего списка слов. Для эффективности сделаем words множеством.

2⃣Затем создадим список оставшихся слов и сформируем опорную строку, объединяя каждое слово с символом '#'.

3⃣В конце вернем длину полученной опорной строки.

😎 Решение:

public class Solution {
    public int MinimumLengthEncoding(string[] words) {
        var good = new HashSet<string>(words);
        foreach (var word in words) {
            for (int k = 1; k < word.Length; k++) {
                good.Remove(word.Substring(k));
            }
        }
        int length = 0;
        foreach (var word in good) {
            length += word.Length + 1;
        }
        return length;
    }
}

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

Задача: 34. Find First and Last Position of Element in Sorted Array
Сложность: medium

Дан отсортированный массив nums. Нужно найти начальную и конечную позицию элемента target. Если target отсутствует, вернуть [-1, -1]. Алгоритм должен работать за O(log n).

Пример:

Input: nums = [5,7,7,8,8,10], target = 8  
Output: [3,4]  

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

1⃣Использовать бинарный поиск (FindBound) для нахождения первой позиции target.

2⃣Если target не найден, вернуть [-1, -1].

3⃣Использовать FindBound снова для нахождения последней позиции target.

😎 Решение:

public class Solution {
    public int[] SearchRange(int[] nums, int target) {
        int first = FindBound(nums, target, true);
        if (first == -1) return new int[] { -1, -1 };
        
        int last = FindBound(nums, target, false);
        return new int[] { first, last };
    }

    private int FindBound(int[] nums, int target, bool isFirst) {
        int left = 0, right = nums.Length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                if (isFirst) {
                    if (mid == left || nums[mid - 1] != target) return mid;
                    right = mid - 1;
                } else {
                    if (mid == right || nums[mid + 1] != target) return mid;
                    left = mid + 1;
                }
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

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

Задача: 1485. Clone Binary Tree With Random Pointer
Сложность: medium

Дано бинарное дерево, такое что каждый узел содержит дополнительный случайный указатель, который может указывать на любой узел в дереве или быть null.
Верните глубокую копию дерева.

Дерево представлено в том же формате ввода/вывода, что и обычные бинарные деревья, где каждый узел представлен в виде пары [val, random_index], где:
- val: целое число, представляющее Node.val
- random_index: индекс узла (во входных данных), на который указывает случайный указатель, или null, если он не указывает ни на один узел.

Вам будет дано дерево в классе Node, и вы должны вернуть клонированное дерево в классе NodeCopy. Класс NodeCopy является клоном класса Node с такими же атрибутами и конструкторами.

Пример:

Input: root = [[1,null],null,[4,3],[7,0]]
Output: [[1,null],null,[4,3],[7,0]]
Explanation: The original binary tree is [1,null,4,7].
The random pointer of node one is null, so it is represented as [1, null].
The random pointer of node 4 is node 7, so it is represented as [4, 3] where 3 is the index of node 7 in the array representing the tree.
The random pointer of node 7 is node 1, so it is represented as [7, 0] where 0 is the index of node 1 in the array representing the tree.

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

1⃣Глубокое копирование дерева:
Инициализируйте хэш-таблицу newOldPairs, которая сопоставляет узлы старого дерева с узлами нового дерева.
Создайте функцию deepCopy(root), которая принимает корень данного дерева и возвращает корень нового дерева. Эта функция создаёт новый узел с теми же значениями, что и корневой узел, и рекурсивно копирует левое и правое поддеревья. Затем она сохраняет пару старого и нового узлов в хэш-таблицу и возвращает новый корень.

2⃣Сопоставление случайных указателей:
Создайте функцию mapRandomPointers(oldNode), которая принимает корень старого дерева и рекурсивно сопоставляет случайные указатели нового дерева с соответствующими узлами старого дерева, используя хэш-таблицу newOldPairs.

3⃣Возвращение клонированного дерева:
Создайте глубокую копию дерева, используя функцию deepCopy(root), и сопоставьте все случайные указатели нового дерева с помощью функции mapRandomPointers(root). Верните новый корень.

😎 Решение:

public class Node {
    public int val;
    public Node left;
    public Node right;
    public Node random;

    public Node(int _val) {
        val = _val;
        left = null;
        right = null;
        random = null;
    }
}

public class NodeCopy {
    public int val;
    public NodeCopy left;
    public NodeCopy right;
    public NodeCopy random;

    public NodeCopy(int _val) {
        val = _val;
        left = null;
        right = null;
        random = null;
    }
}

public class Solution {
    private Dictionary<Node, NodeCopy> newOldPairs = new Dictionary<Node, NodeCopy>();

    private NodeCopy DeepCopy(Node root) {
        if (root == null) return null;
        NodeCopy newRoot = new NodeCopy(root.val);
        newRoot.left = DeepCopy(root.left);
        newRoot.right = DeepCopy(root.right);
        newOldPairs[root] = newRoot;
        return newRoot;
    }

    private void MapRandomPointers(Node oldNode) {
        if (oldNode == null) return;
        if (newOldPairs.TryGetValue(oldNode, out NodeCopy newNode)) {
            newNode.random = newOldPairs.GetValueOrDefault(oldNode.random);
            MapRandomPointers(oldNode.left);
            MapRandomPointers(oldNode.right);
        }
    }

    public NodeCopy CopyRandomBinaryTree(Node root) {
        NodeCopy newRoot = DeepCopy(root);
        MapRandomPointers(root);
        return newRoot;
    }
}

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

Задача: 968. Binary Tree Cameras
Сложность: hard

Вам дан корень бинарного дерева. Мы устанавливаем камеры на узлы дерева, где каждая камера на узле может наблюдать за своим родителем, собой и своими непосредственными детьми.

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

Пример:

Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

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

1⃣Рекурсивное решение (solve):
Для каждого узла определите три состояния:
- [State 0] Строгое поддерево: все узлы ниже этого узла покрыты, но не сам узел.
- [State 1] Нормальное поддерево: все узлы ниже и включая этот узел покрыты, но на этом узле нет камеры.
- [State 2] Установленная камера: все узлы ниже и включая этот узел покрыты, и на этом узле установлена камера.
Рассчитайте эти состояния для левого и правого поддеревьев.

2⃣Рассчёт состояний:
Чтобы покрыть строгое поддерево, дети этого узла должны находиться в состоянии 1.
Чтобы покрыть нормальное поддерево без установки камеры на этом узле, дети этого узла должны находиться в состояниях 1 или 2, и по крайней мере один из этих детей должен быть в состоянии 2.
Чтобы покрыть поддерево при установке камеры на этом узле, дети могут находиться в любом состоянии.

3⃣Минимальное количество камер:
Запустите функцию solve на корневом узле и верните минимальное значение между состояниями 1 и 2.

😎 Решение:

public class Solution {
    public int MinCameraCover(TreeNode root) {
        var ans = Solve(root);
        return Math.Min(ans[1], ans[2]);
    }

    private int[] Solve(TreeNode node) {
        if (node == null) {
            return new int[] { 0, 0, 99999 };
        }

        var L = Solve(node.left);
        var R = Solve(node.right);
        int mL12 = Math.Min(L[1], L[2]);
        int mR12 = Math.Min(R[1], R[2]);

        int d0 = L[1] + R[1];
        int d1 = Math.Min(L[2] + mR12, R[2] + mL12);
        int d2 = 1 + Math.Min(L[0], mL12) + Math.Min(R[0], mR12);
        return new int[] { d0, d1, d2 };
    }
}

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

Задача: 295. Find Median from Data Stream
Сложность: hard

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

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

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

MedianFinder() инициализирует объект MedianFinder.
void addNum(int num) добавляет целое число num из потока данных в структуру данных.
double findMedian() возвращает медиану всех элементов на данный момент. Ответы с точностью до 10^-5 от фактического ответа будут приниматься.

Пример:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

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

1⃣Храните числа в контейнере с возможностью изменения размера:
Создайте массив для хранения чисел.

2⃣Добавление нового числа:
Добавьте новое число в массив.

3⃣Вычисление и вывод медианы:
Отсортируйте массив.
Если размер массива нечетный, верните среднее значение массива.
Если размер массива четный, верните среднее арифметическое двух средних значений массива.

😎 Решение:

using System;
using System.Collections.Generic;

public class MedianFinder {
    private List<int> numbers;

    public MedianFinder() {
        numbers = new List<int>();
    }

    public void AddNum(int num) {
        numbers.Add(num);
    }

    public double FindMedian() {
        numbers.Sort();
        int n = numbers.Count;
        if (n % 2 == 0) {
            return (numbers[n / 2 - 1] + numbers[n / 2]) / 2.0;
        } else {
            return numbers[n / 2];
        }
    }
}

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

Задача: 606. Construct String from Binary Tree
Сложность: Medium

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

Представление узлов: Каждый узел в дереве должен быть представлен его целочисленным значением.

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

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

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

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

Пример:

Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".

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

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

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

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

😎 Решение:

public class Solution {
    public string Tree2str(TreeNode t) {
        var res = new StringBuilder();
        Dfs(t, res);
        return res.ToString();
    }

    private void Dfs(TreeNode t, StringBuilder res) {
        if (t == null) return;
        res.Append(t.val);
        if (t.left == null && t.right == null) return;
        res.Append('(');
        Dfs(t.left, res);
        res.Append(')');
        if (t.right != null) {
            res.Append('(');
            Dfs(t.right, res);
            res.Append(')');
        }
    }
}

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

Задача: 762. Prime Number of Set Bits in Binary Representation
Сложность: hard

Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита.

Пример:

Input: left = 10, right = 15
Output: 5

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

1⃣Создайте функцию для подсчета количества единиц в двоичном представлении числа.

2⃣Создайте функцию для проверки, является ли число простым.

3⃣Пройдите через все числа в диапазоне [left, right] и подсчитайте числа, у которых количество битов в двоичном представлении является простым числом.

😎 Решение:

public class Solution {
    public int CountPrimeSetBits(int left, int right) {
        int count = 0;
        for (int num = left; num <= right; num++) {
            if (IsPrime(BitCount(num))) {
                count++;
            }
        }
        return count;
    }
    
    private int BitCount(int x) {
        int count = 0;
        while (x > 0) {
            count += x & 1;
            x >>= 1;
        }
        return count;
    }
    
    private bool IsPrime(int x) {
        if (x < 2) return false;
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) return false;
        }
        return true;
    }
}

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

Задача: 1231. Divide Chocolate
Сложность: hard

У вас есть одна шоколадка, состоящая из нескольких кусочков. Каждый кусочек имеет свою сладость, заданную массивом сладости. Вы хотите поделиться шоколадом со своими k друзьями, поэтому начинаете разрезать шоколадку на k + 1 кусочков с помощью k разрезов, каждый кусочек состоит из нескольких последовательных кусочков. Будучи щедрым, вы съедите кусочек с минимальной общей сладостью, а остальные кусочки отдадите своим друзьям. Найдите максимальную общую сладость кусочка, который вы можете получить, оптимально разрезав шоколадку.

Пример:

Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6

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

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

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

3⃣Проверка делимости:
Для каждой попытки значения сладости в двоичном поиске проверим, можем ли мы разрезать шоколад так, чтобы каждая из k+1 частей имела сладость не меньше текущего значения.

😎 Решение:

public class Solution {
    public int MaximizeSweetness(int[] sweetness, int k) {
        bool CanDivide(int minSweetness) {
            int currentSum = 0, cuts = 0;
            foreach (var sweet in sweetness) {
                currentSum += sweet;
                if (currentSum >= minSweetness) {
                    cuts++;
                    currentSum = 0;
                }
            }
            return cuts >= k + 1;
        }
        
        int left = sweetness.Min();
        int right = sweetness.Sum() / (k + 1);
        
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (CanDivide(mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
}

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

Задача: 685. Redundant Connection II
Сложность: hard

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

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

Результирующий граф представлен в виде двумерного массива ребер. Каждый элемент массива edges — это пара [ui, vi], представляющая направленное ребро, соединяющее узлы ui и vi, где ui является родителем ребенка vi.

Верните ребро, которое можно удалить, чтобы результирующий граф стал корневым деревом с n узлами. Если существует несколько ответов, верните ответ, который встречается последним в данном двумерном массиве.

Пример:

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

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

1⃣Сначала создаем базовый граф, отслеживая ребра, идущие от узлов с несколькими родителями. В итоге у нас будет либо 2, либо 0 кандидатов на удаление ребра.

2⃣Если кандидатов нет, то каждый узел имеет одного родителя, как в случае 1->2->3->4->1->5. От любого узла идем к его родителю, пока не посетим узел повторно — тогда мы окажемся внутри цикла, и любые последующие посещенные узлы будут частью этого цикла. В этом случае удаляем последнее ребро, входящее в цикл.

3⃣Если есть кандидаты, проверяем, является ли граф, созданный из родителей, корневым деревом. Идем от любого узла к его родителю, пока это возможно, затем выполняем обход в глубину (DFS) от этого корня. Если посещаем каждый узел, удаление последнего из двух кандидатов приемлемо. В противном случае удаляем первое из двух ребер-кандидатов.

😎 Решение:

public class Solution {
    public int[] FindRedundantDirectedConnection(int[][] edges) {
        int N = edges.Length;
        var parent = new Dictionary<int, int>();
        var candidates = new List<int[]>();
        foreach (var edge in edges) {
            if (parent.ContainsKey(edge[1])) {
                candidates.Add(new int[] { parent[edge[1]], edge[1] });
                candidates.Add(edge);
            } else {
                parent[edge[1]] = edge[0];
            }
        }

        int root = Orbit(1, parent).Node;
        if (candidates.Count == 0) {
            var cycle = Orbit(root, parent).Seen;
            foreach (var edge in edges) {
                if (cycle.Contains(edge[0]) && cycle.Contains(edge[1])) {
                    return edge;
                }
            }
        }

        var children = parent.GroupBy(kvp => kvp.Value).ToDictionary(g => g.Key, g => g.Select(kvp => kvp.Key).ToList());

        var seen = new bool[N + 1];
        var stack = new Stack<int>();
        stack.Push(root);
        while (stack.Count > 0) {
            int node = stack.Pop();
            if (!seen[node]) {
                seen[node] = true;
                if (children.ContainsKey(node)) {
                    foreach (int c in children[node]) stack.Push(c);
                }
            }
        }
        return seen.Any(b => !b) ? candidates[0] : candidates[1];
    }

    public class OrbitResult {
        public int Node { get; }
        public HashSet<int> Seen { get; }
        public OrbitResult(int node, HashSet<int> seen) {
            Node = node;
            Seen = seen;
        }
    }

    public OrbitResult Orbit(int node, Dictionary<int, int> parent) {
        var seen = new HashSet<int>();
        while (parent.ContainsKey(node) && !seen.Contains(node)) {
            seen.Add(node);
            node = parent[node];
        }
        return new OrbitResult(node, seen);
    }
}

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

Задача: 1253. Reconstruct a 2-Row Binary Matrix
Сложность: medium

Даны следующие сведения о матрице с n столбцами и 2 строками: Матрица является двоичной, то есть каждый элемент матрицы может быть 0 или 1. Сумма элементов 0-й (верхней) строки задана как upper. Сумма элементов 1-й (нижней) строки задана как lower.
Сумма элементов i-го столбца (индексированного 0) - colsum[i], где colsum - целочисленный массив длины n. Ваша задача - восстановить матрицу с upper, lower и colsum. Вернуть ее в виде двумерного целочисленного массива. Если существует более одного правильного решения, будет принято любое из них. Если правильного решения не существует, верните пустой двумерный массив.

Пример:

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]

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

1⃣Инициализируйте две строки матрицы длины n с нулями.

2⃣Пройдите по массиву colsum и распределите значения 2 по обеим строкам, уменьшая upper и lower.
Пройдите по массиву colsum и распределите значения 1 по строкам, уменьшая соответствующие upper или lower.

3⃣Проверьте, что остатки upper и lower равны нулю.
Если все шаги выполнены успешно, верните восстановленную матрицу, иначе верните пустую матрицу.

😎 Решение:

public class Solution {
    public IList<IList<int>> ReconstructMatrix(int upper, int lower, int[] colsum) {
        int n = colsum.Length;
        int[] top = new int[n];
        int[] bottom = new int[n];

        for (int i = 0; i < n; i++) {
            if (colsum[i] == 2) {
                if (upper > 0 && lower > 0) {
                    top[i] = 1;
                    bottom[i] = 1;
                    upper--;
                    lower--;
                } else {
                    return new List<IList<int>>();
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (colsum[i] == 1) {
                if (upper > lower) {
                    if (upper > 0) {
                        top[i] = 1;
                        upper--;
                    } else {
                        return new List<IList<int>>();
                    }
                } else {
                    if (lower > 0) {
                        bottom[i] = 1;
                        lower--;
                    } else {
                        return new List<IList<int>>();
                    }
                }
            }
        }

        if (upper == 0 && lower == 0) {
            return new List<IList<int>> { top, bottom };
        } else {
            return new List<IList<int>>();
        }
    }
}

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

Задача: 911. Online Election
Сложность: medium

Вам даны два целочисленных массива persons и times. На выборах i-й голос был отдан за person[i] в момент времени times[i]. Для каждого запроса в момент времени t найдите человека, который лидировал на выборах в момент времени t. Голоса, отданные в момент времени t, будут учитываться в нашем запросе. В случае равенства голосов побеждает тот, кто проголосовал последним (среди равных кандидатов). Реализация класса TopVotedCandidate: TopVotedCandidate(int[] persons, int[] times) Инициализирует объект с массивами persons и times. int q(int t) Возвращает номер человека, который лидировал на выборах в момент времени t в соответствии с указанными правилами.

Пример:

Input
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
Output
[null, 0, 1, 1, 0, 0, 1]

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

1⃣Использовать два массива для хранения лиц и времени голосования.

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

3⃣На каждый запрос времени t, найти наибольший индекс времени, который не превышает t, и вернуть лидера на этот момент времени.

😎 Решение:

using System;
using System.Collections.Generic;

public class TopVotedCandidate {
    private int[] times;
    private List<int> leaders;

    public TopVotedCandidate(int[] persons, int[] times) {
        this.times = times;
        this.leaders = new List<int>();
        Dictionary<int, int> counts = new Dictionary<int, int>();
        int leader = -1;

        foreach (int person in persons) {
            if (!counts.ContainsKey(person)) {
                counts[person] = 0;
            }
            counts[person]++;
            if (!counts.ContainsKey(leader) || counts[person] >= counts[leader]) {
                leader = person;
            }
            leaders.Add(leader);
        }
    }

    public int Q(int t) {
        int left = 0;
        int right = times.Length - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (times[mid] <= t) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return leaders[left];
    }
}

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

Задача: 674. Longest Continuous Increasing Subsequence
Сложность: easy

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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