Задача: 670. Maximum Swap
Сложность: medium

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

Верните число с наибольшим значением, которое можно получить.

Пример:

Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

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

1⃣Сохраняем кандидатов как списки длины len(num). Для каждой пары позиций (i, j) выполняем обмен цифр, записываем кандидата, если он больше текущего ответа, затем возвращаем цифры обратно.

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

3⃣Возвращаем максимальное значение из всех кандидатов.

😎 Решение:

public class Solution {
    public int MaximumSwap(int num) {
        char[] A = num.ToString().ToCharArray();
        char[] ans = (char[])A.Clone();
        for (int i = 0; i < A.Length; i++) {
            for (int j = i + 1; j < A.Length; j++) {
                char tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
                for (int k = 0; k < A.Length; k++) {
                    if (A[k] != ans[k]) {
                        if (A[k] > ans[k]) {
                            ans = (char[])A.Clone();
                        }
                        break;
                    }
                }
                A[j] = A[i];
                A[i] = tmp;
            }
        }
        return int.Parse(new string(ans));
    }
}

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

Задача: 1233. Remove Sub-Folders from the Filesystem
Сложность: medium

Если дан список папок folder, верните папки после удаления всех вложенных папок в этих папках. Вы можете вернуть ответ в любом порядке. Если папка[i] находится внутри другой папки[j], она называется ее вложенной папкой. Формат пути - это одна или несколько скомбинированных строк вида: '/', за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" являются допустимыми путями, а пустая строка и "/" - нет.

Пример:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]

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

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

2⃣Фильтрация вложенных папок:
Будем использовать переменную для отслеживания текущей родительской папки.

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

😎 Решение:

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

public class Solution {
    public IList<string> RemoveSubfolders(string[] folder) {
        Array.Sort(folder);
        List<string> result = new List<string>();
        string parent = "";
        
        foreach (var path in folder) {
            if (parent == "" || !path.StartsWith(parent + "/")) {
                parent = path;
                result.Add(path);
            }
        }
        
        return result;
    }
}

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

Задача: 896. Monotonic Array
Сложность: easy

Массив является монотонным, если он либо монотонно возрастает, либо монотонно убывает. Массив nums является монотонно возрастающим, если для всех i <= j, nums[i] <= nums[j]. Массив nums является монотонно убывающим, если для всех i <= j, nums[i] >= nums[j]. Если задан целочисленный массив nums, верните true, если данный массив монотонный, или false в противном случае.

Пример:

Input: nums = [1,2,2,3]
Output: true

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

1⃣Определить два флага: increasing и decreasing.

2⃣Пройтись по массиву: Если текущий элемент больше следующего, установить increasing в false. Если текущий элемент меньше следующего, установить decreasing в false.

3⃣Вернуть true, если хотя бы один из флагов true, иначе вернуть false.

😎 Решение:

public class Solution {
    public bool IsMonotonic(int[] nums) {
        bool increasing = true, decreasing = true;
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] > nums[i - 1]) decreasing = false;
            if (nums[i] < nums[i - 1]) increasing = false;
        }
        return increasing || decreasing;
    }

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

Задача: 782. Transform to Chessboard
Сложность: hard

Дана бинарная сетка размером n x n. В каждом ходе можно поменять местами любые две строки или любые два столбца.

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

Шахматная доска — это доска, на которой ни один 0 и ни одна 1 не соприкасаются друг с другом по вертикали и горизонтали.

Пример:

Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
Output: 2
Explanation: One potential sequence of moves is shown.
The first move swaps the first and second column.
The second move swaps the second and third row.

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

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

2⃣Затем для каждой возможной идеальной трансформации этой линии найдите минимальное количество перестановок, чтобы преобразовать эту линию в её идеальную и добавьте это к ответу. Например, [0, 1, 1, 1, 0, 0] имеет два идеала [0, 1, 0, 1, 0, 1] или [1, 0, 1, 0, 1, 0]; но [0, 1, 1, 1, 0] имеет только один идеал [1, 0, 1, 0, 1].

