#hard
Задача: 499. The Maze III

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

Дан лабиринт размером m x n, позиция мяча ball и отверстия hole, где ball = [ballrow, ballcol] и hole = [holerow, holecol]. Верните строку instructions с кратчайшим путем мячика к отверстию. Если существует несколько вариантов, верните лексикографически минимальный. Если путь невозможен, верните "impossible". Ответ должен содержать 'u' (вверх), 'd' (вниз), 'l' (влево) и 'r' (вправо).
Расстояние — это количество пройденных пустых пространств от начальной позиции (исключительно) до конечной (включительно).

Вы можете предположить, что границы лабиринта — это стены. В примере ниже они не указаны.

Пример:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball = [4,3], hole = [0,1]
Output: "lul"

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

1⃣Инициализация и вспомогательные функции
Создайте функцию valid для проверки, находится ли координата (row, col) в пределах лабиринта и является ли она пустым пространством. Создайте функцию getNeighbors для получения списка соседей для данной позиции. Двигайтесь в каждом направлении (вверх, вниз, влево, вправо) до встречи со стеной.

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

3⃣Поиск кратчайшего пути
Пока очередь не пуста, извлекайте узел с наименьшим расстоянием. Если узел посещен, пропустите его. Если это отверстие, верните текущий путь. Отметьте узел как посещенный, добавьте его соседей в очередь, обновив расстояние и путь. Если пути нет, верните "impossible".

😎 Решение:

using System;
using System.Collections.Generic;

public class State : IComparable<State> {
    public int Row, Col, Dist;
    public string Path;
    public State(int r, int c, int d, string p) { Row = r; Col = c; Dist = d; Path = p; }
    public int CompareTo(State other) {
        return Dist == other.Dist ? string.Compare(Path, other.Path, StringComparison.Ordinal) : Dist - other.Dist;
    }
}

public class Solution {
    private static readonly int[][] Directions = { new[] {0, -1}, new[] {-1, 0}, new[] {0, 1}, new[] {1, 0} };
    private static readonly string[] TextDirections = { "l", "u", "r", "d" };

    public string FindShortestWay(int[][] maze, int[] ball, int[] hole) {
        int m = maze.Length, n = maze[0].Length;
        var heap = new PriorityQueue<State>();
        var seen = new bool[m, n];
        heap.Enqueue(new State(ball[0], ball[1], 0, ""));
        
        while (heap.Count > 0) {
            var curr = heap.Dequeue();
            if (seen[curr.Row, curr.Col]) continue;
            if (curr.Row == hole[0] && curr.Col == hole[1]) return curr.Path;
            seen[curr.Row, curr.Col] = true;
            
            foreach (var (dy, dx, direction) in Directions.Zip(TextDirections)) {
                int r = curr.Row, c = curr.Col, dist = 0;
                while (Valid(r + dy, c + dx, maze, m, n)) {
                    r += dy; c += dx; dist++;
                    if (r == hole[0] && c == hole[1]) break;
                }
                heap.Enqueue(new State(r, c, curr.Dist + dist, curr.Path + direction));
            }
        }
        return "impossible";
    }

    private bool Valid(int row, int col, int[][] maze, int m, int n) {
        return row >= 0 && row < m && col >= 0 && col < n && maze[row][col] == 0;
    }
}

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

#hard
Задача: 502. IPO

Предположим, что LeetCode скоро начнет свое IPO. Чтобы продать свои акции по хорошей цене венчурным капиталистам, LeetCode хочет выполнить несколько проектов для увеличения своего капитала перед IPO. Поскольку у компании ограниченные ресурсы, она может завершить не более k различных проектов до IPO. Помогите LeetCode разработать лучший способ максимизации общего капитала после завершения не более k различных проектов.

Вам дано n проектов, где i-й проект имеет чистую прибыль profits[i] и требует минимального капитала capital[i] для его начала.

Изначально у вас есть капитал w. Когда вы завершаете проект, вы получаете его чистую прибыль, и эта прибыль добавляется к вашему общему капиталу.

