Задача: 663. Equal Tree Partition
Сложность: medium

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

Пример:

Input: root = [5,10,10,null,null,2,3]
Output: true

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

1⃣Вычисление общей суммы:
Напишите функцию для вычисления общей суммы всех узлов дерева.

2⃣Проверка возможности разделения:
Напишите функцию, чтобы рекурсивно проверить, может ли поддерево быть равно половине общей суммы. Если такое поддерево найдено, значит дерево можно разделить на две части с равными суммами.

3⃣Валидация и возврат результата:
Проверьте, что общая сумма четная (так как только в этом случае возможно её разделение на две равные части), и используйте функцию проверки поддерева, чтобы определить, можно ли разделить дерево на две части с равными суммами.

😎 Решение:

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

public class Solution {
    public bool CheckEqualTree(TreeNode root) {
        int totalSum = SumTree(root);
        if (totalSum % 2 != 0) return false;
        int target = totalSum / 2;
        return CheckSubtreeSum(root, target, root);
    }

    private int SumTree(TreeNode node) {
        if (node == null) return 0;
        return node.val + SumTree(node.left) + SumTree(node.right);
    }

    private bool CheckSubtreeSum(TreeNode node, int target, TreeNode root) {
        if (node == null) return false;
        if (node != root && SumTree(node) == target) {
            return true;
        }
        return CheckSubtreeSum(node.left, target, root) || CheckSubtreeSum(node.right, target, root);
    }
}

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

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

Вам дана двоичная матричная сетка m x n. Остров - это группа 1 (представляющая сушу), соединенных в четырех направлениях (горизонтальном или вертикальном). Можно предположить, что все четыре края сетки окружены водой. Остров считается одинаковым с другим, если они имеют одинаковую форму, или имеют одинаковую форму после поворота (только на 90, 180 или 270 градусов) или отражения (влево/вправо или вверх/вниз). Верните количество разных островов.

Пример:

Input: grid = [[1,1,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,1,1]]
Output: 1

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

1⃣Пройдите по каждому элементу матрицы, если найдена земля (1), выполните DFS для обнаружения всех связанных с этим островом земель и сохраните форму острова.

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

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

😎 Решение:

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

public class Solution {
    public int NumDistinctIslands2(int[][] grid) {
        var uniqueIslands = new HashSet<string>();

        for (int i = 0; i < grid.Length; i++) {
            for (int j = 0; j < grid[0].Length; j++) {
                if (grid[i][j] == 1) {
                    var shape = new List<(int, int)>();
                    Dfs(grid, i, j, i, j, shape);
                    uniqueIslands.Add(Normalize(shape));
                }
            }
        }

        return uniqueIslands.Count;
    }

    private void Dfs(int[][] grid, int i, int j, int baseI, int baseJ, List<(int, int)> shape) {
        if (i < 0 || i >= grid.Length || j < 0 || j >= grid[0].Length || grid[i][j] == 0) {
            return;
        }
        grid[i][j] = 0;
        shape.Add((i - baseI, j - baseJ));
        Dfs(grid, i + 1, j, baseI, baseJ, shape);
        Dfs(grid, i - 1, j, baseI, baseJ, shape);
        Dfs(grid, i, j + 1, baseI, baseJ, shape);
        Dfs(grid, i, j - 1, baseI, baseJ, shape);
    }

    private string Normalize(List<(int, int)> shape) {
        var shapes = new List<List<(int, int)>>();
        for (int i = 0; i < 8; i++) {
            shapes.Add(new List<(int, int)>());
        }

        foreach (var (x, y) in shape) {
            shapes[0].Add((x, y));
            shapes[1].Add((x, -y));
            shapes[2].Add((-x, y));
            shapes[3].Add((-x, -y));
            shapes[4].Add((y, x));
            shapes[5].Add((y, -x));
            shapes[6].Add((-y, x));
            shapes[7].Add((-y, -x));
        }

        foreach (var s in shapes) {
            s.Sort();
        }

        string minShape = string.Join(";", shapes[0].Select(p => $"{p.Item1},{p.Item2}"));
        foreach (var s in shapes) {
            string sStr = string.Join(";", s.Select(p => $"{p.Item1},{p.Item2}"));
            if (string.Compare(sStr, minShape, StringComparison.Ordinal) < 0) {
                minShape = sStr;
            }
        }

        return minShape;
    }
}

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

