Задача: 946. Validate Stack Sequences
Сложность: medium

Учитывая, что два целочисленных массива pushed и popped имеют разные значения, верните true, если это могло быть результатом последовательности операций push и pop на изначально пустом стеке, или false в противном случае.

Пример:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true

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

1⃣Инициализировать пустой стек.
Использовать указатель j для отслеживания текущей позиции в массиве popped.

2⃣Пройти по каждому элементу в массиве pushed:
Добавить элемент в стек.
Проверить верхний элемент стека:
Если он совпадает с текущим элементом в popped, удалить элемент из стека и увеличить указатель j.

3⃣В конце вернуть true, если указатель j достиг конца массива popped, иначе вернуть false.

😎 Решение:

public class Solution {
    public bool ValidateStackSequences(int[] pushed, int[] popped) {
        Stack<int> stack = new Stack<int>();
        int j = 0;
        foreach (int x in pushed) {
            stack.Push(x);
            while (stack.Count > 0 && j < popped.Length && stack.Peek() == popped[j]) {
                stack.Pop();
                j++;
            }
        }
        return j == popped.Length;
    }
}

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

Задача: 1101. The Earliest Moment When Everyone Become Friends
Сложность: medium

В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi.

Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b.

Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1.

Пример:

Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output: 3
Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.

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

1⃣Отсортируйте логи по времени в хронологическом порядке, так как в задаче не указано, отсортированы ли они.

2⃣Пройдитесь по отсортированным логам, применяя структуру данных "Объединение-Поиск":
Для каждого лога объедините двух участников, упомянутых в логе, с помощью функции union(a, b).
Каждое объединение добавляет новые связи между участниками.

3⃣Следите за количеством групп:
Изначально каждый участник рассматривается как отдельная группа.
Количество групп уменьшается с каждым полезным объединением.
Момент, когда количество групп уменьшается до одной, является самым ранним моментом, когда все участники становятся связанными (друзьями). Верните этот момент времени.
Если такого момента не существует, верните -1.

😎 Решение:

public class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }

    public bool Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);
        
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            return true;
        }
        return false;
    }
}

public class Solution {
    public int EarliestAcq(int[][] logs, int n) {
        Array.Sort(logs, (a, b) => a[0].CompareTo(b[0]));
        var uf = new UnionFind(n);
        int groupCount = n;
        
        foreach (var log in logs) {
            int timestamp = log[0];
            int friendA = log[1];
            int friendB = log[2];
            if (uf.Union(friendA, friendB)) {
                groupCount--;
            }
            if (groupCount == 1) {
                return timestamp;
            }
        }
        
        return -1;
    }
}

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

Задача: 244. Shortest Word Distance II
Сложность: medium

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

Реализуйте класс 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;
    }
}

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

Задача: 210. Course Schedule II
Сложность: medium

Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив.

Пример:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Объяснение: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0.
Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].

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

1⃣Инициализация и построение графа:
Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе.
Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма.

2⃣Запуск поиска в глубину (DFS):
Для каждого узла в нашем графе выполните поиск в глубину (DFS), если этот узел еще не был посещен во время DFS другого узла.
Предположим, что мы выполняем поиск в глубину для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны.

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

😎 Решение:

public class Solution {
    private const int WHITE = 1;
    private const int GRAY = 2;
    private const int BLACK = 3;

