Задача: 1493. Longest Subarray of 1's After Deleting One Element
Сложность: medium

Дан бинарный массив nums, из которого следует удалить один элемент.

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

Пример:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

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

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

2⃣Итерация по массиву:
При каждом элементе увеличиваем zeroCount, если это ноль.
Если zeroCount превышает 1, сокращаем окно, перемещая левую границу вправо и уменьшая zeroCount, пока количество нулей не станет меньше или равно 1.
Обновляем longestWindow текущей длиной окна i - start.

3⃣ Возврат результата:
Вернуть longestWindow.

😎 Решение:

public class Solution {
    public int LongestSubarray(int[] nums) {
        int zeroCount = 0;
        int longestWindow = 0;
        int start = 0;

        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] == 0) {
                zeroCount++;
            }

            while (zeroCount > 1) {
                if (nums[start] == 0) {
                    zeroCount--;
                }
                start++;
            }

            longestWindow = Math.Max(longestWindow, i - start);
        }

        return longestWindow;
    }
}

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

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

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

Задача: 233. Number of Digit One
Сложность: hard

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

Пример:

Input: n = 13
Output: 6

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

1⃣Итерация по степеням 10: Итеративно увеличивайте значение i от 1 до n, увеличивая i в 10 раз на каждом шаге. Это позволяет анализировать каждую цифру числа n.

2⃣Подсчет групповых единиц: Для каждой итерации добавляйте (n / (i * 10)) * i к счетчику countr, что представляет собой количество единиц, встречающихся в группах размера i после каждого интервала (i * 10).

3⃣Добавление дополнительных единиц: Для каждой итерации добавляйте min(max((n % (i * 10)) - i + 1, 0), i) к счетчику countr, что представляет собой дополнительные единицы, зависящие от цифры на позиции i.

😎 Решение:

public class Solution {
    public int CountDigitOne(int n) {
        int countr = 0;
        for (long i = 1; i <= n; i *= 10) {
            long divider = i * 10;
            countr += (n / divider) * i + Math.Min(Math.Max(n % divider - i + 1, 0), i);
        }
        return countr;
    }
}

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

Задача: №16. 3Sum Closest
Сложность: medium

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

Пример:

Input: nums = [-1,2,1,-4], target = 1  
Output: 2  

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

1⃣Отсортировать массив и инициализировать переменные для отслеживания минимальной разницы.

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

3⃣Возвращать сумму, которая наиболее близка к target.

😎 Решение:

public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        Array.Sort(nums);
        int closestSum = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < nums.Length - 2; i++) {
            int left = i + 1, right = nums.Length - 1;
            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];

                if (Math.Abs(target - currentSum) < Math.Abs(target - closestSum)) {
                    closestSum = currentSum;
                }

                if (currentSum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return closestSum;
    }
}

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

Задача: 1026. Maximum Difference Between Node and Ancestor
Сложность: medium

Учитывая корень бинарного дерева, найдите максимальное значение v, для которого существуют различные вершины a и b, где v = |a.val - b.val| и a является предком b. Вершина a является предком b, если: любой ребенок a равен b или любой ребенок a является предком b.

Пример:

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7

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

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

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

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

😎 Решение:

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

public class Solution {
    public int MaxAncestorDiff(TreeNode root) {
        return Dfs(root, root.val, root.val);
    }
    
    private int Dfs(TreeNode node, int minVal, int maxVal) {
        if (node == null) return maxVal - minVal;
        minVal = Math.Min(minVal, node.val);
        maxVal = Math.Max(maxVal, node.val);
        int left = Dfs(node.left, minVal, maxVal);
        int right = Dfs(node.right, minVal, maxVal);
        return Math.Max(left, right);
    }
}

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

Задача: 136. Single Number
Сложность: easy

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

Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.

Пример:

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

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

1⃣Переберите все элементы в массиве nums.

2⃣Если какое-то число в nums новое для массива, добавьте его.

3⃣Если какое-то число уже есть в массиве, удалите его.

😎 Решение:

public class Solution {
    public int SingleNumber(int[] nums) {
        List<int> no_duplicate_list = new List<int>();
        foreach (int i in nums) {
            if (!no_duplicate_list.Contains(i)) {
                no_duplicate_list.Add(i);
            } else {
                no_duplicate_list.Remove(i);
            }
        }

        return no_duplicate_list[0];
    }
}

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

Задача: 491. Non-decreasing Subsequences
Сложность: medium

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

Пример:

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

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

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