3⃣В Java мы используем целые числа для представления строк как двоичных чисел. Мы проверяем количество различий с [1, 0, 1, 0, 1, 0, ...] с помощью побитового исключающего ИЛИ с 0b010101010101.....01 = 0x55555555. Чтобы убедиться, что мы не добавляем излишне большие элементы.

😎 Решение:

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

public class Solution {
    public int MovesToChessboard(int[][] board) {
        int N = board.Length;
        int ans = 0;
        
        foreach (var count in new List<Dictionary<string, int>> { GetCount(board), GetCount(Transpose(board)) }) {
            if (count.Count != 2 || !new List<int>(count.Values).OrderBy(v => v).SequenceEqual(new List<int> { N / 2, (N + 1) / 2 })) {
                return -1;
            }

            var lines = count.Keys.ToList();
            string line1 = lines[0];
            string line2 = lines[1];
            if (!AllOpposite(line1, line2)) {
                return -1;
            }

            List<int> starts = N % 2 == 0 ? new List<int> { 0, 1 } : new List<int> { line1.Count(c => c == '1') * 2 > N ? 1 : 0 };

            ans += starts.Select(start => line1.Where((c, i) => (c - '0') != (i % 2 == start ? 1 : 0)).Count()).Min() / 2;
        }
        
        return ans;
    }

    private Dictionary<string, int> GetCount(int[][] board) {
        var count = new Dictionary<string, int>();
        foreach (var row in board) {
            var key = string.Join("", row);
            if (count.ContainsKey(key)) {
                count[key]++;
            } else {
                count[key] = 1;
            }
        }
        return count;
    }

    private int[][] Transpose(int[][] board) {
        int N = board.Length;
        var transposed = new int[N][];
        for (int i = 0; i < N; i++) {
            transposed[i] = new int[N];
            for (int j = 0; j < N; j++) {
                transposed[i][j] = board[j][i];
            }
        }
        return transposed;
    }

    private bool AllOpposite(string line1, string line2) {
        for (int i = 0; i < line1.Length; i++) {
            if ((line1[i] ^ line2[i]) == 0) {
                return false;
            }
        }
        return true;
    }
}

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

Задача: 1263. Minimum Moves to Move a Box to Their Target Location
Сложность: hard

Кладовщик - это игра, в которой игрок перемещает коробки по складу, пытаясь доставить их в целевые места. Игра представлена сеткой символов m x n, где каждый элемент - это стена, пол или коробка. Ваша задача - переместить коробку "B" в целевую позицию "T" по следующим правилам: символ "S" представляет игрока. Игрок может перемещаться вверх, вниз, влево, вправо по сетке, если это пол (пустая клетка). Символ '.' обозначает пол, что означает свободную клетку для ходьбы. Символ '#' обозначает стену, что означает препятствие (туда невозможно пройти). В сетке есть только одна коробка 'B' и одна целевая клетка 'T'. Коробку можно переместить на соседнюю свободную клетку, стоя рядом с коробкой, а затем двигаясь в направлении коробки. Это толчок. Игрок не может пройти через коробку. Верните минимальное количество толчков, чтобы переместить коробку к цели. Если нет возможности добраться до цели, верните -1.

Пример:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3

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

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

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

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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int MinPushBox(char[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int[][] directions = new int[][] {
            new int[] {-1, 0}, new int[] {1, 0}, new int[] {0, -1}, new int[] {0, 1}
        };
        
        Func<int, int, bool> isValid = (x, y) => x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != '#';
        
        int px = 0, py = 0, bx = 0, by = 0, tx = 0, ty = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'S') {
                    px = i;
                    py = j;
                } else if (grid[i][j] == 'B') {
                    bx = i;
                    by = j;
                } else if (grid[i][j] == 'T') {
                    tx = i;
                    ty = j;
                }
            }
        }
        
        Queue<int[]> queue = new Queue<int[]>();
        HashSet<string> visited = new HashSet<string>();
        
        queue.Enqueue(new int[] {px, py, bx, by, 0});
        visited.Add($"{px},{py},{bx},{by}");
        
        while (queue.Count > 0) {
            int[] state = queue.Dequeue();
            int px = state[0], py = state[1], bx = state[2], by = state[3], pushes = state[4];
            if (bx == tx && by == ty) {
                return pushes;
            }
            foreach (var dir in directions) {
                int npx = px + dir[0], npy = py + dir[1];
                if (isValid(npx, npy)) {
                    if (npx == bx && npy == by) {
                        int nbx = bx + dir[0], nby = by + dir[1];
                        if (isValid(nbx, nby) && visited.Add($"{npx},{npy},{nbx},{nby}")) {
                            queue.Enqueue(new int[] {npx, npy, nbx, nby, pushes + 1});
                        }
                    } else if (visited.Add($"{npx},{npy},{bx},{by}")) {
                        queue.Enqueue(new int[] {npx, npy, bx, by, pushes});
                    }
                }
            }
        }
        
        return -1;
    }
}

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

