Задача: 168. Excel Sheet Column Title
Сложность: easy

Дано целое число columnNumber, верните соответствующий заголовок столбца, как он отображается в таблице Excel.

Например:
A -> 1
B -> 2
C -> 3
Z -> 26
AA -> 27
AB -> 28

Пример:

Input: columnNumber = 1
Output: "A"

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

1⃣Инициализация пустой строки ans:
Создайте пустую строку ans, которая будет хранить заголовок столбца.

2⃣Циклическое преобразование числа в буквы:
Пока columnNumber больше 0, выполняйте следующие действия:
Вычтите 1 из columnNumber для корректировки индекса (Excel использует 1-индексацию).
Найдите символ, соответствующий остатку от деления columnNumber на 26, и добавьте его в начало строки ans.
Присвойте columnNumber значение от деления columnNumber на 26

3⃣Переворот и возврат результата:
Так как символы добавляются в начало строки, то по завершению цикла строка ans содержит заголовок столбца в обратном порядке. Переверните строку ans, чтобы представить её в правильном порядке.
Верните полученный заголовок столбца.

😎 Решение:

public class Solution {
    public string ConvertToTitle(int columnNumber) {
        string ans = "";

        while (columnNumber > 0) {
            columnNumber--;
            ans = ((char)((columnNumber) % 26 + 'A')) + ans;
            columnNumber = (columnNumber) / 26;
        }

        return ans;
    }
}

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

Задача: 314. Binary Tree Vertical Order Traversal
Сложность: medium

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

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

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

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

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

2⃣Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь.

3⃣После завершения BFS обхода получите хэш-таблицу, содержащую значения узлов, сгруппированные по индексам столбцов. Для каждой группы значений отсортируйте их по индексам строк. Отсортируйте хэш-таблицу по ключам (индексам столбцов) в порядке возрастания и верните результаты по столбцам.

😎 Решение:

using System;
using System.Collections.Generic;

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

public class Solution {
    public IList<IList<int>> VerticalOrder(TreeNode root) {
        IList<IList<int>> output = new List<IList<int>>();
        if (root == null) {
            return output;
        }

        Dictionary<int, List<int>> columnTable = new Dictionary<int, List<int>>();
        Queue<(TreeNode, int)> queue = new Queue<(TreeNode, int)>();
        int column = 0;
        queue.Enqueue((root, column));

        while (queue.Count > 0) {
            var (node, col) = queue.Dequeue();

            if (node != null) {
                if (!columnTable.ContainsKey(col)) {
                    columnTable[col] = new List<int>();
                }
                columnTable[col].Add(node.val);

                queue.Enqueue((node.left, col - 1));
                queue.Enqueue((node.right, col + 1));
            }
        }

        var sortedKeys = new List<int>(columnTable.Keys);
        sortedKeys.Sort();
        foreach (var key in sortedKeys) {
            output.Add(columnTable[key]);
        }

        return output;
    }
}

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

Задача: 1057. Campus Bikes
Сложность: medium

В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Пример:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]

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

1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список.

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

3⃣Заполни и верни массив назначений.

😎 Решение:

public class Solution {
    public int[] AssignBikes(int[][] workers, int[][] bikes) {
        var pairs = new List<(int distance, int workerIdx, int bikeIdx)>();
        
        for (int i = 0; i < workers.Length; i++) {
            for (int j = 0; j < bikes.Length; j++) {
                int distance = Math.Abs(workers[i][0] - bikes[j][0]) + Math.Abs(workers[i][1] - bikes[j][1]);
                pairs.Add((distance, i, j));
            }
        }
        
        pairs.Sort((a, b) => {
            int result = a.distance.CompareTo(b.distance);
            if (result == 0) {
                result = a.workerIdx.CompareTo(b.workerIdx);
                if (result == 0) {
                    result = a.bikeIdx.CompareTo(b.bikeIdx);
                }
            }
            return result;
        });
        
        int[] result = new int[workers.Length];
        bool[] bikeTaken = new bool[bikes.Length];
        bool[] workerAssigned = new bool[workers.Length];
        
        Array.Fill(result, -1);
        
        foreach (var pair in pairs) {
            if (!workerAssigned[pair.workerIdx] && !bikeTaken[pair.bikeIdx]) {
                result[pair.workerIdx] = pair.bikeIdx;
                bikeTaken[pair.bikeIdx] = true;
                workerAssigned[pair.workerIdx] = true;
            }
        }
        
        return result;
    }
}

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

Задача: 897. Increasing Order Search Tree
Сложность: easy

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

Пример:

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

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

1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов.

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