2⃣Функция обратного отслеживания
Если текущий индекс равен длине массива, проверьте длину текущей последовательности и добавьте её в результат, если она содержит не менее двух элементов. Если текущая последовательность остаётся неубывающей после добавления текущего элемента массива, добавьте этот элемент, вызовите рекурсивную функцию для следующего индекса и удалите элемент из последовательности (обратное отслеживание). Всегда вызывайте рекурсивную функцию для следующего индекса без добавления текущего элемента.

3⃣Возврат результата
После завершения всех рекурсивных вызовов преобразуйте множество результатов в список и верните его.

😎 Решение:

public class Solution {
    public IList<IList<int>> FindSubsequences(int[] nums) {
        var result = new HashSet<IList<int>>();
        var sequence = new List<int>();
        Backtrack(nums, 0, sequence, result);
        return result.ToList();
    }

    private void Backtrack(int[] nums, int index, List<int> sequence, HashSet<IList<int>> result) {
        if (index == nums.Length) {
            if (sequence.Count >= 2) {
                result.Add(new List<int>(sequence));
            }
            return;
        }
        if (sequence.Count == 0 || sequence[sequence.Count - 1] <= nums[index]) {
            sequence.Add(nums[index]);
            Backtrack(nums, index + 1, sequence, result);
            sequence.RemoveAt(sequence.Count - 1);
        }
        Backtrack(nums, index + 1, sequence, result);
    }
}

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

Задача: 850. Rectangle Area II
Сложность: hard

Вам дан двумерный массив прямоугольников, выровненных по осям. Каждый прямоугольник[i] = [xi1, yi1, xi2, yi2] обозначает i-й прямоугольник, где (xi1, yi1) — координаты нижнего левого угла, а (xi2, yi2) — координаты верхнего правого угла.

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

Верните общую площадь. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.

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

1⃣Переназначьте каждую x координату на 0, 1, 2, .... Аналогично, переназначьте все y координаты.

2⃣Теперь мы имеем задачу, которую можно решить методом грубой силы: для каждого прямоугольника с переназначенными координатами (rx1, ry1, rx2, ry2) заполним сетку grid[x][y] = True для rx1 <= x < rx2 и ry1 <= y < ry2.

3⃣Затем каждая ячейка grid[rx][ry] будет представлять площадь (imapx(rx+1) - imapx(rx)) * (imapy(ry+1) - imapy(ry)), где если x был переназначен на rx, то imapx(rx) = x ("обратная карта x для переназначенного x равна x"), аналогично для imapy.

😎 Решение:

public class Solution {
    public int RectangleArea(int[][] rectangles) {
        int N = rectangles.Length;
        HashSet<int> Xvals = new HashSet<int>();
        HashSet<int> Yvals = new HashSet<int>();

        foreach (var rec in rectangles) {
            Xvals.Add(rec[0]);
            Xvals.Add(rec[2]);
            Yvals.Add(rec[1]);
            Yvals.Add(rec[3]);
        }

        int[] imapx = Xvals.ToArray();
        Array.Sort(imapx);
        int[] imapy = Yvals.ToArray();
        Array.Sort(imapy);

        Dictionary<int, int> mapx = new Dictionary<int, int>();
        Dictionary<int, int> mapy = new Dictionary<int, int>();
        for (int i = 0; i < imapx.Length; ++i)
            mapx[imapx[i]] = i;
        for (int i = 0; i < imapy.Length; ++i)
            mapy[imapy[i]] = i;

        bool[,] grid = new bool[imapx.Length, imapy.Length];
        foreach (var rec in rectangles)
            for (int x = mapx[rec[0]]; x < mapx[rec[2]]; ++x)
                for (int y = mapy[rec[1]]; y < mapy[rec[3]]; ++y)
                    grid[x, y] = true;

        long ans = 0;
        for (int x = 0; x < grid.GetLength(0); ++x)
            for (int y = 0; y < grid.GetLength(1); ++y)
                if (grid[x, y])
                    ans += (long)(imapx[x + 1] - imapx[x]) * (imapy[y + 1] - imapy[y]);

        ans %= 1_000_000_007;
        return (int)ans;
    }
}

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

Задача: 242. Valid Anagram
Сложность: easy

Даны две строки 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;
}

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

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

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

Задача: 1056. Confusing Number
Сложность: easy

Запутанное число - это число, которое при повороте на 180 градусов становится другим числом, каждая цифра которого действительна. Мы можем повернуть цифры числа на 180 градусов, чтобы получить новые цифры. Когда 0, 1, 6, 8 и 9 поворачиваются на 180 градусов, они становятся 0, 1, 9, 8 и 6 соответственно.
При повороте на 180 градусов 2, 3, 4, 5 и 7 становятся недействительными. Обратите внимание, что после поворота числа мы можем игнорировать ведущие нули. Например, после поворота 8000 мы получим 0008, которое считается просто 8. Если задано целое число n, верните true, если это запутанное число, или false в противном случае.

