C# | LeetCode

Задача: 525. Contiguous Array
Сложность: medium

Дан бинарный массив nums. Верните максимальную длину непрерывного подмассива с равным количеством 0 и 1.

Пример:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

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

1⃣Инициализируйте переменную count для отслеживания разности между количеством 1 и 0, и переменную max_length для хранения максимальной длины подмассива. Создайте хеш-таблицу map для хранения первых встреч каждого значения count. Добавьте начальное значение (0, -1) в хеш-таблицу.

2⃣Итеративно пройдите по массиву nums. На каждой итерации обновляйте значение count (увеличивайте на 1 для 1 и уменьшайте на 1 для 0). Если текущее значение count уже существует в хеш-таблице, вычислите длину подмассива между текущим индексом и индексом из хеш-таблицы. Обновите max_length, если текущий подмассив длиннее.

3⃣Если текущее значение count не существует в хеш-таблице, добавьте его с текущим индексом. После завершения итерации верните max_length.

😎 Решение:

using System.Collections.Generic;

public class Solution {
    public int FindMaxLength(int[] nums) {
        Dictionary<int, int> countMap = new Dictionary<int, int> { {0, -1} };
        int maxLength = 0;
        int count = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            count += (nums[i] == 1 ? 1 : -1);
            
            if (countMap.ContainsKey(count)) {
                maxLength = Math.Max(maxLength, i - countMap[count]);
            } else {
                countMap[count] = i;
            }
        }
        
        return maxLength;
    }
}

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

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

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

🔥 Скрытые вакансии с удаленной работой для C# разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.

🔹 C# .NET Jobs | Вакансии
🔹 Unity Jobs | Вакансии

🔸 Все каналы с вакансиями

Задача: 645. Set Mismatch
Сложность: easy

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

Пример:

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

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

1⃣Пройдите по массиву, используя набор для отслеживания чисел, чтобы определить дублированное число.

2⃣Определите отсутствующее число, используя сумму чисел от 1 до n и текущую сумму массива.

3⃣Верните дублированное и отсутствующее числа в виде массива.

😎 Решение:

public class Solution {
    public int[] FindErrorNums(int[] nums) {
        int n = nums.Length;
        HashSet<int> numSet = new HashSet<int>();
        int duplicate = -1;
        foreach (int num in nums) {
            if (!numSet.Add(num)) {
                duplicate = num;
            }
        }
        int missing = (n * (n + 1)) / 2 - numSet.Sum();
        return new int[] { duplicate, missing };
    }
}

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

Задача: 927. Three Equal Parts
Сложность: hard

Вам дан массив arr, состоящий только из нулей и единиц. Разделите массив на три непустые части так, чтобы все эти части представляли одно и то же двоичное значение. Если это возможно, верните любой [i, j] с 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] - третья часть. Все три части имеют одинаковые двоичные значения. Если это невозможно, верните [-1, -1]. Обратите внимание, что вся часть используется при рассмотрении того, какое двоичное значение она представляет. Например, [1,1,0] представляет 6 в десятичной системе, а не 3. Кроме того, допускаются ведущие нули, поэтому [0,1,1] и [1,1] представляют одно и то же значение.

Пример:

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

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

1⃣Подсчитать количество единиц в массиве.

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

3⃣Если три части одинаковы, вернуть соответствующие индексы, иначе вернуть [-1, -1].

😎 Решение:

public class Solution {
    public int[] ThreeEqualParts(int[] arr) {
        int ones = 0;
        foreach (int num in arr) {
            ones += num;
        }
        if (ones % 3 != 0) return new int[]{-1, -1};
        if (ones == 0) return new int[]{0, arr.Length - 1};

        int partOnes = ones / 3;
        int first = 0, second = 0, third = 0, cnt = 0;
        for (int i = 0; i < arr.Length; i++) {
            if (arr[i] == 1) {
                if (cnt == 0) first = i;
                else if (cnt == partOnes) second = i;
                else if (cnt == 2 * partOnes) third = i;
                cnt++;
            }
        }

        while (third < arr.Length && arr[first] == arr[second] && arr[first] == arr[third]) {
            first++;
            second++;
            third++;
        }

        if (third == arr.Length) return new int[]{first - 1, second};
        return new int[]{-1, -1};
    }
}

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

Задача: CodeTestcaseTest ResultTest Result1187. Make Array Strictly Increasing
Сложность: hard