Задача: 681. Next Closest Time
Сложность: medium

Дано время, представленное в формате "ЧЧ:ММ". Сформируйте ближайшее следующее время, используя текущие цифры. Количество раз, которое можно использовать цифру, не ограничено.

Можно предположить, что заданная строка всегда корректна. Например, "01:34", "12:09" являются корректными. "1:34", "12:9" являются некорректными.

Пример:

Input: time = "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.
It is not 19:33, because this occurs 23 hours and 59 minutes later.

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

1⃣Симулируйте ход часов, увеличивая время на одну минуту. Каждый раз, когда время увеличивается, если все цифры допустимы, верните текущее время.

2⃣Представьте время как целое число t в диапазоне 0 <= t < 24 * 60. Тогда часы равны t / 60, минуты равны t % 60.

3⃣Найдите каждую цифру часов и минут: часы / 10, часы % 10 и т.д.

😎 Решение:

public class Solution {
    public string NextClosestTime(string time) {
        int cur = 60 * int.Parse(time.Substring(0, 2));
        cur += int.Parse(time.Substring(3));
        HashSet<int> allowed = new HashSet<int>();
        foreach (char c in time) if (c != ':') {
            allowed.Add(c - '0');
        }

        while (true) {
            cur = (cur + 1) % (24 * 60);
            int[] digits = new int[] { cur / 60 / 10, cur / 60 % 10, cur % 60 / 10, cur % 60 % 10 };
            bool isValid = true;
            foreach (int d in digits) {
                if (!allowed.Contains(d)) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) {
                return string.Format("{0:D2}:{1:D2}", cur / 60, cur % 60);
            }
        }
    }
}

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

Задача: 1214. Two Sum BSTs
Сложность: medium

Даны корни двух бинарных деревьев поиска, root1 и root2, верните true, если и только если существует узел в первом дереве и узел во втором дереве, значения которых в сумме равны заданному целому числу target.

Пример:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

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

1⃣Создайте два пустых множества node_set1 и node_set2. Выполните обход дерева root1, добавляя значения каждого узла в node_set1, и выполните обход дерева root2, добавляя значения каждого узла в node_set2.

2⃣Итерация по элементам в node_set1: для каждого элемента value1 проверяйте, находится ли target - value1 в node_set2.

3⃣Если target - value1 находится в node_set2, верните true. Если после завершения итерации не найдено ни одной подходящей пары, верните false.

😎 Решение:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    private void Dfs(TreeNode node, HashSet<int> nodeSet) {
        if (node == null) return;
        Dfs(node.left, nodeSet);
        nodeSet.Add(node.val);
        Dfs(node.right, nodeSet);
    }

    public bool TwoSumBSTs(TreeNode root1, TreeNode root2, int target) {
        HashSet<int> nodeSet1 = new HashSet<int>();
        HashSet<int> nodeSet2 = new HashSet<int>();
        Dfs(root1, nodeSet1);
        Dfs(root2, nodeSet2);
        
        foreach (int value1 in nodeSet1) {
            if (nodeSet2.Contains(target - value1)) {
                return true;
            }
        }
        
        return false;
    }
}

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

Задача: 1196. How Many Apples Can You Put into the Basket
Сложность: easy

У вас есть несколько яблок и корзина, которая может выдержать до 5000 единиц веса.

Дан целочисленный массив weight, где weight[i] — это вес i-го яблока. Верните максимальное количество яблок, которые можно положить в корзину.

Пример:

Input: weight = [100,200,150,1000]
Output: 4
Explanation: All 4 apples can be carried by the basket since their sum of weights is 1450.

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