Задача: 636. Exclusive Time of Functions
Сложность: medium

На однопоточном процессоре выполняется программа, содержащая n функций. Каждая функция имеет уникальный ID от 0 до n-1. Вызовы функций хранятся в стеке вызовов: когда начинается вызов функции, ее ID заталкивается в стек, а когда вызов функции заканчивается, ее ID выгружается из стека. Функция, чей идентификатор находится в верхней части стека, является текущей выполняемой функцией. Каждый раз, когда функция запускается или завершается, мы пишем лог с идентификатором, началом или завершением и меткой времени. Вам предоставляется список logs, где logs[i] представляет собой i-е сообщение лога, отформатированное как строка "{function_id}:{"start" | "end"}:{timestamp}". Например, "0:start:3" означает, что вызов функции с идентификатором 0 начался в начале временной метки 3, а "1:end:2" означает, что вызов функции с идентификатором 1 завершился в конце временной метки 2. Обратите внимание, что функция может быть вызвана несколько раз, возможно, рекурсивно. Исключительное время функции - это сумма времен выполнения всех вызовов функции в программе. Например, если функция вызывается дважды, причем один вызов выполняется за 2 единицы времени, а другой - за 1 единицу, то эксклюзивное время равно 2 + 1 = 3. Верните эксклюзивное время каждой функции в массив, где значение по i-му индексу представляет собой эксклюзивное время для функции с идентификатором i.

Пример:

Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3,4]

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

1⃣Парсинг логов
Пройдитесь по каждому логу, чтобы распознать действие (start или end) и идентификатор функции вместе с временной меткой.

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

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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int[] ExclusiveTime(int n, IList<string> logs) {
        Stack<int> stack = new Stack<int>();
        int[] times = new int[n];
        int prevTime = 0;
        
        foreach (string log in logs) {
            string[] parts = log.Split(':');
            int fid = int.Parse(parts[0]);
            string type = parts[1];
            int time = int.Parse(parts[2]);
            
            if (type == "start") {
                if (stack.Count > 0) {
                    times[stack.Peek()] += time - prevTime;
                }
                stack.Push(fid);
                prevTime = time;
            } else {
                times[stack.Pop()] += time - prevTime + 1;
                prevTime = time + 1;
            }
        }
        
        return times;
    }
}

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

Задача: 490. The Maze
Сложность: medium

В лабиринте есть шар, который может перемещаться по пустым пространствам (представленным как 0) и стенам (представленным как 1). Шар может катиться по пустым пространствам вверх, вниз, влево или вправо, но он не остановится до тех пор, пока не наткнется на стену. Когда шар останавливается, он может выбрать следующее направление.

Дан лабиринт размером m x n, начальная позиция шара и место назначения, где start = [startrow, startcol] и destination = [destinationrow, destinationcol]. Верните true, если шар может остановиться в месте назначения, иначе верните false.
Вы можете предположить, что границы лабиринта представляют собой стены. В приведённом ниже примере они не указаны.

Пример:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.

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

1⃣Инициализация и подготовка данных
Определите количество строк и столбцов в лабиринте (m и n). Создайте 2D массив visit для отслеживания посещённых ячеек. Запустите DFS (глубокий поиск) с начальной позиции.

2⃣DFS обход
Если текущая ячейка уже посещена, верните false. Если текущая ячейка совпадает с ячейкой назначения, верните true. Отметьте текущую ячейку как посещённую. Переберите все четыре направления движения (вверх, вправо, вниз, влево): продвигайтесь в выбранном направлении до тех пор, пока не столкнётесь со стеной или границей. После остановки вызовите DFS для новой позиции.

