Задача: 1253. Reconstruct a 2-Row Binary Matrix
Сложность: medium

Даны следующие сведения о матрице с n столбцами и 2 строками: Матрица является двоичной, то есть каждый элемент матрицы может быть 0 или 1. Сумма элементов 0-й (верхней) строки задана как upper. Сумма элементов 1-й (нижней) строки задана как lower.
Сумма элементов i-го столбца (индексированного 0) - colsum[i], где colsum - целочисленный массив длины n. Ваша задача - восстановить матрицу с upper, lower и colsum. Вернуть ее в виде двумерного целочисленного массива. Если существует более одного правильного решения, будет принято любое из них. Если правильного решения не существует, верните пустой двумерный массив.

Пример:

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]

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

1⃣Инициализируйте две строки матрицы длины n с нулями.

2⃣Пройдите по массиву colsum и распределите значения 2 по обеим строкам, уменьшая upper и lower.
Пройдите по массиву colsum и распределите значения 1 по строкам, уменьшая соответствующие upper или lower.

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

😎 Решение:

public class Solution {
    public IList<IList<int>> ReconstructMatrix(int upper, int lower, int[] colsum) {
        int n = colsum.Length;
        int[] top = new int[n];
        int[] bottom = new int[n];

        for (int i = 0; i < n; i++) {
            if (colsum[i] == 2) {
                if (upper > 0 && lower > 0) {
                    top[i] = 1;
                    bottom[i] = 1;
                    upper--;
                    lower--;
                } else {
                    return new List<IList<int>>();
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (colsum[i] == 1) {
                if (upper > lower) {
                    if (upper > 0) {
                        top[i] = 1;
                        upper--;
                    } else {
                        return new List<IList<int>>();
                    }
                } else {
                    if (lower > 0) {
                        bottom[i] = 1;
                        lower--;
                    } else {
                        return new List<IList<int>>();
                    }
                }
            }
        }

        if (upper == 0 && lower == 0) {
            return new List<IList<int>> { top, bottom };
        } else {
            return new List<IList<int>>();
        }
    }
}

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

Задача: 911. Online Election
Сложность: medium

Вам даны два целочисленных массива persons и times. На выборах i-й голос был отдан за person[i] в момент времени times[i]. Для каждого запроса в момент времени t найдите человека, который лидировал на выборах в момент времени t. Голоса, отданные в момент времени t, будут учитываться в нашем запросе. В случае равенства голосов побеждает тот, кто проголосовал последним (среди равных кандидатов). Реализация класса TopVotedCandidate: TopVotedCandidate(int[] persons, int[] times) Инициализирует объект с массивами persons и times. int q(int t) Возвращает номер человека, который лидировал на выборах в момент времени t в соответствии с указанными правилами.

Пример:

Input
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
Output
[null, 0, 1, 1, 0, 0, 1]

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

1⃣Использовать два массива для хранения лиц и времени голосования.

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

3⃣На каждый запрос времени t, найти наибольший индекс времени, который не превышает t, и вернуть лидера на этот момент времени.

😎 Решение:

using System;
using System.Collections.Generic;

public class TopVotedCandidate {
    private int[] times;
    private List<int> leaders;

    public TopVotedCandidate(int[] persons, int[] times) {
        this.times = times;
        this.leaders = new List<int>();
        Dictionary<int, int> counts = new Dictionary<int, int>();
        int leader = -1;

        foreach (int person in persons) {
            if (!counts.ContainsKey(person)) {
                counts[person] = 0;
            }
            counts[person]++;
            if (!counts.ContainsKey(leader) || counts[person] >= counts[leader]) {
                leader = person;
            }
            leaders.Add(leader);
        }
    }

    public int Q(int t) {
        int left = 0;
        int right = times.Length - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (times[mid] <= t) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return leaders[left];
    }
}

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

Задача: 674. Longest Continuous Increasing Subsequence
Сложность: easy

Дан неотсортированный массив целых чисел nums, верните длину самой длинной непрерывной возрастающей подпоследовательности (т.е. подмассива). Подпоследовательность должна быть строго возрастающей.

Непрерывная возрастающая подпоследовательность определяется двумя индексами l и r (l < r) так, что она имеет вид [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] и для каждого l <= i < r выполняется nums[i] < nums[i + 1].

Пример:

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.

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

1⃣Каждая (непрерывная) возрастающая подпоследовательность не пересекается, и граница каждой такой подпоследовательности возникает, когда nums[i-1] >= nums[i]. В этом случае начинается новая возрастающая подпоследовательность с nums[i], и мы сохраняем такой i в переменной anchor.

2⃣Например, если nums = [7, 8, 9, 1, 2, 3], то anchor начинается с 0 (nums[anchor] = 7) и затем устанавливается на anchor = 3 (nums[anchor] = 1). Независимо от значения anchor, мы записываем кандидата на ответ длиной i - anchor + 1, длина подмассива nums[anchor], nums[anchor+1], ..., nums[i], и наш ответ обновляется соответствующим образом.

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

😎 Решение:

public class Solution {
    public int FindLengthOfLCIS(int[] nums) {
        int ans = 0, anchor = 0;
        for (int i = 0; i < nums.Length; ++i) {
            if (i > 0 && nums[i-1] >= nums[i]) anchor = i;
            ans = Math.Max(ans, i - anchor + 1);
        }
        return ans;
    }
}

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

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

Дана двумерная сетка, состоящая из 0 (земля) и 1 (вода).Остров - это максимальная 4-направленно связная группа из 0s, а закрытый остров - это остров, полностью (слева, сверху, справа, снизу) окруженный 1s. Верните количество закрытых островов.

Пример:

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

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

1⃣Пройдите по границам сетки и с помощью поиска в глубину (DFS) или поиска в ширину (BFS) замените все связанные земли (0) на воду (1).

2⃣Пройдите по всей сетке, используя DFS или BFS для поиска всех оставшихся островов (групп 0)

3⃣Подсчитайте количество таких островов.

😎 Решение:

public class Solution {
    public int ClosedIsland(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 0) {
                    Dfs(grid, i, j);
                }
            }
        }