1⃣Преобразование массива в мин-кучу:
Преобразуйте массив weight в мин-кучу, чтобы получить минимальные элементы первым.

2⃣Инициализация переменных:
Инициализируйте переменные apples для подсчета количества яблок и units для записи текущего веса корзины.

3⃣ Добавление яблок в корзину:
Пока текущий вес корзины меньше 5000 единиц и в куче остаются элементы:
Увеличивайте apples на 1.
Увеличивайте units на значение, извлеченное из кучи.

😎 Решение:

public class Solution {
    public int MaxNumberOfApples(int[] weight) {
        var heap = new SortedSet<int>(weight);
        int apples = 0, units = 0;

        foreach (var w in heap) {
            if (units + w <= 5000) {
                units += w;
                apples++;
            } else {
                break;
            }
        }
        return apples;
    }
}

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

Задача: 1503. Last Moment Before All Ants Fall Out of a Plank
Сложность: medium

У нас есть деревянная доска длиной n единиц. Некоторые муравьи ходят по доске, каждый муравей движется со скоростью 1 единица в секунду. Некоторые муравьи движутся влево, другие движутся вправо.

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

Когда муравей достигает одного из концов доски в момент времени t, он сразу же падает с доски.

Дано целое число n и два целых массива left и right, обозначающие позиции муравьев, движущихся влево и вправо соответственно. Верните момент, когда последний(е) муравей(и) падает(ют) с доски.

Пример:

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).

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

1⃣Инициализируйте переменную ans значением 0.

2⃣Итерация по массиву left и обновление ans значением num, если оно больше текущего значения ans.

3⃣Итерация по массиву right и обновление ans значением n - num, если оно больше текущего значения ans. Верните значение ans.

😎 Решение:

public class Solution {
    public int GetLastMoment(int n, int[] left, int[] right) {
        int ans = 0;
        foreach (int num in left) {
            ans = Math.Max(ans, num);
        }
        foreach (int num in right) {
            ans = Math.Max(ans, n - num);
        }
        return ans;
    }
}

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

Задача: 1295. Find Numbers with Even Number of Digits
Сложность: easy

Дан массив чисел nums. Верните количество чисел в массиве, которые содержат четное количество цифр.

Пример:

Input: nums = [12,345,2,6,7896]
Output: 2
Explanation: 
12 contains 2 digits (even number of digits). 
345 contains 3 digits (odd number of digits). 
2 contains 1 digit (odd number of digits). 
6 contains 1 digit (odd number of digits). 
7896 contains 4 digits (even number of digits). 
Therefore only 12 and 7896 contain an even number of digits.

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

1⃣Определите вспомогательную функцию hasEvenDigits, которая принимает num в качестве входных данных и возвращает true, если количество цифр четное, иначе возвращает false.

2⃣Внутри функции hasEvenDigits. Инициализируйте переменную digitCount значением 0. Пока num не равно нулю: Увеличивайте digitCount на 1. Делите num на 10. Возвращайте digitCount & 1 == 0.

3⃣В функции findNumbers. Инициализируйте переменную evenDigitCount значением 0. Для каждого числа num в массиве nums, проверяйте, возвращает ли hasEvenDigits(num) значение true. Если да, увеличивайте evenDigitCount на 1. Возвращайте evenDigitCount.

😎 Решение:

public class Solution {
    private bool HasEvenDigits(int num) {
        int digitCount = 0;
        while (num > 0) {
            digitCount++;
            num /= 10;
        }
        return (digitCount & 1) == 0;
    }

    public int FindNumbers(int[] nums) {
        int evenDigitCount = 0;
        foreach (int num in nums) {
            if (HasEvenDigits(num)) {
                evenDigitCount++;
            }
        }
        return evenDigitCount;
    }
}

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

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

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

Мы определяем массив как неубывающий, если для каждого i (индексация с 0), такого что 0 <= i <= n - 2, выполняется условие nums[i] <= nums[i + 1].

Пример:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

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