Даны два целочисленных массива arr1 и arr2. Верните минимальное количество операций (возможно, ноль), необходимых для того, чтобы сделать arr1 строго возрастающим.

В одной операции вы можете выбрать два индекса 0 <= i < arr1.length и 0 <= j < arr2.length и выполнить присваивание arr1[i] = arr2[j].

Если нет способа сделать arr1 строго возрастающим, верните -1.

Пример:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

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

1⃣ Сначала отсортируйте массив arr2 и инициализируйте хэш-таблицу dp для хранения промежуточных результатов. Определите функцию dfs(i, prev), которая вычисляет минимальное количество операций для сортировки массива arr1, начиная с индекса i, при условии, что предыдущий элемент равен prev. Если результат для (i, prev) уже существует в dp, то просто верните сохраненное значение.

2⃣Внутри функции dfs инициализируйте переменную cost значением float('inf'). Если arr1[i] больше, чем prev, обновите значение cost результатом вызова dfs(i + 1, arr1[i]). Используйте бинарный поиск, чтобы найти индекс idx наименьшего значения в arr2, которое больше prev. Если такой индекс существует, обновите значение cost результатом минимального значения между текущим значением cost и 1 + dfs(i + 1, arr2[idx]).

3⃣После всех вычислений обновите dp[(i, prev)] значением cost и верните cost. В конце вызовите dfs(0, -1) и верните его значение, если оно не равно float('inf'); в противном случае верните -1.

😎 Решение:

public class Solution {
    public int MakeArrayIncreasing(int[] arr1, int[] arr2) {
        Array.Sort(arr2);
        int answer = Dfs(0, -1, arr1, arr2);
        return answer < 2001 ? answer : -1;
    }

    Dictionary<(int, int), int> dp = new Dictionary<(int, int), int>();

    private int Dfs(int i, int prev, int[] arr1, int[] arr2) {
        if (i == arr1.Length) {
            return 0;
        }
        var key = (i, prev);
        if (dp.ContainsKey(key)) {
            return dp[key];
        }

        int cost = 2001;
        if (arr1[i] > prev) {
            cost = Dfs(i + 1, arr1[i], arr1, arr2);
        }

        int idx = Array.BinarySearch(arr2, prev + 1);
        if (idx < 0) {
            idx = ~idx;
        }
        if (idx < arr2.Length) {
            cost = Math.Min(cost, 1 + Dfs(i + 1, arr2[idx], arr1, arr2));
        }

        dp[key] = cost;
        return cost;
    }
}

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

Задача: 1143. Longest Common Subsequence
Сложность: medium

Даны две строки text1 и text2. Верните длину их наибольшей общей подпоследовательности. Если общей подпоследовательности нет, верните 0.

Подпоследовательность строки — это новая строка, созданная из оригинальной строки путем удаления некоторых символов (может быть ни одного) без изменения относительного порядка оставшихся символов.
Например, "ace" является подпоследовательностью "abcde".
Общая подпоследовательность двух строк — это подпоследовательность, которая является общей для обеих строк.

Пример:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

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

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

2⃣Реализуйте рекурсивную функцию memoSolve, которая принимает два указателя на текущие позиции в text1 и text2 и возвращает длину наибольшей общей подпоследовательности для этих подстрок. Если текущие символы совпадают, добавьте 1 к результату рекурсивного вызова для следующих символов. Если не совпадают, найдите максимум между рекурсивными вызовами с измененными указателями.

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

😎 Решение:

public class Solution {
    private int[][] memo;
    private string text1;
    private string text2;
    
    public int LongestCommonSubsequence(string text1, string text2) {
        this.text1 = text1;
        this.text2 = text2;
        memo = new int[text1.Length + 1][];
        for (int i = 0; i < text1.Length + 1; i++) {
            memo[i] = new int[text2.Length + 1];
            Array.Fill(memo[i], -1);
        }
        return MemoSolve(0, 0);
    }
    
    private int MemoSolve(int p1, int p2) {
        if (p1 == text1.Length || p2 == text2.Length) return 0;
        if (memo[p1][p2] != -1) return memo[p1][p2];
        int answer;
        if (text1[p1] == text2[p2]) {
            answer = 1 + MemoSolve(p1 + 1, p2 + 1);
        } else {
            answer = Math.Max(MemoSolve(p1, p2 + 1), MemoSolve(p1 + 1, p2));
        }
        memo[p1][p2] = answer;
        return answer;
    }
}

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

