C# | LeetCode

#medium Задача: 250. Count Univalue Subtrees Дан корень бинарного дерева, верните количество поддеревьев с одинаковыми значениями. Поддерево с одинаковыми значениями означает, что все узлы поддерева имеют одно и то же значение. Пример:

Input: root = [5,1,5,5,5,null,5]
Output: 4

👨‍💻 Алгоритм: 1️⃣Создайте целочисленную переменную count для подсчета количества поддеревьев с одинаковыми значениями. Инициализируйте её значением 0. 2️⃣Выполните обход в глубину (DFS) для данного бинарного дерева. Выполните dfs(root), где dfs — это рекурсивный метод, который принимает узел TreeNode в качестве параметра, от которого начинается обход. Метод возвращает логическое значение, указывающее, является ли поддерево, укоренённое в этом узле, поддеревом с одинаковыми значениями. Выполните следующие действия в этом методе: Если узел равен null, верните true. Рекурсивно проверьте, образует ли левый потомок поддерево с одинаковыми значениями. Выполните isLeftUniValue = dfs(node.left). Рекурсивно проверьте, образует ли правый потомок поддерево с одинаковыми значениями. Выполните isRightUniValue = dfs(node.right). Если оба потомка образуют поддеревья с одинаковыми значениями, т.е. isLeftUniValue && isRightUniValue равно true, сравните значения потомков узла со значением самого узла. Если левый потомок существует и node.left.val != node.val, верните false, так как значения не совпадают и мы не имеем поддерева с одинаковыми значениями. Аналогично, если правый потомок существует и node.right.val != node.val, верните false. В противном случае, увеличьте count на 1 и верните true. В противном случае, одно или оба поддерева потомков не образуют поддеревья с одинаковыми значениями, поэтому дерево, укоренённое в node, также не может быть таким поддеревом. Верните false. 3️⃣Верните count. 😎 Решение:

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

public class Solution {
    private int count = 0;

    private bool Dfs(TreeNode node) {
        if (node == null) {
            return true;
        }

        bool isLeftUniValue = Dfs(node.left);
        bool isRightUniValue = Dfs(node.right);

        if (isLeftUniValue && isRightUniValue) {
            if (node.left != null && node.left.val != node.val) {
                return false;
            }
            if (node.right != null && node.right.val != node.val) {
                return false;
            }
            count++;
            return true;
        }
        return false;
    }

    public int CountUnivalSubtrees(TreeNode root) {
        Dfs(root);
        return count;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 249. Group Shifted Strings Выполните следующие операции сдвига на строке: Правый сдвиг: замените каждую букву следующей буквой английского алфавита, где 'z' заменяется на 'a'. Например, "abc" можно сдвинуть вправо на "bcd" или "xyz" можно сдвинуть вправо на "yza". Левый сдвиг: замените каждую букву предыдущей буквой английского алфавита, где 'a' заменяется на 'z'. Например, "bcd" можно сдвинуть влево на "abc" или "yza" можно сдвинуть влево на "xyz". Мы можем продолжать сдвигать строку в обоих направлениях, чтобы сформировать бесконечную последовательность сдвигов. Например, сдвиньте "abc", чтобы сформировать последовательность: ... <-> "abc" <-> "bcd" <-> ... <-> "xyz" <-> "yza" <-> .... <-> "zab" <-> "abc" <-> ... Вам дан массив строк strings, сгруппируйте все strings[i], которые принадлежат одной и той же последовательности сдвигов. Ответ можно вернуть в любом порядке. Пример:

Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"]

Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]

👨‍💻 Алгоритм: 1️⃣Переберите строки, и для каждой строки найдите ее хэш-значение, сдвигая все символы так, чтобы строка начиналась с 'a'. Значение сдвига равно позиции первого символа строки, и каждый символ сдвигается на это значение с учетом модуля 26. 2️⃣Сопоставьте оригинальную строку с найденным хэш-значением в карте mapHashToList, добавляя оригинальную строку в список, соответствующий ее хэш-значению. 3️⃣Переберите mapHashToList и сохраните список для каждого ключа в карте в массив ответа groups. 😎 Решение:

using System;
using System.Collections.Generic;
using System.Text;

public class Solution {
    private char ShiftLetter(char letter, int shift) {
        return (char) ((letter - shift + 26) % 26 + 'a');
    }
    
