Задача: 103. Binary Tree Zigzag Level Order Traversal
Сложность: medium

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

Пример:

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

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

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

2⃣Здесь мы принимаем второй подход, описанный выше. Можно начать с обычного алгоритма BFS, к которому мы добавляем элемент порядка зигзага с помощью deque (двусторонней очереди).

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

😎 Решение:

public class Solution {
    public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
        List<IList<int>> result = new List<IList<int>>();
        if (root == null)
            return result;
        Queue<TreeNode> nodeQueue = new Queue<TreeNode>();
        nodeQueue.Enqueue(root);
        nodeQueue.Enqueue(null);
        LinkedList<int> levelList = new LinkedList<int>();
        bool isOrderLeft = true;
        while (nodeQueue.Count > 0) {
            TreeNode currentNode = nodeQueue.Dequeue();
            if (currentNode != null) {
                if (isOrderLeft)
                    levelList.AddLast(currentNode.val);
                else
                    levelList.AddFirst(currentNode.val);
                if (currentNode.left != null)
                    nodeQueue.Enqueue(currentNode.left);
                if (currentNode.right != null)
                    nodeQueue.Enqueue(currentNode.right);
            } else {
                result.Add(new List<int>(levelList));
                levelList.Clear();
                if (nodeQueue.Count > 0)
                    nodeQueue.Enqueue(null);
                isOrderLeft = !isOrderLeft;
            }
        }

        return result;
    }
}

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

Задача: 382. Linked List Random Node
Сложность: medium

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

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

Solution(ListNode head) Инициализирует объект с головой односвязного списка head.
int getRandom() Выбирает узел случайным образом из списка и возвращает его значение. Все узлы списка должны иметь равные шансы быть выбранными.

Пример:

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

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

1⃣Реализуйте интерфейс init(head), который будет вызываться при создании объекта. Преобразуйте связанный список в массив для дальнейшего использования.

2⃣В интерфейсе init(head) преобразуйте переданный связанный список в массив, чтобы его можно было использовать позже.

3⃣Реализуйте функцию getRandom(), которая будет выбирать случайный элемент из массива, созданного на первом этапе.

😎 Решение:

using System;
using System.Collections.Generic;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    private List<int> range = new List<int>();
    private Random random = new Random();

    public Solution(ListNode head) {
        while (head != null) {
            range.Add(head.val);
            head = head.next;
        }
    }

    public int GetRandom() {
        int pick = random.Next(range.Count);
        return range[pick];
    }
}

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

Задача: 1019. Next Greater Node In Linked List
Сложность: medium

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

Пример:

Input: head = [2,1,5]
Output: [5,5,0]

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

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

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

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

😎 Решение:

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}

public class Solution {
    public int[] NextLargerNodes(ListNode head) {
        var values = new List<int>();
        while (head != null) {
            values.Add(head.val);
            head = head.next;
        }
        
        var answer = new int[values.Count];
        var stack = new Stack<int>();
        
        for (int i = 0; i < values.Count; i++) {
            while (stack.Count > 0 && values[stack.Peek()] < values[i]) {
                answer[stack.Pop()] = values[i];
            }
            stack.Push(i);
        }
        
        return answer;
    }
}

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

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

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

Пример:

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

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

1⃣Самый простой способ решения задачи — использование рекурсии. Сначала убедимся, что дерево не пустое, а затем рекурсивно вызовем функцию helper(node, level), которая принимает текущий узел и его уровень в качестве аргументов.

2⃣Эта функция выполняет следующее:
Выходной список здесь называется levels, и, таким образом, текущий уровень — это просто длина этого списка len(levels). Сравниваем номер текущего уровня len(levels) с уровнем узла level. Если вы все еще на предыдущем уровне, добавьте новый, добавив новый список в levels.

3⃣Добавьте значение узла в последний список в levels.
Рекурсивно обработайте дочерние узлы, если они не равны None: helper(node.left / node.right, level + 1).

😎 Решение:

public class Solution {
    IList<IList<int>> levels = new List<IList<int>>();