        int count = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 0) {
                    Dfs(grid, i, j);
                    count++;
                }
            }
        }

        return count;
    }

    private void Dfs(int[][] grid, int x, int y) {
        if (x < 0 || y < 0 || x >= grid.Length || y >= grid[0].Length || grid[x][y] == 1) {
            return;
        }
        grid[x][y] = 1;
        Dfs(grid, x + 1, y);
        Dfs(grid, x - 1, y);
        Dfs(grid, x, y + 1);
        Dfs(grid, x, y - 1);
    }
}

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

Задача: 83. Remove Duplicates from Sorted List
Сложность: easy

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

Пример:

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

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

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

2⃣Если узел является дубликатом, мы изменяем указатель next текущего узла так, чтобы он пропускал следующий узел и напрямую указывал на узел, следующий за следующим.

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

😎 Решение:

public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
        ListNode current = head;
        while (current != null && current.next != null) {
            if (current.next.val == current.val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }

        return head;
    }
}

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

Задача: 380. Insert Delete GetRandom O(1)
Сложность: medium

Реализуйте класс RandomizedSet:

RandomizedSet(): Инициализирует объект RandomizedSet.
bool insert(int val): Вставляет элемент val в множество, если его там нет. Возвращает true, если элемент отсутствовал, и false в противном случае.
bool remove(int val): Удаляет элемент val из множества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае.
int getRandom(): Возвращает случайный элемент из текущего множества элементов (гарантируется, что по крайней мере один элемент существует при вызове этого метода). Каждый элемент должен иметь равную вероятность быть возвращенным.
Вы должны реализовать функции класса таким образом, чтобы каждая функция работала в среднем за O(1) по времени.

Пример:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

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

1⃣Создать словарь для хранения значений и их индексов, а также список для хранения значений.

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

3⃣Метод getRandom(): Возвращать случайный элемент из списка, используя встроенную функцию генерации случайных чисел.

😎 Решение:

using System;
using System.Collections.Generic;