Выберите список из не более чем k различных проектов из данных, чтобы максимально увеличить ваш конечный капитал, и верните окончательно максимизированный капитал.

Ответ гарантированно поместится в 32-битное целое число со знаком.

Пример:

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

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

1⃣Сортировка и инициализация
Отсортируйте проекты по возрастанию капитала. Создайте указатель ptr на первый недоступный проект в отсортированном массиве. Создайте приоритетную очередь для прибылей доступных проектов. Изначально очередь пуста.

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

3⃣Увеличение капитала
Максимальное значение в приоритетной очереди — это прибыль проекта, который будет запущен сейчас. Увеличьте капитал на это значение. Удалите его из очереди, так как он больше не может быть использован.

😎 Решение:

public class Solution {
    public int FindMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        var projects = new List<(int capital, int profit)>();
        for (int i = 0; i < profits.Length; i++) {
            projects.Add((capital[i], profits[i]));
        }
        projects.Sort((a, b) => a.capital.CompareTo(b.capital));

        var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        int ptr = 0;

        for (int i = 0; i < k; i++) {
            while (ptr < projects.Count && projects[ptr].capital <= w) {
                maxHeap.Enqueue(projects[ptr].profit, projects[ptr].profit);
                ptr++;
            }
            if (maxHeap.Count == 0) break;
            w += maxHeap.Dequeue();
        }

        return w;
    }
}

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

#hard
Задача: 726. Number of Atoms

Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество элементов. Например, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. Например, "H2O2He3Mg4" также является формулой.
Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. Например, "(H2O2)" и "(H2O2)3" являются формулами.
Возвращает количество всех элементов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые примеры генерируются таким образом, чтобы все значения в выводе помещались в 32-битное целое число.

Пример:

Input: formula = "H2O"
Output: "H2O"

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

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

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

3⃣После завершения обработки строки, объедините все словари из стека и отсортируйте результат.

😎 Решение:

public class Solution {
    public string CountOfAtoms(string formula) {
        var stack = new Stack<Dictionary<string, int>>();
        stack.Push(new Dictionary<string, int>());
        int n = formula.Length;
        int i = 0;

        while (i < n) {
            if (formula[i] == '(') {
                stack.Push(new Dictionary<string, int>());
                i++;
            } else if (formula[i] == ')') {
                var top = stack.Pop();
                i++;
                int start = i;
                while (i < n && Char.IsDigit(formula[i])) {
                    i++;
                }
                int multiplicity = i > start ? int.Parse(formula.Substring(start, i - start)) : 1;
                foreach (var name in top.Keys) {
                    int count = top[name];
                    if (stack.Peek().ContainsKey(name)) {
                        stack.Peek()[name] += count * multiplicity;
                    } else {
                        stack.Peek()[name] = count * multiplicity;
                    }
                }
            } else {
                int start = i;
                i++;
                while (i < n && Char.IsLower(formula[i])) {
                    i++;
                }
                string name = formula.Substring(start, i - start);
                start = i;
                while (i < n && Char.IsDigit(formula[i])) {
                    i++;
                }
                int multiplicity = i > start ? int.Parse(formula.Substring(start, i - start)) : 1;
                if (stack.Peek().ContainsKey(name)) {
                    stack.Peek()[name] += multiplicity;
                } else {
                    stack.Peek()[name] = multiplicity;
                }
            }
        }

        var countMap = stack.Pop();
        var sb = new StringBuilder();
        foreach (var name in countMap.Keys.OrderBy(x => x)) {
            sb.Append(name);
            int count = countMap[name];
            if (count > 1) {
                sb.Append(count);
            }
        }
        return sb.ToString();
    }
}

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

#hard
Задача: 727. Minimum Window Subsequence

Если в строках s1 и s2 нет такого окна, которое покрывало бы все символы в s2, верните пустую строку "". Если таких окон минимальной длины несколько, возвращается окно с самым левым начальным индексом.

Пример:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"

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

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

