Задача: 299. Bulls and Cows
Сложность: medium

Вы играете в игру "Быки и коровы" со своим другом.

Вы записываете секретное число и просите своего друга угадать, что это за число. Когда ваш друг делает предположение, вы даете ему подсказку со следующей информацией:

Количество "быков", то есть цифры в предположении, которые находятся на правильной позиции.
Количество "коров", то есть цифры в предположении, которые есть в вашем секретном числе, но находятся на неправильной позиции. Конкретно, это не-бычьи цифры в предположении, которые можно переставить так, чтобы они стали быками.
Дано секретное число secret и предположение вашего друга guess, верните подсказку для предположения вашего друга.

Подсказка должна быть в формате "xAyB", где x — количество быков, а y — количество коров. Обратите внимание, что и secret, и guess могут содержать повторяющиеся цифры.

Пример:

Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
  |
"7810"

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

1⃣Инициализация счетчиков:
Инициализируйте количество быков и коров значениями ноль.
Создайте хеш-таблицу для хранения символов строки secret и их частот.

2⃣Обход строки guess:
Для каждого символа ch в строке guess:
Если ch присутствует в строке secret:
Если текущий символ ch совпадает с символом на той же позиции в secret (ch == secret[idx]):
Увеличьте количество быков: bulls += 1.
Обновите количество коров, если количество текущего символа в хеш-таблице отрицательное или равно нулю (то есть этот символ уже использовался для коров): cows -= int(h[ch] <= 0).
Если текущий символ ch не совпадает с символом на той же позиции в secret (ch != secret[idx]):
Увеличьте количество коров, если количество текущего символа в хеш-таблице больше нуля: cows += int(h[ch] > 0).
Обновите хеш-таблицу, помечая текущий символ как использованный: h[ch] -= 1.

3⃣Возврат результата:
Верните количество быков и коров в формате "xAyB".

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public string GetHint(string secret, string guess) {
        var h = new Dictionary<char, int>();
        foreach (var ch in secret) {
            if (!h.ContainsKey(ch)) {
                h[ch] = 0;
            }
            h[ch]++;
        }

        int bulls = 0;
        int cows = 0;
        int n = guess.Length;
        var secretArray = secret.ToCharArray();
        var guessArray = guess.ToCharArray();

        for (int idx = 0; idx < n; idx++) {
            var ch = guessArray[idx];
            if (h.ContainsKey(ch)) {
                if (ch == secretArray[idx]) {
                    bulls++;
                    if (h[ch] <= 0) {
                        cows--;
                    }
                } else {
                    if (h[ch] > 0) {
                        cows++;
                    }
                }
                h[ch]--;
            }
        }

        return $"{bulls}A{cows}B";
    }
}

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

Задача: 1120. Maximum Average Subtree
Сложность: medium

Дан корень бинарного дерева. Верните максимальное среднее значение поддерева этого дерева. Ответы, отличающиеся от фактического ответа не более чем на 10^-5, будут приняты.

Поддерево дерева — это любой узел этого дерева плюс все его потомки.

Среднее значение дерева — это сумма его значений, деленная на количество узлов.

Пример:

Input: root = [5,6,1]
Output: 6.00000
Explanation: 
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.

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

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

2⃣Постобход (postorder traversal):
Реализуйте функцию maxAverage, которая выполняет постобход дерева, вычисляя nodeCount, valueSum и maxAverage для каждого узла, начиная с дочерних узлов и продвигаясь к родительским узлам.

3⃣Вычисление максимального среднего значения:
Используйте значения, полученные от дочерних узлов, для вычисления среднего значения для текущего узла и обновите maxAverage, если новое среднее значение больше текущего максимума.

😎 Решение:

public class Solution {
    class State {
        public int nodeCount;
        public int valueSum;
        public double maxAverage;

        public State(int nodes, int sum, double maxAvg) {
            this.nodeCount = nodes;
            this.valueSum = sum;
            this.maxAverage = maxAvg;
        }
    }

    public double MaximumAverageSubtree(TreeNode root) {
        return maxAverage(root).maxAverage;
    }

    private State maxAverage(TreeNode root) {
        if (root == null) {
            return new State(0, 0, 0);
        }

        State left = maxAverage(root.left);
        State right = maxAverage(root.right);

        int nodeCount = left.nodeCount + right.nodeCount + 1;
        int sum = left.valueSum + right.valueSum + root.val;
        double currentAverage = (1.0 * sum) / nodeCount;
        double maxAverage = Math.Max(currentAverage, Math.Max(left.maxAverage, right.maxAverage));

        return new State(nodeCount, sum, maxAverage);
    }
}

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