    public void Helper(TreeNode node, int level) {
        if (levels.Count == level)
            levels.Add(new List<int>());
        levels[level].Add(node.val);
        if (node.left != null)
            Helper(node.left, level + 1);
        if (node.right != null)
            Helper(node.right, level + 1);
    }

    public IList<IList<int>> LevelOrder(TreeNode root) {
        if (root == null)
            return levels;
        Helper(root, 0);
        return levels;
    }
}

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

Задача: 587. Erect the Fence
Сложность: hard

Вам дан массив trees, где trees[i] = [xi, yi] представляет местоположение дерева в саду.

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

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

Пример:

Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
Explanation: All the trees will be on the perimeter of the fence except the tree at [2, 2], which will be inside the fence.

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

1⃣ Сортировка точек и построение нижней оболочки:
Отсортируйте точки по их x-координатам, а в случае совпадения x-координат, по y-координатам.
Постройте нижнюю оболочку, добавляя точки к оболочке и удаляя последние точки, если они не образуют против часовой стрелки поворот.

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

3⃣ Удаление дублирующих элементов и возврат результата:
Используйте HashSet, чтобы удалить дублирующиеся точки из стека.
Преобразуйте результат в массив и верните его.

😎 Решение:

public class Solution {
    public int Orientation(int[] p, int[] q, int[] r) {
        return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
    }

    public IList<IList<int>> OuterTrees(int[][] points) {
        Array.Sort(points, (p, q) => p[0] == q[0] ? p[1].CompareTo(q[1]) : p[0].CompareTo(q[0]));
        List<int[]> hull = new List<int[]>();

        foreach (var point in points) {
            while (hull.Count >= 2 && Orientation(hull[hull.Count - 2], hull[hull.Count - 1], point) > 0)
                hull.RemoveAt(hull.Count - 1);
            hull.Add(point);
        }

        hull.RemoveAt(hull.Count - 1);

        for (int i = points.Length - 1; i >= 0; i--) {
            while (hull.Count >= 2 && Orientation(hull[hull.Count - 2], hull[hull.Count - 1], points[i]) > 0)
                hull.RemoveAt(hull.Count - 1);
            hull.Add(points[i]);
        }

        HashSet<int[]> ret = new HashSet<int[]>(hull, new ArrayComparer());
        return ret.ToList<IList<int>>();
    }

    private class ArrayComparer : IEqualityComparer<int[]> {
        public bool Equals(int[] x, int[] y) {
            return x[0] == y[0] && x[1] == y[1];
        }

        public int GetHashCode(int[] obj) {
            return obj[0].GetHashCode() ^ obj[1].GetHashCode();
        }
    }
}

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

Задача: 1034. Coloring A Border
Сложение : medium

Вам дана целочисленная матричная сетка m x n и три целых числа row, col и color. Каждое значение в сетке представляет собой цвет квадрата сетки в данном месте. Два квадрата называются смежными, если они находятся рядом друг с другом в любом из 4 направлений. Два квадрата принадлежат одному связанному компоненту, если они имеют одинаковый цвет и являются смежными.

Граница связанного компонента - это все квадраты в связанном компоненте, которые либо смежны (по крайней мере) с квадратом, не входящим в компонент, либо находятся на границе сетки (в первой или последней строке или столбце). Вы должны окрасить границу связанного компонента, содержащего квадрат grid[row][col], в цвет. Верните конечную сетку.

Пример:

Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]

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

1⃣Поиск связанного компонента:
Используйте поиск в глубину (DFS) или поиск в ширину (BFS), чтобы найти все клетки, принадлежащие связанному компоненту, содержащему клетку grid[row][col].
Запомните все клетки, которые принадлежат этому компоненту.

2⃣Определение границ компонента:
Для каждой клетки в связанном компоненте проверьте, является ли она границей. Клетка является границей, если она находится на краю сетки или если хотя бы одна из её соседних клеток не принадлежит связанному компоненту или имеет другой цвет.

3⃣Окрашивание границы:
Измените цвет всех клеток, являющихся границами, на заданный цвет.