3⃣Результат
Если любой вызов DFS возвращает true, завершите выполнение и верните true. Если ни один путь не приводит к цели, верните false.

😎 Решение:

public class Solution {
    public bool HasPath(int[][] maze, int[] start, int[] destination) {
        int m = maze.Length, n = maze[0].Length;
        bool[,] visit = new bool[m, n];
        return Dfs(m, n, maze, start, destination, visit);
    }

    private bool Dfs(int m, int n, int[][] maze, int[] curr, int[] destination, bool[,] visit) {
        if (visit[curr[0], curr[1]]) return false;
        if (curr.SequenceEqual(destination)) return true;
        visit[curr[0], curr[1]] = true;
        int[][] directions = new int[][] { new int[] {-1, 0}, new int[] {1, 0}, new int[] {0, -1}, new int[] {0, 1} };
        foreach (var dir in directions) {
            int r = curr[0], c = curr[1];
            while (r >= 0 && r < m && c >= 0 && c < n && maze[r][c] == 0) {
                r += dir[0];
                c += dir[1];
            }
            int[] newCurr = new int[] { r - dir[0], c - dir[1] };
            if (Dfs(m, n, maze, newCurr, destination, visit)) return true;
        }
        return false;
    }
}

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

Задача: 36. Valid Sudoku
Сложность: medium

Определите, является ли доска Судоку размером 9x9 валидной. Нужно проверить только заполненные ячейки:

- В каждой строке цифры 1-9 должны быть без повторений.
- В каждом столбце цифры 1-9 должны быть без повторений.
- В каждом 3x3 блоке цифры 1-9 должны быть без повторений.

Пример:

Input: board =  
[["5","3",".",".","7",".",".",".","."]  
,["6",".",".","1","9","5",".",".","."]  
,[".","9","8",".",".",".",".","6","."]  
,["8",".",".",".","6",".",".",".","3"]  
,["4",".",".","8",".","3",".",".","1"]  
,["7",".",".",".","2",".",".",".","6"]  
,[".","6",".",".",".",".","2","8","."]  
,[".",".",".","4","1","9",".",".","5"]  
,[".",".",".",".","8",".",".","7","9"]]  
Output: true  

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

1⃣Создайте три массива множеств: для строк, столбцов и блоков 3x3.

2⃣Проходя по каждой ячейке и проверяя, не встречалось ли число в соответствующей строке, столбце или блоке

3⃣Если не встретилось — добавить и продолжить; если встреча состоялась — вернуть false

😎 Решение:

public class Solution {
    public bool IsValidSudoku(char[][] board) {
        int N = 9;
        HashSet<char>[] rows = new HashSet<char>[N];
        HashSet<char>[] cols = new HashSet<char>[N];
        HashSet<char>[] boxes = new HashSet<char>[N];

        for (int i = 0; i < N; i++) {
            rows[i] = new HashSet<char>();
            cols[i] = new HashSet<char>();
            boxes[i] = new HashSet<char>();
        }

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                char val = board[r][c];
                if (val == '.') continue;

                if (rows[r].Contains(val) || cols[c].Contains(val) || boxes[(r / 3) * 3 + c / 3].Contains(val)) {
                    return false;
                }

                rows[r].Add(val);
                cols[c].Add(val);
                boxes[(r / 3) * 3 + c / 3].Add(val);
            }
        }

        return true;
    }
}

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

Задача: 130. Surrounded Regions
Сложность: medium

Вам дана матрица размером m на n, которая содержит буквы 'X' и 'O'. Захватите регионы, которые окружены:

Соединение: Ячейка соединена с соседними ячейками по горизонтали или вертикали.
Регион: Для формирования региона соедините каждую ячейку 'O'.
Окружение: Регион окружён ячейками 'X', если можно соединить регион с ячейками 'X', и ни одна из ячеек региона не находится на краю доски.
Окруженный регион захватывается путём замены всех 'O' на 'X' в исходной матрице.

Пример:

Input: board = [["X"]]

Output: [["X"]]

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

