Задача: 132. Palindrome Partitioning II
Сложность: hard

Дана строка s. Разделите строку так, чтобы каждая подстрока разделения была палиндромом.

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

Пример:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

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

1⃣Определение задачи и начальные условия:
Алгоритм обратного отслеживания реализуется путём рекурсивного изучения кандидатов-подстрок. Мы определяем рекурсивный метод findMinimumCut, который находит минимальное количество разрезов для подстроки, начинающейся с индекса start и заканчивающейся на индексе end.
Чтобы найти минимальное количество разрезов, мы также должны знать минимальное количество разрезов, которые были найдены ранее для других разделений на палиндромы. Эта информация отслеживается в переменной minimumCut.
Начальное значение minimumCut будет равно максимально возможному количеству разрезов в строке, что равно длине строки минус один (т.е. разрез между каждым символом).

2⃣Генерация подстрок и рекурсивный поиск:
Теперь, когда мы знаем начальные и конечные индексы, мы должны сгенерировать все возможные подстроки, начиная с индекса start. Для этого мы будем держать начальный индекс постоянным. currentEndIndex обозначает конец текущей подстроки.

3⃣Условие палиндрома и рекурсивное разделение:
Если текущая подстрока является палиндромом, мы сделаем разрез после currentEndIndex и рекурсивно найдем минимальный разрез для оставшейся строки

😎 Решение:

public class Solution {
    public int MinCut(string s) {
        return findMinimumCut(s, 0, s.Length - 1, s.Length - 1);
    }

    private int findMinimumCut(string s, int start, int end, int minimumCut) {
        if (start == end || isPalindrome(s, start, end)) {
            return 0;
        }

        for (int currentEndIndex = start; currentEndIndex <= end; currentEndIndex++) {
            if (isPalindrome(s, start, currentEndIndex)) {
                minimumCut = Math.Min(
                    minimumCut, 1 + findMinimumCut(s, currentEndIndex + 1, end, minimumCut));
            }
        }

        return minimumCut;
    }

    private bool isPalindrome(string s, int start, int end) {
        while (start < end) {
            if (s[start++] != s[end--]) {
                return false;
            }
        }

        return true;
    }
}

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

Задача: 977. Squares of a Sorted Array
Сложность: easy

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

Пример:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

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

1⃣Создайте массив квадратов каждого элемента.

2⃣Отсортируйте массив квадратов.

3⃣Верните отсортированный массив квадратов.

😎 Решение:

using System;
using System.Linq;

public class Solution {
    public int[] SortedSquares(int[] nums) {
        int[] ans = nums.Select(num => num * num).ToArray();
        Array.Sort(ans);
        return ans;
    }
}

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

Задача: 230. Kth Smallest Element in a BST
Сложность: medium

Дан корень бинарного дерева поиска и целое число k. Верните k-ое по величине значение (нумерация с 1) среди всех значений узлов в дереве.

Пример:

Input: root = [3,1,4,null,2], k = 1
Output: 1

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

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

2⃣Извлечение узлов и проверка: Когда достигнете самого левого узла, извлеките узел из стека и уменьшите значение k на 1. Если k становится равным нулю, верните значение текущего узла, так как это и есть k-ое по величине значение.

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

😎 Решение:

public class Solution {
    public int KthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        
        while (true) {
            while (root != null) {
                stack.Push(root);
                root = root.left;
            }
            root = stack.Pop();
            if (--k == 0) return root.val;
            root = root.right;
        }
    }
}

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

Задача: 1257. Smallest Common Region
Сложность: medium

Вам даны списки регионов, в которых первый регион каждого списка включает все остальные регионы этого списка. Естественно, если регион x содержит другой регион y, то x больше y. Также, по определению, регион x содержит сам себя. Даны два региона: region1 и region2, верните наименьший регион, который содержит их оба. Если вам даны регионы r1, r2 и r3 такие, что r1 включает r3, то гарантированно не существует r2 такого, что r2 включает r3. Гарантированно существует наименьший регион.

Пример:

Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"

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