😎 Решение:

func colorBorder(grid [][]int, row int, col int, color int) [][]int {
    m, n := len(grid), len(grid[0])
    originalColor := grid[row][col]
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    borders := [][]int{}

    var dfs func(r, c int)
    dfs = func(r, c int) {
        visited[r][c] = true
        isBorder := false
        for _, dir := range [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} {
            nr, nc := r+dir[0], c+dir[1]
            if nr >= 0 && nr < m && nc >= 0 && nc < n {
                if !visited[nr][nc] {
                    if grid[nr][nc] == originalColor {
                        dfs(nr, nc)
                    } else {
                        isBorder = true
                    }
                }
            } else {
                isBorder = true
            }
        }
        if isBorder || r == 0 || r == m-1 || c == 0 || c == n-1 {
            borders = append(borders, []int{r, c})
        }
    }

    dfs(row, col)
    for _, border := range borders {
        grid[border[0]][border[1]] = color
    }

    return grid
}

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

Задача: 445. Add Two Numbers II
Сложность: medium

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

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

Пример:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

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

1⃣Создайте два связанных списка r1 и r2, чтобы хранить перевернутые связанные списки l1 и l2 соответственно. Создайте два целых числа totalSum и carry для хранения суммы и переноса текущих цифр. Создайте новый ListNode, ans, который будет хранить сумму текущих цифр. Мы будем складывать два числа, используя перевернутый список, добавляя цифры по одной. Продолжаем, пока не пройдем все узлы в r1 и r2.

2⃣Если r1 не равен null, добавляем r1.val к totalSum. Если r2 не равен null, добавляем r2.val к totalSum. Устанавливаем ans.val = totalSum % 10. Сохраняем перенос как totalSum / 10. Создаем новый ListNode, newNode, который будет иметь значение как перенос. Устанавливаем next для newNode как ans. Обновляем ans = newNode, чтобы использовать ту же переменную ans для следующей итерации. Обновляем totalSum = carry.

3⃣Если carry == 0, это означает, что newNode, созданный в финальной итерации цикла while, имеет значение 0. Поскольку мы выполняем ans = newNode в конце каждой итерации цикла while, чтобы избежать возврата связанного списка с головой, равной 0 (начальный ноль), возвращаем следующий элемент, т.е. возвращаем ans.next. В противном случае, если перенос не равен 0, значение ans не равно нулю. Следовательно, просто возвращаем ans.

😎 Решение:

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    private ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }

    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        ListNode r1 = ReverseList(l1);
        ListNode r2 = ReverseList(l2);

        int carry = 0;
        ListNode ans = null;

        while (r1 != null || r2 != null || carry > 0) {
            if (r1 != null) {
                carry += r1.val;
                r1 = r1.next;
            }
            if (r2 != null) {
                carry += r2.val;
                r2 = r2.next;
            }

            ListNode newNode = new ListNode(carry % 10);
            newNode.next = ans;
            ans = newNode;
            carry /= 10;
        }

        return ans;
    }
}

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

Задача: 1531. String Compression II
Сложность: hard

Дана строка s и целое число k. Необходимо удалить не более k символов из s так, чтобы длина сжатой версии строки s с использованием RLE была минимальной.

Найдите минимальную длину сжатой версии строки s после удаления не более k символов.

Пример:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

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

1⃣Обходим символы строки слева направо, решая для каждого символа, включать его в сжатую строку или нет. Это создает состояния (строка, оставшиеся для включения символы), которые можно представить в виде бинарного дерева, где левые потомки означают включение символов, а правые — их пропуск. Многочисленные повторяющиеся подзадачи указывают на необходимость использования динамического программирования.

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