2⃣Поддерживайте счетчики для символов в текущем окне и требуемых символов из s2.

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

😎 Решение:

public class Solution {
    public string MinWindow(string s1, string s2) {
        if (string.IsNullOrEmpty(s1) || string.IsNullOrEmpty(s2)) {
            return "";
        }

        var dictT = new Dictionary<char, int>();
        foreach (char c in s2) {
            if (dictT.ContainsKey(c)) {
                dictT[c]++;
            } else {
                dictT[c] = 1;
            }
        }

        int required = dictT.Count;
        int l = 0, r = 0, formed = 0;
        var windowCounts = new Dictionary<char, int>();
        int[] ans = { int.MaxValue, 0, 0 };

        while (r < s1.Length) {
            char c = s1[r];
            if (windowCounts.ContainsKey(c)) {
                windowCounts[c]++;
            } else {
                windowCounts[c] = 1;
            }

            if (dictT.ContainsKey(c) && windowCounts[c] == dictT[c]) {
                formed++;
            }

            while (l <= r && formed == required) {
                c = s1[l];

                if (r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }

                windowCounts[c]--;
                if (dictT.ContainsKey(c) && windowCounts[c] < dictT[c]) {
                    formed--;
                }

                l++;
            }

            r++;
        }

        return ans[0] == int.MaxValue ? "" : s1.Substring(ans[1], ans[0]);
    }
}

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

#hard
Задача: 728. Self Dividing Numbers

Например, 128 является саморазделяющимся числом, потому что 128 % 1 == 0, 128 % 2 == 0 и 128 % 8 == 0. Саморазделяющееся число не может содержать цифру ноль. Если даны два целых числа left и right, верните список всех саморазделяющихся чисел в диапазоне [left, right].

Пример:

Input: left = 1, right = 22
Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]

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

1⃣Переберите все числа в диапазоне от left до right.

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

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

😎 Решение:

public class Solution {
    public IList<int> SelfDividingNumbers(int left, int right) {
        List<int> result = new List<int>();
        for (int num = left; num <= right; num++) {
            if (IsSelfDividing(num)) {
                result.Add(num);
            }
        }
        return result;
    }
    
    private bool IsSelfDividing(int num) {
        int n = num;
        while (n > 0) {
            int digit = n % 10;
            if (digit == 0 || num % digit != 0) {
                return false;
            }
            n /= 10;
        }
        return true;
    }
}

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

#hard
Задача: 730. Count Different Palindromic Subsequences

Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi.

Пример:

Input: s = "bccb"
Output: 6

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

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

2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j.

3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок.

😎 Решение:

public class Solution {
    public int CountPalindromicSubsequences(string s) {
        const int MOD = 1000000007;
        int n = s.Length;
        int[,] dp = new int[n, n];

        for (int i = 0; i < n; i++) {
            dp[i, i] = 1;
        }

        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (s[i] == s[j]) {
                    int l = i + 1, r = j - 1;
                    while (l <= r && s[l] != s[i]) l++;
                    while (l <= r && s[r] != s[j]) r--;
                    
                    if (l > r) {
                        dp[i, j] = dp[i + 1, j - 1] * 2 + 2;
                    } else if (l == r) {
                        dp[i, j] = dp[i + 1, j - 1] * 2 + 1;
                    } else {
                        dp[i, j] = dp[i + 1, j - 1] * 2 - dp[l + 1, r - 1];
                    }
                } else {
                    dp[i, j] = dp[i + 1, j] + dp[i, j - 1] - dp[i + 1, j - 1];
                }

                dp[i, j] = (dp[i, j] + MOD) % MOD;
            }
        }

        return dp[0, n - 1];
    }
}

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

#hard
Задача: 732. My Calendar III

k-бронирование происходит, когда k событий имеют некоторое непустое пересечение (т.е, дано некоторое время, общее для всех k событий). Даны некоторые события [startTime, endTime), после каждого данного события верните целое число k, представляющее максимальное k-бронирование между всеми предыдущими событиями. Реализация класса MyCalendarThree: MyCalendarThree() Инициализирует объект. int book(int startTime, int endTime) Возвращает целое число k, представляющее наибольшее целое число, при котором в календаре существует k-бронирование.