1⃣Инициализация переменных:
Завести переменную count для подсчета числа изменений.
Проверить последовательность чисел в массиве nums.

2⃣Проверка условий:
Если nums[i] > nums[i + 1], то увеличиваем count.
Если count превышает 1, возвращаем false, так как больше одного изменения недопустимо.
Если nums[i - 1] > nums[i + 1] и nums[i] > nums[i + 2], то возвращаем false.

3⃣Возврат результата:
Если количество изменений не превышает 1, вернуть true.

😎 Решение:

public class Solution {
    public bool CheckPossibility(int[] nums) {
        int count = 0;
        
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] < nums[i - 1]) {
                if (count > 0) {
                    return false;
                }
                count++;
                if (i == 1 || nums[i] >= nums[i - 2]) {
                    nums[i - 1] = nums[i];
                } else {
                    nums[i] = nums[i - 1];
                }
            }
        }
        
        return true;
    }
}

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

Задача: 841. Keys and Rooms
Сложность: medium

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

Дан массив rooms, где rooms[i] — это набор ключей, которые вы можете получить, если посетите комнату i. Верните true, если вы можете посетить все комнаты, или false в противном случае.

Пример:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

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

1⃣Создайте массив seen для отслеживания посещенных комнат и стек stack для ключей, которые нужно использовать.

2⃣Поместите ключ от комнаты 0 в стек и отметьте комнату 0 как посещенную.

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

😎 Решение:

public class Solution {
    public bool CanVisitAllRooms(IList<IList<int>> rooms) {
        bool[] seen = new bool[rooms.Count];
        seen[0] = true;
        Stack<int> stack = new Stack<int>();
        stack.Push(0);

        while (stack.Count > 0) {
            int node = stack.Pop();
            foreach (int nei in rooms[node]) {
                if (!seen[nei]) {
                    seen[nei] = true;
                    stack.Push(nei);
                }
            }
        }

        foreach (bool v in seen) {
            if (!v) return false;
        }
        return true;
    }
}

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

Задача: 202. Happy Number
Сложность: easy

Напишите алгоритм для определения, является ли число n счастливым.

Счастливое число определяется следующим процессом:

Начиная с любого положительного целого числа, замените число суммой квадратов его цифр.
Повторяйте процесс, пока число не станет равным 1 (где оно и останется), или пока оно бесконечно не будет циклически повторяться в цикле, который не включает 1.
Те числа, для которых этот процесс завершается 1, являются счастливыми.
Верните true, если n является счастливым числом, и false, если нет.

Пример:

Input: n = 2
Output: false

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

1⃣Для заданного числа n определите следующее число в последовательности: используйте операторы деления и взятия остатка для последовательного извлечения цифр из числа, пока не закончатся все цифры. Каждую извлеченную цифру возводите в квадрат и суммируйте полученные значения. Это техника "последовательного извлечения цифр" является полезным инструментом для решения множества задач.

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

3⃣Если числа нет в HashSet, добавьте его туда. Если число уже есть в HashSet, это означает, что вы находитесь в цикле, и следует вернуть false. HashSet используется вместо Vector, List или Array, потому что проверка присутствия числа в HashSet занимает время O(1), тогда как в других структурах данных это займет время O(n). Правильный выбор структур данных является ключевым элементом решения подобных задач.

😎 Решение:

using System.Collections.Generic;

public class Solution {
    private int GetNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int digit = n % 10;
            n /= 10;
            totalSum += digit * digit;
        }
        return totalSum;
    }

    public bool IsHappy(int n) {
        HashSet<int> seen = new HashSet<int>();
        while (n != 1 && !seen.Contains(n)) {
            seen.Add(n);
            n = GetNext(n);
        }
        return n == 1;
    }
}

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

Задача: 965. Univalued Binary Tree
Сложность: easy

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

Дан корень бинарного дерева, верните true, если данное дерево является одноценным, или false в противном случае.

Пример:

Input: root = [1,1,1,1,1,null,1]
Output: true

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

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

2⃣Проверьте, что все значения в списке одинаковы.

3⃣Если все значения одинаковы, верните true, иначе верните false.

😎 Решение:

public class Solution {
    private List<int> vals;

    public bool IsUnivalTree(TreeNode root) {
        vals = new List<int>();
        Dfs(root);
        foreach (int v in vals) {
            if (v != vals[0]) {
                return false;
            }
        }
        return true;
    }

    private void Dfs(TreeNode node) {
        if (node != null) {
            vals.Add(node.val);
            Dfs(node.left);
            Dfs(node.right);
        }
    }
}

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

Задача: 919. Complete Binary Tree Inserter
Сложность: medium

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

Реализуйте класс CBTInserter: CBTInserter(TreeNode root) Инициализирует структуру данных корнем полного бинарного дерева. int insert(int v) Вставляет TreeNode в дерево со значением Node.val == val так, что дерево остается полным, и возвращает значение родителя вставленного TreeNode. TreeNode get_root() Возвращает корневой узел дерева.

Пример:

Input
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
Output
[null, 1, 2, [1, 2, 3, 4]]

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

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

2⃣Вставка: Добавление нового узла в первое доступное место слева направо.

3⃣Возвращение корня: Просто возвращает корневой узел.

😎 Решение:

using System.Collections.Generic;

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

public class CBTInserter {
    private TreeNode root;
    private Queue<TreeNode> deque;

    public CBTInserter(TreeNode root) {
        this.root = root;
        this.deque = new Queue<TreeNode>();
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        while (queue.Count > 0) {
            TreeNode node = queue.Dequeue();
            if (node.left == null || node.right == null) {
                deque.Enqueue(node);
            }
            if (node.left != null) {
                queue.Enqueue(node.left);
            }
            if (node.right != null) {
                queue.Enqueue(node.right);
            }
        }
    }

    public int Insert(int v) {
        TreeNode node = deque.Peek();
        TreeNode newNode = new TreeNode(v);
        if (node.left == null) {
            node.left = newNode;
        } else {
            node.right = newNode;
            deque.Dequeue();
        }
        deque.Enqueue(newNode);
        return node.val;
    }

    public TreeNode Get_root() {
        return root;
    }
}

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

Задача: 1329. Sort the Matrix Diagonally
Сложность: medium

Диагональ матрицы — это диагональная линия ячеек, начинающаяся с какой-либо ячейки в самой верхней строке или в самом левом столбце и идущая в направлении вниз-вправо до конца матрицы. Например, диагональ матрицы, начинающаяся с mat[2][0], где mat — это матрица размером 6 x 3, включает ячейки mat[2][0], mat[3][1] и mat[4][2].

Дана матрица mat размером m x n, состоящая из целых чисел. Отсортируйте каждую диагональ матрицы по возрастанию и верните полученную матрицу.

Пример:

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

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

1⃣Сохраните размеры матрицы m и n. Создайте хеш-карту из минимальных куч для хранения элементов диагоналей.

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

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

😎 Решение:

public class Solution {
    public int[][] DiagonalSort(int[][] mat) {
        int m = mat.Length;
        int n = mat[0].Length;

        var diagonals = new Dictionary<int, PriorityQueue<int, int>>();

        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                int key = row - col;
                if (!diagonals.ContainsKey(key)) {
                    diagonals[key] = new PriorityQueue<int, int>();
                }
                diagonals[key].Enqueue(mat[row][col], mat[row][col]);
            }
        }

        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                int key = row - col;
                mat[row][col] = diagonals[key].Dequeue();
            }
        }

        return mat;
    }
}

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

Задача: 261. Graph Valid Tree
Сложность: medium

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

Верните true, если рёбра данного графа образуют допустимое дерево, и false в противном случае.

Пример:

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

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

1⃣Проверьте, что количество рёбер равно n - 1. Если нет, верните false.

2⃣Используйте итеративный обход в глубину (DFS) для проверки связности графа и отсутствия циклов. Создайте стек для хранения узлов для посещения и множество для отслеживания посещённых узлов. Начните с узла 0.