3⃣Связываем состояния друг с другом: удаление нового символа увеличивает i на один и уменьшает k на один; включение нового символа оставляет длину сжатия неизменной (кроме случаев, когда частота последнего символа 1, 9 или 99) или увеличивает длину на один, если новый символ не равен последнему символу сжатия.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    private Dictionary<int, int> memo = new Dictionary<int, int>();
    private HashSet<int> add = new HashSet<int> { 1, 9, 99 };

    public int GetLengthOfOptimalCompression(string s, int k) {
        return Dp(s, 0, (char)('a' + 26), 0, k);
    }

    private int Dp(string s, int idx, char lastChar, int lastCharCount, int k) {
        if (k < 0) {
            return int.MaxValue / 2;
        }

        if (idx == s.Length) {
            return 0;
        }

        int key = idx * 101 * 27 * 101 + (lastChar - 'a') * 101 * 101 + lastCharCount * 101 + k;

        if (memo.ContainsKey(key)) {
            return memo[key];
        }

        int deleteChar = Dp(s, idx + 1, lastChar, lastCharCount, k - 1);
        int keepChar;
        if (s[idx] == lastChar) {
            keepChar = Dp(s, idx + 1, lastChar, lastCharCount + 1, k) + (add.Contains(lastCharCount) ? 1 : 0);
        } else {
            keepChar = Dp(s, idx + 1, s[idx], 1, k) + 1;
        }

        int res = Math.Min(keepChar, deleteChar);
        memo[key] = res;

        return res;
    }
}

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

Задача: 1165. Single-Row Keyboard
Сложность: easy

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

Дана строка keyboard длиной 26, указывающая на раскладку клавиатуры (индексирована от 0 до 25). Изначально ваш палец находится на индексе 0. Чтобы напечатать символ, нужно переместить палец на индекс нужного символа. Время, затраченное на перемещение пальца с индекса i на индекс j, равно |i - j|.

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

Пример:

Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4.

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

1⃣Клавиатура содержит уникальные строчные английские буквы, поэтому мы можем сопоставить её с массивом размера 26. Создадим массив размера 26, назовём его keyIndices. Сохраните индекс каждой буквы в этом массиве, проходя по строке keyboard. Инициализируйте переменную result значением 0, которая будет хранить сумму всех расстояний. Объявите переменную prev, которая будет хранить индекс предыдущей клавиши. Поскольку начальная позиция равна 0, инициализируйте её значением 0.

2⃣Проходите по строке word буква за буквой. Для каждой буквы c добавьте ∣prev−indexOf(c)∣ к result. Обновите prev до индекса c.

3⃣Повторите шаги 6 и 7 для всех букв. В конце прохода result будет содержать итоговое время, необходимое для набора слова.

😎 Решение:

public class Solution {
    public int CalculateTime(string keyboard, string word) {
        int[] keyIndices = new int[26];
        for (int i = 0; i < keyboard.Length; i++) {
            keyIndices[keyboard[i] - 'a'] = i;
        }
        
        int prev = 0;
        int result = 0;
        
        foreach (char c in word) {
            int index = keyIndices[c - 'a'];
            result += Math.Abs(prev - index);
            prev = index;
        }
        
        return result;
    }
}

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

Задача: 484. Find Permutation
Сложность: Medium

Перестановка perm из n целых чисел всех чисел в диапазоне [1, n] может быть представлена в виде строки s длиной n - 1, где:

s[i] == 'I', если perm[i] < perm[i + 1], и
s[i] == 'D', если perm[i] > perm[i + 1].
Дана строка s, восстановите лексикографически наименьшую перестановку perm и верните её.

Пример:

Input: s = "I"
Output: [1,2]
Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.

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

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

2⃣Для каждого числа i
Если текущий символ в строке s равен 'D', добавьте i в стек. Если текущий символ в строке s равен 'I', добавьте i в стек, затем извлеките все элементы из стека и добавьте их в result.

3⃣Завершение
Добавьте n в стек и извлеките все элементы из стека, добавив их в result. Верните список result, который представляет лексикографически наименьшую перестановку.

😎 Решение:

public class Solution {
    public int[] FindPermutation(string s) {
        int[] res = new int[s.Length + 1];
        Stack<int> stack = new Stack<int>();
        int j = 0;
        for (int i = 1; i <= s.Length; i++) {
            if (s[i - 1] == 'I') {
                stack.Push(i);
                while (stack.Count > 0) {
                    res[j++] = stack.Pop();
                }
            } else {
                stack.Push(i);
            }
        }
        stack.Push(s.Length + 1);
        while (stack.Count > 0) {
            res[j++] = stack.Pop();
        }
        return res;
    }
}

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