1⃣Построим дерево регионов, где каждый регион указывает на своего родителя.

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

3⃣Найдем последний общий регион в путях двух заданных регионов.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public string FindSmallestRegion(IList<IList<string>> regions, string region1, string region2) {
        var parent = new Dictionary<string, string>();

        foreach (var regionList in regions) {
            for (int i = 1; i < regionList.Count; i++) {
                parent[regionList[i]] = regionList[0];
            }
        }

        var ancestors1 = new HashSet<string>();
        while (region1 != null) {
            ancestors1.Add(region1);
            region1 = parent.ContainsKey(region1) ? parent[region1] : null;
        }

        while (!ancestors1.Contains(region2)) {
            region2 = parent[region2];
        }

        return region2;
    }
}

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

Задача: 437. Path Sum III
Сложность: medium

Дан корень бинарного дерева и целое число targetSum, вернуть количество путей, где сумма значений вдоль пути равна targetSum.

Путь не обязательно должен начинаться или заканчиваться в корне или на листе, но он должен идти вниз (т.е. перемещаться только от родительских узлов к дочерним).

Пример:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

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

1⃣Инициализируем счетчик путей в дереве count = 0 и хеш-таблицу h, где ключ - это префиксная сумма, а значение - сколько раз она встречалась. Выполним рекурсивный обход дерева в порядке preorder: узел -> левый -> правый. Функция preorder(node: TreeNode, curr_sum: int) принимает два аргумента: узел дерева и префиксную сумму перед этим узлом. Чтобы запустить рекурсию, вызовем preorder(root, 0).

2⃣Сначала обновим текущую префиксную сумму, добавив значение текущего узла: curr_sum += node.val. Теперь можно обновить счетчик. Рассмотрим две ситуации. В первой ситуации путь в дереве с целевой суммой начинается с корня. Это означает, что текущая префиксная сумма равна целевой сумме curr_sum == k, поэтому увеличиваем счетчик на 1: count += 1. Во второй ситуации путь с целевой суммой начинается где-то ниже. Это означает, что нужно добавить к счетчику количество раз, когда мы видели префиксную сумму curr_sum - target: count += h[curr_sum - target].

3⃣Логика проста: текущая префиксная сумма - это curr_sum, а несколько элементов назад префиксная сумма была curr_sum - target. Все элементы между ними суммируются до curr_sum - (curr_sum - target) = target. Теперь обновим хеш-таблицу: h[curr_sum] += 1. Проанализируем левое и правое поддеревья: preorder(node.left, curr_sum), preorder(node.right, curr_sum). После обработки текущего поддерева удалим текущую префиксную сумму из хеш-таблицы, чтобы не смешивать параллельные поддеревья: h[curr_sum] -= 1. Когда обход в порядке preorder завершен, счетчик обновлен. Вернем его.

😎 Решение:

public class Solution {
    public int PathSum(TreeNode root, int sum) {
        int count = 0;
        int k = sum;
        var h = new Dictionary<int, int>();
        
        Preorder(root, 0, h, ref count, k);
        
        return count;
    }
    
    private void Preorder(TreeNode node, int curr_sum, Dictionary<int, int> h, ref int count, int k) {
        if (node == null) return;
        
        curr_sum += node.val;
        
        if (curr_sum == k) {
            count++;
        }
        
        if (h.TryGetValue(curr_sum - k, out int value)) {
            count += value;
        }
        
        if (!h.ContainsKey(curr_sum)) {
            h[curr_sum] = 0;
        }
        h[curr_sum]++;
        
        Preorder(node.left, curr_sum, h, ref count, k);
        Preorder(node.right, curr_sum, h, ref count, k);
        
        h[curr_sum]--;
    }
}

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

Задача: 1277. Count Square Submatrices with All Ones
Сложность: medium

Если задана матрица m * n из единиц и нулей, верните, сколько квадратных подматриц имеют все единицы.

Пример:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15

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

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

2⃣Пройдите по каждому элементу матрицы и обновите dp следующим образом: если элемент равен 1, то dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.

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

😎 Решение:

public class Solution {
    public int CountSquares(int[][] matrix) {
        int m = matrix.Length, n = matrix[0].Length;
        int[,] dp = new int[m, n];
        int count = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    if (i == 0 || j == 0) {
                        dp[i, j] = 1;
                    } else {
                        dp[i, j] = Math.Min(dp[i-1, j], Math.Min(dp[i, j-1], dp[i-1, j-1])) + 1;
                    }
                    count += dp[i, j];
                }
            }
        }

        return count;
    }
}

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

Задача: 84. Largest Rectangle in Histogram
Сложность: hard

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

Пример:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

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

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

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

3⃣Вычисление максимальной площади:
Таким образом, мы можем найти требуемый прямоугольник с максимальной площадью.

😎 Решение:

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        int max_area = 0;
        for (int i = 0; i < heights.Length; i++) {
            for (int j = i; j < heights.Length; j++) {
                int min_height = Int32.MaxValue;
                for (int k = i; k <= j; k++) {
                    min_height = Math.Min(min_height, heights[k]);
                }

                max_area = Math.Max(max_area, min_height * (j - i + 1));
            }
        }

        return max_area;
    }
}

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

Задача: 408. Valid Word Abbreviation
Сложность: easy

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

Например, строка "замена" может быть сокращена следующим образом (но не ограничивается этим): "s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("замена") "su3i1u2on" ("su bst i t u ti on") "substitution" (без замены подстрок) Следующие сокращения не являются допустимыми:

"s55n" ("s ubsti tutio n", заменяемые подстроки смежные) "s010n" (содержит ведущие нули) "s0ubstitution" (заменяет пустую подстроку) Если задано строковое слово и аббревиатура abbr, верните, соответствует ли строка заданной аббревиатуре.

Подстрока - это непрерывная непустая последовательность символов в строке.

Пример:

Input: word = "internationalization", abbr = "i12iz4n"
Output: true

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

1⃣Инициализируйте два указателя: один для строки word и один для аббревиатуры abbr. Начните сравнение символов строки и аббревиатуры с начала.

2⃣Если символ аббревиатуры - это цифра, вычислите полное число и переместите указатель строки word на это количество символов. Если символ аббревиатуры - это буква, убедитесь, что он совпадает с текущим символом строки.

3⃣Повторяйте шаг 2, пока оба указателя не достигнут конца строки и аббревиатуры соответственно. Если это так, верните true, иначе false.

😎 Решение:

public class Solution {
    public bool ValidWordAbbreviation(string word, string abbr) {
        int i = 0, j = 0;
        while (i < word.Length && j < abbr.Length) {
            if (char.IsDigit(abbr[j])) {
                if (abbr[j] == '0') {
                    return false;
                }
                int num = 0;
                while (j < abbr.Length && char.IsDigit(abbr[j])) {
                    num = num * 10 + (abbr[j] - '0');
                    j++;
                }
                i += num;
            } else {
                if (word[i] != abbr[j]) {
                    return false;
                }
                i++;
                j++;
            }
        }
        return i == word.Length && j == abbr.Length;
    }
}

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