    private string GetHash(string s) {
        int shift = s[0];
        StringBuilder hashKey = new StringBuilder();
        
        foreach (char letter in s) {
            hashKey.Append(ShiftLetter(letter, shift));
        }
        
        return hashKey.ToString();
    }
    
    public IList<IList<string>> GroupStrings(IList<string> strings) {
        var mapHashToList = new Dictionary<string, IList<string>>();
        
        foreach (string str in strings) {
            string hashKey = GetHash(str);
            if (!mapHashToList.ContainsKey(hashKey)) {
                mapHashToList[hashKey] = new List<string>();
            }
            mapHashToList[hashKey].Add(str);
        }
        
        var groups = new List<IList<string>>();
        foreach (var pair in mapHashToList) {
            groups.Add(pair.Value);
        }
        
        return groups;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 247. Strobogrammatic Number II Дано целое число n, верните все стробограмматические числа длины n. Ответ можно возвращать в любом порядке. Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами). Пример:

Input: n = 2
Output: ["11","69","88","96"]

👨‍💻 Алгоритм: 1️⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа. 2️⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n: Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"]. Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns. Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n. 3️⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums. 😎 Решение:

using System;
using System.Collections.Generic;
using System.Text;

public class Solution {
    private List<List<char>> reversiblePairs = new List<List<char>> {
        new List<char>{'0', '0'}, new List<char>{'1', '1'}, 
        new List<char>{'6', '9'}, new List<char>{'8', '8'}, new List<char>{'9', '6'}
    };
    
    public List<string> GenerateStroboNumbers(int n, int finalLength) {
        if (n == 0) {
            return new List<string> { "" };
        }
        
        if (n == 1) {
            return new List<string> { "0", "1", "8" };
        }
        
        List<string> prevStroboNums = GenerateStroboNumbers(n - 2, finalLength);
        List<string> currStroboNums = new List<string>();
        
        foreach (string prevStroboNum in prevStroboNums) {
            foreach (List<char> pair in reversiblePairs) {
                if (pair[0] != '0' || n != finalLength) {
                    currStroboNums.Add(pair[0] + prevStroboNum + pair[1]);
                }
            }
        }
        
        return currStroboNums;
    }
    