    public int[] FindOrder(int numCourses, int[][] prerequisites) {
        bool isPossible = true;
        var color = new Dictionary<int, int>();
        var adjList = new Dictionary<int, List<int>>();
        var topologicalOrder = new List<int>();

        for (int i = 0; i < numCourses; i++) color[i] = WHITE;

        foreach (var relation in prerequisites) {
            int dest = relation[0];
            int src = relation[1];
            if (!adjList.ContainsKey(src)) adjList[src] = new List<int>();
            adjList[src].Add(dest);
        }

        for (int i = 0; i < numCourses && isPossible; i++) {
            if (color[i] == WHITE) {
                Dfs(i, color, adjList, ref isPossible, topologicalOrder);
            }
        }

        if (isPossible) {
            var order = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                order[i] = topologicalOrder[numCourses - i - 1];
            }
            return order;
        } else {
            return new int[0];
        }
    }

    private void Dfs(int node, Dictionary<int, int> color, Dictionary<int, List<int>> adjList,
                     ref bool isPossible, List<int> topologicalOrder) {
        if (!isPossible) return;
        color[node] = GRAY;

        if (adjList.ContainsKey(node)) {
            foreach (int neighbor in adjList[node]) {
                if (color[neighbor] == WHITE) {
                    Dfs(neighbor, color, adjList, ref isPossible, topologicalOrder);
                } else if (color[neighbor] == GRAY) {
                    isPossible = false;
                }
            }
        }

        color[node] = BLACK;
        topologicalOrder.Add(node);
    }
}

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

Задача: 65. Valid Number
Сложность: hard

Принять символ s, определите, является ли она действительным числом.
Допустимые примеры: "2", "0089", "-0.1", "+3.14", "4.", "-0.9", "2e10", "-90E3"и др.
Недопустимые примеры: "abc", "1e", "e3", "99e2.5", "--6", "-+3"и др.

Пример:

Input: s = "0"

Output: true

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

1⃣Объявите три переменные: seenDigit, seenExponent и seenDot, установив их все в false. Перебирайте символы входной строки. Если символ является цифрой, установите seenDigit в true.

2⃣Если символ является знаком (+ или -), проверьте, является ли он первым символом ввода или предшествует ли он показателю степени (экспоненте). Если нет, верните false. Если символ является экспонентой (e или E), сначала проверьте, была ли уже видна экспонента или еще не было увидено ни одной цифры. Если что-то из этого верно, верните false. В противном случае установите seenExponent в true и сбросьте seenDigit, потому что после экспоненты должно следовать новое целое число.

3⃣Если символ — точка (.), проверьте, были ли уже видны точка или экспонента. Если да, верните false. Иначе установите seenDot в true. Если символ чему-то иначе, верните false. В конце верните значение seenDigit, потому что, например, ввод вида "21e" должен быть признан недействительным, если после e не следуют цифры.

😎 Решение:

public class Solution {
    public bool IsNumber(string s) {
        bool seenDigit = false;
        bool seenExponent = false;
        bool seenDot = false;
        for (int i = 0; i < s.Length; i++) {
            char curr = s[i];
            if (Char.IsDigit(curr)) {
                seenDigit = true;
            } else if (curr == '+' || curr == '-') {
                if (i > 0 && s[i - 1] != 'e' && s[i - 1] != 'E') {
                    return false;
                }
            } else if (curr == 'e' || curr == 'E') {
                if (seenExponent || !seenDigit) {
                    return false;
                }

                seenExponent = true;
                seenDigit = false;
            } else if (curr == '.') {
                if (seenDot || seenExponent) {
                    return false;
                }

                seenDot = true;
            } else {
                return false;
            }
        }

        return seenDigit;
    }
}

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

Задача: 930. Binary Subarrays With Sum
Сложность: medium

Если задан двоичный массив nums и целочисленная цель, верните количество непустых подмассивов с целью sum. Подмассив - это смежная часть массива.

Пример:

Input: nums = [1,0,1,0,1], goal = 2
Output: 4

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

1⃣Использовать словарь для хранения количества встреченных сумм префиксов.
Инициализировать текущую сумму и счетчик подмассивов с нулевыми значениями.

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

3⃣Вернуть счетчик подмассивов.

😎 Решение:

using System.Collections.Generic;