3⃣Если все узлы посещены и циклы не обнаружены, верните true. В противном случае, верните false.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public bool ValidTree(int n, int[][] edges) {
        if (edges.Length != n - 1) {
            return false;
        }
        
        List<int>[] adjList = new List<int>[n];
        for (int i = 0; i < n; i++) {
            adjList[i] = new List<int>();
        }
        foreach (var edge in edges) {
            adjList[edge[0]].Add(edge[1]);
            adjList[edge[1]].Add(edge[0]);
        }
        
        Dictionary<int, int> parent = new Dictionary<int, int> { { 0, -1 } };
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(0);
        
        while (queue.Count > 0) {
            int node = queue.Dequeue();
            foreach (int neighbor in adjList[node]) {
                if (neighbor == parent[node]) {
                    continue;
                }
                if (parent.ContainsKey(neighbor)) {
                    return false;
                }
                parent[neighbor] = node;
                queue.Enqueue(neighbor);
            }
        }
        
        return parent.Count == n;
    }
}

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

Задача: 80. Remove Duplicates from Sorted Array II
Сложность: medium

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

Поскольку в некоторых языках программирования невозможно изменить длину массива, результат следует разместить в первой части массива nums. Более формально, если после удаления дубликатов остаётся k элементов, то первые k элементов массива nums должны содержать итоговый результат. Не важно, что остаётся за пределами первых k элементов.

Верните k после размещения итогового результата в первые k слотов массива nums.

Не выделяйте дополнительное пространство для другого массива. Вы должны сделать это, изменяя исходный массив на месте с использованием дополнительной памяти O(1).

Пример:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

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

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

2⃣Обработка элементов массива: Для каждого элемента в массиве:

3⃣Если текущий элемент такой же, как предыдущий (nums[i] == nums[i - 1]), увеличьте count.
Если count больше 2, это означает, что текущий элемент встречается более двух раз. В этом случае удалите этот элемент из массива с помощью операции удаления, поддерживаемой вашим языком программирования (например, del, pop, remove), и уменьшите индекс i на 1, чтобы корректно обработать следующий элемент.
Если текущий элемент отличается от предыдущего (nums[i] != nums[i - 1]), это означает начало новой последовательности, поэтому сбросьте count к 1.
Возвращение результата: После обработки всех элементов в массиве, все ненужные дубликаты удалены, и в массиве остаются только допустимые элементы. Верните длину обработанного массива, так как это количество элементов, которые теперь соответствуют условиям задачи.

😎 Решение:

public class Solution {
    public int RemoveDuplicates(int[] nums) {
        if (nums.Length < 3)
            return nums.Length;
        int j = 2;
        for (int i = 2; i < nums.Length; i++) {
            if (nums[i] != nums[j - 2]) {
                nums[j++] = nums[i];
            }
        }

        return j;
    }
}

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

Задача: 1089. Duplicate Zeros
Сложность: easy

Дан массив целых чисел фиксированной длины arr, дублируйте каждое вхождение нуля, сдвигая оставшиеся элементы вправо.

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

Пример:

Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

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

1⃣Найдите количество нулей, которые будут продублированы, назовем это possible_dups. Необходимо убедиться, что мы не считаем нули, которые будут отброшены, так как отброшенные нули не будут частью итогового массива. Количество possible_dups даст нам количество элементов, которые будут отброшены из исходного массива. В любой момент времени length_ - possible_dups — это количество элементов, которые будут включены в итоговый массив.

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

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

😎 Решение:

public class Solution {
    public void DuplicateZeros(int[] arr) {
        int possibleDups = 0;
        int length_ = arr.Length - 1;

        for (int left = 0; left <= length_ - possibleDups; left++) {
            if (arr[left] == 0) {
                if (left == length_ - possibleDups) {
                    arr[length_] = 0;
                    length_ -= 1;
                    break;
                }
                possibleDups++;
            }
        }

        int last = length_ - possibleDups;

        for (int i = last; i >= 0; i--) {
            if (arr[i] == 0) {
                arr[i + possibleDups] = 0;
                possibleDups--;
                arr[i + possibleDups] = 0;
            } else {
                arr[i + possibleDups] = arr[i];
            }
        }
    }
}

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