public class RandomizedSet {
    private Dictionary<int, int> dict;
    private List<int> list;
    private Random rand;

    public RandomizedSet() {
        dict = new Dictionary<int, int>();
        list = new List<int>();
        rand = new Random();
    }

    public bool Insert(int val) {
        if (dict.ContainsKey(val)) {
            return false;
        }
        dict[val] = list.Count;
        list.Add(val);
        return true;
    }

    public bool Remove(int val) {
        if (!dict.ContainsKey(val)) {
            return false;
        }
        int index = dict[val];
        int lastElement = list[list.Count - 1];
        list[index] = lastElement;
        dict[lastElement] = index;
        list.RemoveAt(list.Count - 1);
        dict.Remove(val);
        return true;
    }

    public int GetRandom() {
        return list[rand.Next(list.Count)];
    }
}

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

Задача: 1217. Minimum Cost to Move Chips to The Same Position
Сложность: easy

У нас есть n фишек, где позиция i-й фишки равна position[i].

Нам нужно переместить все фишки в одну и ту же позицию. За один шаг мы можем изменить позицию i-й фишки с position[i] на:
position[i] + 2 или position[i] - 2 с затратами = 0.
position[i] + 1 или position[i] - 1 с затратами = 1.
Верните минимальные затраты, необходимые для перемещения всех фишек в одну и ту же позицию.

Пример:

Input: position = [2,2,2,3,3]
Output: 2
Explanation: We can move the two chips at position  3 to position 2. Each move has cost = 1. The total cost = 2.

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

1⃣Посчитать количество фишек на четных и нечетных позициях.

2⃣Сравнить количество фишек на четных и нечетных позициях.

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

😎 Решение:

public class Solution {
    public int MinCostToMoveChips(int[] position) {
        int evenCount = 0;
        int oddCount = 0;
        
        foreach (int pos in position) {
            if (pos % 2 == 0) {
                evenCount++;
            } else {
                oddCount++;
            }
        }
        
        return Math.Min(evenCount, oddCount);
    }
}

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

Задача: 218. The Skyline Problem
Сложность: hard

Горизонт города — это внешний контур силуэта, образованного всеми зданиями в этом городе, когда они видны издалека. Учитывая расположения и высоты всех зданий, верните горизонт, образованный этими зданиями в совокупности.

Геометрическая информация о каждом здании задана в массиве buildings, где buildings[i] = [lefti, righti, heighti]:

lefti — это координата x левого края i-го здания.
righti — это координата x правого края i-го здания.
heighti — это высота i-го здания.
Вы можете предположить, что все здания — это идеальные прямоугольники, стоящие на абсолютно плоской поверхности на высоте 0.

Пример:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

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

1⃣Соберите все уникальные позиции для левых и правых краев зданий в массиве buildings и сохраните их в список edgeSet. Инициализируйте хэш-таблицу edgeIndexMap для хранения соответствующих индексов и значений элементов из heights.

2⃣Пройдитесь по всем зданиям в массиве buildings, найдите индексы их левого и правого краев, а также их высоту. Для каждого здания обновите максимальную высоту в диапазоне [leftIndex, rightIndex).

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

😎 Решение:

public class Solution {
    public IList<IList<int>> GetSkyline(int[][] buildings) {
        var edgeSet = new SortedSet<int>();
        foreach (var building in buildings) {
            edgeSet.Add(building[0]);
            edgeSet.Add(building[1]);
        }
        var edges = edgeSet.ToList();
        var edgeIndexMap = new Dictionary<int, int>();
        for (int i = 0; i < edges.Count; ++i) {
            edgeIndexMap[edges[i]] = i;
        }
        var heights = new int[edges.Count];
        foreach (var building in buildings) {
            int left = building[0], right = building[1], height = building[2];
            int leftIndex = edgeIndexMap[left], rightIndex = edgeIndexMap[right];
            for (int idx = leftIndex; idx < rightIndex; ++idx) {
                heights[idx] = Math.Max(heights[idx], height);
            }
        }
        var answer = new List<IList<int>>();
        for (int i = 0; i < heights.Length; ++i) {
            int currHeight = heights[i], currPos = edges[i];
            if (answer.Count == 0 || answer[answer.Count - 1][1] != currHeight) {
                answer.Add(new List<int> { currPos, currHeight });
            }
        }
        return answer;
    }
}

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