Задача: 384. Shuffle an Array
Сложность: medium

Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания.

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

Solution(int[] nums): Инициализирует объект целочисленным массивом nums.
int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его.
int[] shuffle(): Возвращает случайное перемешивание массива.

Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

1⃣Алгоритм Фишера-Йейтса удивительно похож на решение грубой силы. На каждой итерации алгоритма мы генерируем случайное целое число между текущим индексом и последним индексом массива.

2⃣Затем мы меняем местами элементы на текущем индексе и выбранном индексе. Это симулирует выбор (и удаление) элемента из "шляпы", так как следующий диапазон, из которого мы выбираем случайный индекс, не будет включать последний обработанный элемент.

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

😎 Решение:

using System;

public class Solution {
    private int[] array;
    private int[] original;
    private Random rand = new Random();

    private int RandRange(int min, int max) {
        return rand.Next(min, max);
    }

    private void SwapAt(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public Solution(int[] nums) {
        array = (int[])nums.Clone();
        original = (int[])nums.Clone();
    }

    public int[] Reset() {
        array = (int[])original.Clone();
        return original;
    }

    public int[] Shuffle() {
        for (int i = 0; i < array.Length; i++) {
            int randIndex = RandRange(i, array.Length);
            SwapAt(i, randIndex);
        }
        return array;
    }
}

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

Задача: 498. Diagonal Traverse
Сложность: medium

Дан массив m x n матрицы mat, верните массив всех элементов матрицы в диагональном порядке.

Пример:

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

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

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

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

3⃣Обработка диагоналей
Для каждой диагонали сохраните её элементы в списке intermediate. Переверните элементы диагонали, если её номер чётный. Добавьте элементы диагонали в массив result.

😎 Решение:

public class Solution {
    public int[] FindDiagonalOrder(int[][] mat) {
        if (mat == null || mat.Length == 0) return new int[0];
        int N = mat.Length, M = mat[0].Length;
        List<int> result = new List<int>();
        
        for (int d = 0; d < N + M - 1; ++d) {
            List<int> intermediate = new List<int>();
            int r = d < M ? 0 : d - M + 1;
            int c = d < M ? d : M - 1;
            
            while (r < N && c >= 0) {
                intermediate.Add(mat[r][c]);
                r++;
                c--;
            }
            
            if (d % 2 == 0) {
                intermediate.Reverse();
            }
            result.AddRange(intermediate);
        }
        
        return result.ToArray();
    }
}

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

Задача: 750. Number Of Corner Rectangles
Сложность: medium

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

Пример:

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

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

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

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

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

😎 Решение:

public class Solution {
    public int CountCornerRectangles(int[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.Length; i++) {
            for (int j = i + 1; j < grid.Length; j++) {
                int numPairs = 0;
                for (int k = 0; k < grid[0].Length; k++) {
                    if (grid[i][k] == 1 && grid[j][k] == 1) {
                        numPairs++;
                    }
                }
                if (numPairs > 1) {
                    count += numPairs * (numPairs - 1) / 2;
                }
            }
        }
        return count;
    }
}

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

Задача: 1046. Last Stone Weight
Сложность: easy

Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два самых тяжелых камня и разбиваем их вместе. Предположим, что два самых тяжелых камня имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y имеет новый вес y - x. В конце игры остается не более одного камня. Верните вес последнего оставшегося камня. Если камней не осталось, верните 0.

Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

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

1⃣Создай максимальную кучу из массива камней.

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

3⃣Повторяй шаг 2, пока не останется один или ноль камней, и верни вес последнего оставшегося камня или 0, если камней не осталось.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int LastStoneWeight(int[] stones) {
        var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
        foreach (var stone in stones) {
            maxHeap.Enqueue(stone, stone);
        }
        
        while (maxHeap.Count > 1) {
            var first = maxHeap.Dequeue();
            var second = maxHeap.Dequeue();
            if (first != second) {
                maxHeap.Enqueue(first - second, first - second);
            }
        }
        
        return maxHeap.Count == 0 ? 0 : maxHeap.Dequeue();
    }
}

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