Пример:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

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

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

2⃣Для каждого нового события обновите словари начала и конца событий.

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

😎 Решение:

using System;
using System.Collections.Generic;

public class MyCalendarThree {
    private SortedDictionary<int, int> events;

    public MyCalendarThree() {
        events = new SortedDictionary<int, int>();
    }

    public int Book(int startTime, int endTime) {
        if (!events.ContainsKey(startTime)) {
            events[startTime] = 0;
        }
        if (!events.ContainsKey(endTime)) {
            events[endTime] = 0;
        }
        events[startTime]++;
        events[endTime]--;
        
        int active = 0;
        int maxActive = 0;
        foreach (var count in events.Values) {
            active += count;
            maxActive = Math.Max(maxActive, active);
        }
        
        return maxActive;
    }
}

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

#hard
Задача: 736. Parse Lisp Expression

Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.

Пример:

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14

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

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

2⃣Используйте рекурсивный подход для обработки различных типов выражений (let, add, mult, и переменных).

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

😎 Решение:

public class Solution {
    public int Evaluate(string expression) {
        return Evaluate(expression, new Dictionary<string, int>());
    }
    
    private int Evaluate(string expression, Dictionary<string, int> env) {
        if (expression[0] != '(') {
            return int.TryParse(expression, out var result) ? result : env[expression];
        }
        
        var tokens = Tokenize(expression);
        if (tokens[0] == "let") {
            for (int i = 1; i < tokens.Count - 2; i += 2) {
                env[tokens[i]] = Evaluate(tokens[i + 1], env);
            }
            return Evaluate(tokens[^1], env);
        } else if (tokens[0] == "add") {
            return Evaluate(tokens[1], env) + Evaluate(tokens[2], env);
        } else if (tokens[0] == "mult") {
            return Evaluate(tokens[1], env) * Evaluate(tokens[2], env);
        }
        return 0;
    }
    
    private List<string> Tokenize(string expression) {
        var tokens = new List<string>();
        var token = string.Empty;
        int parens = 0;
        foreach (var c in expression) {
            if (c == '(') {
                parens++;
                if (parens == 1) continue;
            } else if (c == ')') {
                parens--;
                if (parens == 0) {
                    tokens.AddRange(Tokenize(token));
                    token = string.Empty;
                    continue;
                }
            } else if (c == ' ' && parens == 1) {
                if (!string.IsNullOrEmpty(token)) {
                    tokens.Add(token);
                    token = string.Empty;
                }
                continue;
            }
            token += c;
        }
        if (!string.IsNullOrEmpty(token)) {
            tokens.Add(token);
        }
        return tokens;
    }
}

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

#hard
Задача: 741. Cherry Pickup

Вам дана сетка n x n, представляющая поле вишен. Каждая клетка - одно из трех возможных целых чисел. 0 означает, что клетка пуста, и вы можете пройти через нее, 1 означает, что клетка содержит вишню, которую вы можете сорвать и пройти через нее, или -1 означает, что клетка содержит шип, который преграждает вам путь. Верните максимальное количество вишен, которое вы можете собрать, следуя следующим правилам: Начиная с позиции (0, 0) и достигая (n - 1, n - 1) путем перемещения вправо или вниз через допустимые клетки пути (клетки со значением 0 или 1).
После достижения (n - 1, n - 1) вернитесь в (0, 0), двигаясь влево или вверх по клеткам с действительными путями. Проходя через клетку пути, содержащую вишню, вы поднимаете ее, и клетка становится пустой клеткой 0. Если между (0, 0) и (n - 1, n - 1) нет действительного пути, то вишни собрать нельзя.

Пример:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5

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

1⃣Используйте динамическое программирование для подсчета максимального количества вишен, которые можно собрать при движении от (0, 0) до (n - 1, n - 1).