Задача: 727. Minimum Window Subsequence
Сложность: hard

Если в строках s1 и s2 нет такого окна, которое покрывало бы все символы в s2, верните пустую строку "". Если таких окон минимальной длины несколько, возвращается окно с самым левым начальным индексом.

Пример:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"

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

1⃣Используйте два указателя для определения текущего окна.

2⃣Поддерживайте счетчики для символов в текущем окне и требуемых символов из s2.

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

😎 Решение:

public class Solution {
    public string MinWindow(string s1, string s2) {
        if (string.IsNullOrEmpty(s1) || string.IsNullOrEmpty(s2)) {
            return "";
        }

        var dictT = new Dictionary<char, int>();
        foreach (char c in s2) {
            if (dictT.ContainsKey(c)) {
                dictT[c]++;
            } else {
                dictT[c] = 1;
            }
        }

        int required = dictT.Count;
        int l = 0, r = 0, formed = 0;
        var windowCounts = new Dictionary<char, int>();
        int[] ans = { int.MaxValue, 0, 0 };

        while (r < s1.Length) {
            char c = s1[r];
            if (windowCounts.ContainsKey(c)) {
                windowCounts[c]++;
            } else {
                windowCounts[c] = 1;
            }

            if (dictT.ContainsKey(c) && windowCounts[c] == dictT[c]) {
                formed++;
            }

            while (l <= r && formed == required) {
                c = s1[l];

                if (r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }

                windowCounts[c]--;
                if (dictT.ContainsKey(c) && windowCounts[c] < dictT[c]) {
                    formed--;
                }

                l++;
            }

            r++;
        }

        return ans[0] == int.MaxValue ? "" : s1.Substring(ans[1], ans[0]);
    }
}

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

Задача: 316. Remove Duplicate Letters
Сложность: medium

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

Пример:

Input: s = "bcabc"
Output: "abc"

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

1⃣Инициализация стека
Создайте стек, который будет хранить результат, построенный по мере итерации строки.

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

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

😎 Решение:

public class Solution {
    public string RemoveDuplicateLetters(string s) {
        var stack = new Stack<char>();
        var seen = new HashSet<char>();
        var lastOccurrence = new Dictionary<char, int>();
        for (int i = 0; i < s.Length; i++) {
            lastOccurrence[s[i]] = i;
        }

        for (int i = 0; i < s.Length; i++) {
            char c = s[i];
            if (!seen.Contains(c)) {
                while (stack.Count > 0 && c < stack.Peek() && i < lastOccurrence[stack.Peek()]) {
                    seen.Remove(stack.Pop());
                }
                seen.Add(c);
                stack.Push(c);
            }
        }
        return new string(stack.Reverse().ToArray());
    }
}

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

Задача: 395. Longest Substring with At Least K Repeating Characters
Сложность: medium

Дана строка s и целое число k, верните длину самой длинной подстроки строки s, такая что частота каждого символа в этой подстроке больше или равна k.

Если такой подстроки не существует, верните 0.

Пример:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

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

1⃣Генерируйте подстроки из строки s, начиная с индекса start и заканчивая индексом end. Используйте массив countMap для хранения частоты каждого символа в подстроке.

2⃣Метод isValid использует countMap для проверки, что каждый символ в подстроке встречается как минимум k раз. Если условие выполняется, текущая подстрока считается допустимой.

3⃣Отслеживайте максимальную длину допустимой подстроки, обновляя её, когда найдена более длинная подстрока, удовлетворяющая условиям. В конце возвращайте длину самой длинной подстроки.

😎 Решение:

public class Solution {
    public int LongestSubstring(string s, int k) {
        if (s.Length == 0 || k > s.Length) {
            return 0;
        }
        int[] countMap = new int[26];
        int n = s.Length;
        int result = 0;
        
        for (int start = 0; start < n; start++) {
            Array.Fill(countMap, 0);
            for (int end = start; end < n; end++) {
                countMap[s[end] - 'a']++;
                if (IsValid(countMap, k)) {
                    result = Math.Max(result, end - start + 1);
                }
            }
        }
        return result;
    }

    private bool IsValid(int[] countMap, int k) {
        int countLetters = 0, countAtLeastK = 0;
        for (int i = 0; i < 26; i++) {
            if (countMap[i] > 0) countLetters++;
            if (countMap[i] >= k) countAtLeastK++;
        }
        return countLetters == countAtLeastK;
    }
}

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

Задача: 767. Reorganize String
Сложность: medium

Дана строка s, переставьте символы строки s так, чтобы любые два соседних символа не были одинаковыми.

Верните любую возможную перестановку строки s или верните "", если это невозможно.

Пример:

Input: s = "aab"
Output: "aba"

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

1⃣Инициализируйте пустой список ans для хранения переставленных символов. Создайте приоритетную очередь pq, используя структуру данных кучи. Каждый элемент в pq — это кортеж, содержащий количество символов и сам символ. Приоритетная очередь упорядочена так, что элементы с большим количеством имеют более высокий приоритет.

2⃣Извлеките элемент с наивысшим приоритетом из pq. Присвойте его количество и символ переменным count_first и char_first соответственно. Если ans пуст или текущий символ char_first отличается от последнего символа в ans, добавьте char_first в ans. Если количество char_first не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Перейдите к следующей итерации.

3⃣В противном случае, если char_first совпадает с последним символом в ans, нужно выбрать другой символ. Если pq пуста, верните пустую строку, так как переставить символы невозможно. Извлеките следующий элемент из pq, присвоив его количество и символ переменным count_second и char_second соответственно. Добавьте char_second в ans. Если количество char_second не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Наконец, поместите оригинальный char_first обратно в pq. Верните переставленные символы как строку, объединив элементы в ans.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public string ReorganizeString(string s) {
        int[] charCounts = new int[26];
        foreach (char c in s) {
            charCounts[c - 'a']++;
        }

        var pq = new PriorityQueue<int[], int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        for (int i = 0; i < 26; i++) {
            if (charCounts[i] > 0) {
                pq.Enqueue(new int[] { charCounts[i], i + 'a' }, charCounts[i]);
            }
        }

        var result = new List<char>();
        while (pq.Count > 0) {
            var first = pq.Dequeue();
            if (result.Count == 0 || first[1] != result[^1]) {
                result.Add((char)first[1]);
                if (--first[0] > 0) {
                    pq.Enqueue(first, first[0]);
                }
            } else {
                if (pq.Count == 0) {
                    return "";
                }
                var second = pq.Dequeue();
                result.Add((char)second[1]);
                if (--second[0] > 0) {
                    pq.Enqueue(second, second[0]);
                }
                pq.Enqueue(first, first[0]);
            }
        }

        return new string(result.ToArray());
    }
}

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

Задача: №19. Remove Nth Node From End of List
Сложность: medium

Учитывая заголовок связанного списка, удалите n-й узел с конца списка и верните его заголовок.

Пример:

Input: head = [1,2,3,4,5], n = 2  
Output: [1,2,3,5]  

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

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

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

3⃣Обновить ссылку, исключив n-й узел с конца.

😎 Решение:

public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = dummy, second = dummy;

        for (int i = 0; i <= n; i++) {
            first = first.next;
        }

        while (first != null) {
            first = first.next;
            second = second.next;
        }

        second.next = second.next.next;
        return dummy.next;
    }
}

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

Задача: 689. Maximum Sum of 3 Non-Overlapping Subarrays
Сложность: hard

Дан целочисленный массив nums и целое число k. Найдите три непересекающихся подмассива длины k с максимальной суммой и верните их.

Верните результат в виде списка индексов, представляющих начальную позицию каждого интервала (нумерация с 0). Если существует несколько ответов, верните лексикографически наименьший.

Пример:

Input: nums = [1,2,1,2,6,7,5,1], k = 2
Output: [0,3,5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

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

1⃣Предположим, что фиксирован j. Нам нужно узнать на интервалах i∈[0,j−k] и l∈[j+k,len(W)−1], где наибольшее значение W[i] (и соответственно W[l]) встречается первым (то есть, с наименьшим индексом).

2⃣Мы можем решить эту задачу с помощью динамического программирования. Например, если мы знаем, что i - это место, где наибольшее значение W[i] встречается первым на [0,5], то на [0,6] первое появление наибольшего W[i] должно быть либо i, либо 6. Если, скажем, 6 лучше, тогда мы устанавливаем best = 6. В конце left[z] будет первым вхождением наибольшего значения W[i] на интервале i∈[0,z], а right[z] будет таким же, но на интервале i∈[z,len(W)−1].

3⃣Это означает, что для некоторого выбора j, кандидат на ответ должен быть (left[j - k], j, right[j + k]). Мы выбираем кандидата, который дает максимальное значение W[i] + W[j] + W[l].

😎 Решение:

public class Solution {
    public int[] MaxSumOfThreeSubarrays(int[] nums, int k) {
        int[] W = new int[nums.Length - k + 1];
        int currSum = 0;
        for (int i = 0; i < nums.Length; i++) {
            currSum += nums[i];
            if (i >= k) {
                currSum -= nums[i - k];
            }
            if (i >= k - 1) {
                W[i - k + 1] = currSum;
            }
        }

        int[] left = new int[W.Length];
        int best = 0;
        for (int i = 0; i < W.Length; i++) {
            if (W[i] > W[best]) best = i;
            left[i] = best;
        }

        int[] right = new int[W.Length];
        best = W.Length - 1;
        for (int i = W.Length - 1; i >= 0; i--) {
            if (W[i] >= W[best]) best = i;
            right[i] = best;
        }

        int[] ans = new int[] {-1, -1, -1};
        for (int j = k; j < W.Length - k; j++) {
            int i = left[j - k], l = right[j + k];
            if (ans[0] == -1 || W[i] + W[j] + W[l] > W[ans[0]] + W[ans[1]] + W[ans[2]]) {
                ans[0] = i;
                ans[1] = j;
                ans[2] = l;
            }
        }
        return ans;
    }
}

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

Задача: 939. Minimum Area Rectangle
Сложность: medium

Дан массив точек в плоскости X-Y points, где points[i] = [xi, yi]. Верните минимальную площадь прямоугольника, образованного из этих точек, со сторонами, параллельными осям X и Y. Если такого прямоугольника не существует, верните 0.

Пример:

Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

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

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

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

3⃣Если минимальная площадь остается бесконечной, вернуть 0. Иначе вернуть минимальную площадь.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int MinAreaRect(int[][] points) {
        var pointSet = new HashSet<string>();
        foreach (var point in points) {
            pointSet.Add($"{point[0]},{point[1]}");
        }
        
        int minArea = int.MaxValue;
        for (int i = 0; i < points.Length; i++) {
            for (int j = i + 1; j < points.Length; j++) {
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                if (x1 != x2 && y1 != y2 && pointSet.Contains($"{x1},{y2}") && pointSet.Contains($"{x2},{y1}")) {
                    minArea = Math.Min(minArea, Math.Abs(x2 - x1) * Math.Abs(y2 - y1));
                }
            }
        }
        
        return minArea == int.MaxValue ? 0 : minArea;
    }
}

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

Задача: 766. Toeplitz Matrix
Сложность: easy

Дана матрица размером m x n. Вернуть true, если матрица является Тёплицевой. В противном случае вернуть false.

Матрица является Тёплицевой, если все диагонали, идущие от верхнего левого к нижнему правому углу, содержат одинаковые элементы.

Пример:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

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

1⃣Что отличает две координаты (r1, c1) и (r2, c2) на одной диагонали? Оказывается, две координаты находятся на одной диагонали тогда и только тогда, когда r1 - c1 == r2 - c2.м