public class Solution {
    public int NumSubarraysWithSum(int[] nums, int goal) {
        var prefixSumCount = new Dictionary<int, int>();
        prefixSumCount[0] = 1;
        int currentSum = 0;
        int count = 0;
        
        foreach (int num in nums) {
            currentSum += num;
            if (prefixSumCount.ContainsKey(currentSum - goal)) {
                count += prefixSumCount[currentSum - goal];
            }
            if (prefixSumCount.ContainsKey(currentSum)) {
                prefixSumCount[currentSum]++;
            } else {
                prefixSumCount[currentSum] = 1;
            }
        }
        
        return count;
    }
}

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

Задача: 280. Wiggle Sort
Сложность: medium

Дан целочисленный массив nums, упорядочьте его так, чтобы nums[0] <= nums[1] >= nums[2] <= nums[3]....

Вы можете считать, что входной массив всегда имеет допустимый ответ.

Пример:

Input: nums = [3,5,2,1,6,4]
Output: [3,5,1,6,2,4]
Explanation: [1,6,2,5,3,4] is also accepted.

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

1⃣Итерируйтесь по каждому элементу с индексом i в массиве nums, начиная с 0 и до nums.length - 2, так как последний элемент не имеет следующего элемента для обмена.

2⃣Проверьте, является ли i четным и nums[i] > nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1].

3⃣Проверьте, является ли i нечетным и nums[i] < nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1].

😎 Решение:

public class Solution {
    private void Swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void WiggleSort(int[] nums) {
        for (int i = 0; i < nums.Length - 1; i++) {
            if ((i % 2 == 0 && nums[i] > nums[i + 1]) || (i % 2 == 1 && nums[i] < nums[i + 1])) {
                Swap(nums, i, i + 1);
            }
        }
    }
}

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

Задача: 836. Rectangle Overlap
Сложность: easy

Прямоугольник, выровненный по осям, представляется в виде списка [x1, y1, x2, y2], где (x1, y1) — координата его нижнего левого угла, а (x2, y2) — координата его верхнего правого угла. Его верхняя и нижняя грани параллельны оси X, а левая и правая грани параллельны оси Y.

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

Даны два выровненных по осям прямоугольника rec1 и rec2, вернуть true, если они перекрываются, в противном случае вернуть false.

Пример:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

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

1⃣Рассчитайте ширину пересечения: пересечение по оси x положительно, если min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]).

2⃣Рассчитайте высоту пересечения: пересечение по оси y положительно, если min(rec1[3], rec2[3]) > max(rec1[1], rec2[1]).

3⃣Если и ширина, и высота пересечения положительны, прямоугольники перекрываются.

😎 Решение:

public class Solution {
    public bool IsRectangleOverlap(int[] rec1, int[] rec2) {
        return Math.Min(rec1[2], rec2[2]) > Math.Max(rec1[0], rec2[0]) &&
               Math.Min(rec1[3], rec2[3]) > Math.Max(rec1[1], rec2[1]);
    }
}

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

Задача: 918. Maximum Sum Circular Subarray
Сложность: medium

Если задан круговой целочисленный массив nums длины n, верните максимально возможную сумму непустого подмассива nums. Круговой массив означает, что конец массива соединяется с его началом. Формально, следующий элемент nums[i] равен nums[(i + 1) % n], а предыдущий элемент nums[i] равен nums[(i - 1 + n) % n]. Подмассив может включать каждый элемент фиксированного буфера nums не более одного раза. Формально, для подмассива nums[i], nums[i + 1], ..., nums[j] не существует i <= k1, k2 <= j, при этом k1 % n == k2 % n.

Пример:

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

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

1⃣Найти стандартную максимальную сумму подмассива с помощью алгоритма Кадане.

2⃣Найти минимальную сумму подмассива с помощью алгоритма Кадане и вычесть ее из общей суммы массива.

3⃣Вернуть максимум между стандартной максимальной суммой подмассива и общей суммой массива минус минимальную сумму подмассива, если результат не равен 0 (чтобы учесть случай, когда все числа отрицательные).

😎 Решение:

public class Solution {
    public int MaxSubarraySumCircular(int[] nums) {
        int Kadane(int[] arr) {
            int currentSum = arr[0], maxSum = arr[0];
            for (int i = 1; i < arr.Length; i++) {
                currentSum = Math.Max(arr[i], currentSum + arr[i]);
                maxSum = Math.Max(maxSum, currentSum);
            }
            return maxSum;
        }

        int maxKadane = Kadane(nums);
        int totalSum = nums.Sum();
        int minKadane = Kadane(nums.Select(num => -num).ToArray());

        return Math.Max(maxKadane, totalSum + minKadane == 0 ? maxKadane : totalSum + minKadane);
    }
}

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

Задача: 562. Longest Line of Consecutive One in Matrix
Сложность: medium

Дана бинарная матрица размера m x n. Вернуть длину самой длинной последовательной линии из единиц в матрице.

Линия может быть горизонтальной, вертикальной, диагональной или анти-диагональной.

Пример:

Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3

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

1⃣Создайте 3 матрицы для хранения текущей длины последовательных единиц: horizontal, vertical, diagonal и anti_diagonal.

2⃣Итерируйте через каждый элемент матрицы: Если элемент равен 1, обновите соответствующие значения в матрицах horizontal, vertical, diagonal и anti_diagonal. Обновите максимальную длину последовательной линии.

3⃣Верните максимальную длину.

😎 Решение:

public class Solution {
    public int LongestLine(int[][] mat) {
        if (mat == null || mat.Length == 0 || mat[0].Length == 0) {
            return 0;
        }
        
        int m = mat.Length;
        int n = mat[0].Length;
        int maxLength = 0;
        
        int[,] horizontal = new int[m, n];
        int[,] vertical = new int[m, n];
        int[,] diagonal = new int[m, n];
        int[,] antiDiagonal = new int[m, n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    horizontal[i, j] = (j > 0 ? horizontal[i, j-1] : 0) + 1;
                    vertical[i, j] = (i > 0 ? vertical[i-1, j] : 0) + 1;
                    diagonal[i, j] = (i > 0 && j > 0 ? diagonal[i-1, j-1] : 0) + 1;
                    antiDiagonal[i, j] = (i > 0 && j < n - 1 ? antiDiagonal[i-1, j+1] : 0) + 1;
                    
                    maxLength = Math.Max(maxLength, horizontal[i, j]);
                    maxLength = Math.Max(maxLength, vertical[i, j]);
                    maxLength = Math.Max(maxLength, diagonal[i, j]);
                    maxLength = Math.Max(maxLength, antiDiagonal[i, j]);
                }
            }
        }
        
        return maxLength;
    }
}

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

Задача: 1013. Partition Array Into Three Parts With Equal Sum
Сложность: easy

Если задан массив целых чисел arr, верните true, если мы можем разбить массив на три непустые части с равными суммами. Формально, мы можем разбить массив, если можем найти индексы i + 1 < j с (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])

Пример:

Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true

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

1⃣Вычисление общей суммы:
Вычислите общую сумму всех элементов массива. Если эта сумма не делится на 3 без остатка, вернуть false, так как невозможно разбить массив на три части с равной суммой.

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

3⃣Проверка третьей части:
Убедитесь, что оставшаяся часть массива также имеет ту же сумму, что и две найденные части. Если да, вернуть true, иначе false.

😎 Решение:

public class Solution {
    public bool CanThreePartsEqualSum(int[] arr) {
        int totalSum = arr.Sum();
        if (totalSum % 3 != 0) {
            return false;
        }
        
        int target = totalSum / 3, partSum = 0, count = 0, n = arr.Length;
        
        for (int i = 0; i < n; i++) {
            partSum += arr[i];
            if (partSum == target) {
                count++;
                partSum = 0;
                if (count == 2 && i < n - 1) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

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

Задача: 567. Permutation in String
Сложность: medium

Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае.

Другими словами, верните true, если одна из перестановок s1 является подстрокой s2.

Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

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

1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2.

2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1.

3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.

😎 Решение:

public class Solution {
    public bool CheckInclusion(string s1, string s2) {
        int s1Len = s1.Length, s2Len = s2.Length;
        if (s1Len > s2Len) return false;
        
        int[] s1Count = new int[26];
        int[] s2Count = new int[26];
        
        for (int i = 0; i < s1Len; i++) {
            s1Count[s1[i] - 'a']++;
            s2Count[s2[i] - 'a']++;
        }
        
        for (int i = 0; i < s2Len - s1Len; i++) {
            if (s1Count.SequenceEqual(s2Count)) return true;
            s2Count[s2[i] - 'a']--;
            s2Count[s2[i + s1Len] - 'a']++;
        }
        
        return s1Count.SequenceEqual(s2Count);
    }
}

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

Задача: 1014. Best Sightseeing Pair
Сложность: medium

Вам дан целочисленный массив values, в котором values[i] представляет собой значение i-й достопримечательности. Две достопримечательности i и j имеют расстояние j - i между собой. Оценка пары (i < j) достопримечательностей равна values[i] + values[j] + i - j: сумма значений достопримечательностей минус расстояние между ними. Возвращается максимальная оценка пары достопримечательностей.

Пример:

Input: values = [8,1,5,2,6]
Output: 11

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

1⃣Инициализация переменных:
Инициализируйте переменную max_score для хранения максимальной оценки пары.
Инициализируйте переменную max_i_plus_value для хранения максимального значения выражения values[i] + i при проходе по массиву.

2⃣Проход по массиву:
Пройдитесь по массиву начиная с первого элемента и для каждого элемента values[j] вычислите текущую оценку пары как values[j] - j + max_i_plus_value.
Обновите значение max_score, если текущая оценка больше.
Обновите значение max_i_plus_value, если текущий элемент values[j] + j больше предыдущего max_i_plus_value.

3⃣Возврат результата:
Верните значение max_score как максимальную оценку пары достопримечательностей.

😎 Решение:

public class Solution {
    public int MaxScoreSightseeingPair(int[] values) {
        int maxScore = 0;
        int maxIPlusValue = values[0];
        
        for (int j = 1; j < values.Length; j++) {
            maxScore = Math.Max(maxScore, maxIPlusValue + values[j] - j);
            maxIPlusValue = Math.Max(maxIPlusValue, values[j] + j);
        }
        
        return maxScore;
    }
}

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

Задача: 220. Contains Duplicate III
Сложность: hard

Вам дан массив целых чисел nums и два целых числа indexDiff и valueDiff.

Найдите пару индексов (i, j) таких, что:
i != j,
abs(i - j) <= indexDiff,
abs(nums[i] - nums[j]) <= valueDiff.

Верните true, если такая пара существует, или false в противном случае.

Пример:

Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

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

1⃣Инициализация и вычисление корзин:
Рассчитать ширину корзины w = t + 1.
Инициализировать пустой хэш-таблицей buckets.
Определить функцию getID, которая возвращает идентификатор корзины для элемента x и ширины корзины w.

2⃣Итерация и проверка корзин:
Перебрать все элементы массива nums.
Для каждого элемента nums[i]:
Определить его корзину с помощью getID.
Проверить, есть ли в текущей корзине элемент. Если есть, вернуть true.
Проверить соседние корзины на наличие "почти дубликатов". Если есть, вернуть true.
Если текущая корзина пуста и в соседних корзинах нет "почти дубликатов", добавить текущий элемент в соответствующую корзину.
Если текущий индекс превышает k, удалить элемент из корзины, которая вышла за пределы окна.

3⃣Завершение:
Если ни одна пара "почти дубликатов" не найдена, вернуть false.

😎 Решение:

public class Solution {
    public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (t < 0) return false;
        Dictionary<long, long> buckets = new Dictionary<long, long>();
        long w = (long)t + 1;

        for (int i = 0; i < nums.Length; i++) {
            long bucket = GetID(nums[i], w);
            if (buckets.ContainsKey(bucket)) return true;
            if (buckets.ContainsKey(bucket - 1) && Math.Abs(nums[i] - buckets[bucket - 1]) < w) return true;
            if (buckets.ContainsKey(bucket + 1) && Math.Abs(nums[i] - buckets[bucket + 1]) < w) return true;
            buckets[bucket] = nums[i];
            if (i >= k) {
                buckets.Remove(GetID(nums[i - k], w));
            }
        }
        return false;
    }

    private long GetID(long x, long w) {
        return x < 0 ? (x + 1) / w - 1 : x / w;
    }
}

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

Задача: 1232. Check If It Is a Straight Line
Сложность: easy

Вам дан массив координат, coordinates[i] = [x, y], где [x, y] - координаты точки. Проверьте, образуют ли эти точки прямую линию в плоскости XY.

Пример:

Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true

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

1⃣Определение наклона:
Вычисляем наклон между первыми двумя точками и используем его как эталон.

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

3⃣Если все наклоны совпадают, то все точки лежат на одной прямой.

😎 Решение:

public class Solution {
    public bool CheckStraightLine(int[][] coordinates) {
        int x0 = coordinates[0][0], y0 = coordinates[0][1];
        int x1 = coordinates[1][0], y1 = coordinates[1][1];
        
        foreach (var point in coordinates) {
            int x = point[0], y = point[1];
            if ((x1 - x0) * (y - y0) != (y1 - y0) * (x - x0)) {
                return false;
            }
        }
        return true;
    }
}

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

Задача: 35. Search Insert Position
Сложность: easy

Дан отсортированный массив уникальных целых чисел и целевое значение. Верните индекс, если target найден. Если нет, верните индекс, где он должен быть вставлен, сохраняя порядок. Алгоритм должен работать за O(log n).

Пример:

Input: nums = [1,3,5,6], target = 5  
Output: 2  

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

1⃣Установить границы бинарного поиска: влево = 0, вправо = n - 1.

2⃣Выполнить бинарный поиск: сравнить середину с целью и сменить границу.

3⃣Вернуть влево как позицию вставки, если цель не найдена

😎 Решение:

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        int left = 0, right = nums.Length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        }
        return left;
    }
}

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