2⃣Примените еще один проход с использованием динамического программирования для движения обратно от (n - 1, n - 1) до (0, 0), чтобы учитывать вишни, собранные на обратном пути.

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

😎 Решение:

using System;

public class Solution {
    public int CherryPickup(int[][] grid) {
        int n = grid.Length;
        int[][][] dp = new int[n][][];
        for (int i = 0; i < n; i++) {
            dp[i] = new int[n][];
            for (int j = 0; j < n; j++) {
                dp[i][j] = new int[2 * n - 1];
                Array.Fill(dp[i][j], int.MinValue);
            }
        }
        dp[0][0][0] = grid[0][0];

        for (int k = 1; k < 2 * n - 1; k++) {
            for (int i1 = Math.Max(0, k - n + 1); i1 <= Math.Min(n - 1, k); i1++) {
                for (int i2 = Math.Max(0, k - n + 1); i2 <= Math.Min(n - 1, k); i2++) {
                    int j1 = k - i1, j2 = k - i2;
                    if (j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1) {
                        int maxCherries = int.MinValue;
                        if (i1 > 0 && i2 > 0) maxCherries = Math.Max(maxCherries, dp[i1 - 1][i2 - 1][k - 1]);
                        if (i1 > 0) maxCherries = Math.Max(maxCherries, dp[i1 - 1][i2][k - 1]);
                        if (i2 > 0) maxCherries = Math.Max(maxCherries, dp[i1][i2 - 1][k - 1]);
                        maxCherries = Math.Max(maxCherries, dp[i1][i2][k - 1]);
                        if (maxCherries != int.MinValue) {
                            dp[i1][i2][k] = maxCherries + grid[i1][j1];
                            if (i1 != i2) dp[i1][i2][k] += grid[i2][j2];
                        }
                    }
                }
            }
        }

        return Math.Max(0, dp[n - 1][n - 1][2 * n - 1]);
    }
}

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

#hard
Задача: 745. Prefix and Suffix Search

Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

1⃣Сохраните слова и их индексы в словаре.

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

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

😎 Решение:

using System;
using System.Collections.Generic;

public class WordFilter {
    private Dictionary<string, int> prefixSuffixMap = new Dictionary<string, int>();
    
    public WordFilter(string[] words) {
        for (int index = 0; index < words.Length; index++) {
            string word = words[index];
            int length = word.Length;
            for (int prefixLength = 1; prefixLength <= length; prefixLength++) {
                for (int suffixLength = 1; suffixLength <= length; suffixLength++) {
                    string prefix = word.Substring(0, prefixLength);
                    string suffix = word.Substring(length - suffixLength);
                    string key = prefix + "#" + suffix;
                    prefixSuffixMap[key] = index;
                }
            }
        }
    }
    
    public int F(string pref, string suff) {
        string key = pref + "#" + suff;
        return prefixSuffixMap.ContainsKey(key) ? prefixSuffixMap[key] : -1;
    }
}

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

#hard
Задача: 757. Set Intersection Size At Least Two

Вам дан двумерный целочисленный массив intervals, в котором intervals[i] = [starti, endi] представляет все целые числа от starti до endi включительно. Содержащее множество - это массив nums, в котором каждый интервал из intervals содержит не менее двух целых чисел в nums. Например, если intervals = [[1,3], [3,7], [8,9]], то [1,2,4,7,8,9] и [2,3,4,8,9] - содержащие множества. Верните минимально возможный размер содержащего множества.

Пример:

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5

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

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

2⃣Инициализируйте пустое множество для хранения чисел.

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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int MinSetSize(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));
        var nums = new List<int>();
        foreach (var interval in intervals) {
            int start = interval[0];
            int end = interval[1];
            if (nums.Count == 0 || nums[nums.Count - 1] < start) {
                nums.Add(end - 1);
                nums.Add(end);
            } else if (nums[nums.Count - 1] == end - 1) {
                nums.Add(end);
            }
        }
        return nums.Count;
    }
}

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

#hard
Задача: 759. Employee Free Time

Нам дан список 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;
    }
}

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