Задача: 166. Fraction to Recurring Decimal
Сложность: medium

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

Если дробная часть повторяется, заключите повторяющуюся часть в скобки.

Если возможны несколько ответов, верните любой из них.

Гарантируется, что длина строки ответа будет меньше 10^4 для всех предоставленных входных данных.

Пример:

Input: numerator = 1, denominator = 2
Output: "0.5"

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

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

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

3⃣Учет особенностей:
Будьте осторожны с крайними случаями, такими как отрицательные дроби или особо сложные случаи, например, деление −1 на −2147483648. В этих случаях следует корректно обрабатывать знаки и возможные переполнения.

😎 Решение:

public class Solution {
    public string FractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }

        StringBuilder fraction = new StringBuilder();
        if (numerator < 0 ^ denominator < 0) {
            fraction.Append("-");
        }
        long dividend = Math.Abs((long)numerator);
        long divisor = Math.Abs((long)denominator);
        fraction.Append(dividend / divisor);
        long remainder = dividend % divisor;
        if (remainder == 0) {
            return fraction.ToString();
        }

        fraction.Append(".");
        Dictionary<long, int> map = new Dictionary<long, int>();
        while (remainder != 0) {
            if (map.ContainsKey(remainder)) {
                fraction.Insert(map[remainder], "(");
                fraction.Append(")");
                break;
            }

            map[remainder] = fraction.Length;
            remainder *= 10;
            fraction.Append(remainder / divisor);
            remainder %= divisor;
        }

        return fraction.ToString();
    }
}

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

Задача: 289. Game of Life
Сложность: medium

Согласно статье Википедии: "Игра Жизнь, также известная просто как Жизнь, — это клеточный автомат, созданный британским математиком Джоном Хортоном Конуэем в 1970 году."

Доска состоит из сетки клеток размером m x n, где каждая клетка имеет начальное состояние: живая (представляется числом 1) или мёртвая (представляется числом 0). Каждая клетка взаимодействует с восемью соседями (по горизонтали, вертикали и диагоналям) согласно следующим четырём правилам (взято из вышеупомянутой статьи Википедии):

Любая живая клетка с менее чем двумя живыми соседями умирает, как будто из-за недостатка населения.
Любая живая клетка с двумя или тремя живыми соседями остаётся живой до следующего поколения.
Любая живая клетка с более чем тремя живыми соседями умирает, как будто из-за перенаселения.
Любая мёртвая клетка с ровно тремя живыми соседями становится живой, как будто вследствие размножения.
Следующее состояние создаётся путем одновременного применения вышеупомянутых правил ко всем клеткам в текущем состоянии, где рождения и смерти происходят одновременно. Дано текущее состояние сетки m x n, верните следующее состояние.

Пример:

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

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

1⃣Пройдите в каждую камеру. Для каждого — посчитайте количество живых соседей (всего 8 соседей по горизонтали, вертикали и диагонали).

2⃣Применить правила жизни:
Живая клетка с <2 или >3 поднятиями соседей умирает →-1
( у насМёртвая клетка с точностью 3 поднимается и соседями осматривается → 2
(используем -1 и 2 как временные маркеры, чтобы открыть окно)

3⃣Еще раз пройдите доске и приведите все значения к конечному разуму:
>0→ живая клетка (1)
<=0→ мёртвая клетка (0)

😎 Решение:

public class Solution {
    public void GameOfLife(int[][] board) {
        int[] neighbors = {0, 1, -1};
        int rows = board.Length;
        int cols = board[0].Length;

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                int liveNeighbors = 0;

                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        if (!(neighbors[i] == 0 && neighbors[j] == 0)) {
                            int r = row + neighbors[i];
                            int c = col + neighbors[j];

                            if ((r < rows && r >= 0) && (c < cols && c >= 0) && (Math.Abs(board[r][c]) == 1)) {
                                liveNeighbors++;
                            }
                        }
                    }
                }

                if ((board[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    board[row][col] = -1;
                }
                if (board[row][col] == 0 && liveNeighbors == 3) {
                    board[row][col] = 2;
                }
            }
        }

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (board[row][col] > 0) {
                    board[row][col] = 1;
                } else {
                    board[row][col] = 0;
                }
            }
        }
    }
}

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