Задача: 955. Delete Columns to Make Sorted II
Сложность: medium

Вам дан массив из n строк одинаковой длины. Мы можем выбрать любые индексы удаления и удалить все символы в этих индексах для каждой строки.

Например, если у нас есть strs = ["abcdef", "uvwxyz"] и индексы удаления {0, 2, 3}, то конечный массив после удаления будет ["bef", "vyz"]. Предположим, что мы выбрали набор индексов удаления answer таким образом, что после удаления конечный массив имеет элементы в лексикографическом порядке (т.е, strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]). Возвращает минимально возможное значение answer.length.

Пример:

Input: strs = ["ca","bb","ac"]
Output: 1

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

1⃣Определить количество строк n и длину каждой строки m.
Создать массив delete_count длиной m, который будет отслеживать количество удаляемых столбцов.

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

3⃣Повторять процесс до тех пор, пока массив строк не станет лексикографически отсортированным.
Вернуть количество удаленных столбцов.

😎 Решение:

public class Solution {
    public int MinDeletionSize(string[] strs) {
        int n = strs.Length;
        int m = strs[0].Length;
        bool[] deleteCount = new bool[m];
        
        bool IsSorted() {
            for (int i = 0; i < n - 1; i++) {
                for (int j = 0; j < m; j++) {
                    if (deleteCount[j]) continue;
                    if (strs[i][j] > strs[i + 1][j]) return false;
                    if (strs[i][j] < strs[i + 1][j]) break;
                }
            }
            return true;
        }
        
        while (!IsSorted()) {
            for (int j = 0; j < m; j++) {
                if (deleteCount[j]) continue;
                for (int i = 0; i < n - 1; i++) {
                    if (strs[i][j] > strs[i + 1][j]) {
                        deleteCount[j] = true;
                        break;
                    }
                }
                if (deleteCount[j]) break;
            }
        }
        
        int count = 0;
        foreach (bool del in deleteCount) {
            if (del) count++;
        }
        return count;
    }
}

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

