C# | LeetCode

Задача: 285. Inorder Successor in BST Сложность: medium Дан корень бинарного дерева поиска и узел p в нем. Верните преемника этого узла в порядке возрастания в бинарном дереве поиска (BST). Если у данного узла нет преемника в порядке возрастания в дереве, верните null. Преемник узла p — это узел с наименьшим ключом, который больше p.val. Пример:

Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

👨‍💻 Алгоритм: 1⃣Если у узла pесть правое поддерево: Ищем самый левый ((наименьший) узел в этом поддереве — это и будет преемник. 2⃣Если правого поддерева нет: Запускаем в порядке обхода от root, отслеживаем предыдущий узел. Если предыдущий узел — это p, то текущий — наш преемник. 3⃣При обходе обновляем previous, если преемник найден — сохраняем его в inorderSuccessorNode. 😎 Решение:

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

public class Solution {
    private TreeNode previous = null;
    private TreeNode inorderSuccessorNode = null;

    public TreeNode InorderSuccessor(TreeNode root, TreeNode p) {
        if (p.right != null) {
            TreeNode leftmost = p.right;
            while (leftmost.left != null) {
                leftmost = leftmost.left;
            }
            inorderSuccessorNode = leftmost;
        } else {
            InorderCase2(root, p);
        }
        return inorderSuccessorNode;
    }

    private void InorderCase2(TreeNode node, TreeNode p) {
        if (node == null) {
            return;
        }

        InorderCase2(node.left, p);

        if (previous == p && inorderSuccessorNode == null) {
            inorderSuccessorNode = node;
            return;
        }

        previous = node;

        InorderCase2(node.right, p);
    }
}

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

Задача: 190. Reverse Bits Сложность: easy Переверните биты заданного 32-битного беззнакового целого числа. Пример:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:

👨‍💻 Алгоритм: 1⃣Итерируем по байтам целого числа, используя побитовую операцию И (n & 0xff) с маской 11111111, чтобы извлечь крайний правый байт числа. 2⃣Для каждого байта сначала переворачиваем биты внутри байта с помощью функции reverseByte(byte). Затем сдвигаем перевернутые биты на их окончательные позиции. 3⃣В функции reverseByte(byte) используем технику мемоизации, которая сохраняет результат функции и возвращает его непосредственно при последующих вызовах с тем же входным значением. Мемоизация — это компромисс между использованием памяти и объемом вычислений. 😎 Решение:

using System.Collections.Generic;

public class Solution {
    private Dictionary<uint, uint> cache = new Dictionary<uint, uint>();

    public uint ReverseByte(uint byteValue) {
        if (cache.TryGetValue(byteValue, out uint cachedValue)) {
            return cachedValue;
        }
        uint value = (byteValue * 0x0202020202 & 0x010884422010) % 1023;
        cache[byteValue] = value;
        return value;
    }

    public uint ReverseBits(uint n) {
        uint ret = 0, power = 24;
        while (n != 0) {
            ret += ReverseByte(n & 0xff) << (int)power;
            n = n >> 8;
            power -= 8;
        }
        return ret;
    }
}

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

Задача: 771. Jewels and Stones Сложность: medium Вам даны строки jewels, представляющие типы камней, которые являются драгоценностями, и stones, представляющие камни, которые у вас есть. Каждый символ в stones является типом камня, который у вас есть. Вы хотите узнать, сколько из камней, которые у вас есть, также являются драгоценностями. Буквы чувствительны к регистру, поэтому "a" считается другим типом камня, чем "A". Пример:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

👨‍💻 Алгоритм: 1⃣Создайте множество из строки jewels для быстрой проверки, является ли камень драгоценностью. Это позволит эффективно проверять принадлежность каждого камня к драгоценностям. 2⃣Инициализируйте счетчик для подсчета количества камней, которые являются драгоценностями. Пройдите по каждому символу в строке stones и проверьте, содержится ли этот символ в множестве jewels. 3⃣Если символ содержится в множестве, увеличьте счетчик. В конце верните значение счетчика, которое будет количеством камней, являющихся драгоценностями. 😎 Решение:

public class Solution {
    public int NumJewelsInStones(string J, string S) {
        int ans = 0;
        foreach (char s in S)
            foreach (char j in J)
                if (j == s) {
                    ans++;
                    break;
                }
        return ans;
    }
}

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

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

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

👨‍💻 Алгоритм: 1⃣addScore(playerId, score): Если игрок уже существует в таблице лидеров, добавляем к его текущему счету новое значение. Если игрок не существует, добавляем его с заданным счетом. 2⃣top(K): Сортируем игроков по их счету в порядке убывания. Возвращаем сумму очков K лучших игроков. 3⃣reset(playerId): Устанавливаем счет игрока в 0. 😎 Решение:

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

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

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

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

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

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

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

Задача: 1365. How Many Numbers Are Smaller Than the Current Number Сложность: easy Дан массив nums. Для каждого элемента nums[i] определите, сколько чисел в массиве меньше его. То есть, для каждого nums[i] вам нужно посчитать количество допустимых j, таких что j != i и nums[j] < nums[i]. Верните ответ в виде массива. Пример:

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

👨‍💻 Алгоритм: 1⃣Создание копии и сортировка массива: Создайте отсортированную копию массива nums, чтобы легко находить количество элементов, меньших текущего. 2⃣Поиск индекса каждого элемента: Для каждого элемента nums[i] найдите его индекс в отсортированной копии массива. Этот индекс указывает количество элементов, меньших nums[i]. 3⃣Формирование ответа: Сформируйте массив ответов, где каждый элемент будет соответствовать количеству чисел, меньших текущего. 😎 Решение:

using System;
using System.Linq;

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

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

Задача: 993. Cousins in Binary Tree Сложность: easy Дан корень бинарного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, иначе верните false. Два узла бинарного дерева являются кузенами, если они находятся на одной глубине и имеют разных родителей. Обратите внимание, что в бинарном дереве корневой узел находится на глубине 0, а дети каждого узла глубины k находятся на глубине k + 1. Пример:

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

👨‍💻 Алгоритм: 1⃣Поиск глубины и родителя для каждого узла: Используйте поиск в глубину (DFS) для обхода дерева. Для каждого узла сохраняйте его глубину и родителя, если значение узла равно x или y. 2⃣Проверка условий на кузенов: Узлы являются кузенами, если они находятся на одной глубине, но имеют разных родителей. 3⃣Возврат результата: Если узлы удовлетворяют условиям на кузенов, верните true, иначе верните false. 😎 Решение:

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

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

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

Задача: 827. Making A Large Island Сложность: hard Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1. Верните размер самого большого острова в grid после выполнения этой операции. Остров — это группа 1, соединенных в 4 направлениях. Пример:

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

👨‍💻 Алгоритм: 1⃣Пройдите по матрице и пометьте каждую группу, используя уникальный индекс, и запомните её размер. 2⃣Для каждого 0 в матрице проверьте соседние группы и вычислите потенциальный размер острова, если изменить этот 0 на 1. 3⃣Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1. 😎 Решение:

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

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

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

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

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

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

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

Задача: 1318. Minimum Flips to Make a OR b Equal to c Сложность: medium Даны три положительных числа a, b и c. Верните минимальное количество переворотов, необходимых в некоторых битах a и b, чтобы сделать (a OR b == c) (побитовая операция OR). Операция переворота состоит из изменения любого отдельного бита с 1 на 0 или с 0 на 1 в их двоичном представлении. Пример:

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

👨‍💻 Алгоритм: 1⃣Инициализируйте переменную answer как 0, которая будет использоваться для отслеживания минимального количества необходимых переворотов. 2⃣Итеративно обрабатывайте каждый бит двоичного представления чисел a, b и c одновременно: Если (c & 1) == 0, обновите answer как answer += (a & 1) + (b & 1). Если (c & 1) == 1, и если оба значения a & 1 и b & 1 равны 0, увеличьте answer на 1. 3⃣Сдвигайте все числа вправо с помощью a >>= 1, b >>= 1, c >>= 1. Если все числа равны 0, верните answer, в противном случае, повторите шаги 2 и 3. 😎 Решение:

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

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

⏳ Осталось 20 мест Акция со скидкой 50% для первых 500 пользователей easyoffer подходит к концу 🔥 Узнай вопросы и задачи с собеседований в конкретных компаниях 🔥 Получи лучшие ответы и видео-примеры от middle/senior специалистов 🔥 Обходи фильтры ATS, добавив топ30 ключевых слов в свое резюме 🔥 Экономь время с помощью автоматических откликов 🔥 Подготовься идеально к интервью с тренажёрами и симуляторами Успей забрать место по акции: 👉 https://easyoffer.ru/pro

Задача: 1089. Duplicate Zeros Сложность: easy Дан массив целых чисел фиксированной длины arr, дублируйте каждое вхождение нуля, сдвигая оставшиеся элементы вправо. Учтите, что элементы за пределами длины исходного массива не записываются. Внесите указанные изменения в массив на месте и ничего не возвращайте. Пример:

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

👨‍💻 Алгоритм: 1⃣Найдите количество нулей, которые будут продублированы, назовем это possible_dups. Необходимо убедиться, что мы не считаем нули, которые будут отброшены, так как отброшенные нули не будут частью итогового массива. Количество possible_dups даст нам количество элементов, которые будут отброшены из исходного массива. В любой момент времени length_ - possible_dups — это количество элементов, которые будут включены в итоговый массив. 2⃣Обработайте крайний случай для нуля, находящегося на границе оставшихся элементов. Будьте особенно внимательны при дублировании нулей в оставшемся массиве. Следует учитывать, лежит ли ноль на границе. Этот ноль может быть учтен с возможными дубликатами или может быть просто включен в оставшиеся элементы, когда не осталось места для его дубликата. Если он является частью possible_dups, мы хотим его дублировать, в противном случае — нет. 3⃣Итерируйте массив с конца и копируйте ненулевой элемент один раз, а нулевой элемент дважды. Когда мы говорим об отбрасывании лишних элементов, это означает, что мы начинаем с левой стороны лишних элементов и начинаем перезаписывать их новыми значениями, в конечном итоге сдвигая оставшиеся элементы вправо и создавая пространство для всех дублированных элементов в массиве. 😎 Решение:

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

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

        int last = length_ - possibleDups;

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

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

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

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

👩‍💻 C# вакансии всех грейдов: удалёнка, реклок, щедрый оффер! Только с прямыми контактами в Telegram! Ноль автоотказов — живой диалог и быстрые объективные решения. 👩‍💻 C# 👩‍💻 Python 👩‍💻 Java 👣 Go 🤖 ML & DS 👩‍💻 DevOps 🔎 QA 👩‍💻 Frontend 👩‍💻 Node.js 🖥 SQL 👩‍💻 UX/UI 🖼️ PHP 👩‍💻 Mobile 📋 Analyst 💼 1C 👨‍✈️ CyberSec 👩‍💻 IT HR Подпишись чтобы не упустить свой шанс получить лучший оффер!

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

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

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

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

⏳ 90 акционных мест Акция со скидкой 50% для первых 500 пользователей easyoffer подходит к концу 🔥 Узнай вопросы и задачи с собеседований в конкретных компаниях 🔥 Получи лучшие ответы и видео-примеры от middle/senior специалистов 🔥 Обходи фильтры ATS, добавив топ30 ключевых слов в свое резюме 🔥 Экономь время с помощью автоматических откликов 🔥 Подготовься идеально к интервью с тренажёрами и симуляторами Успей забрать место по акции: 👉 https://easyoffer.ru/pro

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

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

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

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

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

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

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

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

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

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