C# | LeetCode

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

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

Задача: 399. Evaluate Division Сложность: medium Вам дан массив пар переменных equations и массив вещественных чисел values, где equations[i] = [Ai, Bi] и values[i] представляют уравнение Ai / Bi = values[i]. Каждая Ai или Bi - это строка, представляющая одну переменную. Вам также даны некоторые запросы, где queries[j] = [Cj, Dj] представляет j-й запрос, в котором вы должны найти ответ для Cj / Dj = ?. Верните ответы на все запросы. Если ни один ответ не может быть определен, верните -1.0. Замечание: входные данные всегда действительны. Можно предположить, что вычисление запросов не приведет к делению на ноль и что противоречия нет. Примечание: Переменные, которые не встречаются в списке уравнений, являются неопределенными, поэтому для них ответ не может быть определен. Пример:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

👨‍💻 Алгоритм: 1⃣Создание графа: Представьте каждую переменную как узел в графе. Используйте уравнения для создания ребер между узлами, где каждое ребро имеет вес, равный значению уравнения (Ai / Bi = values[i]). Создайте также обратные ребра с обратным весом (Bi / Ai = 1 / values[i]). 2⃣Поиск пути: Для каждого запроса используйте поиск в глубину (DFS) или поиск в ширину (BFS) для поиска пути от Cj до Dj. Если путь найден, вычислите произведение весов вдоль пути, чтобы найти значение Cj / Dj. Если путь не найден, верните -1.0. 3⃣Обработка запросов: Пройдитесь по всем запросам и используйте граф для вычисления результатов каждого запроса. 😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public double[] CalcEquation(IList<IList<string>> equations, double[] values, IList<IList<string>> queries) {
        var graph = new Dictionary<string, Dictionary<string, double>>();

        for (int i = 0; i < equations.Count; i++) {
            string A = equations[i][0], B = equations[i][1];
            double value = values[i];
            if (!graph.ContainsKey(A)) graph[A] = new Dictionary<string, double>();
            if (!graph.ContainsKey(B)) graph[B] = new Dictionary<string, double>();
            graph[A][B] = value;
            graph[B][A] = 1.0 / value;
        }

        double Bfs(string start, string end) {
            if (!graph.ContainsKey(start) || !graph.ContainsKey(end)) return -1.0;
            var q = new Queue<(string, double)>();
            q.Enqueue((start, 1.0));
            var visited = new HashSet<string>();
            
            while (q.Count > 0) {
                var (current, curProduct) = q.Dequeue();
                if (current == end) return curProduct;
                visited.Add(current);
                foreach (var neighbor in graph[current]) {
                    if (!visited.Contains(neighbor.Key)) {
                        q.Enqueue((neighbor.Key, curProduct * neighbor.Value));
                    }
                }
            }
            return -1.0;
        }

        var results = new double[queries.Count];
        for (int i = 0; i < queries.Count; i++) {
            string C = queries[i][0], D = queries[i][1];
            results[i] = Bfs(C, D);
        }
        return results;
    }
}

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

Задача: 224. Basic Calculator Сложность: hard Дана строка s, представляющая собой допустимое выражение, реализуйте базовый калькулятор для его вычисления и верните результат вычисления. Примечание: нельзя использовать встроенные функции, которые оценивают строки как математические выражения, такие как eval(). Пример:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

👨‍💻 Алгоритм: 1⃣Итерация строки выражения в обратном порядке: Читаем выражение символ за символом, формируя операнды из нескольких цифр, если символ - цифра. Сохраняем операнды в стек, как только встречаем нецифровой символ. 2⃣Обработка выражения внутри скобок: Когда встречаем открывающую скобку '(', оцениваем выражение, удаляя операнды и операторы из стека до соответствующей закрывающей скобки. Результат выражения помещаем обратно в стек. 3⃣Финальная оценка выражения: Продолжаем процесс до получения финального результата. Если стек не пуст после обработки всех символов, оцениваем оставшиеся элементы как одно финальное выражение. 😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {

    public int EvaluateExpr(Stack<object> stack) {
        if (stack.Count == 0 || !(stack.Peek() is int)) {
            stack.Push(0);
        }

        int res = (int)stack.Pop();

        while (stack.Count != 0 && !((char)stack.Peek() == ')')) {
            char sign = (char)stack.Pop();

            if (sign == '+') {
                res += (int)stack.Pop();
            } else {
                res -= (int)stack.Pop();
            }
        }
        return res;
    }

    public int Calculate(string s) {
        int operand = 0;
        int n = 0;
        Stack<object> stack = new Stack<object>();

        for (int i = s.Length - 1; i >= 0; i--) {
            char ch = s[i];

            if (char.IsDigit(ch)) {
                operand = (int)Math.Pow(10, n) * (ch - '0') + operand;
                n += 1;
            } else if (ch != ' ') {
                if (n != 0) {
                    stack.Push(operand);
                    n = 0;
                    operand = 0;
                }
                if (ch == '(') {
                    int res = EvaluateExpr(stack);
                    stack.Pop();
                    stack.Push(res);
                } else {
                    stack.Push(ch);
                }
            }
        }

        if (n != 0) {
            stack.Push(operand);
        }

        return EvaluateExpr(stack);
    }
}

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

Задача: 419. Battleships in a Board Сложность: medium Если задана матричная доска размером m x n, где каждая клетка - линкор 'X' или пустая '.', верните количество линкоров на доске. Линкоры могут располагаться на доске только горизонтально или вертикально. Другими словами, они могут быть выполнены только в форме 1 x k (1 строка, k столбцов) или k x 1 (k строк, 1 столбец), где k может быть любого размера. Между двумя линкорами есть хотя бы одна горизонтальная или вертикальная клетка (т. е. нет соседних линкоров). Пример:

Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
Output: 2

👨‍💻 Алгоритм: 1⃣Пройдите по каждой клетке матрицы. 2⃣Если текущая клетка содержит 'X' и она не является продолжением линкора (т.е. не имеет 'X' сверху или слева), увеличьте счетчик линкоров. 3⃣Верните итоговый счетчик. 😎 Решение:

public class Solution {
    public int CountBattleships(char[][] board) {
        int m = board.Length;
        int n = board[0].Length;
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X') {
                    if ((i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.')) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
}

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

Задача: 1025. Divisor Game Сложность: easy Алиса и Боб играют в игру по очереди, причем Алиса начинает первой. Изначально на доске мелом написано число n. В свой ход каждый игрок делает ход, состоящий из: выбора любого x при 0 < x < n и n % x == 0. Замены числа n на доске на n - x. Также, если игрок не может сделать ход, он проигрывает игру. Возвращается true тогда и только тогда, когда Алиса выигрывает игру, предполагая, что оба игрока играют оптимально. Пример:

Input: n = 2
Output: true

👨‍💻 Алгоритм: 1⃣Определение выигрыша: Заметим, что если число n четное, Алиса всегда выигрывает, потому что она может уменьшить n на 1, и оставить Боба с нечетным числом. Если число n нечетное, Алиса всегда проигрывает, потому что Боб может уменьшить n на 1, и оставить Алису с четным числом. 2⃣Проверка четности числа: Проверяем, четное ли число n. Если n четное, возвращаем true, если нечетное, возвращаем false. 3⃣Возврат результата: Возвращаем результат в зависимости от четности числа n. 😎 Решение:

public class Solution {
    public bool DivisorGame(int n) {
        return n % 2 == 0;
    }
}

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

Задача: 126.Word Ladder II Сложность: hard Последовательность преобразований от слова beginWord до слова endWord с использованием словаря wordList — это последовательность слов beginWord -> s1 -> s2 -> ... -> sk, для которой выполняются следующие условия: Каждая пара соседних слов отличается ровно одной буквой. Каждое si для 1 <= i <= k находится в wordList. Отметим, что beginWord не обязательно должно быть в wordList. sk == endWord. Для двух слов, beginWord и endWord, и словаря wordList, вернуть все самые короткие последовательности преобразований от beginWord до endWord или пустой список, если такая последовательность не существует. Каждая последовательность должна возвращаться в виде списка слов [beginWord, s1, s2, ..., sk]. Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation: There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

👨‍💻 Алгоритм: 1⃣Сохранение слов из списка слов (wordList) в хэш-таблицу (unordered set) для эффективного удаления слов в процессе поиска в ширину (BFS). 2⃣Выполнение BFS, добавление связей в список смежности (adjList). После завершения уровня удалять посещенные слова из wordList. 3⃣Начать с beginWord и отслеживать текущий путь как currPath, просматривать все возможные пути, и когда путь ведет к endWord, сохранять путь в shortestPaths. 😎 Решение:

public class Solution {
    Dictionary<string, List<string>> adjList = new Dictionary<string, List<string>>();
    List<string> currPath = new List<string>();
    List<IList<string>> shortestPaths = new List<IList<string>>();

    private List<string> FindNeighbors(string word, HashSet<string> wordList) {
        List<string> neighbors = new List<string>();
        char[] charList = word.ToCharArray();
        for (int i = 0; i < word.Length; i++) {
            char oldChar = charList[i];
            for (char c = 'a'; c <= 'z'; c++) {
                if (c != oldChar) {
                    charList[i] = c;
                    string newWord = new string(charList);
                    if (wordList.Contains(newWord)) neighbors.Add(newWord);
                }
            }
            charList[i] = oldChar;
        }
        return neighbors;
    }

    private void Backtrack(string source, string destination) {
        if (source == destination) {
            var tempPath = new List<string>(currPath);
            tempPath.Reverse();
            shortestPaths.Add(tempPath);
            return;
        }
        if (adjList.ContainsKey(source)) {
            foreach (var neighbor in adjList[source]) {
                currPath.Add(neighbor);
                Backtrack(neighbor, destination);
                currPath.RemoveAt(currPath.Count - 1);
            }
        }
    }

    private void Bfs(string beginWord, HashSet<string> wordList) {
        Queue<string> q = new Queue<string>(new[] { beginWord });
        wordList.Remove(beginWord);
        while (q.Count > 0) {
            for (int i = q.Count; i > 0; i--) {
                var currWord = q.Dequeue();
                foreach (var neighbor in FindNeighbors(currWord, wordList)) {
                    if (!adjList.TryGetValue(neighbor, out var list)) {
                        list = adjList[neighbor] = new List<string>();
                        q.Enqueue(neighbor);
                    }
                    list.Add(currWord);
                }
            }
        }
    }

    public IList<IList<string>> FindLadders(string beginWord, string endWord, IList<string> wordList) {
        Bfs(beginWord, new HashSet<string>(wordList));
        currPath.Add(endWord);
        Backtrack(endWord, beginWord);
        return shortestPaths;
    }
}

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

Задача: 848. Shifting Letters Сложность: medium Вам дана строка s из строчных букв английского алфавита и целочисленный массив shifts такой же длины. Назовем shift() буквы следующей буквой в алфавите (с переходом так, что 'z' становится 'a'). Например, shift('a') = 'b', shift('t') = 'u', и shift('z') = 'a'. Теперь для каждого shifts[i] = x мы хотим сдвинуть первые i + 1 букв строки s на x раз. Верните итоговую строку после применения всех таких сдвигов к s. Пример:

Input: s = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: We start with "abc".
After shifting the first 1 letters of s by 3, we have "dbc".
After shifting the first 2 letters of s by 5, we have "igc".
After shifting the first 3 letters of s by 9, we have "rpl", the answer.

👨‍💻 Алгоритм: 1⃣Вычислите общее количество сдвигов для всех символов строки, используя массив shifts. 2⃣Пройдите по строке s и примените вычисленные сдвиги к каждому символу, начиная с первого и уменьшая количество сдвигов на текущем шаге. 3⃣Постройте и верните итоговую строку после всех сдвигов. 😎 Решение:

public class Solution {
    public string ShiftingLetters(string s, int[] shifts) {
        var result = new char[s.Length];
        int totalShifts = 0;
        foreach (int shift in shifts) {
            totalShifts = (totalShifts + shift) % 26;
        }

        for (int i = 0; i < s.Length; ++i) {
            int newCharValue = (s[i] - 'a' + totalShifts) % 26;
            result[i] = (char)(newCharValue + 'a');
            totalShifts = (totalShifts - shifts[i] + 26) % 26;
        }

        return new string(result);
    }
}

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

Задача: 928. Minimize Malware Spread II Сложность: hard Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом. Пример:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

👨‍💻 Алгоритм: 1⃣Определить компоненты связности в графе. Для каждой компоненты связности определить количество зараженных узлов и общее количество узлов. 2⃣Для каждого узла в initial удалить его и пересчитать количество зараженных узлов. 3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если несколько узлов минимизируют количество зараженных узлов одинаково, выбрать узел с наименьшим индексом. 😎 Решение:

public class Solution {
    public int MinMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.Length;
        var visited = new HashSet<int>();
        var components = new List<HashSet<int>>();
        
        void Dfs(int node) {
            var stack = new Stack<int>();
            stack.Push(node);
            var component = new HashSet<int>();
            while (stack.Count > 0) {
                int u = stack.Pop();
                if (!visited.Contains(u)) {
                    visited.Add(u);
                    component.Add(u);
                    for (int v = 0; v < n; v++) {
                        if (graph[u][v] == 1 && !visited.Contains(v)) {
                            stack.Push(v);
                        }
                    }
                }
            }
            components.Add(component);
        }
        
        for (int i = 0; i < n; i++) {
            if (!visited.Contains(i)) {
                Dfs(i);
            }
        }
        
        int[] infectedInComponent = new int[components.Count];
        int[] nodeToComponent = new int[n];
        Array.Fill(nodeToComponent, -1);
        
        for (int idx = 0; idx < components.Count; idx++) {
            var component = components[idx];
            foreach (int node in component) {
                nodeToComponent[node] = idx;
                if (Array.IndexOf(initial, node) >= 0) {
                    infectedInComponent[idx]++;
                }
            }
        }
        
        int minInfected = int.MaxValue;
        int resultNode = initial.Min();
        
        foreach (int node in initial) {
            int componentIdx = nodeToComponent[node];
            if (infectedInComponent[componentIdx] == 1) {
                int componentSize = components[componentIdx].Count;
                if (componentSize < minInfected || (componentSize == minInfected && node < resultNode)) {
                    minInfected = componentSize;
                    resultNode = node;
                }
            }
        }
        
        return resultNode;
    }
}

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

Задача: 786. K-th Smallest Prime Fraction Сложность: medium Вам дан отсортированный массив целых чисел arr, содержащий 1 и простые числа, где все элементы массива arr уникальны. Также дано целое число k. Для каждого i и j, где 0 <= i < j < arr.length, мы рассматриваем дробь arr[i] / arr[j]. Верните k-ую наименьшую дробь из рассмотренных. Верните ответ в виде массива из двух целых чисел размера 2, где answer[0] == arr[i] и answer[1] == arr[j]. Пример:

Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.

👨‍💻 Алгоритм: 1⃣Инициализируйте пустую приоритетную очередь pq для хранения пар дробей и соответствующих им индексов. Итеративно пройдите по входному массиву arr, используя переменную цикла i. Для каждого элемента arr[i] вычислите дробь, образованную делением его на наибольший элемент в массиве (arr[arr.size() - 1]). Поместите пару, состоящую из отрицательного значения дроби (-1.0 * arr[i] / arr[arr.size() - 1]) и соответствующих индексов (i для числителя и arr.size() - 1 для знаменателя), в приоритетную очередь pq. Приоритетная очередь pq теперь содержит все дроби, образованные делением каждого элемента на наибольший элемент в массиве, отсортированные в порядке возрастания значений дробей. 2⃣Повторите следующие шаги k - 1 раз: удалите верхний элемент (наименьшую дробь) из приоритетной очереди pq и сохраните его индексы в переменной cur. Уменьшите индекс знаменателя (cur[1]--). Вычислите новую дробь, образованную делением числителя в cur[0] на уменьшенный знаменатель (arr[cur[1]]). Поместите новое значение дроби (-1.0 * arr[cur[0]] / arr[cur[1]]) и соответствующие индексы (cur[0] для числителя и cur[1] для знаменателя) в приоритетную очередь pq. После k - 1 итераций верхний элемент приоритетной очереди pq будет k-й наименьшей дробью. 3⃣Извлеките индексы числителя и знаменателя из верхнего элемента приоритетной очереди и сохраните их в result. Верните массив, содержащий значения числителя (arr[result[0]]) и знаменателя (arr[result[1]]), соответствующие k-й наименьшей дроби. 😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int[] KthSmallestPrimeFraction(int[] arr, int k) {
        var pq = new PriorityQueue<(double Fraction, int[] Indices), double>();

        for (int i = 0; i < arr.Length - 1; i++) {
            pq.Enqueue((arr[i] / (double)arr[arr.Length - 1], new int[] { i, arr.Length - 1 }), arr[i] / (double)arr[arr.Length - 1]);
        }

        for (int i = 0; i < k - 1; i++) {
            var (fraction, indices) = pq.Dequeue();
            var numeratorIndex = indices[0];
            var denominatorIndex = indices[1] - 1;
            if (denominatorIndex > numeratorIndex) {
                pq.Enqueue((arr[numeratorIndex] / (double)arr[denominatorIndex], new int[] { numeratorIndex, denominatorIndex }), arr[numeratorIndex] / (double)arr[denominatorIndex]);
            }
        }

        var result = pq.Dequeue();
        return new int[] { arr[result.Indices[0]], arr[result.Indices[1]] };
    }
}

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

Задача: 978. Longest Turbulent Subarray Сложность: medium Дан целочисленный массив arr, верните длину максимального турбулентного подмассива массива arr. Подмассив считается турбулентным, если знак сравнения меняется между каждой парой смежных элементов в подмассиве. Более формально, подмассив [arr[i], arr[i + 1], ..., arr[j]] массива arr считается турбулентным тогда и только тогда, когда: Для всех i <= k < j: arr[k] > arr[k + 1], когда k нечетное, и arr[k] < arr[k + 1], когда k четное. Или, для всех i <= k < j: arr[k] > arr[k + 1], когда k четное, и arr[k] < arr[k + 1], когда k нечетное. Пример:

Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

👨‍💻 Алгоритм: 1⃣Сканируйте массив слева направо. Используйте переменные для отслеживания начала текущего блока и максимальной длины турбулентного подмассива. 2⃣Если достигли конца блока (последний элемент или текущий элемент не соответствует условию чередования), зафиксируйте длину этого блока как потенциальный ответ и установите начало нового блока на следующий элемент. 3⃣Повторяйте шаг 2 до конца массива и верните максимальную длину турбулентного подмассива. 😎 Решение:

public class Solution {
    public int MaxTurbulenceSize(int[] A) {
        int N = A.Length;
        int ans = 1;
        int anchor = 0;

        for (int i = 1; i < N; ++i) {
            int c = Math.Sign(A[i - 1] - A[i]);
            if (c == 0) {
                anchor = i;
            } else if (i == N - 1 || c * Math.Sign(A[i] - A[i + 1]) != -1) {
                ans = Math.Max(ans, i - anchor + 1);
                anchor = i;
            }
        }

        return ans;
    }
}

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

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

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

Задача: 1673. Find the Most Competitive Subsequence Сложность: medium Дан целочисленный массив nums и положительное целое число k. Верните наиболее конкурентоспособную подпоследовательность массива nums размера k. Подпоследовательность массива — это результирующая последовательность, полученная путем удаления некоторых (возможно, нуля) элементов из массива. Мы определяем, что подпоследовательность a более конкурентоспособна, чем подпоследовательность b (одинаковой длины), если в первой позиции, где они различаются, подпоследовательность a имеет число меньше, чем соответствующее число в b. Например, [1,3,4] более конкурентоспособна, чем [1,3,5], потому что первая позиция, где они различаются, это последнее число, и 4 меньше, чем 5. Пример:

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

👨‍💻 Алгоритм: 1⃣ Создайте двустороннюю очередь (deque), которая будет хранить выбранную подпоследовательность. 2⃣ Переберите массив nums, выбирая наиболее конкурентоспособные элементы и добавляя их в очередь. Сравнивайте последний элемент в очереди с текущим элементом, удаляя из очереди более крупные элементы, если можно удалить больше элементов, чем необходимо для достижения размера k. 3⃣ В конце получите первые k элементов из очереди и создайте результирующий массив. 😎 Решение:

public class Solution {
    public int[] MostCompetitive(int[] nums, int k) {
        var queue = new LinkedList<int>();
        int additionalCount = nums.Length - k;
        
        foreach (int num in nums) {
            while (queue.Count > 0 && queue.Last.Value > num && additionalCount > 0) {
                queue.RemoveLast();
                additionalCount--;
            }
            queue.AddLast(num);
        }
        
        return queue.Take(k).ToArray();
    }
}

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

Задача: 1018. Binary Prefix Divisible By 5 Сложность: easy Вам дан двоичный массив nums (индексированный 0). Мы определяем xi как число, двоичным представлением которого является подмассив nums[0..i] (от старшего бита к младшему). Например, если nums = [1,0,1], то x0 = 1, x1 = 2 и x2 = 5. Верните массив булевых чисел answer, где answer[i] истинно, если xi делится на 5. Пример:

Input: nums = [0,1,1]
Output: [true,false,false]

👨‍💻 Алгоритм: 1⃣Инициализация и вычисление: Создайте переменную x для хранения текущего числа в десятичной системе. Создайте пустой массив answer для хранения результатов делимости на 5. 2⃣Итерация по массиву: Пройдите по всем элементам массива nums. Для каждого элемента: Обновите значение x, учитывая текущий бит. Проверяйте, делится ли x на 5, и добавьте результат (true или false) в массив answer. Чтобы избежать переполнения, используйте модуль 5 для переменной x. 3⃣Возврат результата: Верните массив answer с результатами проверки делимости на 5. 😎 Решение:

public class Solution {
    public bool[] PrefixesDivBy5(int[] nums) {
        int x = 0;
        bool[] answer = new bool[nums.Length];
        for (int i = 0; i < nums.Length; i++) {
            x = (x * 2 + nums[i]) % 5;
            answer[i] = x == 0;
        }
        return answer;
    }
}

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

Задача: 819. Most Common Word Сложность: easy Дана строка paragraph и массив строк banned, представляющий запрещенные слова. Верните наиболее часто встречающееся слово, которое не запрещено. Гарантируется, что существует хотя бы одно слово, которое не запрещено, и что ответ является уникальным. Слова в paragraph нечувствительны к регистру, и ответ должен быть возвращен в нижнем регистре. Пример:

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

👨‍💻 Алгоритм: 1⃣Заменяем всю пунктуацию пробелами и одновременно переводим каждую букву в нижний регистр. Это можно сделать и в два этапа, но здесь мы объединяем их в один этап. 2⃣Разбиваем полученный результат на слова, используя пробелы в качестве разделителей. 3⃣Затем итерируемся по словам, чтобы подсчитать количество появлений каждого уникального слова, исключая слова из списка запрещенных. С помощью хеш-таблицы {слово->количество} проходим по всем элементам, чтобы найти слово с наивысшей частотой. 😎 Решение:

public class Solution {
    public string MostCommonWord(string paragraph, IList<string> banned) {
        string normalizedStr = new string(paragraph.Select(c => char.IsLetterOrDigit(c) ? char.ToLower(c) : ' ').ToArray());
        string[] words = normalizedStr.Split(new[] {' '}, StringSplitOptions.RemoveEmptyEntries);
        var wordCount = new Dictionary<string, int>();
        var bannedWords = new HashSet<string>(banned);

        foreach (string word in words) {
            if (!bannedWords.Contains(word)) {
                if (!wordCount.ContainsKey(word)) {
                    wordCount[word] = 0;
                }
                wordCount[word]++;
            }
        }

        return wordCount.OrderByDescending(kv => kv.Value).First().Key;
    }
}

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

Задача: 1023. Camelcase Matching Сложность: medium Учитывая массив строк queries и строку pattern, верните булевский массив answer, где answer[i] - true, если queries[i] соответствует pattern, и false в противном случае. Слово запроса queries[i] соответствует pattern, если вы можете вставить строчные английские буквы pattern так, чтобы они были равны запросу. Вы можете вставить каждый символ в любую позицию и не можете вставить ни одного символа. Пример:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Создайте массив answer для хранения результатов соответствия каждого запроса шаблону. 2⃣Проверка каждого запроса: Для каждого запроса из queries, проверьте, можно ли вставить строчные буквы в pattern, чтобы они соответствовали запросу. Используйте два указателя, один для query и один для pattern. Перемещайте оба указателя, пока они не достигнут конца строк. Если текущие символы совпадают, переместите оба указателя. Если символы не совпадают и текущий символ в запросе является строчной буквой, переместите только указатель запроса. 3⃣Возврат результата: Если указатель шаблона достиг конца строки, добавьте true в answer, иначе добавьте false. Верните массив answer. 😎 Решение:

public class Solution {
    public bool[] CamelMatch(string[] queries, string pattern) {
        bool Matches(string query, string pattern) {
            int i = 0, j = 0;
            while (i < query.Length) {
                if (j < pattern.Length && query[i] == pattern[j]) {
                    j++;
                } else if (char.IsUpper(query[i])) {
                    return false;
                }
                i++;
            }
            return j == pattern.Length;
        }
        
        bool[] answer = new bool[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            answer[i] = Matches(queries[i], pattern);
        }
        
        return answer;
    }
}

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

Задача: 961. N-Repeated Element in Size 2N Array Сложность: easy Вам дан целочисленный массив nums со следующими свойствами: nums.length == 2 * n. nums содержит n + 1 уникальных элементов. Ровно один элемент массива nums повторяется n раз. Верните элемент, который повторяется n раз. Пример:

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

👨‍💻 Алгоритм: 1⃣Проверить все подмассивы длиной 4. В таком подмассиве обязательно будет главный элемент, повторяющийся n раз. 2⃣Сравнить элементы массива с их соседями на расстоянии 1, 2 и 3. Если найдется повторяющийся элемент, он и будет искомым. 3⃣Вернуть найденный элемент. 😎 Решение:

public class Solution {
    public int RepeatedNTimes(int[] A) {
        for (int k = 1; k <= 3; ++k) {
            for (int i = 0; i < A.Length - k; ++i) {
                if (A[i] == A[i + k]) {
                    return A[i];
                }
            }
        }
        throw new InvalidOperationException("No solution found");
    }
}

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

Задача: 269. Alien Dictionary Сложность: hard Есть новый инопланетный язык, который использует английский алфавит. Однако порядок букв в нем неизвестен. Вам дан список строк words из словаря инопланетного языка. Утверждается, что строки в words отсортированы лексикографически по правилам этого нового языка. Если это утверждение неверно и данное расположение строк в words не может соответствовать никакому порядку букв, верните "". В противном случае верните строку из уникальных букв нового инопланетного языка, отсортированных в лексикографическом порядке по правилам нового языка. Если существует несколько решений, верните любое из них. Пример:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

👨‍💻 Алгоритм: 1⃣Извлечение отношений порядка и создание списков смежности: Извлечь отношения порядка между буквами из слов. Вставить их в список смежности, обрабатывая случаи, когда одно слово является префиксом другого. 2⃣Подсчет числа входящих ребер: Подсчитать количество входящих ребер (in-degree) для каждой буквы. Построить исходящий список смежности и одновременно считать входящие ребра для каждой буквы. 3⃣Обход в ширину (BFS): Инициализировать очередь буквами с нулевым in-degree. Выполнять BFS, добавляя буквы в результат, когда их in-degree становится нулевым. Продолжать до тех пор, пока очередь не станет пустой. Проверить наличие циклов и вернуть результат. 😎 Решение:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public string AlienOrder(string[] words) {
        var adjList = new Dictionary<char, HashSet<char>>();
        var inDegree = new Dictionary<char, int>();

        foreach (var word in words) {
            foreach (var c in word) {
                inDegree[c] = 0;
            }
        }

        for (int i = 0; i < words.Length - 1; i++) {
            var firstWord = words[i];
            var secondWord = words[i + 1];
            for (int j =

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

Задача: 1530. Number of Good Leaf Nodes Pairs Сложность: medium Вам дан корень бинарного дерева и целое число distance. Пара двух различных листовых узлов бинарного дерева называется хорошей, если длина кратчайшего пути между ними меньше или равна distance. Верните количество хороших пар листовых узлов в дереве. Пример:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

👨‍💻 Алгоритм: 1⃣Инициализируйте список смежности для преобразования дерева в граф и множество для хранения листовых узлов. Используйте вспомогательный метод traverseTree для обхода дерева, чтобы построить граф и найти листовые узлы. В параметрах поддерживайте текущий узел, а также родительский узел. Если текущий узел является листом, добавьте его в множество. В списке смежности добавьте текущий узел в список соседей родительского узла и наоборот. Рекурсивно вызовите traverseTree для левого и правого дочернего узла текущего узла. 2⃣Инициализируйте переменную ans для подсчета количества хороших пар листовых узлов. Итеративно переберите каждый листовой узел в множестве. Запустите BFS для текущего листового узла. BFS можно прервать досрочно, как только будут обнаружены все узлы, находящиеся на расстоянии от текущего листового узла. Увеличьте ans для каждого листового узла, найденного в каждом запуске BFS. 3⃣Верните ans / 2. Мы считаем каждую пару дважды, поэтому нужно разделить на 2, чтобы получить фактическое количество. 😎 Решение:

public class Solution {
    public int CountPairs(TreeNode root, int distance) {
        var graph = new Dictionary<TreeNode, List<TreeNode>>();
        var leafNodes = new HashSet<TreeNode>();
        TraverseTree(root, null, graph, leafNodes);
        int ans = 0;
        foreach (var leaf in leafNodes) {
            var bfsQueue = new Queue<TreeNode>();
            var seen = new HashSet<TreeNode>();
            bfsQueue.Enqueue(leaf);
            seen.Add(leaf);
            for (int i = 0; i <= distance; i++) {
                int size = bfsQueue.Count;
                for (int j = 0; j < size; j++) {
                    var currNode = bfsQueue.Dequeue();
                    if (leafNodes.Contains(currNode) && currNode != leaf) {
                        ans++;
                    }
                    if (graph.ContainsKey(currNode)) {
                        foreach (var neighbor in graph[currNode]) {
                            if (!seen.Contains(neighbor)) {
                                bfsQueue.Enqueue(neighbor);
                                seen.Add(neighbor);
                            }
                        }
                    }
                }
            }
        }
        return ans / 2;
    }

    private void TraverseTree(TreeNode currNode, TreeNode prevNode,
                              Dictionary<TreeNode, List<TreeNode>> graph, HashSet<TreeNode> leafNodes) {
        if (currNode == null) {
            return;
        }
        if (currNode.left == null && currNode.right == null) {
            leafNodes.Add(currNode);
        }
        if (prevNode != null) {
            if (!graph.ContainsKey(prevNode)) {
                graph[prevNode] = new List<TreeNode>();
            }
            graph[prevNode].Add(currNode);
            if (!graph.ContainsKey(currNode)) {
                graph[currNode] = new List<TreeNode>();
            }
            graph[currNode].Add(prevNode);
        }
        TraverseTree(currNode.left, currNode, graph, leafNodes);
        TraverseTree(currNode.right, currNode, graph, leafNodes);
    }
}

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

Задача: 1319. Number of Operations to Make Network Connected Сложность: medium Дано n компьютеров, пронумерованных от 0 до n - 1, соединённых Ethernet-кабелями connections, образующими сеть, где connections[i] = [ai, bi] представляет собой соединение между компьютерами ai и bi. Любой компьютер может достичь любого другого компьютера напрямую или косвенно через сеть. Вам даны начальные соединения сети. Вы можете извлекать определённые кабели между двумя напрямую соединёнными компьютерами и размещать их между любыми парами несоединённых компьютеров, чтобы сделать их напрямую соединёнными. Верните минимальное количество раз, которое необходимо сделать это, чтобы соединить все компьютеры. Если это невозможно, верните -1. Пример:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.

👨‍💻 Алгоритм: 1⃣Проверьте размер connections. Если он меньше n - 1, у нас недостаточно ребер, чтобы соединить весь граф. В этом случае возвращаем -1. 2⃣Создайте список смежности с помощью connections, где adj[x] содержит всех соседей узла x. Создайте целое число numberOfConnectedComponents, которое хранит количество компонент связности в графе. Инициализируйте его значением 0. 3⃣Создайте массив visit длиной n для отслеживания посещенных узлов. Пройдите по всем узлам, и для каждого узла i проверьте, был ли он посещен. Если узел i не был посещен, увеличьте numberOfConnectedComponents на 1 и начните обход DFS: Используйте функцию dfs для выполнения обхода. Для каждого вызова передавайте узел, ребра и visit в качестве параметров, начиная с узла i. Отметьте узел как посещенный. Пройдитесь по всем соседям узла. Если какой-либо сосед еще не был посещен, рекурсивно вызовите dfs с этим соседом в качестве узла. Верните numberOfConnectedComponents - 1. 😎 Решение:

public class Solution {
    private void Dfs(int node, Dictionary<int, List<int>> adj, bool[] visit) {
        visit[node] = true;
        if (!adj.ContainsKey(node)) {
            return;
        }
        foreach (int neighbor in adj[node]) {
            if (!visit[neighbor]) {
                visit[neighbor] = true;
                Dfs(neighbor, adj, visit);
            }
        }
    }

    public int MakeConnected(int n, int[][] connections) {
        if (connections.Length < n - 1) {
            return -1;
        }

        var adj = new Dictionary<int, List<int>>();
        foreach (var connection in connections) {
            if (!adj.ContainsKey(connection[0])) {
                adj[connection[0]] = new List<int>();
            }
            if (!adj.ContainsKey(connection[1])) {
                adj[connection[1]] = new List<int>();
            }
            adj[connection[0]].Add(connection[1]);
            adj[connection[1]].Add(connection[0]);
        }

        int numberOfConnectedComponents = 0;
        bool[] visit = new bool[n];
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                numberOfConnectedComponents++;
                Dfs(i, adj, visit);
            }
        }

        return numberOfConnectedComponents - 1;
    }
}

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

📺 База 1000+ реальных собеседований На программиста, тестировщика, аналитика, проджекта и другие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!