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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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