Задача: 1318. Minimum Flips to Make a OR b Equal to c
Сложность: medium

Даны три положительных числа a, b и c. Верните минимальное количество переворотов, необходимых в некоторых битах a и b, чтобы сделать (a OR b == c) (побитовая операция OR). Операция переворота состоит из изменения любого отдельного бита с 1 на 0 или с 0 на 1 в их двоичном представлении.

Пример:

Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)

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

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

2⃣Итеративно обрабатывайте каждый бит двоичного представления чисел a, b и c одновременно:

Если (c & 1) == 0, обновите answer как answer += (a & 1) + (b & 1).
Если (c & 1) == 1, и если оба значения a & 1 и b & 1 равны 0, увеличьте answer на 1.

3⃣Сдвигайте все числа вправо с помощью a >>= 1, b >>= 1, c >>= 1. Если все числа равны 0, верните answer, в противном случае, повторите шаги 2 и 3.

😎 Решение:

public class Solution {
    public int MinFlips(int a, int b, int c) {
        int answer = 0;
        while (a != 0 || b != 0 || c != 0) {
            if ((c & 1) == 1) {
                if ((a & 1) == 0 && (b & 1) == 0) {
                    answer++;
                }
            } else {
                answer += (a & 1) + (b & 1);
            }
            a >>= 1;
            b >>= 1;
            c >>= 1;
        }
        return answer;
    }
}

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

Задача: 827. Making A Large Island
Сложность: hard

Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1.

Верните размер самого большого острова в grid после выполнения этой операции.

Остров — это группа 1, соединенных в 4 направлениях.

Пример:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

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

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

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

3⃣Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1.

😎 Решение:

public class Solution {
    private static readonly int[] dr = { -1, 0, 1, 0 };
    private static readonly int[] dc = { 0, -1, 0, 1 };
    private int[][] grid;
    private int N;

    public int LargestIsland(int[][] grid) {
        this.grid = grid;
        N = grid.Length;

        int index = 2;
        int[] area = new int[N * N + 2];
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                if (grid[r][c] == 1) {
                    area[index] = Dfs(r, c, index++);
                }
            }
        }

        int ans = area.Max();
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                if (grid[r][c] == 0) {
                    HashSet<int> seen = new HashSet<int>();
                    foreach (var move in Neighbors(r, c)) {
                        if (grid[move.Item1][move.Item2] > 1) {
                            seen.Add(grid[move.Item1][move.Item2]);
                        }
                    }
                    int bns = 1;
                    foreach (int i in seen) bns += area[i];
                    ans = Math.Max(ans, bns);
                }
            }
        }
        return ans;
    }

    private int Dfs(int r, int c, int index) {
        int ans = 1;
        grid[r][c] = index;
        foreach (var move in Neighbors(r, c)) {
            if (grid[move.Item1][move.Item2] == 1) {
                grid[move.Item1][move.Item2] = index;
                ans += Dfs(move.Item1, move.Item2, index);
            }
        }
        return ans;
    }

    private IEnumerable<(int, int)> Neighbors(int r, int c) {
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            if (nr >= 0 && nr < N && nc >= 0 && nc < N) {
                yield return (nr, nc);
            }
        }
    }
}

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

Задача: 993. Cousins in Binary Tree
Сложность: easy

Дан корень бинарного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, иначе верните false.

Два узла бинарного дерева являются кузенами, если они находятся на одной глубине и имеют разных родителей.

Обратите внимание, что в бинарном дереве корневой узел находится на глубине 0, а дети каждого узла глубины k находятся на глубине k + 1.

Пример:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

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

1⃣Поиск глубины и родителя для каждого узла:
Используйте поиск в глубину (DFS) для обхода дерева.
Для каждого узла сохраняйте его глубину и родителя, если значение узла равно x или y.