    public List<string> FindStrobogrammatic(int n) {
        return GenerateStroboNumbers(n, n);
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#easy Задача: 246. Strobogrammatic Number Дана строка num, представляющая собой целое число. Верните true, если num является стробограмматическим числом. Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами). Пример:

Input: num = "69"
Output: true

👨‍💻 Алгоритм: 1️⃣Создайте новую строку, перебирая оригинальную строку num в обратном порядке. Для каждого символа проверьте, является ли он допустимым для поворота (0, 1, 6, 8, 9). Если символ недопустим (2, 3, 4, 5, 7), немедленно верните false. 2️⃣Для каждого допустимого символа добавьте его соответствующее значение после поворота (0 ⟶ 0, 1 ⟶ 1, 6 ⟶ 9, 8 ⟶ 8, 9 ⟶ 6) в новую строку. 3️⃣Сравните полученную строку с исходной строкой num. Если они равны, верните true, в противном случае верните false. 😎 Решение:

using System.Text;

public class Solution {
    public bool IsStrobogrammatic(string num) {
        StringBuilder rotated = new StringBuilder();
        for (int i = num.Length - 1; i >= 0; i--) {
            char c = num[i];
            if (c == '0' || c == '1' || c == '8') {
                rotated.Append(c);
            } else if (c == '6') {
                rotated.Append('9');
            } else if (c == '9') {
                rotated.Append('6');
            } else {
                return false;
            }
        }
        return num == rotated.ToString();
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 245. Shortest Word Distance II Дан массив строк wordsDict и две строки word1 и word2, которые уже существуют в массиве. Верните наименьшее расстояние между вхождениями этих двух слов в списке. Обратите внимание, что word1 и word2 могут быть одинаковыми. Гарантируется, что они представляют собой два отдельных слова в списке. Пример:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

👨‍💻 Алгоритм: 1️⃣Переберите список wordsDict и сохраните индексы слова word1 в список indices1 и индексы слова word2 в список indices2. Инициализируйте переменную shortestDistance = INT_MAX. 2️⃣Переберите индексы в списке indices1 и для каждого индекса найдите верхнюю границу в списке indices2, используя бинарный поиск, и сохраните этот индекс в переменную x. Рассмотрите индексы indices2[x] и indices2[x - 1], обновляя shortestDistance, если индексы не совпадают. 3️⃣Верните значение переменной shortestDistance. 😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int ShortestWordDistance(string[] wordsDict, string word1, string word2) {
        List<int> indices1 = new List<int>();
        List<int> indices2 = new List<int>();
        for (int i = 0; i < wordsDict.Length; i++) {
            if (wordsDict[i] == word1) {
                indices1.Add(i);
            }
            if (wordsDict[i] == word2) {
                indices2.Add(i);
            }
        }

        int shortestDistance = int.MaxValue;
        foreach (int index in indices1) {
            int x = indices2.BinarySearch(index);
            if (x < 0) {
                x = ~x;
            }
            if (x < indices2.Count) {
                shortestDistance = Math.Min(shortestDistance, indices2[x] - index);
            }
            if (x > 0 && indices2[x - 1] != index) {
                shortestDistance = Math.Min(shortestDistance, index - indices2[x - 1]);
            }
        }
        return shortestDistance;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 244. Shortest Word Distance II Создайте структуру данных, которая будет инициализироваться массивом строк, а затем должна отвечать на запросы о наименьшем расстоянии между двумя разными строками из массива. Реализуйте класс WordDistance: WordDistance(String[] wordsDict) инициализирует объект с массивом строк wordsDict. int shortest(String word1, String word2) возвращает наименьшее расстояние между word1 и word2 в массиве wordsDict. Пример:

Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]
Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");    // return 1

👨‍💻 Алгоритм: 1️⃣В конструкторе класса переберите заданный список слов и создайте словарь, сопоставляя слово с его позициями в массиве. Поскольку мы обрабатываем слова слева направо, индексы будут по умолчанию отсортированы для всех слов. 2️⃣Для данной пары слов получите список индексов (вхождений в исходный массив слов). Назовём эти два массива loc1 и loc2. Инициализируйте две переменные-указателя l1 = 0 и l2 = 0. 3️⃣Для данных l1 и l2 обновите (если возможно) минимальную разницу (расстояние) до текущего момента, т.е. dist = min(dist, abs(loc1[l1] - loc2[l2])). Затем проверьте, если loc1[l1] < loc2[l2], и если это так, переместите l1 на один шаг вперёд, т.е. l1 = l1 + 1. В противном случае, переместите l2 на один шаг вперёд, т.е. l2 = l2 + 1. Продолжайте это делать, пока все элементы в меньшем из двух массивов позиций не будут обработаны. Верните глобальное минимальное расстояние между словами. 😎 Решение:

using System;
using System.Collections.Generic;

public class WordDistance {
    private Dictionary<string, List<int>> locations;

    public WordDistance(string[] words) {
        locations = new Dictionary<string, List<int>>();
        for (int i = 0; i < words.Length; i++) {
            if (!locations.ContainsKey(words[i])) {
                locations[words[i]] = new List<int>();
            }
            locations[words[i]].Add(i);
        }
    }

    public int Shortest(string word1, string word2) {
        List<int> loc1 = locations[word1];
        List<int> loc2 = locations[word2];
        int l1 = 0, l2 = 0, minDiff = int.MaxValue;

        while (l1 < loc1.Count && l2 < loc2.Count) {
            minDiff = Math.Min(minDiff, Math.Abs(loc1[l1] - loc2[l2]));
            if (loc1[l1] < loc2[l2]) {
                l1++;
            } else {
                l2++;
            }
        }
        return minDiff;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#easy Задача: 243. Shortest Word Distance Дан массив строк wordsDict и две разные строки, которые уже существуют в массиве: word1 и word2. Верните кратчайшее расстояние между этими двумя словами в списке. Пример:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Output: 3

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

public class Solution {
    public int ShortestDistance(string[] words, string word1, string word2) {
        int minDistance = words.Length;
        for (int i = 0; i < words.Length; i++) {
            if (words[i] == word1) {
                for (int j = 0; j < words.Length; j++) {
                    if (words[j] == word2) {
                        minDistance = Math.Min(minDistance, Math.Abs(i - j));
                    }
                }
            }
        }
        return minDistance;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#easy Задача: 242. Valid Anagram Даны две строки s и t, верните true, если t является анаграммой s, и false в противном случае. Анаграмма — это слово или фраза, сформированная путём перестановки букв другого слова или фразы, обычно используя все исходные буквы ровно один раз. Пример:

Input: s = "anagram", t = "nagaram"
Output: true

👨‍💻 Алгоритм: 1️⃣Создайте массив размером 26 для подсчета частот каждой буквы (поскольку s и t содержат только буквы от 'a' до 'z'). 2️⃣Пройдитесь по строке s, увеличивая счетчик соответствующей буквы. Затем пройдитесь по строке t, уменьшая счетчик для каждой буквы. 3️⃣Проверьте, не опустился ли счетчик ниже нуля во время обхода строки t. Если это произошло, значит в t есть лишняя буква, которой нет в s, и следует вернуть false. Если после проверки всех букв все счетчики равны нулю, возвращайте true, указывая на то, что t является анаграммой s. 😎 Решение:

public bool IsAnagram(string s, string t) {
    if (s.Length != t.Length) {
        return false;
    }
    int[] table = new int[26];
    for (int i = 0; i < s.Length; i++) {
        table[s[i] - 'a']++;
        table[t[i] - 'a']--;
    }
    foreach (int count in table) {
        if (count != 0) return false;
    }
    return true;
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 240. Search a 2D Matrix II Напишите эффективный алгоритм, который ищет значение target в матрице целых чисел размером m на n. У этой матрицы есть следующие свойства: Целые числа в каждой строке отсортированы по возрастанию слева направо. Целые числа в каждом столбце отсортированы по возрастанию сверху вниз. Пример:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

👨‍💻 Алгоритм: 1️⃣Проверка матрицы: Перед началом поиска убедитесь, что матрица не пуста и не содержит null. 2️⃣Итерация по диагоналям: Итерируйте по диагоналям матрицы, используя инвариант отсортированности срезов строк и столбцов, начиная с текущей позиции (строка, столбец). Для каждого такого среза используйте бинарный поиск для нахождения целевого значения. 3️⃣Бинарный поиск и завершение: Продолжайте бинарный поиск до тех пор, пока не исчерпаете все диагонали (в этом случае возвращается False) или пока не найдете целевое значение (в этом случае возвращается True). Функция бинарного поиска должна уметь работать как с рядами, так и с колонками матрицы. 😎 Решение:

public class Solution {
    private bool BinarySearch(int[,] matrix, int target, int start, bool vertical) {
        int lo = start;
        int hi = vertical ? matrix.GetLength(1) - 1 : matrix.GetLength(0) - 1;

        while (hi >= lo) {
            int mid = (lo + hi) / 2;
            int value = vertical ? matrix[start, mid] : matrix[mid, start];
            if (value < target) {
                lo = mid + 1;
            } else if (value > target) {
                hi = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }

    public bool SearchMatrix(int[,] matrix, int target) {
        if (matrix == null || matrix.Length == 0) return false;

        int shorterDim = Math.Min(matrix.GetLength(0), matrix.GetLength(1));
        for (int i = 0; i < shorterDim; i++) {
            if (BinarySearch(matrix, target, i, true) || BinarySearch(matrix, target, i, false)) {
                return true;
            }
        }
        return false;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#easy Задача: 263. Ugly Number Уродливое число — это положительное целое число, простые множители которого ограничены числами 2, 3 и 5. Дано целое число n, верните true, если n является уродливым числом. Пример:

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

👨‍💻 Алгоритм: 1️⃣Если данное целое число n неположительное, верните false, так как неположительное число не может быть уродливым. 2️⃣Определите функцию keepDividingWhenDivisible, которая принимает два аргумента: делимое и делитель. Эта функция будет делить делимое на делитель до тех пор, пока оно делится без остатка. Функция возвращает измененное делимое. Последовательно примените эту функцию к n с делителями 2, 3 и 5. 3️⃣Если после всех делений n равно 1, верните true, иначе верните false. 😎 Решение:

public class Solution {
    public bool IsUgly(int n) {
        if (n <= 0) {
            return false;
        }
        foreach (int factor in new int[] {2, 3, 5}) {
            n = KeepDividingWhenDivisible(n, factor);
        }
        return n == 1;
    }

    private int KeepDividingWhenDivisible(int dividend, int divisor) {
        while (dividend % divisor == 0) {
            dividend /= divisor;
        }
        return dividend;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых