Задача: 1260. Shift 2D Grid
Сложность: easy

Дана двумерная сетка размером m x n и целое число k. Требуется сдвинуть сетку k раз. За одну операцию сдвига: элемент в grid[i][j] перемещается в grid[i][j + 1]. Элемент в grid[i][n - 1] перемещается в grid[i + 1][0]. Элемент в grid[m - 1][n - 1] перемещается в grid[0][0]. Верните двумерную сетку после применения операции сдвига k раз.

Пример:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]

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

1⃣Преобразовать двумерную сетку в одномерный массив.

2⃣Выполнить сдвиг элементов в одномерном массиве.

3⃣Преобразовать одномерный массив обратно в двумерную сетку.

😎 Решение:

public class Solution {
    public IList<IList<int>> ShiftGrid(int[][] grid, int k) {
        int m = grid.Length;
        int n = grid[0].Length;
        int total = m * n;
        k = k % total;

        if (k == 0) {
            return grid;
        }

        int[] flatArray = new int[total];
        for (int i = 0; i < total; i++) {
            flatArray[i] = grid[i / n][i % n];
        }

        int[] newArray = new int[total];
        for (int i = 0; i < total; i++) {
            newArray[(i + k) % total] = flatArray[i];
        }

        var newGrid = new List<IList<int>>();
        for (int i = 0; i < m; i++) {
            var newRow = new List<int>();
            for (int j = 0; j < n; j++) {
                newRow.Add(newArray[i * n + j]);
            }
            newGrid.Add(newRow);
        }

        return newGrid;
    }
}

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

Задача: 905. Sort Array By Parity
Сложность: easy

Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию.

Пример:

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

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

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

2⃣Пройтись по массиву и добавить четные числа в один список, а нечетные в другой.

3⃣Объединить два списка и вернуть результат.

😎 Решение:

public class Solution {
    public int[] SortArrayByParity(int[] nums) {
        List<int> evens = new List<int>();
        List<int> odds = new List<int>();
        foreach (int num in nums) {
            if (num % 2 == 0) {
                evens.Add(num);
            } else {
                odds.Add(num);
            }
        }
        evens.AddRange(odds);
        return evens.ToArray();
    }
}

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

Задача: 686. Repeated String Match
Сложность: medium

Даны две строки a и b. Верните минимальное количество повторений строки a, чтобы строка b стала её подстрокой. Если сделать b подстрокой a невозможно, верните -1.

Обратите внимание: строка "abc", повторенная 0 раз, это "", повторенная 1 раз - "abc", повторенная 2 раза - "abcabc".

Пример:

Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.

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

1⃣ Найти минимальное количество повторений строки A, чтобы её длина стала больше или равна длине B. Это значение q = ceil(len(B) / len(A)).

2⃣Проверить, является ли B подстрокой строки A, повторенной q раз. Если да, вернуть q. Иначе, проверить строку A, повторенную (q+1) раз. Если B является подстрокой этой строки, вернуть q+1.

3⃣Если B не является подстрокой ни в одном из случаев, вернуть -1.

😎 Решение:

public class Solution {
    public int RepeatedStringMatch(string A, string B) {
        int q = 1;
        var S = new StringBuilder(A);
        while (S.Length < B.Length) {
            S.Append(A);
            q++;
        }
        if (S.ToString().Contains(B)) return q;
        if (S.Append(A).ToString().Contains(B)) return q + 1;
        return -1;
    }
}

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

Задача: 170. Two Sum III - Data structure design
Сложность: easy

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

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

- TwoSum() инициализирует объект TwoSum с изначально пустым массивом.
- void add(int number) добавляет число в структуру данных.
- boolean find(int value) возвращает true, если существует хотя бы одна пара чисел, сумма которых равна значению value, в противном случае возвращает false.

Пример:

Input
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output
[null, null, null, null, true, false]

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

1⃣Инициализация указателей:
Инициализируйте два указателя low и high, которые указывают на первый и последний элементы списка соответственно.

2⃣Итерация с использованием двух указателей:
Запустите цикл для итерации по списку. Цикл завершится, когда будет найдено решение с двумя суммами или когда два указателя встретятся.
На каждом шаге цикла перемещайте один из указателей в зависимости от различных условий:
Если сумма элементов, на которые указывают текущие указатели, меньше желаемого значения, то необходимо попытаться увеличить сумму для достижения желаемого значения, то есть переместить указатель low вперёд для получения большего значения.
Если сумма элементов больше желаемого значения, то следует попытаться уменьшить сумму, перемещая указатель high в сторону указателя low.
Если сумма равна желаемому значению, можно сразу выполнить возврат из функции.

3⃣Завершение цикла:
Если цикл завершается тем, что два указателя встречаются, то можно быть уверенным, что решения для желаемого значения не существует.

😎 Решение:

public class TwoSum {
    private List<int> nums;
    private bool is_sorted;
    public TwoSum() {
        this.nums = new List<int>();
        this.is_sorted = false;
    }
    public void Add(int number) {
        this.nums.Add(number);
        this.is_sorted = false;
    }
    public bool Find(int value) {
        if (!this.is_sorted) {
            this.nums.Sort();
            this.is_sorted = true;
        }

        int low = 0, high = this.nums.Count - 1;
        while (low < high) {
            int twosum = this.nums[low] + this.nums[high];
            if (twosum < value)
                low += 1;
            else if (twosum > value)
                high -= 1;
            else
                return true;
        }

        return false;
    }
}

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

Задача: 653. Two Sum IV - Input is a BST
Сложность: easy

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

Пример:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

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

1⃣Выполните обход BST и сохраните все значения узлов в набор.

2⃣Для каждого узла в процессе обхода проверьте, существует ли в наборе значение, равное k минус значение текущего узла.

3⃣Если найдена такая пара, верните true. Если обход завершен и пары не найдены, верните false.

😎 Решение:

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public bool FindTarget(TreeNode root, int k) {
        HashSet<int> seen = new HashSet<int>();
        return Find(root, k, seen);
    }

    private bool Find(TreeNode node, int k, HashSet<int> seen) {
        if (node == null) return false;
        if (seen.Contains(k - node.val)) return true;
        seen.Add(node.val);
        return Find(node.left, k, seen) || Find(node.right, k, seen);
    }
}

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

Задача: 96. Unique Binary Search Trees
Сложность: medium

Дано целое число n. Верните количество структурно уникальных деревьев бинарного поиска (BST), которые содержат ровно n узлов с уникальными значениями от 1 до n.

Пример:

Input: n = 3
Output: 5

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

1⃣Введите функцию G(n)— она указывает количество уникальных BST, которые можно построить из nузлов. Также определяем F(i, n)— количество BST, где корень — это i.

2⃣G(n)можно выразить через сумму всех F(i, n), где iот 1до n.
Формула:
G(n) = G(0)⋅G(n−1) + G(1)⋅G(n−2) + ... + G(n−1)⋅G(0)
(это называется числа Каталана )

3⃣Инициализируемся G[0] = 1и G[1] = 1стимулируем считаем G[n], используя значение значения.

😎 Решение:

public class Solution {
    public int NumTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j];
            }
        }

        return G[n];
    }
}

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

Задача: 291. Word Pattern II
Сложность: medium

Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.

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

Пример:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

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

1⃣Инициализация структур данных и определение рекурсивной функции:
Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.
Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.
Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.

2⃣Рекурсивная проверка соответствия:
Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.
Получите символ из шаблона по индексу pIndex.
Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.

3⃣Отображение новых подстрок:
Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.
Для каждой новой подстроки проверьте, существует ли она уже в `

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public bool WordPatternMatch(string pattern, string s) {
        var symbolMap = new Dictionary<char, string>();
        var wordSet = new HashSet<string>();
        return IsMatch(s, 0, pattern, 0, symbolMap, wordSet);
    }

    private bool IsMatch(string s, int sIndex, string pattern, int pIndex,
                         Dictionary<char, string> symbolMap, HashSet<string> wordSet) {
        if (pIndex == pattern.Length) {
            return sIndex == s.Length;
        }
        char symbol = pattern[pIndex];
        if (symbolMap.ContainsKey(symbol)) {
            string word = symbolMap[symbol];
            if (!s.Substring(sIndex).StartsWith(word)) {
                return false;
            }
            return IsMatch(s, sIndex + word.Length, pattern, pIndex + 1, symbolMap, wordSet);
        }
        for (int k = sIndex + 1; k <= s.Length; k++) {
            string newWord = s.Substring(sIndex, k - sIndex);
            if (wordSet.Contains(newWord)) {
                continue;
            }
            symbolMap[symbol] = newWord;
            wordSet.Add(newWord);
            if (IsMatch(s, k, pattern, pIndex + 1, symbolMap, wordSet)) {
                return true;
            }
            symbolMap.Remove(symbol);
            wordSet.Remove(newWord);
        }
        return false;
    }
}

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

Задача: 759. Employee Free Time
Сложность: hard

Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.

Пример:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]

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

1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.

2⃣Объедините пересекающиеся интервалы в один.

3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

using System;
using System.Collections.Generic;

public class Interval {
    public int start;
    public int end;
    public Interval() {
        start = 0; end = 0;
    }
    public Interval(int s, int e) {
        start = s; end = e;
    }
}

public class Solution {
    public IList<Interval> EmployeeFreeTime(IList<IList<Interval>> schedule) {
        List<Interval> intervals = new List<Interval>();
        foreach (var employee in schedule) {
            intervals.AddRange(employee);
        }
        
        intervals.Sort((a, b) => a.start.CompareTo(b.start));
        
        List<Interval> merged = new List<Interval>();
        foreach (var interval in intervals) {
            if (merged.Count == 0 || merged[merged.Count - 1].end < interval.start) {
                merged.Add(interval);
            } else {
                merged[merged.Count - 1].end = Math.Max(merged[merged.Count - 1].end, interval.end);
            }
        }
        
        List<Interval> freeTime = new List<Interval>();
        for (int i = 1; i < merged.Count; i++) {
            if (merged[i].start > merged[i - 1].end) {
                freeTime.Add(new Interval(merged[i - 1].end, merged[i].start));
            }
        }
        
        return freeTime;
    }
}

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

Задача: 787. Cheapest Flights Within K Stops
Сложность: medium

Есть n городов, соединенных некоторым количеством рейсов. Вам дан массив flights, где flights[i] = [fromi, toi, pricei] указывает на то, что существует рейс из города fromi в город toi с ценой pricei.

Также даны три целых числа src, dst и k. Верните самую дешевую цену от src до dst с не более чем k остановками. Если такого маршрута нет, верните -1.

Пример:

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

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

1⃣Создайте список смежности, где adj[X] содержит всех соседей узла X и соответствующую цену, которую нужно заплатить, чтобы перейти к соседу. Инициализируйте массив dist, хранящий минимальную цену для достижения узла из узла src. Инициализируйте его большими значениями. Инициализируйте очередь, хранящую пары {node, distance}. Изначально очередь должна содержать только {src, 0}. Создайте переменную stops и установите ее значение равным 0.

2⃣Выполняйте поиск в ширину (BFS), пока очередь не станет пустой или пока stops > k. Итерируйте по всем узлам на определенном уровне. Это будет сделано путем запуска вложенного цикла и посещения всех узлов, которые в данный момент находятся в очереди. В каждой паре {node, distance} итерируйте по всем соседям узла. Для каждого соседа проверьте, меньше ли dist[neighbor] чем distance + цена ребра. Если это так, обновите dist[neighbor] и добавьте {neighbor, dist[neighbor]} в очередь.

3⃣После итерации по всем узлам на текущем уровне увеличьте stops на один. Мы посетили все узлы на определенном уровне и готовы посетить следующий уровень узлов. Когда мы достигнем условия, при котором либо очередь станет пустой, либо stops == k, у нас будет наш ответ в dist[dst]. Если dist[dst] не изменилось с начального большого значения, значит, мы никогда не достигли его, и следует вернуть -1.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        var adj = new List<(int, int)>[n];
        for (int i = 0; i < n; i++) adj[i] = new List<(int, int)>();
        foreach (var flight in flights) {
            adj[flight[0]].Add((flight[1], flight[2]));
        }
        var dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        var q = new Queue<(int node, int distance)>();
        q.Enqueue((src, 0));
        int stops = 0;

        while (stops <= k && q.Count > 0) {
            int sz = q.Count;
            for (int i = 0; i < sz; i++) {
                var (node, distance) = q.Dequeue();
                foreach (var (neighbour, price) in adj[node]) {
                    if (price + distance >= dist[neighbour]) continue;
                    dist[neighbour] = price + distance;
                    q.Enqueue((neighbour, dist[neighbour]));
                }
            }
            stops++;
        }
        return dist[dst] == int.MaxValue ? -1 : dist[dst];
    }
}

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

Задача: 845. Longest Mountain in Array
Сложность: medium

Вы можете вспомнить, что массив arr является горным массивом тогда и только тогда, когда:
длина массива arr >= 3
Существует индекс i (счёт начинается с 0) такой, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан целочисленный массив arr, верните длину самой длинной подпоследовательности, которая является горной. Верните 0, если такой подпоследовательности нет.

Пример:

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

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

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

2⃣Для каждого индекса, который может быть началом горного массива, определите пиковый элемент и найдите правую границу горного массива.

3⃣Если найден горный массив, обновите максимальную длину и переместите основание на конец текущего горного массива.

😎 Решение:

class Solution {
public:
    int longestMountain(vector<int>& A) {
        int N = A.size();
        int ans = 0, base = 0;
        while (base < N) {
            int end = base;
            if (end + 1 < N && A[end] < A[end + 1]) {
                while (end + 1 < N && A[end] < A[end + 1]) end++;
                if (end + 1 < N && A[end] > A[end + 1]) {
                    while (end + 1 < N && A[end] > A[end + 1]) end++;
                    ans = max(ans, end - base + 1);
                }
            }
            base = max(end, base + 1);
        }
        return ans;
    }
};

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

Задача: 486. Predict the Winner
Сложность: Medium

Дан целочисленный массив nums. Два игрока играют в игру с этим массивом: игрок 1 и игрок 2.

Игрок 1 и игрок 2 ходят по очереди, начиная с игрока 1. Оба игрока начинают игру с нулевым счетом. В каждый ход игрок берет одно из чисел с любого конца массива (то есть nums[0] или nums[nums.length - 1]), что уменьшает размер массива на 1. Игрок добавляет выбранное число к своему счету. Игра заканчивается, когда в массиве не останется элементов.

Верните true, если игрок 1 может выиграть игру. Если счета обоих игроков равны, игрок 1 все равно считается победителем, и вы также должны вернуть true. Вы можете считать, что оба игрока играют оптимально.

Пример:

Input: nums = [1,5,2]
Output: false
Explanation: Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return 

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

1⃣Определите maxDiff(left, right) как максимальную разницу в счете, которую текущий игрок может достичь. Если left = right, верните nums[left].

2⃣В противном случае текущий игрок может выбрать nums[left] или nums[right]. Максимальная разница в счете, которую он может получить, равна большему из значений nums[left] - maxDiff(left + 1, right) и nums[right] - maxDiff(left, right - 1).

3⃣Верните true, если maxDiff(0, n - 1) >= 0. Этот вызов сделан с точки зрения первого игрока, и первый игрок является победителем, если у игроков одинаковый счет (разница 0).

😎 Решение:

public class Solution {
    private int MaxDiff(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }

        int scoreByLeft = nums[left] - MaxDiff(nums, left + 1, right);
        int scoreByRight = nums[right] - MaxDiff(nums, left, right - 1);

        return Math.Max(scoreByLeft, scoreByRight);
    }

    public bool PredictTheWinner(int[] nums) {
        return MaxDiff(nums, 0, nums.Length - 1) >= 0;
    }
}

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

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

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

Задача: 1261. Find Elements in a Contaminated Binary Tree
Сложность: medium

Дано двоичное дерево со следующими правилами: root.val == 0 Если treeNode.val == x и treeNode.left != null, то treeNode.left.val == 2 * x + 1 Если treeNode.val == x и treeNode.right != null, то treeNode.right.val == 2 * x + 2 Теперь двоичное дерево загрязнено, то есть все treeNode.val были изменены на -1. Реализация класса FindElements: FindElements(TreeNode* root) Инициализирует объект с загрязненным двоичным деревом и восстанавливает его. bool find(int target) Возвращает true, если целевое значение существует в восстановленном двоичном дереве.

Пример:

Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output
[null,false,true]

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

1⃣Восстановление дерева: Начните с корневого узла, установите его значение на 0. Затем рекурсивно восстановите значения для всех узлов, используя правила left.val = 2 * parent.val + 1 и right.val = 2 * parent.val + 2.

2⃣Сохранение значений: Используйте структуру данных, такую как множество (set), для хранения всех восстановленных значений узлов.

3⃣Поиск значений: Реализуйте метод поиска, который проверяет, содержится ли целевое значение в множестве восстановленных значений.

😎 Решение:

using System.Collections.Generic;

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

public class FindElements {
    private HashSet<int> values = new HashSet<int>();

    public FindElements(TreeNode root) {
        root.val = 0;
        values.Add(0);
        Recover(root);
    }

    private void Recover(TreeNode node) {
        if (node.left != null) {
            node.left.val = 2 * node.val + 1;
            values.Add(node.left.val);
            Recover(node.left);
        }
        if (node.right != null) {
            node.right.val = 2 * node.val + 2;
            values.Add(node.right.val);
            Recover(node.right);
        }
    }

    public bool Find(int target) {
        return values.Contains(target);
    }
}

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

Задача: 592. Fraction Addition and Subtraction
Сложность: medium

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

Окончательный результат должен быть несократимой дробью. Если ваш окончательный результат является целым числом, преобразуйте его в формат дроби с знаменателем 1. Таким образом, 2 должно быть преобразовано в 2/1.

Пример:

Input: expression = "-1/2+1/2+1/3"
Output: "1/3"

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

1⃣Начните сканирование строки и разделите её на части, содержащие числители и знаменатели, с учетом знаков.

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

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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public string FractionAddition(string expression) {
        var sign = new List<char>();
        if (expression[0] != '-') sign.Add('+');
        foreach (char ch in expression) {
            if (ch == '+' || ch == '-') sign.Add(ch);
        }

        int prevNum = 0, prevDen = 1, i = 0;
        var fractions = expression.Replace("-", "+-").Split(new[] { '+' }, StringSplitOptions.RemoveEmptyEntries);
        
        foreach (var sub in fractions) {
            var fraction = sub.Split('/');
            int num = int.Parse(fraction[0]);
            int den = int.Parse(fraction[1]);
            int g = Math.Abs(Gcd(prevDen, den));
            if (sign[i++] == '+') prevNum = prevNum * den / g + num * prevDen / g;
            else prevNum = prevNum * den / g - num * prevDen / g;
            prevDen = prevDen * den / g;
            g = Math.Abs(Gcd(prevDen, prevNum));
            prevNum /= g;
            prevDen /= g;
        }
        
        return $"{prevNum}/{prevDen}";
    }

    private int Gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
}

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

Задача: 654. Maximum Binary Tree
Сложность: medium

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

Пример:

Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]

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

1⃣Найдите максимальное значение в текущем подмассиве и создайте узел с этим значением.

2⃣Рекурсивно постройте левое поддерево для подмассива слева от максимального значения.

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

😎 Решение:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public TreeNode ConstructMaximumBinaryTree(int[] nums) {
        return Build(nums, 0, nums.Length);
    }

    private TreeNode Build(int[] nums, int l, int r) {
        if (l == r) return null;
        int maxIndex = Max(nums, l, r);
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = Build(nums, l, maxIndex);
        root.right = Build(nums, maxIndex + 1, r);
        return root;
    }

    private int Max(int[] nums, int l, int r) {
        int maxIndex = l;
        for (int i = l + 1; i < r; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}

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

Задача: 376. Wiggle Subsequence
Сложность: medium

Колеблющаяся последовательность — это последовательность, в которой разности между последовательными числами строго чередуются между положительными и отрицательными. Первая разность (если она существует) может быть как положительной, так и отрицательной. Последовательность с одним элементом и последовательность с двумя неравными элементами тривиально являются колеблющимися последовательностями.

Например, [1, 7, 4, 9, 2, 5] — это колеблющаяся последовательность, потому что разности (6, -3, 5, -7, 3) чередуются между положительными и отрицательными.
В отличие от нее, [1, 4, 7, 2, 5] и [1, 7, 4, 5, 5] не являются колеблющимися последовательностями. Первая не является, потому что первые две разности положительные, а вторая не является, потому что последняя разность равна нулю.
Подпоследовательность получается путем удаления некоторых элементов (возможно, нуля) из исходной последовательности с сохранением оставшихся элементов в их первоначальном порядке.

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

Пример:

Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

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

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

2⃣up[i] относится к длине самой длинной колеблющейся подпоследовательности на данный момент, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся восходящим колебанием. Аналогично, down[i] относится к длине самой длинной колеблющейся подпоследовательности, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся нисходящим колебанием.

3⃣up[i] обновляется каждый раз, когда мы находим восходящее колебание, заканчивающееся на i-м элементе. Чтобы найти up[i], необходимо учесть максимальное значение всех предыдущих подпоследовательностей, заканчивающихся нисходящим колебанием, т.е. down[j], для каждого j<i и nums[i]>nums[j]. Аналогично, down[i] обновляется при нахождении нисходящего колебания.

😎 Решение:

public class Solution {
    public int WiggleMaxLength(int[] nums) {
        if (nums.Length < 2)
            return nums.Length;
        int[] up = new int[nums.Length];
        int[] down = new int[nums.Length];
        for (int i = 1; i < nums.Length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    up[i] = Math.Max(up[i], down[j] + 1);
                } else if (nums[i] < nums[j]) {
                    down[i] = Math.Max(down[i], up[j] + 1);
                }
            }
        }
        return 1 + Math.Max(down[nums.Length - 1], up[nums.Length - 1]);
    }
}

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

Задача: 1064. Fixed Point
Сложность: easy

Дан массив различных целых чисел arr, отсортированный в порядке возрастания. Верните наименьший индекс i, который удовлетворяет условию arr[i] == i. Если такого индекса нет, верните -1.

Пример:

Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.

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

1⃣Инициализируйте значение left как 0, right как N - 1 и answer как -1.

2⃣Пока размер области поиска не равен нулю, то есть left <= right, выполните следующие шаги: найдите mid как mid = (left + right) / 2. Сравните arr[mid] и mid: если arr[mid] = mid, сохраните mid в answer и перейдите в левую часть, изменив right на mid - 1; если arr[mid] < mid, перейдите в правую часть, изменив left на mid + 1; если arr[mid] > mid, перейдите в левую часть, изменив right на mid - 1.

3⃣Верните answer.

😎 Решение:

public class Solution {
    public int FixedPoint(int[] arr) {
        int left = 0, right = arr.Length - 1;
        int answer = -1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            
            if (arr[mid] == mid) {
                answer = mid;
                right = mid - 1;
            } else if (arr[mid] < mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return answer;
    }
}
public class Solution {
    public int FixedPoint(int[] arr) {
        int left = 0, right = arr.Length - 1;
        int answer = -1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            
            if (arr[mid] == mid) {
                answer = mid;
                right = mid - 1;
            } else if (arr[mid] < mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return answer;
    }
}

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

Задача: 1190. Reverse Substrings Between Each Pair of Parentheses
Сложность: medium

Дана строка s, состоящая из строчных букв английского алфавита и скобок.

Переверните строки в каждой паре соответствующих скобок, начиная с самой внутренней.

Ваш результат не должен содержать скобок.

Пример:

Input: s = "(abcd)"
Output: "dcba"

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

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

2⃣Для каждого символа currentChar во входной строке:

Если это '(', добавьте длину строки result в openParenthesesIndices, чтобы отметить потенциальную начальную точку разворота.
Если это ')', извлеките значение из openParenthesesIndices и переверните result от извлеченного индекса для выполнения необходимого разворота.
В противном случае добавьте currentChar к result для построения строки.

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

😎 Решение:

public class Solution {
    public string ReverseParentheses(string s) {
        Stack<int> openParenthesesIndices = new Stack<int>();
        StringBuilder result = new StringBuilder();

        foreach (char currentChar in s) {
            if (currentChar == '(') {
                openParenthesesIndices.Push(result.Length);
            } else if (currentChar == ')') {
                int start = openParenthesesIndices.Pop();
                Reverse(result, start, result.Length - 1);
            } else {
                result.Append(currentChar);
            }
        }

        return result.ToString();
    }

    private void Reverse(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb[start];
            sb[start++] = sb[end];
            sb[end--] = temp;
        }
    }
}

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

Задача: 1522. Diameter of N-Ary Tree
Сложность: medium

Дано корневое дерево N-арности, нужно вычислить длину диаметра дерева.

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

(Входная сериализация N-арного дерева представлена их обходом в порядке уровней, каждая группа дочерних узлов разделена значением null.)

Пример:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3
Explanation: Diameter is shown in red color.

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

1⃣Определите функцию height(node), которая возвращает высоту узла. Функция может быть реализована рекурсивно, основываясь на вычислении максимальной высоты среди всех дочерних узлов плюс один.

2⃣Внутри функции height(node) выберите две наибольшие высоты среди дочерних узлов. Эти два значения помогут вычислить длину пути, которая будет кандидатом на диаметр всего дерева.

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

😎 Решение:

public class Solution {
    private int diameter = 0;

    private int Height(Node node) {
        if (node.children.Count == 0) return 0;

        int maxHeight1 = 0, maxHeight2 = 0;
        foreach (var child in node.children) {
            int parentHeight = Height(child) + 1;
            if (parentHeight > maxHeight1) {
                maxHeight2 = maxHeight1;
                maxHeight1 = parentHeight;
            } else if (parentHeight > maxHeight2) {
                maxHeight2 = parentHeight;
            }
            int distance = maxHeight1 + maxHeight2;
            diameter = Math.Max(diameter, distance);
        }

        return maxHeight1;
    }

    public int Diameter(Node root) {
        diameter = 0;
        Height(root);
        return diameter;
    }
}

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

Задача: 721. Accounts Merge
Сложность: medium

Дан список аккаунтов, в котором каждый элемент accounts[i] - это список строк, где первый элемент accounts[i][0] - это имя, а остальные элементы - это email, представляющие электронную почту аккаунта. Теперь мы хотим объединить эти аккаунты. Два аккаунта определенно принадлежат одному человеку, если у обоих аккаунтов есть какой-то общий email. Обратите внимание, что даже если два аккаунта имеют одинаковое имя, они могут принадлежать разным людям, поскольку у людей могут быть одинаковые имена. Изначально у человека может быть любое количество счетов, но все его счета обязательно должны иметь одинаковое имя. После объединения счетов верните счета в следующем формате: первый элемент каждого счета - имя, а остальные элементы - электронные письма в отсортированном порядке. Сами аккаунты могут быть возвращены в любом порядке.

Пример:

nput: accounts = [["John","[email protected]","[email protected]"],["John","[email protected]","[email protected]"],["Mary","[email protected]"],["John","[email protected]"]]
Output: [["John","[email protected]","[email protected]","[email protected]"],["Mary","[email protected]"],["John","[email protected]"]]

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

1⃣Создайте граф, в котором узлы представляют email-адреса, а ребра соединяют email-адреса, принадлежащие одному аккаунту.

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

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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public IList<IList<string>> AccountsMerge(IList<IList<string>> accounts) {
        var emailToName = new Dictionary<string, string>();
        var graph = new Dictionary<string, HashSet<string>>();
        
        foreach (var account in accounts) {
            string name = account[0];
            string firstEmail = account[1];
            foreach (var email in account.Skip(1)) {
                if (!graph.ContainsKey(firstEmail)) graph[firstEmail] = new HashSet<string>();
                if (!graph.ContainsKey(email)) graph[email] = new HashSet<string>();
                graph[firstEmail].Add(email);
                graph[email].Add(firstEmail);
                emailToName[email] = name;
            }
        }
        
        var seen = new HashSet<string>();
        var mergedAccounts = new List<IList<string>>();
        
        foreach (var email in emailToName.Keys) {
            if (!seen.Contains(email)) {
                var emails = new List<string>();
                var stack = new Stack<string>();
                stack.Push(email);
                while (stack.Count > 0) {
                    var node = stack.Pop();
                    if (!seen.Contains(node)) {
                        seen.Add(node);
                        emails.Add(node);
                        foreach (var neighbor in graph[node]) {
                            stack.Push(neighbor);
                        }
                    }
                }
                emails.Sort();
                mergedAccounts.Add(new List<string> { emailToName[email] });
                mergedAccounts[mergedAccounts.Count - 1].AddRange(emails);
            }
        }
        
        return mergedAccounts;
    }
}

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

Задача: 958. Check Completeness of a Binary Tree
Сложность: medium

Дан корень бинарного дерева, определите, является ли оно полным бинарным деревом.

В полном бинарном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. На последнем уровне h может быть от 1 до 2^h узлов включительно.

Пример:

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

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

1⃣Если корень дерева равен null, верните true.

2⃣Инициализируйте переменную nullNodeFound как false для отслеживания того, встречался ли уже null-узел. Создайте очередь и поместите в неё корень дерева.

3⃣Пока очередь не пуста:
Извлеките первый элемент из очереди.
Если элемент равен null, установите nullNodeFound в true.
Если элемент не равен null, проверьте, встречался ли уже null-узел. Если nullNodeFound равен true, верните false. В противном случае добавьте в очередь левого и правого потомков текущего узла.

😎 Решение:

public class Solution {
    public bool IsCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<TreeNode> q = new Queue<TreeNode>();
        q.Enqueue(root);
        bool nullNodeFound = false;

        while (q.Count > 0) {
            TreeNode node = q.Dequeue();

            if (node == null) {
                nullNodeFound = true;
            } else {
                if (nullNodeFound) {
                    return false;
                }
                q.Enqueue(node.left);
                q.Enqueue(node.right);
            }
        }
        return true;
    }
}

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