1⃣Выбор начальных ячеек и инициация DFS:
Начинаем с выбора всех ячеек, расположенных на границах доски.
Затем, начиная с каждой выбранной ячейки на границе, выполняем обход в глубину (DFS).

2⃣Логика и выполнение DFS:
Если ячейка на границе оказывается 'O', это означает, что эта ячейка "жива", вместе с другими ячейками 'O', соединёнными с этой граничной ячейкой. Две ячейки считаются соединёнными, если между ними существует путь, состоящий только из букв 'O'.
Цель нашего обхода DFS будет заключаться в том, чтобы отметить все такие связанные ячейки 'O', которые исходят из границы, каким-либо отличительным символом, например, 'E'.

3⃣Классификация и финальная обработка ячеек:
После обхода всех граничных ячеек мы получаем три типа ячеек:
Ячейки с буквой 'X': эти ячейки можно считать стеной.
Ячейки с буквой 'O': эти ячейки не затрагиваются в нашем обходе DFS, то есть они не имеют соединения с границей, следовательно, они захвачены. Эти ячейки следует заменить на букву 'X'.
Ячейки с буквой 'E': это ячейки, отмеченные в ходе нашего обхода DFS, то есть ячейки, имеющие хотя бы одно соединение с границами, следовательно, они не захвачены. В результате мы должны вернуть этим ячейкам их исходную букву 'O'.

😎 Решение:

public class Solution {
    public void Solve(char[][] board) {
        if (board == null || board.Length == 0) {
            return;
        }

        this.ROWS = board.Length;
        this.COLS = board[0].Length;
        List<int[]> borders = new List<int[]>();
        for (int r = 0; r < this.ROWS; ++r) {
            borders.Add(new int[] { r, 0 });
            borders.Add(new int[] { r, this.COLS - 1 });
        }

        for (int c = 0; c < this.COLS; ++c) {
            borders.Add(new int[] { 0, c });
            borders.Add(new int[] { this.ROWS - 1, c });
        }

        foreach (var pair in borders) {
            this.DFS(board, pair[0], pair[1]);
        }

        for (int r = 0; r < this.ROWS; ++r) {
            for (int c = 0; c < this.COLS; ++c) {
                if (board[r][c] == 'O')
                    board[r][c] = 'X';
                if (board[r][c] == 'E')
                    board[r][c] = 'O';
            }
        }
    }

    int ROWS, COLS;

    protected void DFS(char[][] board, int row, int col) {
        if (board[row][col] != 'O')
            return;
        board[row][col] = 'E';
        if (col < this.COLS - 1)
            DFS(board, row, col + 1);
        if (row < this.ROWS - 1)
            DFS(board, row + 1, col);
        if (col > 0)
            DFS(board, row, col - 1);
        if (row > 0)
            DFS(board, row - 1, col);
    }
}

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

🔥 Записал видос "Как за 3 минуты настроить Автоотклики на вакансии HeadHunter" больше не придется заниматься этой унылой рутиной

📺 Видео: https://youtu.be/G_FOwEGPwlw

Задача: 200. Number of Islands
Сложность: medium

Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов.

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

Пример:

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

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

1⃣Линейно просканируйте двумерную карту, если узел содержит '1', то это корневой узел, который запускает поиск в глубину (DFS).

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

3⃣Подсчитайте количество корневых узлов, запускающих DFS. Это количество будет равно количеству островов, так как каждый DFS, начинающийся с какого-либо корня, идентифицирует остров.

😎 Решение:

public class Solution {
    private void Dfs(char[][] grid, int r, int c) {
        int nr = grid.Length;
        int nc = grid[0].Length;

        grid[r][c] = '0';
        if (r - 1 >= 0 && grid[r - 1][c] == '1') Dfs(grid, r - 1, c);
        if (r + 1 < nr && grid[r + 1][c] == '1') Dfs(grid, r + 1, c);
        if (c - 1 >= 0 && grid[r][c - 1] == '1') Dfs(grid, r, c - 1);
        if (c + 1 < nc && grid[r][c + 1] == '1') Dfs(grid, r, c + 1);
    }