2⃣Это приводит к следующей идее: запоминайте значение этой диагонали как groups[r - c]. Если обнаружено несоответствие, то матрица не является Тёплицевой; в противном случае, она является таковой.

3⃣Таким образом, для каждой ячейки матрицы сохраняйте значение диагонали в словаре groups с ключом r - c. Проходите по всем ячейкам матрицы и проверяйте, совпадает ли текущее значение с сохранённым в groups. Если где-то обнаруживается несоответствие, верните false. Если все элементы соответствуют, верните true.

😎 Решение:

public class Solution {
    public bool IsToeplitzMatrix(int[][] matrix) {
        Dictionary<int, int> groups = new Dictionary<int, int>();
        for (int r = 0; r < matrix.Length; ++r) {
            for (int c = 0; c < matrix[0].Length; ++c) {
                if (!groups.ContainsKey(r - c))
                    groups[r - c] = matrix[r][c];
                else if (groups[r - c] != matrix[r][c])
                    return false;
            }
        }
        return true;
    }
}

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

Задача: 1338. Reduce Array Size to The Half
Сложность: medium

Дан массив целых чисел arr. Вы можете выбрать набор чисел и удалить все вхождения этих чисел из массива.

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

Пример:

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

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

1⃣Отсортировать массив и создать список подсчета количества вхождений каждого числа.

2⃣Отсортировать список подсчета в порядке убывания.

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

😎 Решение:

public class Solution {
    public int MinSetSize(int[] arr) {
        Array.Sort(arr);
        
        List<int> counts = new List<int>();
        int currentRun = 1;
        for (int i = 1; i < arr.Length; i++) {
            if (arr[i] == arr[i - 1]) {
                currentRun += 1;
                continue;
            }
            counts.Add(currentRun);
            currentRun = 1;
        }
        counts.Add(currentRun);
        
        counts.Sort((a, b) => b.CompareTo(a));
        
        int numbersRemovedFromArr = 0;
        int setSize = 0;
        foreach (int count in counts) {
            numbersRemovedFromArr += count;
            setSize += 1;   
            if (numbersRemovedFromArr >= arr.Length / 2) {
                break;
            }
        }
        
        return setSize;
    }
}

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

Задача: 741. Cherry Pickup
Сложность: hard

Вам дана сетка n x n, представляющая поле вишен. Каждая клетка - одно из трех возможных целых чисел. 0 означает, что клетка пуста, и вы можете пройти через нее, 1 означает, что клетка содержит вишню, которую вы можете сорвать и пройти через нее, или -1 означает, что клетка содержит шип, который преграждает вам путь. Верните максимальное количество вишен, которое вы можете собрать, следуя следующим правилам: Начиная с позиции (0, 0) и достигая (n - 1, n - 1) путем перемещения вправо или вниз через допустимые клетки пути (клетки со значением 0 или 1).
После достижения (n - 1, n - 1) вернитесь в (0, 0), двигаясь влево или вверх по клеткам с действительными путями. Проходя через клетку пути, содержащую вишню, вы поднимаете ее, и клетка становится пустой клеткой 0. Если между (0, 0) и (n - 1, n - 1) нет действительного пути, то вишни собрать нельзя.

Пример:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5

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

1⃣Используйте динамическое программирование для подсчета максимального количества вишен, которые можно собрать при движении от (0, 0) до (n - 1, n - 1).

2⃣Примените еще один проход с использованием динамического программирования для движения обратно от (n - 1, n - 1) до (0, 0), чтобы учитывать вишни, собранные на обратном пути.

3⃣Объедините результаты двух проходов, чтобы найти максимальное количество вишен, которые можно собрать.

😎 Решение:

using System;