2⃣Проверка условий на кузенов:
Узлы являются кузенами, если они находятся на одной глубине, но имеют разных родителей.

3⃣Возврат результата:
Если узлы удовлетворяют условиям на кузенов, верните true, иначе верните false.

😎 Решение:

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

public class Solution {
    private TreeNode parentX = null;
    private TreeNode parentY = null;
    private int depthX = -1;
    private int depthY = -1;
    
    public bool IsCousins(TreeNode root, int x, int y) {
        Dfs(root, null, 0, x, y);
        return depthX == depthY && parentX != parentY;
    }
    
    private void Dfs(TreeNode node, TreeNode parent, int depth, int x, int y) {
        if (node == null) {
            return;
        }
        if (node.val == x) {
            parentX = parent;
            depthX = depth;
        } else if (node.val == y) {
            parentY = parent;
            depthY = depth;
        } else {
            Dfs(node.left, node, depth + 1, x, y);
            Dfs(node.right, node, depth + 1, x, y);
        }
    }
}

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

Задача: 1365. How Many Numbers Are Smaller Than the Current Number
Сложность: easy

Дан массив nums. Для каждого элемента nums[i] определите, сколько чисел в массиве меньше его. То есть, для каждого nums[i] вам нужно посчитать количество допустимых j, таких что j != i и nums[j] < nums[i].

Верните ответ в виде массива.

Пример:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

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

1⃣Создание копии и сортировка массива:
Создайте отсортированную копию массива nums, чтобы легко находить количество элементов, меньших текущего.

2⃣Поиск индекса каждого элемента:
Для каждого элемента nums[i] найдите его индекс в отсортированной копии массива. Этот индекс указывает количество элементов, меньших nums[i].

3⃣Формирование ответа:
Сформируйте массив ответов, где каждый элемент будет соответствовать количеству чисел, меньших текущего.

😎 Решение:

using System;
using System.Linq;

public class Solution {
    public int[] SmallerNumbersThanCurrent(int[] nums) {
        int[] sortedNums = (int[]) nums.Clone();
        Array.Sort(sortedNums);
        return nums.Select(num => Array.IndexOf(sortedNums, num)).ToArray();
    }
}

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

Задача: 1244. Design A Leaderboard
Сложность: medium

Разработайте класс Leaderboard, который содержит 3 функции: addScore(playerId, score): Обновляет таблицу лидеров, добавляя счет к счету данного игрока. Если в таблице лидеров нет игрока с таким id, добавьте его в таблицу лидеров с заданным счетом. top(K): Возвращает сумму очков K лучших игроков. reset(playerId): Сбрасывает счет игрока с заданным идентификатором в 0 (другими словами, стирает его из таблицы лидеров). Гарантируется, что игрок был добавлен в таблицу лидеров до вызова этой функции. Изначально таблица лидеров пуста.

Пример:

Input: 
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output: 
[null,null,null,null,null,null,73,null,null,null,141]

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

1⃣addScore(playerId, score):
Если игрок уже существует в таблице лидеров, добавляем к его текущему счету новое значение.
Если игрок не существует, добавляем его с заданным счетом.

2⃣top(K):
Сортируем игроков по их счету в порядке убывания.
Возвращаем сумму очков K лучших игроков.

3⃣reset(playerId):
Устанавливаем счет игрока в 0.

😎 Решение:

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

public class Leaderboard {
    private Dictionary<int, int> scores;

    public Leaderboard() {
        scores = new Dictionary<int, int>();
    }

    public void AddScore(int playerId, int score) {
        if (scores.ContainsKey(playerId)) {
            scores[playerId] += score;
        } else {
            scores[playerId] = score;
        }
    }

    public int Top(int K) {
        return scores.Values.OrderByDescending(x => x).Take(K).Sum();
    }

    public void Reset(int playerId) {
        if (scores.ContainsKey(playerId)) {
            scores[playerId] = 0;
        }
    }
}

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