Задача: 954. Array of Doubled Pairs
Сложность: medium

Если задан целочисленный массив четной длины arr, верните true, если можно переупорядочить arr так, чтобы arr[2 * i + 1] = 2 * arr[2 * i] для каждого 0 <= i < len(arr) / 2, или false в противном случае.

Пример:

Input: arr = [3,1,3,6]
Output: false

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

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

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

3⃣Если для каждого элемента можно найти пару, вернуть true, иначе вернуть false.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public bool CanReorderDoubled(int[] arr) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        foreach (int num in arr) {
            if (count.ContainsKey(num)) {
                count[num]++;
            } else {
                count[num] = 1;
            }
        }
        Array.Sort(arr, (a, b) => Math.Abs(a).CompareTo(Math.Abs(b)));
        foreach (int num in arr) {
            if (count[num] == 0) continue;
            if (!count.ContainsKey(2 * num) || count[2 * num] == 0) return false;
            count[num]--;
            count[2 * num]--;
        }
        return true;
    }
}

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

Задача: 374. Guess Number Higher or Lower
Сложность: easy

Мы играем в игру "Угадай число". Правила игры следующие:

Я загадываю число от 1 до n. Вам нужно угадать, какое число я загадал.

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

Вы вызываете предопределенный API int guess(int num), который возвращает один из трех возможных результатов:

-1: Ваше предположение больше загаданного числа (т.е. num > pick).
1: Ваше предположение меньше загаданного числа (т.е. num < pick).
0: Ваше предположение равно загаданному числу (т.е. num == pick).
Верните загаданное число.

Пример:

Input: n = 10, pick = 6
Output: 6

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

1⃣Применяем бинарный поиск для нахождения загаданного числа. Начинаем с числа, расположенного в середине диапазона. Передаем это число функции guess.

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

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

😎 Решение:

public class Solution : GuessGame {
    public int GuessNumber(int n) {
        int low = 1;
        int high = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int res = guess(mid);
            if (res == 0)
                return mid;
            else if (res < 0)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }
}

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

Задача: 672. Bulb Switcher II
Сложность: medium

Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:

Кнопка 1: Переключает состояние всех лампочек.
Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).
Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).
Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).
Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.

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

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

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

1⃣Рассчитаем возможные множества остатков: то есть какие множества c_i = f_i (mod 2) возможны.

2⃣Так как c_i ≡ f_i и c_i ≤ f_i, если ∑f_i ≠ ∑c_i, или если ∑f_i < ∑c_i, это невозможно. В противном случае это возможно простым построением: выполните операции, указанные c_i, затем выполните операцию номер 1 с четным числом оставшихся операций.

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

😎 Решение:

public class Solution {
    public int FlipLights(int n, int m) {
        var seen = new HashSet<int>();
        n = Math.Min(n, 6);
        int shift = Math.Max(0, 6 - n);
        for (int cand = 0; cand < 16; ++cand) {
            int bcount = Convert.ToString(cand, 2).Count(c => c == '1');
            if (bcount % 2 == m % 2 && bcount <= m) {
                int lights = 0;
                if (((cand >> 0) & 1) > 0) lights ^= 0b111111 >> shift;
                if (((cand >> 1) & 1) > 0) lights ^= 0b010101 >> shift;
                if (((cand >> 2) & 1) > 0) lights ^= 0b101010 >> shift;
                if (((cand >> 3) & 1) > 0) lights ^= 0b100100 >> shift;
                seen.Add(lights);
            }
        }
        return seen.Count;
    }
}

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

Задача: 37. Sudoku Solver
Сложность: hard

Напишите программу для решения головоломки Судоку, заполнив пустые ячейки.

Решение должно удовлетворять следующим условиям:

- В каждой строке числа 1-9 встречаются ровно один раз.
- В каждом столбце числа 1-9 встречаются ровно один раз.
- В каждом 3x3 блоке числа 1-9 встречаются ровно один раз.
- Символ '.' обозначает пустые ячейки.

Пример:

Input: board =  
[["5","3",".",".","7",".",".",".","."]  
,["6",".",".","1","9","5",".",".","."]  
,[".","9","8",".",".",".",".","6","."]  
,["8",".",".",".","6",".",".",".","3"]  
,["4",".",".","8",".","3",".",".","1"]  
,["7",".",".",".","2",".",".",".","6"]  
,[".","6",".",".",".",".","2","8","."]  
,[".",".",".","4","1","9",".",".","5"]  
,[".",".",".",".","8",".",".","7","9"]]  