Задача: 940. Distinct Subsequences II
Сложность: hard

Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (Например, "ace" является подпоследовательностью "abcde", а "aec" - нет.

Пример:

Input: s = "abc"
Output: 7

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

1⃣Определить матрицу DP, где dp[i][j] будет хранить количество подпоследовательностей строки s с длиной i, оканчивающихся символом j.

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

3⃣Вернуть сумму всех значений в DP по модулю 10^9 + 7.

😎 Решение:

public class Solution {
    private const int MOD = 1000000007;
    
    public int CountSubsequences(string s) {
        int[] dp = new int[26];
        foreach (char c in s) {
            int index = c - 'a';
            dp[index] = (dp.Sum() + 1) % MOD;
        }
        return dp.Sum() % MOD;
    }
}

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

Задача: 1357. Apply Discount Every n Orders
Сложность: medium

В супермаркете, который посещает множество покупателей, товары представлены двумя параллельными массивами целых чисел products и prices, где i-й товар имеет идентификатор products[i] и цену prices[i].

Когда покупатель оплачивает товар, его счет представлен двумя параллельными массивами целых чисел product и amount, где j-й приобретенный товар имеет идентификатор product[j], а amount[j] - количество купленного товара. Их промежуточный итог рассчитывается как сумма каждого amount[j] * (цена j-го товара).

Супермаркет решил провести распродажу. Каждому n-му покупателю, оплачивающему свои покупки, будет предоставлена скидка в процентах. Сумма скидки задается параметром discount, и покупатель получит скидку в discount процентов от своего промежуточного итога. Формально, если их промежуточный итог составляет bill, то они фактически заплатят bill * ((100 - discount) / 100).

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

Cashier(int n, int discount, int[] products, int[] prices): инициализирует объект с параметрами n, discount, а также массивами товаров и их цен.
double getBill(int[] product, int[] amount): возвращает итоговую сумму счета с примененной скидкой (если применима). Ответы, отличающиеся от фактического значения не более чем на 10^-5, будут приняты.

Пример:

Input
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
Output
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]

👨‍💻 Алгоритм:
1⃣Инициализация объекта:
Создайте класс Cashier с конструктором, который принимает параметры n, discount, products и prices. В конструкторе инициализируйте необходимые переменные и создайте словарь для сопоставления идентификаторов продуктов с их ценами.

2⃣Обработка каждого счета:
Создайте метод getBill, который принимает массивы product и amount.
Вычислите промежуточный итог счета, умножая количество каждого продукта на его цену и суммируя результаты.
Увеличьте счетчик клиентов. Если клиент является n-м по счету, примените скидку к промежуточному итогу.

3⃣Верните итоговую сумму счета.

😎 Решение:

using System;
using System.Collections.Generic;

public class Cashier {
    private int n;
    private int discount;
    private Dictionary<int, int> productsPrices;
    private int customerCount;

    public Cashier(int n, int discount, int[] products, int[] prices) {
        this.n = n;
        this.discount = discount;
        this.productsPrices = new Dictionary<int, int>();
        for (int i = 0; i < products.Length; i++) {
            this.productsPrices[products[i]] = prices[i];
        }
        this.customerCount = 0;
    }

    public double GetBill(int[] product, int[] amount) {
        customerCount++;
        double bill = 0.0;
        
        for (int i = 0; i < product.Length; i++) {
            bill += productsPrices[product[i]] * amount[i];
        }
        
        if (customerCount % n == 0) {
            bill *= (100.0 - discount) / 100.0;
        }
        
        return bill;
    }
}

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

Задача: 1302. Deepest Leaves Sum
Сложность: medium

Дано корень бинарного дерева, вернуть сумму значений его самых глубоких листьев.

Пример:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

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

1⃣Поместите корень в стек.

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

3⃣Верните deepest_sum.

😎 Решение:

public class Solution {
    public int DeepestLeavesSum(TreeNode root) {
        int deepestSum = 0, depth = 0;
        var stack = new Stack<(TreeNode node, int depth)>();
        stack.Push((root, 0));

        while (stack.Count > 0) {
            var (node, currDepth) = stack.Pop();

            if (node.left == null && node.right == null) {
                if (depth < currDepth) {
                    deepestSum = node.val;
                    depth = currDepth;
                } else if (depth == currDepth) {
                    deepestSum += node.val;
                }
            } else {
                if (node.right != null) {
                    stack.Push((node.right, currDepth + 1));
                }
                if (node.left != null) {
                    stack.Push((node.left, currDepth + 1));
                }
            }
        }
        return deepestSum;
    }
}

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

Задача: 660. Remove 9
Сложность: hard

Начните с целого числа 1, уберите любое число, которое содержит 9, такое как 9, 19, 29...

Теперь у вас будет новая последовательность целых чисел [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ...].

Дано целое число n, верните n-е (начиная с 1) целое число в новой последовательности.

Пример:

Input: n = 9
Output: 10

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

1⃣Инициализация:
Начните с числа 1 и создайте переменную для отслеживания количества найденных чисел, не содержащих цифру 9.

2⃣Итерация и проверка:
Последовательно увеличивайте число и проверяйте, содержит ли оно цифру 9.
Если не содержит, увеличьте счетчик.

3⃣Поиск n-го числа:
Продолжайте процесс до тех пор, пока не найдете n-е число, не содержащее цифру 9.

😎 Решение:

public class Solution {
    public int NewInteger(int n) {
        int count = 0;
        int num = 0;
        while (count < n) {
            num++;
            if (!num.ToString().Contains("9")) {
                count++;
            }
        }
        return num;
    }
}

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

Задача: 62. Unique Paths
Сложность: medium

На сетке размером m на n находится робот. Изначально робот расположен в верхнем левом углу (то есть, в клетке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть, в клетку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени.

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

Тестовые случаи сгенерированы таким образом, что ответ будет меньше или равен 2 * 10^9.

Пример:

Input: m = 3, n = 7
Output: 28

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

Инициализировать двумерный массив d[m][n] = количество путей. Сначала установить количество путей равным 1 для первой строки и первого столбца. Для упрощения можно инициализировать весь двумерный массив единицами.

2⃣Проитерировать по всем "внутренним" ячейкам: d[col][row] = d[col - 1][row] + d[col][row - 1].

3⃣Вернуть d[m - 1][n - 1].

😎 Решение:

public class Solution {
    public int UniquePaths(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }

        return UniquePaths(m - 1, n) + UniquePaths(m, n - 1);
    }
}

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

Задача: 406. Queue Reconstruction by Height
Сложность: medium

Вам дан массив людей, people, которые являются атрибутами некоторых людей в очереди (не обязательно по порядку). Каждый people[i] = [hi, ki] представляет собой человека ростом hi, перед которым стоят ровно ki других людей, чей рост больше или равен hi. Реконструируйте и верните очередь, представленную входным массивом people. Возвращаемая очередь должна быть отформатирована как массив queue, где queue[j] = [hj, kj] - это атрибуты j-го человека в очереди (queue[0] - человек, находящийся в начале очереди).

Пример:

Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

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

1⃣Отсортируйте массив people по убыванию роста hi. Если два человека имеют одинаковый рост, отсортируйте их по возрастанию значения ki.

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

3⃣Верните список результата.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int[][] ReconstructQueue(int[][] people) {
        Array.Sort(people, (a, b) => a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        List<int[]> result = new List<int[]>();
        foreach (var person in people) {
            result.Insert(person[1], person);
        }
        return result.ToArray();
    }
}

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

Задача: 393. UTF-8 Validation
Сложность: medium

Дан целочисленный массив data, представляющий данные, верните, является ли это допустимой UTF-8 кодировкой (т.е. переводится в последовательность допустимых UTF-8 закодированных символов).

Символ в UTF-8 может быть от 1 до 4 байтов в длину, при этом соблюдаются следующие правила:

Для 1-байтового символа первый бит — 0, за которым следует его Unicode код.
Для n-байтового символа первые n битов — все единицы, (n + 1)-й бит — 0, за которыми следуют n - 1 байт с наиболее значимыми 2 битами, равными 10.
Это работает следующим образом:

     Количество байтов  |        UTF-8 Октетная последовательность
                       |              (бинарная)
   --------------------+-----------------------------------------
            1          |   0xxxxxxx
            2          |   110xxxxx 10xxxxxx
            3          |   1110xxxx 10xxxxxx 10xxxxxx
            4          |   11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

x обозначает бит в бинарной форме байта, который может быть как 0, так и 1.

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

Пример:

Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

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

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

2⃣Далее нужно рассмотреть два сценария. Первый — мы находимся в процессе обработки некоторого UTF-8 закодированного символа. В этом случае нужно просто проверить первые два бита строки и посмотреть, равны ли они "10", т.е. наиболее значимые два бита целого числа равны 1 и 0. bin_rep[:2] == "10". Второй сценарий — мы уже обработали несколько допустимых UTF-8 символов и должны начать обработку нового UTF-8 символа. В этом случае нужно посмотреть на префикс строкового представления и посчитать количество единиц, которые мы встречаем до первой нули. Это скажет нам, каков размер следующего UTF-8 символа.

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

Теперь давайте перейдем к реализации этого алгоритма.

😎 Решение:

public class Solution {
    public bool ValidUtf8(int[] data) {
        int nBytes = 0;
        foreach (int num in data) {
            string binRep = Convert.ToString(num, 2).PadLeft(8, '0').Substring(0, 8);
            if (nBytes == 0) {
                foreach (char bit in binRep) {
                    if (bit == '0') break;
                    nBytes++;
                }
                if (nBytes == 0) continue;
                if (nBytes == 1 || nBytes > 4) return false;
            } else {
                if (!(binRep[0] == '1' && binRep[1] == '0')) return false;
            }
            nBytes--;
        }
        return nBytes == 0;
    }
}

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

Задача: 731. My Calendar II
Сложность: medium

Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к тройному бронированию. Тройное бронирование происходит, когда три события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendarTwo: MyCalendarTwo() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая тройного бронирования. В противном случае возвращается false и событие не добавляется в календарь.

Пример:

Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

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

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

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

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

😎 Решение:

using System;
using System.Collections.Generic;

public class MyCalendarTwo {
    private List<(int, int)> events;
    private List<(int, int)> overlaps;

    public MyCalendarTwo() {
        events = new List<(int, int)>();
        overlaps = new List<(int, int)>();
    }

    public bool Book(int start, int end) {
        foreach (var (os, oe) in overlaps) {
            if (start < oe && end > os) {
                return false;
            }
        }
        foreach (var (es, ee) in events) {
            if (start < ee && end > es) {
                overlaps.Add((Math.Max(start, es), Math.Min(end, ee)));
            }
        }
        events.Add((start, end));
        return true;
    }
}

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

Задача: 849. Maximize Distance to Closest Person
Сложность: medium

Вам дан массив, представляющий ряд сидений, где seats[i] = 1 означает, что на i-м месте сидит человек, а seats[i] = 0 означает, что i-е место пусто (индексация с нуля).
Есть по крайней мере одно пустое место и по крайней мере один человек, сидящий на месте.
Алекс хочет сесть на такое место, чтобы расстояние между ним и ближайшим к нему человеком было максимальным.

Верните это максимальное расстояние до ближайшего человека.

Пример:

Input: seats = [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (i.e. seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

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

1⃣Следите за prev, занятым местом слева или на текущей позиции i, и future, занятым местом справа или на текущей позиции i.

2⃣Для каждого пустого места i определите ближайшее занятие места как min(i - prev, future - i), с учетом, что i - prev считается бесконечностью, если слева нет занятого места, и future - i считается бесконечностью, если справа нет занятого места.

3⃣Найдите и верните максимальное расстояние до ближайшего занятого места.

😎 Решение:

public class Solution {
    public int MaxDistToClosest(int[] seats) {
        int n = seats.Length;
        int prev = -1, future = 0;
        int ans = 0;

        for (int i = 0; i < n; ++i) {
            if (seats[i] == 1) {
                prev = i;
            } else {
                while (future < n && (seats[future] == 0 || future < i)) {
                    future++;
                }
                int left = prev == -1 ? n : i - prev;
                int right = future == n ? n : future - i;
                ans = Math.Max(ans, Math.Min(left, right));
            }
        }

        return ans;
    }
}

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

Задача: 1039. Minimum Score Triangulation of Polygon
Сложность: medium

У вас есть выпуклый n-сторонний многоугольник, каждая вершина которого имеет целочисленное значение. Вам дан целочисленный массив values, где values[i] - это значение i-й вершины (т.е. по часовой стрелке). Вы должны триангулировать многоугольник на n - 2 треугольника. Для каждого треугольника значение этого треугольника равно произведению значений его вершин, а общий балл триангуляции равен сумме этих значений для всех n - 2 треугольников в триангуляции. Верните наименьший возможный общий балл, который вы можете получить с помощью некоторой триангуляции многоугольника.

Пример:

Input: values = [1,2,3]
Output: 6

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

1⃣Инициализация:
Создаем двумерный массив dp, где dp[i][j] будет хранить минимальный возможный общий балл триангуляции многоугольника, состоящего из вершин от i до j.

2⃣Основное заполнение dp:
Проходим по всем возможным длинам подмногоугольников, начиная с треугольников (длина 3) до всего многоугольника (длина n).
Для каждого подмногоугольника находим минимальный возможный общий балл, проверяя все возможные треугольники, которые могут быть образованы из этого подмногоугольника.
Заполнение dp для каждого подмногоугольника:
Для каждого подмногоугольника от i до j, и для каждой возможной вершины k между i и j, обновляем значение dp[i][j], как сумму минимальных значений триангуляций левой и правой частей подмногоугольника, а также значения текущего треугольника, образованного вершинами i, k и j.

3⃣Возврат результата:
Ответ будет в dp[0][n-1], который хранит минимальный возможный общий балл триангуляции для всего многоугольника.

😎 Решение:

public class Solution {
    public int MinScoreTriangulation(int[] values) {
        int n = values.Length;
        int[,] dp = new int[n, n];
        
        for (int length = 2; length < n; ++length) {
            for (int i = 0; i < n - length; ++i) {
                int j = i + length;
                dp[i, j] = int.MaxValue;
                for (int k = i + 1; k < j; ++k) {
                    dp[i, j] = Math.Min(dp[i, j], dp[i, k] + dp[k, j] + values[i] * values[j] * values[k]);
                }
            }
        }
        
        return dp[0, n - 1];
    }
}

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

Задача: 294. Flip Game II
Сложность: medium

Вы играете в игру Flip со своим другом.

Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда игрок больше не может сделать ход, и, следовательно, другой игрок становится победителем.

Верните true, если начальный игрок может гарантировать победу, и false в противном случае.

Пример:

Input: currentState = "++++"
Output: true
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".

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

1⃣Генерация всех возможных следующих ходов:
Для текущего состояния currentState, создайте все возможные новые состояния, заменяя каждую пару "++" на "--".

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

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

😎 Решение:

public class Solution {
    public bool CanWin(string currentState) {
        char[] stateArray = currentState.ToCharArray();
        
        for (int i = 0; i < stateArray.Length - 1; i++) {
            if (stateArray[i] == '+' && stateArray[i + 1] == '+') {
                stateArray[i] = '-';
                stateArray[i + 1] = '-';
                string newState = new string(stateArray);
                
                if (!CanWin(newState)) {
                    stateArray[i] = '+';
                    stateArray[i + 1] = '+';
                    return true;
                }
                
                stateArray[i] = '+';
                stateArray[i + 1] = '+';
            }
        }
        
        return false;
    }
}

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

Задача: 593. Valid Square
Сложность: medium

Даны координаты четырех точек в 2D-пространстве p1, p2, p3 и p4. Верните true, если эти четыре точки образуют квадрат.

Координата точки pi представлена как [xi, yi]. Ввод не дан в каком-либо определенном порядке.

Корректный квадрат имеет четыре равные стороны с положительной длиной и четыре равных угла (по 90 градусов).

Пример:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: true

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

1⃣Определите функцию для вычисления расстояния между двумя точками.

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

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

😎 Решение:

public class Solution {
    private int Dist(int[] p1, int[] p2) {
        return (p2[1] - p1[1]) * (p2[1] - p1[1]) + (p2[0] - p1[0]) * (p2[0] - p1[0]);
    }

    private bool Check(int[] p1, int[] p2, int[] p3, int[] p4) {
        return Dist(p1, p2) > 0 &&
               Dist(p1, p2) == Dist(p2, p3) &&
               Dist(p2, p3) == Dist(p3, p4) &&
               Dist(p3, p4) == Dist(p4, p1) &&
               Dist(p1, p3) == Dist(p2, p4);
    }

    public bool ValidSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        return Check(p1, p2, p3, p4) ||
               Check(p1, p3, p2, p4) ||
               Check(p1, p2, p4, p3);
    }
}

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