Задача: 850. Rectangle Area II
Сложность: hard

Вам дан двумерный массив прямоугольников, выровненных по осям. Каждый прямоугольник[i] = [xi1, yi1, xi2, yi2] обозначает i-й прямоугольник, где (xi1, yi1) — координаты нижнего левого угла, а (xi2, yi2) — координаты верхнего правого угла.

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

Верните общую площадь. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.

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

1⃣Переназначьте каждую x координату на 0, 1, 2, .... Аналогично, переназначьте все y координаты.

2⃣Теперь мы имеем задачу, которую можно решить методом грубой силы: для каждого прямоугольника с переназначенными координатами (rx1, ry1, rx2, ry2) заполним сетку grid[x][y] = True для rx1 <= x < rx2 и ry1 <= y < ry2.

3⃣Затем каждая ячейка grid[rx][ry] будет представлять площадь (imapx(rx+1) - imapx(rx)) * (imapy(ry+1) - imapy(ry)), где если x был переназначен на rx, то imapx(rx) = x ("обратная карта x для переназначенного x равна x"), аналогично для imapy.

😎 Решение:

public class Solution {
    public int RectangleArea(int[][] rectangles) {
        int N = rectangles.Length;
        HashSet<int> Xvals = new HashSet<int>();
        HashSet<int> Yvals = new HashSet<int>();

        foreach (var rec in rectangles) {
            Xvals.Add(rec[0]);
            Xvals.Add(rec[2]);
            Yvals.Add(rec[1]);
            Yvals.Add(rec[3]);
        }

        int[] imapx = Xvals.ToArray();
        Array.Sort(imapx);
        int[] imapy = Yvals.ToArray();
        Array.Sort(imapy);

        Dictionary<int, int> mapx = new Dictionary<int, int>();
        Dictionary<int, int> mapy = new Dictionary<int, int>();
        for (int i = 0; i < imapx.Length; ++i)
            mapx[imapx[i]] = i;
        for (int i = 0; i < imapy.Length; ++i)
            mapy[imapy[i]] = i;

        bool[,] grid = new bool[imapx.Length, imapy.Length];
        foreach (var rec in rectangles)
            for (int x = mapx[rec[0]]; x < mapx[rec[2]]; ++x)
                for (int y = mapy[rec[1]]; y < mapy[rec[3]]; ++y)
                    grid[x, y] = true;

        long ans = 0;
        for (int x = 0; x < grid.GetLength(0); ++x)
            for (int y = 0; y < grid.GetLength(1); ++y)
                if (grid[x, y])
                    ans += (long)(imapx[x + 1] - imapx[x]) * (imapy[y + 1] - imapy[y]);

        ans %= 1_000_000_007;
        return (int)ans;
    }
}

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

Задача: 78. Subsets
Сложность: medium

Дан массив целых чисел nums, содержащий уникальные элементы. Верните все возможные подмножества (степенной набор).

Множество решений не должно содержать дублирующихся подмножеств. Результат может быть возвращен в любом порядке.

Пример:

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

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

1⃣Определяем функцию обратного отслеживания под названием backtrack(first, curr), которая принимает индекс первого элемента, который нужно добавить, и текущую комбинацию в качестве аргументов.

2⃣Если текущая комбинация завершена, мы добавляем её в итоговый вывод.

3⃣В противном случае перебираем индексы i от first до длины всей последовательности n, добавляем элемент nums[i] в текущую комбинацию curr, продолжаем добавлять больше чисел в комбинацию: backtrack(i + 1, curr) и возвращаемся, удаляя nums[i] из curr.

😎 Решение:

class Solution {
    private List<IList<int>> output = new List<IList<int>>();
    private int n, k;

    private void backtrack(int first, List<int> curr, int[] nums) {
        if (curr.Count == k) output.Add(new List<int>(curr));
        for (int i = first; i < n; ++i) {
            curr.Add(nums[i]);
            backtrack(i + 1, curr, nums);
            curr.RemoveAt(curr.Count - 1);
        }
    }

    public IList<IList<int>> Subsets(int[] nums) {
        n = nums.Length;
        for (k = 0; k < n + 1; ++k) {
            backtrack(0, new List<int>(), nums);
        }

        return output;
    }
}

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

Задача: 496. Next Greater Element I
Сложность: easy