⚡ Официальный релиз easyoffer 2.0 состоится уже в течение нескольких дней.

Напоминаю, что в честь релиза запускаем акцию.

Первые 500 покупателей получат:

🚀 Скидку 50% на PRO тариф на 1 год
🎁 Подарок ценностью 5000₽ для тех, кто подписан на этот канал

🔔 Подпишитесь на этот канал: https://t.iss.one/+b2fZN17A9OQ3ZmJi
В нем мы опубликуем сообщение о релизе в первую очередь

Задача: 1466. Reorder Routes to Make All Paths Lead to the City Zero
Сложность: medium

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

Дороги представлены массивом connections, где connections[i] = [ai, bi] представляет дорогу от города ai до города bi.
В этом году в столице (город 0) будет большое событие, и многие люди хотят приехать в этот город.
Ваша задача состоит в том, чтобы переориентировать некоторые дороги так, чтобы каждый город мог посетить город 0. Верните минимальное количество изменённых дорог.

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

Пример:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

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

1⃣Создайте переменную count для подсчета количества рёбер, которые необходимо изменить. Инициализируйте её нулём. Создайте список смежности adj, который содержит список пар целых чисел так, чтобы adj[node] содержал всех соседей node в форме (neighbor, sign), где neighbor - соседний узел, а sign обозначает направление ребра (оригинальное или искусственное).

2⃣Начните обход в глубину (DFS). Используйте функцию dfs для выполнения обхода. В каждом вызове передавайте параметры node, parent и adj. Начните с узла 0 и parent равным -1.

3⃣Перебирайте всех соседей узла с помощью adj[node]. Для каждого neighbor, sign в adj[node], проверьте, равен ли neighbor родителю. Если равен, не посещайте его снова. Если neighbor не равен parent, выполните count += sign и рекурсивно вызовите dfs с node = neighbor и parent = node. По завершении обхода DFS, в count будет содержаться количество рёбер, которые необходимо изменить. Верните count.

😎 Решение:

public class Solution {
    int count = 0;

    void Dfs(int node, int parent, Dictionary<int, List<Tuple<int, int>>> adj) {
        if (!adj.ContainsKey(node)) return;
        foreach (var nei in adj[node]) {
            int neighbor = nei.Item1;
            int sign = nei.Item2;
            if (neighbor != parent) {
                count += sign;
                Dfs(neighbor, node, adj);
            }
        }
    }

    public int MinReorder(int n, int[][] connections) {
        var adj = new Dictionary<int, List<Tuple<int, int>>>();
        foreach (var connection in connections) {
            if (!adj.ContainsKey(connection[0])) adj[connection[0]] = new List<Tuple<int, int>>();
            if (!adj.ContainsKey(connection[1])) adj[connection[1]] = new List<Tuple<int, int>>();
            adj[connection[0]].Add(Tuple.Create(connection[1], 1));
            adj[connection[1]].Add(Tuple.Create(connection[0], 0));
        }
        Dfs(0, -1, adj);
        return count;
    }
}

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

Задача: 1135. Connecting Cities With Minimum Cost
Сложность: medium

Есть n городов, пронумерованных от 1 до n. Вам даны целое число n и массив connections, где connections[i] = [xi, yi, costi] указывает, что стоимость соединения города xi и города yi (двунаправленное соединение) равна costi.

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

Стоимость - это сумма использованных стоимостей соединений.

Пример:

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.

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

1⃣Сортировка рёбер:
Отсортируйте все соединения (рёбра) в графе по их весам (стоимости) в порядке возрастания.