Пример:

Input: n = 6
Output: true

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

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

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

3⃣Проверь, что перевернутая строка отличается от исходной.

😎 Решение:

public class Solution {
    public bool IsConfusingNumber(int n) {
        string nStr = n.ToString();
        Dictionary<char, char> rotationMap = new Dictionary<char, char> {
            {'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}
        };
        StringBuilder rotatedStr = new StringBuilder();

        foreach (char ch in nStr) {
            if (!rotationMap.ContainsKey(ch)) {
                return false;
            }
            rotatedStr.Insert(0, rotationMap[ch]);
        }

        return rotatedStr.ToString() != nStr;
    }
}

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

Задача: 948. Bag of Tokens
Сложность: medium

Вы начинаете с начальной силой, равной power, начальным счетом 0 и мешком жетонов, представленным в виде целочисленного массива tokens, где каждый tokens[i] обозначает значение tokeni. Ваша цель - максимизировать общее количество очков, стратегически разыгрывая эти жетоны. За один ход вы можете разыграть неразыгранный жетон одним из двух способов (но не обоими для одного и того же жетона): лицом вверх: Если ваша текущая сила не меньше жетонов[i], вы можете сыграть токени, потеряв силу жетонов[i] и получив 1 очко. Лицом вниз: Если ваш текущий счет не меньше 1, вы можете сыграть токени, получив силу токенов[i] и потеряв 1 счет. Верните максимально возможный счет, который вы можете получить, сыграв любое количество токенов.

Пример:

Input: tokens = [100], power = 50

Output: 0

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

1⃣Отсортировать массив tokens.
Использовать два указателя: left и right, чтобы отслеживать начало и конец массива токенов.
Инициализировать переменные для текущей силы power, текущего счета score и максимального счета maxScore

2⃣Повторять следующие шаги, пока left не превысит right:
Если текущая сила power достаточна для разыгрывания токена tokens[left] лицом вверх, разыграть его и увеличить счет.
Если текущая сила недостаточна, но счет больше 0, разыграть токен tokens[right] лицом вниз и уменьшить счет.
Обновить максимальный счет, если текущий счет больше максимального.

3⃣Вернуть максимальный счет.

😎 Решение:

public class Solution {
    public int BagOfTokensScore(int[] tokens, int power) {
        Array.Sort(tokens);
        int left = 0, right = tokens.Length - 1;
        int score = 0, maxScore = 0;
        
        while (left <= right) {
            if (power >= tokens[left]) {
                power -= tokens[left];
                score++;
                left++;
                maxScore = Math.Max(maxScore, score);
            } else if (score > 0) {
                power += tokens[right];
                score--;
                right--;
            } else {
                break;
            }
        }
        
        return maxScore;
    }
}

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

Задача: 950. Reveal Cards In Increasing Order
Сложность: medium

Вам дана колода целочисленных массивов. Имеется колода карт, в которой каждая карта имеет уникальное целое число. Целое число на i-й карте - deck[i]. Вы можете упорядочить колоду в любом порядке. Изначально все карты в одной колоде лежат лицевой стороной вниз (нераскрытыми). Вы будете выполнять следующие действия несколько раз, пока все карты не будут раскрыты: возьмите верхнюю карту колоды, раскройте ее и выньте из колоды. Если в колоде еще есть карты, положите следующую верхнюю карту колоды на дно колоды. Если еще есть нераскрытые карты, вернитесь к шагу 1. В противном случае остановитесь. Верните порядок колоды, при котором карты раскрываются в порядке возрастания. Обратите внимание, что первая запись в ответе считается верхом колоды.

Пример:

Input: deck = [17,13,11,2,3,5,7]
Output: [2,13,3,11,5,17,7]

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

1⃣Создать индексы карт в порядке, в котором они будут раскрываться.

2⃣Отсортировать колоду карт по возрастанию.

3⃣Заполнить результат раскрытия карт по ранее созданным индексам.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int[] DeckRevealedIncreasing(int[] deck) {
        int n = deck.Length;
        Queue<int> index = new Queue<int>();
        for (int i = 0; i < n; i++) {
            index.Enqueue(i);
        }
        
        Array.Sort(deck);
        int[] result = new int[n];
        
        foreach (int card in deck) {
            result[index.Dequeue()] = card;
            if (index.Count > 0) {
                index.Enqueue(index.Dequeue());
            }
        }
        
        return result;
    }
}

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