Следующий больший элемент для некоторого элемента x в массиве — это первый больший элемент, который находится справа от x в том же массиве.

Вам даны два различных целочисленных массива с индексами, начинающимися с 0: nums1 и nums2, где nums1 является подмножеством nums2.
Для каждого 0 <= i < nums1.length найдите индекс j, такой что nums1[i] == nums2[j], и определите следующий больший элемент для nums2[j] в nums2. Если следующего большего элемента нет, то ответ для этого запроса — -1.

Верните массив ans длиной nums1.length, где ans[i] — это следующий больший элемент, как описано выше.

Пример:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

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

1⃣Инициализация и поиск совпадений
Создайте массив res для хранения результатов. Для каждого элемента nums1[i] найдите его индекс j в массиве nums2.

2⃣Поиск следующего большего элемента
После нахождения индекса j в nums2 начните поиск элемента справа от nums2[j], который больше nums1[i]. Если такой элемент найден, добавьте его в res.

3⃣Заполнение результата
Если следующий больший элемент не найден, добавьте -1 в соответствующую позицию res. Верните массив res.

😎 Решение:

public class Solution {
    public int[] NextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.Length];
        Array.Fill(res, -1);
        
        for (int i = 0; i < nums1.Length; i++) {
            bool found = false;
            for (int j = 0; j < nums2.Length; j++) {
                if (nums2[j] == nums1[i]) {
                    found = true;
                }
                if (found && nums2[j] > nums1[i]) {
                    res[i] = nums2[j];
                    break;
                }
            }
        }
        
        return res;
    }
}

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

Задача: 1242. Web Crawler Multithreaded
Сложность: medium

Учитывая URL startUrl и интерфейс HtmlParser, реализуйте многопоточный веб-краулер, который будет просматривать все ссылки, находящиеся под тем же именем хоста, что и startUrl. Верните все URL, полученные вашим веб-краулером, в любом порядке.

Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все URL с веб-страницы данного URL. Не просматривать одну и ту же ссылку дважды. Исследовать только те ссылки, которые находятся под тем же именем хоста, что и startUrl.

Пример:

Input:
urls = [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.google.com",
  "http://news.yahoo.com/us"
]
edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl = "http://news.yahoo.com/news/topics/"
Output: [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.yahoo.com/us"
]

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

1⃣Извлечь имя хоста из startUrl.
Использовать многопоточность для обработки URL-адресов.

2⃣Хранить посещенные URL-адреса, чтобы избежать повторного посещения.

3⃣Использовать HtmlParser для получения URL-адресов с веб-страниц.

😎 Решение:

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Net;
using System.Threading.Tasks;

public class HtmlParser {
    public List<string> GetUrls(string url) {
        return new List<string>();
    }
}

public class Solution {
    private ConcurrentDictionary<string, bool> visited = new ConcurrentDictionary<string, bool>();
    private string hostname;
    private HtmlParser htmlParser;

    public IList<string> Crawl(string startUrl, HtmlParser htmlParser) {
        this.hostname = new Uri(startUrl).Host;
        this.htmlParser = htmlParser;

        var tasks = new List<Task>();
        visited.TryAdd(startUrl, true);
        tasks.Add(Task.Run(() => Visit(startUrl)));

        Task.WaitAll(tasks.ToArray());
        return visited.Keys.ToList();
    }

    private async Task Visit(string url) {
        foreach (var nextUrl in htmlParser.GetUrls(url)) {
            if (new Uri(nextUrl).Host == hostname && visited.TryAdd(nextUrl, true)) {
                await Visit(nextUrl);
            }
        }
    }
}

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

Задача: 1464. Maximum Product of Two Elements in an Array
Сложность: easy

Дан массив целых чисел nums, выберите два разных индекса i и j этого массива. Верните максимальное значение (nums[i]-1)*(nums[j]-1).

Пример:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, 
that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. 

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

1⃣Инициализируйте biggest = 0 и secondBiggest = 0.

2⃣Итерируйте по каждому элементу массива nums:
Если текущий элемент больше biggest, обновите secondBiggest = biggest и biggest = текущий элемент.
Иначе обновите secondBiggest, если текущий элемент больше secondBiggest.

3⃣Верните (biggest - 1) * (secondBiggest - 1).

😎 Решение:

public class Solution {
    public int MaxProduct(int[] nums) {
        int biggest = 0;
        int secondBiggest = 0;
        foreach (int num in nums) {
            if (num > biggest) {
                secondBiggest = biggest;
                biggest = num;
            } else if (num > secondBiggest) {
                secondBiggest = num;
            }
        }
        return (biggest - 1) * (secondBiggest - 1);
    }
}

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