    public int NumIslands(char[][] grid) {
        int nr = grid.Length;
        if (nr == 0) return 0;
        int nc = grid[0].Length;

        int numIslands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    numIslands++;
                    Dfs(grid, r, c);
                }
            }
        }

        return numIslands;
    }
}

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

Задача: 976. Largest Perimeter Triangle
Сложность: easy

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

Пример:

Input: nums = [1,2,1,10]
Output: 0
Explanation: 
You cannot use the side lengths 1, 1, and 2 to form a triangle.
You cannot use the side lengths 1, 1, and 10 to form a triangle.
You cannot use the side lengths 1, 2, and 10 to form a triangle.
As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

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

1⃣Отсортируйте массив nums в порядке возрастания.

2⃣Для каждого элемента c в массиве, начиная с конца: Выберите два наибольших возможных значения a и b, которые находятся перед c в отсортированном массиве (т.е. значения, смежные с c). Проверьте, образуют ли a, b и c треугольник (условие треугольника: a + b > c). Если образуют, верните их сумму как периметр треугольника.

3⃣Если не удалось найти такие значения, верните 0.

😎 Решение:

public class Solution {
    public int LargestPerimeter(int[] A) {
        Array.Sort(A);
        for (int i = A.Length - 3; i >= 0; --i)
            if (A[i] + A[i + 1] > A[i + 2])
                return A[i] + A[i + 1] + A[i + 2];
        return 0;
    }
}

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

Задача: 145. Binary Tree Postorder Traversal
Сложность: easy

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

Пример:

Input: root = [1,null,2,3]
Output: [3,2,1]

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

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

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

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

😎 Решение:

public class Solution {
    public IList<int> PostorderTraversal(TreeNode root) {
        List<int> output = new List<int>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if (root == null)
            return output;
        stack.Push(root);
        while (stack.Count > 0) {
            root = stack.Pop();
            output.Add(root.val);
            if (root.left != null)
                stack.Push(root.left);
            if (root.right != null)
                stack.Push(root.right);
        }

        output.Reverse();
        return output;
    }
}

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

Задача: 283. Move Zeroes
Сложность: easy

Дан целочисленный массив nums. Переместите все нули в конец массива, сохраняя относительный порядок ненулевых элементов.

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

Пример:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

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

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

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

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

😎 Решение:

public class Solution {
    public void MoveZeroes(int[] nums) {
        int lastNonZeroFoundAt = 0;
        for (int cur = 0; cur < nums.Length; cur++) {
            if (nums[cur] != 0) {
                int temp = nums[lastNonZeroFoundAt];
                nums[lastNonZeroFoundAt] = nums[cur];
                nums[cur] = temp;
                lastNonZeroFoundAt++;
            }
        }
    }
}

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

Задача: 310. Minimum Height Trees
Сложность: medium

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

Дано дерево из n узлов, помеченных от 0 до n - 1, и массив из n - 1 ребер, где edges[i] = [ai, bi] указывает на наличие неориентированного ребра между узлами ai и bi в дереве. Вы можете выбрать любой узел дерева в качестве корня. Когда вы выбираете узел x в качестве корня, дерево имеет высоту h. Среди всех возможных корневых деревьев те, которые имеют минимальную высоту (то есть min(h)), называются деревьями с минимальной высотой (MHT).

Верните список всех меток корней MHT. Вы можете вернуть ответ в любом порядке.

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

Пример:

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

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

1⃣Создание списка смежности
Создайте список смежности, представляющий граф.

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

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

😎 Решение:

public class Solution {
    public IList<int> FindMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return new List<int> { 0 };
        
        var adj = new List<HashSet<int>>();
        for (int i = 0; i < n; i++) adj.Add(new HashSet<int>());
        foreach (var edge in edges) {
            adj[edge[0]].Add(edge[1]);
            adj[edge[1]].Add(edge[0]);
        }
        
        var leaves = new List<int>();
        for (int i = 0; i < n; i++) {
            if (adj[i].Count == 1) leaves.Add(i);
        }
        
        int remainingNodes = n;
        while (remainingNodes > 2) {
            remainingNodes -= leaves.Count;
            var newLeaves = new List<int>();
            foreach (var leaf in leaves) {
                var neighbor = adj[leaf].First();
                adj[neighbor].Remove(leaf);
                if (adj[neighbor].Count == 1) newLeaves.Add(neighbor);
            }
            leaves = newLeaves;
        }
        