Задача: 460. LFU Cache
Сложность: hard

Реализуйте кеш с политикой LFU (наименее часто используемый):
Каждый элемент имеет счетчик частоты использования.
При обработке удаляется элемент с минимальной степенью защиты , а если таких несколько — исключительно недавно использованный

Пример:

Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

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

1⃣insert(int key, int frequency, int value):
Вставить пару частота-значение в cache с заданным ключом.
Получить LinkedHashSet, соответствующий данной частоте (по умолчанию пустой Set), и вставить в него ключ.

2⃣int get(int key):
Если ключа нет в кеше, вернуть -1.
Получить частоту и значение из кеша.
Удалить ключ из LinkedHashSet, связанного с частотой.
Если minf == frequency и LinkedHashSet пуст, увеличить minf на 1 и удалить запись частоты из frequencies.
Вызвать insert(key, frequency + 1, value).
Вернуть значение.

3⃣void put(int key, int value):
Если capacity <= 0, выйти.
Если ключ существует, обновить значение и вызвать get(key).
Если размер кеша равен capacity, удалить первый элемент из LinkedHashSet, связанного с minf, и из кеша.
Установить minf в 1.
Вызвать insert(key, 1, value).

😎 Решение:

using System;
using System.Collections.Generic;

public class LFUCache {
    private Dictionary<int, LinkedList<(int, int)>> frequencies = new Dictionary<int, LinkedList<(int, int)>>();
    private Dictionary<int, (int, LinkedListNode<(int, int)>)> cache = new Dictionary<int, (int, LinkedListNode<(int, int)>)>();
    private int capacity;
    private int minf;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minf = 0;
    }
    private void Insert(int key, int frequency, int value) {
        if (!frequencies.ContainsKey(frequency)) {
            frequencies[frequency] = new LinkedList<(int, int)>();
        }
        frequencies[frequency].AddLast((key, value));
        cache[key] = (frequency, frequencies[frequency].Last);
    }
    public int Get(int key) {
        if (!cache.ContainsKey(key)) return -1;
        var (frequency,        node) = cache[key];
        frequencies[frequency].Remove(node);
        if (frequencies[frequency].Count == 0) {
            frequencies.Remove(frequency);
            if (minf == frequency) minf++;
        }
        Insert(key, frequency + 1, node.Value.Item2);
        return node.Value.Item2;
    }
    public void Put(int key, int value) {
        if (capacity <= 0) return;
        if (cache.ContainsKey(key)) {
            cache[key].node.Value = (key, value);
            Get(key);
            return;
        }
        if (cache.Count == capacity) {
            var oldest = frequencies[minf].First.Value;
            frequencies[minf].RemoveFirst();
            cache.Remove(oldest.Item1);
            if (frequencies[minf].Count == 0) frequencies.Remove(minf);
        }
        minf = 1;
        Insert(key, 1, value);
    }
}

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

Задача: 684. Redundant Connection
Сложность: medium

В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов.

Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе.

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

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

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