Output:  
[["5","3","4","6","7","8","9","1","2"]  
,["6","7","2","1","9","5","3","4","8"]  
,["1","9","8","3","4","2","5","6","7"]  
,["8","5","9","7","6","1","4","2","3"]  
,["4","2","6","8","5","3","7","9","1"]  
,["7","1","3","9","2","4","8","5","6"]  
,["9","6","1","5","3","7","2","8","4"]  
,["2","8","7","4","1","9","6","3","5"]  
,["3","4","5","2","8","6","1","7","9"]]  

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

1⃣Реализуйте обратный поиск: найдите первую пустую ячейку и попробуйте вставить числа от 1 до 9.

2⃣Проверять достоверность вставок: не нарушать правила чисел, строки, столбцы и блоки.

3⃣Если число достоверно — вставьте и перейдите к следующей ячейке, иначе откатиться (назад) и еще раз попробовать.

😎 Решение:

public class Solution {
    private const int N = 9;
    private char[][] board;
    private bool[,] rows = new bool[N, N + 1];
    private bool[,] cols = new bool[N, N + 1];
    private bool[,] boxes = new bool[N, N + 1];

    public void SolveSudoku(char[][] inputBoard) {
        board = inputBoard;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (board[r][c] != '.') {
                    int num = board[r][c] - '0';
                    PlaceNumber(num, r, c, true);
                }
            }
        }
        Backtrack(0, 0);
    }

    private bool Backtrack(int row, int col) {
        if (col == N) { col = 0; row++; }
        if (row == N) return true;

        if (board[row][col] != '.') return Backtrack(row, col + 1);

        for (int num = 1; num <= 9; num++) {
            if (CouldPlace(num, row, col)) {
                PlaceNumber(num, row, col, true);
                if (Backtrack(row, col + 1)) return true;
                PlaceNumber(num, row, col, false);
            }
        }

        return false;
    }

    private bool CouldPlace(int num, int row, int col) {
        int boxIndex = (row / 3) * 3 + col / 3;
        return !rows[row, num] && !cols[col, num] && !boxes[boxIndex, num];
    }

    private void PlaceNumber(int num, int row, int col, bool place) {
        board[row][col] = place ? (char)(num + '0') : '.';
        rows[row, num] = place;
        cols[col, num] = place;
        boxes[(row / 3) * 3 + col / 3, num] = place;
    }
}

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

Задача: 1129. Shortest Path with Alternating Colors
Сложность: medium

Вам дано целое число n, количество узлов в ориентированном графе, где узлы помечены от 0 до n - 1. Каждое ребро в этом графе может быть красным или синим, и могут быть самопетли и параллельные ребра.

Вам даны два массива redEdges и blueEdges, где:
redEdges[i] = [ai, bi] указывает, что в графе существует направленное красное ребро от узла ai к узлу bi, и
blueEdges[j] = [uj, vj] указывает, что в графе существует направленное синее ребро от узла uj к узлу vj.
Верните массив answer длины n, где каждый answer[x] — это длина кратчайшего пути от узла 0 до узла x, такого что цвета ребер чередуются вдоль пути, или -1, если такого пути не существует.

Пример:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

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

1⃣Создание структуры данных и инициализация:
Создайте список смежности adj, который будет содержать пары (сосед, цвет) для каждого узла.
Создайте массив answer длиной n, инициализированный значением -1, чтобы хранить длину кратчайшего пути для каждого узла.
Создайте 2D массив visit для отслеживания, были ли узлы посещены с использованием ребра определённого цвета.

2⃣Инициализация очереди и начальных условий:
Создайте очередь для хранения трёх значений (узел, количество шагов, цвет предыдущего ребра).
Добавьте в очередь начальный узел (0, 0, -1) и установите visit[0][0] и visit[0][1] в true, так как повторное посещение узла 0 бессмысленно.

3⃣Обработка очереди и обновление результата:
Пока очередь не пуста, извлекайте элемент из очереди и получайте (узел, количество шагов, цвет предыдущего ребра).
Для каждого соседа, если сосед не был посещён с использованием ребра текущего цвета и текущий цвет не равен предыдущему, обновите массив answer и добавьте соседа в очередь.

😎 Решение:

public class Solution {
    public int[] ShortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        var adj = new Dictionary<int, List<(int, int)>>();
        foreach (var edge in redEdges) {
            if (!adj.ContainsKey(edge[0])) adj[edge[0]] = new List<(int, int)>();
            adj[edge[0]].Add((edge[1], 0));
        }
        foreach (var edge in blueEdges) {
            if (!adj.ContainsKey(edge[0])) adj[edge[0]] = new List<(int, int)>();
            adj[edge[0]].Add((edge[1], 1));
        }

        var answer = new int[n];
        Array.Fill(answer, -1);
        var visit = new bool[n, 2];
        var queue = new Queue<(int node, int steps, int prevColor)>();
        queue.Enqueue((0, 0, -1));
        answer[0] = 0;
        visit[0, 0] = true;
        visit[0, 1] = true;

        while (queue.Count > 0) {
            var (node, steps, prevColor) = queue.Dequeue();
            if (!adj.ContainsKey(node)) continue;

            foreach (var (neighbor, color) in adj[node]) {
                if (!visit[neighbor, color] && color != prevColor) {
                    if (answer[neighbor] == -1) answer[neighbor] = steps + 1;
                    visit[neighbor, color] = true;
                    queue.Enqueue((neighbor, steps + 1, color));
                }
            }
        }
        return answer;
    }
}

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

Задача: 400. Nth Digit
Сложность: medium

Дано целое число n, вернуть n-ю цифру бесконечной последовательности чисел [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].

Пример:

Input: n = 3
Output: 3

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

1⃣Определение диапазона:
Начните с определения количества цифр в числах текущего диапазона (1-9, 10-99, 100-999 и т.д.).
Уменьшайте значение n, вычитая количество цифр в текущем диапазоне, пока не найдете диапазон, в который попадает n-я цифра.

2⃣Нахождение конкретного числа:
Когда определите диапазон, найдите точное число, содержащее n-ю цифру.
Определите индекс цифры в этом числе.

3⃣Возвращение n-й цифры:
Извлеките и верните n-ю цифру из найденного числа.

😎 Решение:

public class Solution {
    public int FindNthDigit(int n) {
        long length = 1, count = 9, start = 1;
        
        while (n > length * count) {
            n -= (int)(length * count);
            length++;
            count *= 10;
            start *= 10;
        }
        
        start += (n - 1) / length;
        string s = start.ToString();
        return s[(n - 1) % (int)length] - '0';
    }
}

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

Задача: 656. Coin Path
Сложность: hard

Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y.

Пример:

Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]

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

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

2⃣Храните путь до каждого индекса для отслеживания наименьшего лексикографического пути.

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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public List<int> MinCostPath(int[] coins, int maxJump) {
        int n = coins.Length;
        if (coins[0] == -1) return new List<int>();
        
        int[] dp = new int[n];
        Array.Fill(dp, int.MaxValue);
        dp[0] = coins[0];
        List<int>[] path = new List<int>[n];
        for (int i = 0; i < n; i++) path[i] = new List<int>();
        path[0].Add(1);
        
        PriorityQueue<(int cost, int index), int> heap = new PriorityQueue<(int, int), int>();
        heap.Enqueue((coins[0], 0), coins[0]);
        
        while (heap.Count > 0) {
            var (currentCost, i) = heap.Dequeue();
            if (currentCost > dp[i]) continue;
            for (int k = 1; k <= maxJump; k++) {
                if (i + k < n && coins[i + k] != -1) {
                    int newCost = currentCost + coins[i + k];
                    if (newCost < dp[i + k] || (newCost == dp[i + k] && ComparePaths(path[i], path[i + k], i + k + 1))) {
                        dp[i + k] = newCost;
                        path[i + k] = new List<int>(path[i]);
                        path[i + k].Add(i + k + 1);
                        heap.Enqueue((newCost, i + k), newCost);
                    }
                }
            }
        }
        
        return dp[n - 1] == int.MaxValue ? new List<int>() : path[n - 1];
    }

    private bool ComparePaths(List<int> path1, List<int> path2, int newIndex) {
        List<int> newPath1 = new List<int>(path1);
        newPath1.Add(newIndex);
        return string.Join(",", newPath1).CompareTo(string.Join(",", path2)) < 0;
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        int[] coins = { 0, 2, 4, -1, 2, 5 };
        int maxJump = 2;
        var result = solution.MinCostPath(coins, maxJump);
    }
}

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

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

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

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

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

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

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

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

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

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

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

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

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