public class Solution {
    public int CherryPickup(int[][] grid) {
        int n = grid.Length;
        int[][][] dp = new int[n][][];
        for (int i = 0; i < n; i++) {
            dp[i] = new int[n][];
            for (int j = 0; j < n; j++) {
                dp[i][j] = new int[2 * n - 1];
                Array.Fill(dp[i][j], int.MinValue);
            }
        }
        dp[0][0][0] = grid[0][0];

        for (int k = 1; k < 2 * n - 1; k++) {
            for (int i1 = Math.Max(0, k - n + 1); i1 <= Math.Min(n - 1, k); i1++) {
                for (int i2 = Math.Max(0, k - n + 1); i2 <= Math.Min(n - 1, k); i2++) {
                    int j1 = k - i1, j2 = k - i2;
                    if (j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1) {
                        int maxCherries = int.MinValue;
                        if (i1 > 0 && i2 > 0) maxCherries = Math.Max(maxCherries, dp[i1 - 1][i2 - 1][k - 1]);
                        if (i1 > 0) maxCherries = Math.Max(maxCherries, dp[i1 - 1][i2][k - 1]);
                        if (i2 > 0) maxCherries = Math.Max(maxCherries, dp[i1][i2 - 1][k - 1]);
                        maxCherries = Math.Max(maxCherries, dp[i1][i2][k - 1]);
                        if (maxCherries != int.MinValue) {
                            dp[i1][i2][k] = maxCherries + grid[i1][j1];
                            if (i1 != i2) dp[i1][i2][k] += grid[i2][j2];
                        }
                    }
                }
            }
        }

        return Math.Max(0, dp[n - 1][n - 1][2 * n - 1]);
    }
}

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

Задача: 201. Bitwise AND of Numbers Range
Сложность: medium

Даны два целых числа left и right, которые представляют диапазон [left, right], верните побитовое И всех чисел в этом диапазоне включительно.

Пример:

Input: left = 5, right = 7
Output: 4

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

1⃣Сдвигать left и right вправо, пока они не станут равными.

2⃣Подсчитать количество сдвигов.

3⃣Сдвинуть left влево на количество сдвигов и вернуть результат.

😎 Решение:

public class Solution {
    public int RangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m < n) {
            m >>= 1;
            n >>= 1;
            shift++;
        }
        return m << shift;
    }
}

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

Задача: 543. Diameter of Binary Tree
Сложность: easy

Учитывая корень бинарного дерева, вернуть длину диаметра дерева.

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

Длина пути между двумя узлами представлена числом ребер между ними.

Пример:

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

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

1⃣Инициализируйте целочисленную переменную diameter для отслеживания самого длинного пути, найденного с помощью DFS.

2⃣Реализуйте рекурсивную функцию longestPath, которая принимает TreeNode в качестве входных данных и рекурсивно исследует дерево: Если узел равен None, вернуть 0. Рекурсивно исследовать левые и правые дочерние узлы, возвращая длины путей leftPath и rightPath. Если сумма leftPath и rightPath больше текущего diameter, обновить diameter. Вернуть большее из leftPath и rightPath плюс 1.

3⃣Вызвать longestPath с root.

😎 Решение:

public class Solution {
    private int diameter;
    
    public int DiameterOfBinaryTree(TreeNode root) {
        diameter = 0;
        LongestPath(root);
        return diameter;
    }
    
    private int LongestPath(TreeNode node) {
        if (node == null) return 0;
        
        int leftPath = LongestPath(node.left);
        int rightPath = LongestPath(node.right);
        
        diameter = Math.Max(diameter, leftPath + rightPath);
        
        return Math.Max(leftPath, rightPath) + 1;
    }
}

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

Задача: 1509. Minimum Difference Between Largest and Smallest Value in Three Moves
Сложность: medium

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

За один ход вы можете выбрать один элемент массива nums и изменить его на любое значение.

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

Пример:

Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

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

1⃣Инициализация: определите размер массива nums, если размер меньше или равен 4, верните 0. Отсортируйте массив nums и инициализируйте переменную minDiff очень большим числом.

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

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

😎 Решение:

public class Solution {
    public int MinDifference(int[] nums) {
        int numsSize = nums.Length;
        
        if (numsSize <= 4) return 0;
        
        Array.Sort(nums);
        
        int minDiff = int.MaxValue;
        
        for (int left = 0, right = numsSize - 4; left < 4; left++, right++) {
            minDiff = Math.Min(minDiff, nums[right] - nums[left]);
        }
        
        return minDiff;
    }
}

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