Задача: 826. Most Profit Assigning Work
Сложность: medium

У вас есть n заданий и m рабочих. Вам даны три массива: difficulty, profit и worker, где:
difficulty[i] и profit[i] — сложность и прибыль i-го задания,
worker[j] — способность j-го рабочего (т.е. j-й рабочий может выполнить задание со сложностью не больше worker[j]).
Каждому рабочему можно назначить не более одного задания, но одно задание может быть выполнено несколько раз.
Например, если три рабочих выполняют одно и то же задание с оплатой $1, общая прибыль составит $3. Если рабочий не может выполнить ни одно задание, его прибыль равна $0.

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

Пример:

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.

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

1⃣Создание и сортировка профиля работы
Инициализируйте массив пар jobProfile с {0, 0}. Для каждого задания добавьте {difficulty[i], profit[i]} в jobProfile. Отсортируйте jobProfile по возрастанию сложности.

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

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

😎 Решение:

public class Solution {
    public int MaxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        var jobProfile = new List<int[]> { new int[] { 0, 0 } };
        for (int i = 0; i < difficulty.Length; i++) {
            jobProfile.Add(new int[] { difficulty[i], profit[i] });
        }
        jobProfile.Sort((a, b) => a[0].CompareTo(b[0]));
        
        for (int i = 1; i < jobProfile.Count; i++) {
            jobProfile[i][1] = Math.Max(jobProfile[i][1], jobProfile[i - 1][1]);
        }
        
        int netProfit = 0;
        foreach (int ability in worker) {
            int l = 0, r = jobProfile.Count - 1, jobProfit = 0;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (jobProfile[mid][0] <= ability) {
                    jobProfit = Math.Max(jobProfit, jobProfile[mid][1]);
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            netProfit += jobProfit;
        }
        return netProfit;
    }
}

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

Задача: CodeTestcaseTest ResultTest Result1523. Count Odd Numbers in an Interval Range
Сложность: easy

### Условие задачи

Даны два неотрицательных целых числа low и high. Верните количество нечётных чисел между low и high (включительно).

Пример:

Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].

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

1⃣Проверьте, является ли число low нечётным. Это можно легко сделать с помощью оператора %, но мы используем побитовый оператор &, так как он более эффективен.

2⃣Если low нечётное, увеличьте его на 1.

3⃣Верните (high - low) / 2 + 1. Важный момент здесь - проверить, не стало ли low больше, чем high после увеличения. Это произойдёт, если low = high, и в этом случае следует вернуть 0.

😎 Решение:

public class Solution {
    public int CountOdds(int low, int high) {
        if ((low & 1) == 0) {
            low++;
        }
        return low > high ? 0 : (high - low) / 2 + 1;
    }
}

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

Задача: 363. Max Sum of Rectangle No Larger Than K
Сложность: hard

Дана матрица размером m x n и целое число k, вернуть максимальную сумму прямоугольника в матрице, такая что его сумма не превышает k.

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

Пример:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

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

1⃣Создать вспомогательную функцию updateResult, которая будет находить максимальную сумму подмассива в одномерном массиве, не превышающую k.

2⃣Преобразовать каждую подматрицу в одномерный массив и применить к ней функцию updateResult.

3⃣Вернуть максимальную найденную сумму.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    private int result = int.MinValue;

    private void UpdateResult(int[] nums, int k) {
        int sum = 0;
        var sortedSum = new SortedSet<int> { 0 };

        foreach (int num in nums) {
            sum += num;
            var x = sortedSum.GetViewBetween(sum - k, int.MaxValue);
            if (x.Count > 0) {
                result = Math.Max(result, sum - x.Min);
            }
            sortedSum.Add(sum);
        }
    }

    public int MaxSumSubmatrix(int[][] matrix, int k) {
        int rows = matrix.Length;
        int cols = matrix[0].Length;

        for (int i = 0; i < rows; i++) {
            var rowSum = new int[cols];
            for (int row = i; row < rows; row++) {
                for (int col = 0; col < cols; col++) {
                    rowSum[col] += matrix[row][col];
                }
                UpdateResult(rowSum, k);
                if (result == k) {
                    return result;
                }
            }
        }
        return result;
    }
}

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

Задача: 659. Split Array into Consecutive Subsequences
Сложность: medium

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

Определите, можно ли разделить nums на одну или несколько подпоследовательностей так, чтобы выполнялись оба следующих условия:

Каждая подпоследовательность является последовательностью последовательных возрастающих чисел (то есть каждое целое число на 1 больше предыдущего).
Все подпоследовательности имеют длину 3 или более.
Верните true, если можно разделить nums согласно вышеуказанным условиям, или false в противном случае.

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

Пример:

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

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

1⃣Подсчет частоты элементов:
Создайте хеш-таблицу для подсчета количества вхождений каждого элемента в массиве nums.

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

3⃣Проверка результата:
Верните true, если все элементы успешно распределены по подпоследовательностям.

😎 Решение:

using System.Collections.Generic;

public class Solution {
    public bool IsPossible(int[] nums) {
        var freq = new Dictionary<int, int>();
        var need = new Dictionary<int, int>();
        
        foreach (var num in nums) {
            if (freq.ContainsKey(num)) {
                freq[num]++;
            } else {
                freq[num] = 1;
            }
        }
        
        foreach (var num in nums) {
            if (freq[num] == 0) continue;
            if (need.ContainsKey(num) && need[num] > 0) {
                need[num]--;
                if (need.ContainsKey(num + 1)) {
                    need[num + 1]++;
                } else {
                    need[num + 1] = 1;
                }
            } else if (freq.ContainsKey(num + 1) && freq[num + 1] > 0 &&
                       freq.ContainsKey(num + 2) && freq[num + 2] > 0) {
                freq[num + 1]--;
                freq[num + 2]--;
                if (need.ContainsKey(num + 3)) {
                    need[num + 3]++;
                } else {
                    need[num + 3] = 1;
                }
            } else {
                return false;
            }
            freq[num]--;
        }
        
        return true;
    }
}

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

Задача: 149. Max Points on a Line
Сложность: hard

Дан массив точек, где points[i] = [xi, yi] представляет точку на плоскости XY. Верните максимальное количество точек, которые лежат на одной прямой.

Пример:

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

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

1⃣Итерация по всем точкам:
Проходим по всем точкам массива. Пусть текущая точка будет points[i]. Создаём хеш-таблицу cnt для подсчёта углов.

2⃣Расчёт углов и подсчёт:
Для каждой точки j, не равной i, рассчитываем арктангенс вектора points[j] - points[i] и добавляем это значение в хеш-таблицу

3⃣Обновление ответа:
Пусть k будет максимальным количеством вхождений какого-либо значения угла в хеш-таблице. Обновляем ответ значением k + 1 (прибавляем 1, потому что точка points[i] также лежит на этой линии, и её нужно включить в ответ).

😎 Решение:

public class Solution {
    public int MaxPoints(int[][] points) {
        int n = points.Length;
        if (n == 1) {
            return 1;
        }

        int result = 2;
        for (int i = 0; i < n; i++) {
            Dictionary<double, int> cnt = new Dictionary<double, int>();
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    double key = Math.Atan2(points[j][1] - points[i][1],
                                            points[j][0] - points[i][0]);
                    if (cnt.ContainsKey(key)) {
                        cnt[key]++;
                    } else {
                        cnt[key] = 1;
                    }
                }
            }

            result = Math.Max(result, cnt.Values.Max() + 1);
        }

        return result;
    }
}

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

Задача: 813. Largest Sum of Averages
Сложность: medium

Вам дан целочисленный массив nums и целое число k. Вы можете разбить массив на не более чем k непустых смежных подмассивов. Оценка разбиения равна сумме средних значений каждого подмассива.

Обратите внимание, что при разбиении должны быть использованы все целые числа из nums, и что оценка не обязательно является целым числом.

Верните максимальную оценку, которую можно достичь среди всех возможных разбиений. Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты.

Пример:

Input: nums = [9,1,2,3,9], k = 3
Output: 20.00000
Explanation: 
The best choice is to partition nums into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned nums into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.

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

1⃣Пусть dp(i, k) будет лучшей оценкой для разбиения массива A[i:] на не более чем k частей. Если первая группа, в которую мы разбиваем A[i:], заканчивается перед j, тогда наше разбиение-кандидат имеет оценку average(i, j) + dp(j, k-1), где average(i, j) = (A[i] + A[i+1] + ... + A[j-1]) / (j - i) (деление с плавающей запятой). Мы берем наивысшую оценку из этих вариантов, помня, что разбиение необязательно - dp(i, k) также может быть просто average(i, N).