3⃣Вернуть новый корень дерева (первый элемент списка).

😎 Решение:

using System;
using System.Collections.Generic;

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 {
    public TreeNode IncreasingBST(TreeNode root) {
        List<TreeNode> nodes = new List<TreeNode>();
        
        Inorder(root, nodes);
        
        for (int i = 0; i < nodes.Count - 1; i++) {
            nodes[i].left = null;
            nodes[i].right = nodes[i + 1];
        }
        
        nodes[nodes.Count - 1].left = null;
        nodes[nodes.Count - 1].right = null;
        return nodes[0];
    }
    
    private void Inorder(TreeNode node, List<TreeNode> nodes) {
        if (node == null) return;
        Inorder(node.left, nodes);
        nodes.Add(node);
        Inorder(node.right, nodes);
    }
}

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

Задача: 187. Repeated DNA Sequences
Сложность: medium

ДНК состоит из серии нуклеотидов, обозначаемых как 'A', 'C', 'G' и 'T'.

Например, "ACGAATTCCG" — это последовательность ДНК.
При изучении ДНК полезно определять повторяющиеся последовательности внутри молекулы ДНК.

Дана строка s, представляющая последовательность ДНК. Верните все последовательности длиной 10 букв (подстроки), которые встречаются более одного раза в молекуле ДНК. Ответ можно возвращать в любом порядке.

Пример:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

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

1⃣Перебираем начальные позиции последовательности от 1 до 𝑁−𝐿, где 𝑁 — длина строки, а 𝐿 — длина подстроки (в данном случае 10):
Если начальная позиция 𝑠𝑡𝑎𝑟𝑡==0, вычисляем хеш первой последовательности 𝑠[0:𝐿].
В противном случае вычисляем скользящий хеш из предыдущего значения хеша.

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

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

😎 Решение:

public class Solution {
    public IList<string> FindRepeatedDnaSequences(string s) {
        int L = 10, n = s.Length;
        if (n <= L) return new List<string>();
        int a = 4, aL = (int)Math.Pow(a, L);
        Dictionary<char, int> toInt = new Dictionary<char, int>{{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
        int[] nums = s.Select(c => toInt[c]).ToArray();
        int h = 0;
        HashSet<int> seen = new HashSet<int>();
        HashSet<string> output = new HashSet<string>();
        for (int start = 0; start < n - L + 1; start++) {
            if (start != 0)
                h = h * a - nums[start - 1] * aL + nums[start + L - 1];
            else
                for (int i = 0; i < L; i++)
                    h = h * a + nums[i];
            if (seen.Contains(h))
                output.Add(s.Substring(start, L));
            seen.Add(h);
        }
        return output.ToList();
    }
}

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

Задача: 1095. Find in Mountain Array
Сложность: hard

Массив arr является горным массивом тогда и только тогда, когда:

Длина массива arr >= 3.
Существует некоторое i с 0 < i < arr.length - 1 такое, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан горный массив mountainArr, верните минимальный индекс, такой что mountainArr.get(index) == target. Если такого индекса не существует, верните -1.

Вы не можете напрямую обращаться к массиву. Вы можете использовать интерфейс MountainArray:

MountainArray.get(k) возвращает элемент массива на индексе k (индексация начинается с 0).
MountainArray.length() возвращает длину массива.
Решения, использующие более 100 вызовов MountainArray.get, будут оценены как неправильные. Также любые решения, которые пытаются обойти ограничение, будут дисквалифицированы.

Пример:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

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

1⃣Найти индекс пика: Инициализируем два указателя low и high, где low начинается с 1, а high — с длины массива минус 2. Используем бинарный поиск для нахождения пикового элемента: если элемент в середине меньше следующего элемента, то пиковый элемент находится справа, иначе он находится слева. Продолжаем сужать диапазон поиска до тех пор, пока low не станет равным high. Это и будет индекс пика.

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

3⃣Бинарный поиск в убывающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от пикового индекса плюс 1 до конца массива. Проводим бинарный поиск, но с учетом убывающей последовательности: если значение в середине больше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс. Если значение не найдено, возвращаем -1.

😎 Решение:

public class Solution {
    public int FindInMountainArray(int target, MountainArray mountainArr) {
        int length = mountainArr.length();

        int low = 1, high = length - 2;
        while (low != high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        int peak = low;

        low = 0;
        high = peak;
        while (low < high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (mountainArr.get(low) == target) {
            return low;
        }

        low = peak + 1;
        high = length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) > target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (mountainArr.get(low) == target) {
            return low;
        }

        return -1;
    }
}

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

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

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