2⃣Итерация по рёбрам и объединение:
Используйте структуру данных Disjoint Set (Union-Find) для проверки циклов и объединения поддеревьев. Для каждого ребра проверьте, принадлежат ли его концы разным поддеревьям, и если да, объедините их, добавив ребро в минимальное остовное дерево (MST).

3⃣Проверка соединённости:
Подсчитайте количество рёбер в MST. Если оно меньше n-1, верните -1, так как соединить все города невозможно. Иначе верните суммарную стоимость рёбер в MST.

😎 Решение:

public class DisjointSet {
    private int[] parent;

    public DisjointSet(int n) {
        parent = new int[n + 1];
        for (int i = 0; i <= n; ++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) {
            parent[rootY] = rootX;
        }
    }
}

public class Solution {
    public int MinimumCost(int n, int[][] connections) {
        Array.Sort(connections, (a, b) => a[2].CompareTo(b[2]));
        DisjointSet disjointSet = new DisjointSet(n);
        int totalCost = 0;
        int edgesUsed = 0;

        foreach (var connection in connections) {
            int x = connection[0];
            int y = connection[1];
            int cost = connection[2];

            if (disjointSet.Find(x) != disjointSet.Find(y)) {
                disjointSet.Union(x, y);
                totalCost += cost;
                edgesUsed++;
                if (edgesUsed == n - 1) {
                    return totalCost;
                }
            }
        }
        return edgesUsed == n - 1 ? totalCost : -1;
    }
}

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

Задача: 235. Lowest Common Ancestor of a Binary Search Tree
Сложность: medium

Дано бинарное дерево поиска (BST). Найдите наименьший общий предок (LCA) двух заданных узлов в BST.

Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)."

Пример:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

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

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

2⃣Продолжение поиска в поддереве: Если оба узла p и q находятся в правом поддереве текущего узла, продолжайте поиск в правом поддереве, начиная с шага 1. Если оба узла p и q находятся в левом поддереве текущего узла, продолжайте поиск в левом поддереве, начиная с шага 1.

3⃣Нахождение LCA: Если узлы p и q находятся в разных поддеревьях относительно текущего узла или один из узлов равен текущему узлу, то текущий узел является наименьшим общим предком (LCA). Верните этот узел как результат.

😎 Решение:

public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int parentVal = root.val;
        int pVal = p.val;
        int qVal = q.val;

        if (pVal > parentVal && qVal > parentVal) {
            return LowestCommonAncestor(root.right, p, q);
        } else if (pVal < parentVal && qVal < parentVal) {
            return LowestCommonAncestor(root.left, p, q);
        } else {
            return root;
        }
    }
}

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

Задача: 748. Shortest Completing Word
Сложность: easy

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

Пример:

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"

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

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

2⃣Пройти по массиву words, проверяя каждое слово на соответствие требованиям.

3⃣Найти самое короткое завершающее слово среди подходящих.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public string ShortestCompletingWord(string licensePlate, string[] words) {
        var licenseCount = GetCharCount(licensePlate);

        string result = null;
        foreach (var word in words) {
            if (IsCompletingWord(word, licenseCount)) {
                if (result == null || word.Length < result.Length) {
                    result = word;
                }
            }
        }
        return result;
    }

    private Dictionary<char, int> GetCharCount(string s) {
        var count = new Dictionary<char, int>();
        foreach (var c in s.ToLower()) {
            if (char.IsLetter(c)) {
                count[c] = count.GetValueOrDefault(c, 0) + 1;
            }
        }
        return count;
    }

    private bool IsCompletingWord(string word, Dictionary<char, int> licenseCount) {
        var wordCount = new Dictionary<char, int>();
        foreach (var c in word) {
            wordCount[c] = wordCount.GetValueOrDefault(c, 0) + 1;
        }
        foreach (var entry in licenseCount) {
            if (!wordCount.ContainsKey(entry.Key) || wordCount[entry.Key] < entry.Value) {
                return false;
            }
        }
        return true;
    }
}

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