2⃣В общем случае наша рекурсия выглядит так: dp(i, k) = max(average(i, N), max_{j > i}(average(i, j) + dp(j, k-1))). Мы можем рассчитывать average немного быстрее, используя префиксные суммы. Если P[x+1] = A[0] + A[1] + ... + A[x], тогда average(i, j) = (P[j] - P[i]) / (j - i).

3⃣Наша реализация демонстрирует подход "снизу вверх" для динамического программирования. На шаге k во внешнем цикле, dp[i] представляет собой dp(i, k) из обсуждения выше, и мы рассчитываем следующий слой dp(i, k+1). Завершение второго цикла для i = 0..N-1 означает завершение расчета правильного значения для dp(i, t), а внутренний цикл выполняет расчет max_{j > i}(average(i, j) + dp(j, k)).

😎 Решение:

using System;

public class Solution {
    public double LargestSumOfAverages(int[] A, int K) {
        int N = A.Length;
        double[] P = new double[N + 1];

        // Префиксные суммы
        for (int i = 0; i < N; ++i)
            P[i + 1] = P[i] + A[i];

        double[] dp = new double[N];
       
        for (int i = 0; i < N; ++i)
            dp[i] = (P[N] - P[i]) / (N - i);
        
        for (int k = 0; k < K - 1; ++k) {
            for (int i = 0; i < N; ++i) {
                for (int j = i + 1; j < N; ++j) {
                    dp[i] = Math.Max(dp[i], (P[j] - P[i]) / (j - i) + dp[j]);
                }
            }
        }

        return dp[0];
    }
}

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

Задача: 531. Lonely Pixel I
Сложность: medium

Дано изображение размером m x n, состоящее из чёрных ('B') и белых ('W') пикселей. Верните количество чёрных одиночных пикселей.

Чёрный одиночный пиксель — это символ 'B', расположенный в такой позиции, где в той же строке и в том же столбце нет других чёрных пикселей.

Пример:

Input: picture = [["W","W","B"],["W","B","W"],["B","W","W"]]
Output: 3
Explanation: All the three 'B's are black lonely pixels.

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

1⃣ Подсчёт количества чёрных пикселей в строках и столбцах:
Пройдите по всей матрице picture, для каждой чёрной клетки (x, y) увеличивайте rowCount[x] и colCount[y] на 1.

2⃣ Поиск одиночных чёрных пикселей:
Снова пройдите по всей матрице и для каждой чёрной клетки (x, y) проверьте значения rowCount[x] и colCount[y]. Если оба значения равны 1, увеличьте переменную answer на 1.

3⃣ Возврат результата:
Верните answer.

😎 Решение:

public class Solution {
    public int FindLonelyPixel(char[][] picture) {
        int n = picture.Length;
        int m = picture[0].Length;
        
        int[] rowCount = new int[n];
        int[] columnCount = new int[m];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (picture[i][j] == 'B') {
                    rowCount[i]++;
                    columnCount[j]++;
                }
            }
        }
        
        int answer = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (picture[i][j] == 'B' && rowCount[i] == 1 && columnCount[j] == 1) {
                    answer++;
                }
            }
        }
        
        return answer;
    }
}

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

Задача: 646. Maximum Length of Pair Chain
Сложность: medium

Вам дан массив из n пар, где pairs[i] = [lefti, righti] и lefti < righti. Пара p2 = [c, d] следует за парой p1 = [a, b], если b < c. Таким образом можно построить цепочку пар. Верните самую длинную цепочку, которую можно составить. Вам не нужно использовать все заданные интервалы. Вы можете выбирать пары в любом порядке.

Пример:

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

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

1⃣Отсортируйте пары по второму элементу каждой пары (righti).

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

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

😎 Решение:

public class Solution {
    public int FindLongestChain(int[][] pairs) {
        Array.Sort(pairs, (a, b) => a[1] - b[1]);
        int currentEnd = int.MinValue;
        int count = 0;
        foreach (var pair in pairs) {
            if (currentEnd < pair[0]) {
                currentEnd = pair[1];
                count++;
            }
        }
        return count;
    }
}

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

Задача: 1315. Sum of Nodes with Even-Valued Grandparent
Сложность: medium

Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.

A grandparent of a node is the parent of its parent if it exists.

Пример:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

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

1⃣Определите метод solve(), который принимает TreeNode root, значение родителя parent и значение бабушки или дедушки gParent. Этот метод возвращает сумму значений узлов с четным значением бабушки и дедушки в поддереве узла root. Если root равен null, верните 0 как сумму.

2⃣Рекурсивно пройдите по левому и правому дочерним узлам, передавая в качестве значения parent root, а в качестве значения gParent parent. Если значение gParent четное, добавьте значение root к ответу.

3⃣Вызовите рекурсивную функцию solve() с корневым узлом и значениями -1 для parent и gParent. Верните сумму для левого и правого дочерних узлов и значение для текущего узла.

😎 Решение:

public class Solution {
    private int Solve(TreeNode root, int parent, int gParent) {
        if (root == null) {
            return 0;
        }
        return Solve(root.left, root.val, parent) + Solve(root.right, root.val, parent) + (gParent % 2 == 0 ? root.val : 0);
    }

    public int SumEvenGrandparent(TreeNode root) {
        return Solve(root, -1, -1);
    }
}

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

Задача: 474. Ones and Zeroes
Сложность: medium

Дан массив двоичных строк strs и два целых числа m и n.

Верните размер наибольшего подмножества strs, такого что в подмножестве содержится не более m нулей и n единиц.

Множество x является подмножеством множества y, если все элементы множества x также являются элементами множества y.

Пример:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

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

1⃣Рассматриваем все возможные подмножества, прерывая цикл, если количество нулей превышает m или количество единиц превышает n.

2⃣Считаем количество нулей и единиц в каждом подмножестве.

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

😎 Решение:

public class Solution {
    public int FindMaxForm(string[] strs, int m, int n) {
        int maxlen = 0;
        for (int i = 0; i < (1 << strs.Length); i++) {
            int zeroes = 0, ones = 0, len = 0;
            for (int j = 0; j < 32; j++) {
                if ((i & (1 << j)) != 0) {
                    int[] count = CountZeroesOnes(strs[j]);
                    zeroes += count[0];
                    ones += count[1];
                    if (zeroes > m || ones > n)
                        break;
                    len++;
                }
            }
            if (zeroes <= m && ones <= n)
                maxlen = Math.Max(maxlen, len);
        }
        return maxlen;
    }

    public int[] CountZeroesOnes(string s) {
        int[] c = new int[2];
        foreach (char ch in s) {
            c[ch - '0']++;
        }
        return c;
    }
}

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

Задача: 648. Replace Words
Сложность: medium

В английском языке есть понятие "корень", за которым может следовать какое-то другое слово, чтобы образовать другое более длинное слово - назовем это слово производным. Например, если за корнем "help" следует слово "ful", мы можем образовать производное "helpful". Дайте словарь, состоящий из множества корней, и предложение, состоящее из слов, разделенных пробелами, замените все производные в предложении на образующий их корень. Если производное может быть заменено более чем одним корнем, замените его корнем, имеющим наименьшую длину. Верните предложение после замены.

Пример:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

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

1⃣Преобразуйте словарь корней в набор для быстрого поиска.

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

3⃣Замените слово найденным корнем и соберите обновленное предложение.

😎 Решение:

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

public class Solution {
    public string ReplaceWords(IList<string> roots, string sentence) {
        var rootSet = new HashSet<string>(roots);
        
        string Replace(string word) {
            for (int i = 1; i <= word.Length; i++) {
                string prefix = word.Substring(0, i);
                if (rootSet.Contains(prefix)) {
                    return prefix;
                }
            }
            return word;
        }
        
        return string.Join(" ", sentence.Split(' ').Select(Replace));
    }
}

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

Задача: 404. Sum of Left Leaves
Сложность: easy

Если задан корень бинарного дерева, верните сумму всех левых листьев. Лист - это узел, не имеющий детей. Левый лист - это лист, который является левым ребенком другого узла.

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: 24

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

1⃣Рекурсивный обход дерева
Обходите дерево с помощью рекурсивной функции, которая принимает текущий узел и флаг, указывающий, является ли узел левым ребенком.

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

3⃣Рекурсивный вызов для детей
Рекурсивно вызовите функцию для левого и правого детей текущего узла, передавая соответствующий флаг.

😎 Решение:

public class Solution {
    public int SumOfLeftLeaves(TreeNode root) {
        return Dfs(root, false);
    }
    
    private int Dfs(TreeNode node, bool isLeft) {
        if (node == null) return 0;
        if (node.left == null && node.right == null) return isLeft ? node.val : 0;
        return Dfs(node.left, true) + Dfs(node.right, false);
    }
}

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

Задача: 93. Restore IP Addresses
Сложность: medium

Сообщение, содержащее буквы от A до Z, можно закодировать в числа с использованием следующего соответствия:

- 'A' -> "1"
- 'B' -> "2"
- ...
- 'Z' -> "26"

Для декодирования закодированного сообщения все цифры должны быть сгруппированы и затем отображены обратно в буквы с использованием обратного соответствия (существует несколько способов). Например, "11106" можно представить как:

- "AAJF" с группировкой (1 1 10 6)
- "KJF" с группировкой (11 10 6)

Обратите внимание, что группировка (1 11 06) недопустима, потому что "06" не может быть преобразовано в 'F', так как "6" отличается от "06".

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

Тестовые случаи сформированы таким образом, что ответ укладывается в 32-битное целое число.

Пример:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

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

1⃣Входим в рекурсию с данной строкой, начиная с индекса 0.

2⃣Для окончательного случая рекурсии мы проверяем конец строки. Если мы достигли конца строки, возвращаем 1. Каждый раз, когда мы входим в рекурсию, это для подстроки исходной строки. Если первый символ в подстроке равен 0, то прекращаем этот путь, возвращая 0. Таким образом, этот путь не будет влиять на количество способов.

3⃣Мемоизация помогает снизить сложность, которая иначе была бы экспоненциальной. Мы проверяем словарь memo, чтобы увидеть, существует ли уже результат для данной подстроки. Если результат уже находится в memo, мы возвращаем этот результат. В противном случае количество способов для данной строки определяется путем рекурсивного вызова функции с индексом +1 для следующей подстроки и индексом +2 после проверки на валидность двузначного декодирования. Результат также сохраняется в memo с ключом как текущий индекс, чтобы сохранить его для будущих пересекающихся подзадач.

😎 Решение:

public class Solution {
    private bool valid(string s, int start, int length) {
        return length == 1 ||
               (s[start] != '0' &&
                (length < 3 || int.Parse(s.Substring(start, length)) <= 255));
    }

    private void helper(string s, int startIndex, List<int> dots,
                        List<string> ans) {
        var remainingLength = s.Length - startIndex;
        var remainingNumberOfIntegers = 4 - dots.Count;
        if (remainingLength > remainingNumberOfIntegers * 3 ||
            remainingLength < remainingNumberOfIntegers)
            return;
        if (dots.Count == 3) {
            if (valid(s, startIndex, remainingLength)) {
                var temp = "";
                var last = 0;
                foreach (var dot in dots) {
                    temp += s.Substring(last, dot) + ".";
                    last += dot;
                }

                temp += s.Substring(startIndex);
                ans.Add(temp);
            }

            return;
        }

        for (int curPos = 1; curPos <= 3 && curPos <= remainingLength;
             ++curPos) {
            dots.Add(curPos);
            if (valid(s, startIndex, curPos)) {
                helper(s, startIndex + curPos, dots, ans);
            }

            dots.RemoveAt(dots.Count - 1);
        }
    }

    public IList<string> RestoreIpAddresses(string s) {
        var ans = new List<string>();
        helper(s, 0, new List<int>(), ans);
        return ans;
    }
}

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

Задача: 1180. Count Substrings with Only One Distinct Letter
Сложность: easy

Дана строка s. Верните количество подстрок, которые содержат только одну уникальную букву.

Пример:

Input: s = "aaaba"
Output: 8
Explanation: The substrings with one distinct letter are "aaa", "aa", "a", "b".
"aaa" occurs 1 time.
"aa" occurs 2 times.
"a" occurs 4 times.
"b" occurs 1 time.
So the answer is 1 + 2 + 4 + 1 = 8.

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

1⃣Инициализируйте целочисленную переменную total для подсчета количества подстрок, а также два указателя left и right, которые отмечают начало и конец подстроки, содержащей только одну уникальную букву.

2⃣Итерируйте по строке S: Если мы не достигли конца и новый символ S[right] такой же, как и начальный символ S[left], увеличьте right на 1 для дальнейшего исследования строки S; в противном случае вычислите длину подстроки как right - left и примените формулу суммы арифметической последовательности; не забудьте установить right в left для начала исследования новой подстроки.

3⃣После завершения итерации добавьте к total количество подстрок для последнего сегмента, если он не был учтен. Верните значение total.

😎 Решение:

public class Solution {
    public int CountLetters(string S) {
        int total = 0;
        int left = 0;

        for (int right = 0; right <= S.Length; right++) {
            if (right == S.Length || S[left] != S[right]) {
                int lenSubstring = right - left;
                total += (1 + lenSubstring) * lenSubstring / 2;
                left = right;
            }
        }
        return total;
    }
}

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