1⃣Для каждого ребра (u, v) создайте представление графа с использованием списка смежности. Это позволит легко выполнять обход в глубину (DFS) для проверки соединений между узлами.

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

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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    HashSet<int> seen = new HashSet<int>();
    const int MAX_EDGE_VAL = 1000;

    public int[] FindRedundantConnection(int[][] edges) {
        List<int>[] graph = new List<int>[MAX_EDGE_VAL + 1];
        for (int i = 0; i <= MAX_EDGE_VAL; i++) {
            graph[i] = new List<int>();
        }

        foreach (var edge in edges) {
            seen.Clear();
            if (graph[edge[0]].Count > 0 && graph[edge[1]].Count > 0 &&
                    Dfs(graph, edge[0], edge[1])) {
                return edge;
            }
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        throw new InvalidOperationException("No redundant connection found");
    }

    public bool Dfs(List<int>[] graph, int source, int target) {
        if (!seen.Contains(source)) {
            seen.Add(source);
            if (source == target) return true;
            foreach (int nei in graph[source]) {
                if (Dfs(graph, nei, target)) return true;
            }
        }
        return false;
    }
}

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

Задача: 1042. Flower Planting With No Adjacent
Сложность: medium

У вас есть n садов, помеченных от 1 до n, и массив paths, где paths[i] = [xi, yi] описывает двунаправленный путь между садом xi и садом yi. В каждом саду вы хотите посадить один из 4 типов цветов. Все сады имеют не более 3 путей, входящих и выходящих из него. Ваша задача - выбрать тип цветка для каждого сада так, чтобы для любых двух садов, соединенных путем, они имели разные типы цветов. Верните любой такой выбор в виде массива answer, где answer[i] - тип цветка, посаженного в (i+1)-м саду. Типы цветов обозначаются 1, 2, 3 или 4. Ответ гарантированно существует.

Пример:

Input: n = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]

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

1⃣Построение графа:
Создайте граф из садов и путей между ними.

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

3⃣Мы будем проходить по каждому саду и выбирать тип цветка, который не совпадает с типами цветов в соседних садах. Поскольку у каждого сада не более трех соседей, всегда будет возможность выбрать тип цветка из 4 возможных типов.

😎 Решение:

public class Solution {
    public int[] GardenNoAdj(int n, int[][] paths) {
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        foreach (var path in paths) {
            graph[path[0] - 1].Add(path[1] - 1);
            graph[path[1] - 1].Add(path[0] - 1);
        }
        
        int[] answer = new int[n];
        for (int garden = 0; garden < n; garden++) {
            bool[] used = new bool[5];
            foreach (int neighbor in graph[garden]) {
                used[answer[neighbor]] = true;
            }
            for (int flower = 1; flower <= 4; flower++) {
                if (!used[flower]) {
                    answer[garden] = flower;
                    break;
                }
            }
        }
        
        return answer;
    }
}

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

Задача: 1506. Find Root of N-Ary Tree
Сложность: medium

Вам даны все узлы N-арного дерева в виде массива объектов Node, где каждый узел имеет уникальное значение.

Верните корень N-арного дерева.

Пример:

Input: tree = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]
Explanation: The tree from the input data is shown above.
The driver code creates the tree and gives findRoot the Node objects in an arbitrary order.
For example, the passed array could be [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)] or [Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)].
The findRoot function should return the root Node(1), and the driver code will serialize it and compare with the input data.
The input data and serialized Node(1) are the same, so the test passes.

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

1⃣Используйте хэшсет (named as seen) для отслеживания всех посещенных дочерних узлов. В конечном итоге корневой узел не будет в этом множестве.

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

3⃣Посетите список еще раз. На этот раз у нас будут все дочерние узлы в хэшсете. Как только вы наткнетесь на узел, который не находится в хэшсете, это и будет корневой узел, который мы ищем.

😎 Решение:

public class Solution {
    public Node FindRoot(IList<Node> tree) {
        HashSet<int> seen = new HashSet<int>();

        foreach (Node node in tree) {
            foreach (Node child in node.children) {
                seen.Add(child.val);
            }
        }

        Node root = null;
        foreach (Node node in tree) {
            if (!seen.Contains(node.val)) {
                root = node;
                break;
            }
        }
        return root;
    }
}

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