        return leaves;
    }
}

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

Задача: 1129. Shortest Path with Alternating Colors
Сложность: medium

Вам дано целое число n, количество узлов в ориентированном графе, где узлы помечены от 0 до n - 1. Каждое ребро в этом графе может быть красным или синим, и могут быть самопетли и параллельные ребра.

Вам даны два массива redEdges и blueEdges, где:
redEdges[i] = [ai, bi] указывает, что в графе существует направленное красное ребро от узла ai к узлу bi, и
blueEdges[j] = [uj, vj] указывает, что в графе существует направленное синее ребро от узла uj к узлу vj.
Верните массив answer длины n, где каждый answer[x] — это длина кратчайшего пути от узла 0 до узла x, такого что цвета ребер чередуются вдоль пути, или -1, если такого пути не существует.

Пример:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

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

1⃣Создание структуры данных и инициализация:
Создайте список смежности adj, который будет содержать пары (сосед, цвет) для каждого узла.
Создайте массив answer длиной n, инициализированный значением -1, чтобы хранить длину кратчайшего пути для каждого узла.
Создайте 2D массив visit для отслеживания, были ли узлы посещены с использованием ребра определённого цвета.

2⃣Инициализация очереди и начальных условий:
Создайте очередь для хранения трёх значений (узел, количество шагов, цвет предыдущего ребра).
Добавьте в очередь начальный узел (0, 0, -1) и установите visit[0][0] и visit[0][1] в true, так как повторное посещение узла 0 бессмысленно.

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

😎 Решение:

public class Solution {
    public int[] ShortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        var adj = new Dictionary<int, List<(int, int)>>();
        foreach (var edge in redEdges) {
            if (!adj.ContainsKey(edge[0])) adj[edge[0]] = new List<(int, int)>();
            adj[edge[0]].Add((edge[1], 0));
        }
        foreach (var edge in blueEdges) {
            if (!adj.ContainsKey(edge[0])) adj[edge[0]] = new List<(int, int)>();
            adj[edge[0]].Add((edge[1], 1));
        }

        var answer = new int[n];
        Array.Fill(answer, -1);
        var visit = new bool[n, 2];
        var queue = new Queue<(int node, int steps, int prevColor)>();
        queue.Enqueue((0, 0, -1));
        answer[0] = 0;
        visit[0, 0] = true;
        visit[0, 1] = true;

        while (queue.Count > 0) {
            var (node, steps, prevColor) = queue.Dequeue();
            if (!adj.ContainsKey(node)) continue;

            foreach (var (neighbor, color) in adj[node]) {
                if (!visit[neighbor, color] && color != prevColor) {
                    if (answer[neighbor] == -1) answer[neighbor] = steps + 1;
                    visit[neighbor, color] = true;
                    queue.Enqueue((neighbor, steps + 1, color));
                }
            }
        }
        return answer;
    }
}

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

Задача: 1218. Longest Arithmetic Subsequence of Given Difference
Сложность: medium

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

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

Пример:

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

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

1⃣Инициализируйте пустой хеш-таблицу dp и установите answer = 1.

2⃣Итеративно обработайте массив arr. Для каждого элемента arr[i]:
Вычислите before_a, максимальную длину арифметической подпоследовательности, заканчивающейся на arr[i] - difference:
- если arr[i] - difference существует в dp, установите before_a = dp[arr[i] - difference].
- в противном случае, установите before_a = 0.
Установите dp[arr[i]] = before_a + 1, обновите answer как answer = max(answer, dp[arr[i]]).

3⃣Верните answer после завершения итерации.

😎 Решение:

public class Solution {
    public int LongestSubsequence(int[] arr, int difference) {
        Dictionary<int, int> dp = new Dictionary<int, int>();
        int answer = 1;
        
        foreach (int a in arr) {
            int beforeA = dp.ContainsKey(a - difference) ? dp[a - difference] : 0;
            dp[a] = beforeA + 1;
            answer = Math.Max(answer, dp[a]);
        }
        
        return answer;
    }
}

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