#medium
Задача: 673. Number of Longest Increasing Subsequence

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

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

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

1⃣Объявите два массива динамического программирования length и count, и инициализируйте их значениями length[i]=1 и count[i]=1. Итерируйте i от 0 до n−1. Для каждого i итерируйте j от 0 до i−1 и, если nums[j] < nums[i], обновите length[i] и count[i] в зависимости от значений length[j] и count[j].

2⃣Найдите максимальное значение в массиве length и сохраните его в переменной maxLength. Инициализируйте переменную result = 0.

3⃣Итерируйте i от 0 до n−1 и, если length[i] = maxLength, добавьте count[i] к result. Верните result.

😎 Решение:

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> length(n, 1);
        vector<int> count(n, 1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (length[j] + 1 > length[i]) {
                        length[i] = length[j] + 1;
                        count[i] = 0;
                    }
                    if (length[j] + 1 == length[i]) {
                        count[i] += count[j];
                    }
                }
            }
        }

        int maxLength = *max_element(length.begin(), length.end());
        int result = 0;

        for (int i = 0; i < n; i++) {
            if (length[i] == maxLength) {
                result += count[i];
            }
        }

        return result;
    }
};

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

#easy
Задача: 674. Longest Continuous Increasing Subsequence

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

Непрерывная возрастающая подпоследовательность определяется двумя индексами l и r (l < r) так, что она имеет вид [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] и для каждого l <= i < r выполняется nums[i] < nums[i + 1].

Пример:

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.

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

1⃣Каждая (непрерывная) возрастающая подпоследовательность не пересекается, и граница каждой такой подпоследовательности возникает, когда nums[i-1] >= nums[i]. В этом случае начинается новая возрастающая подпоследовательность с nums[i], и мы сохраняем такой i в переменной anchor.

2⃣Например, если nums = [7, 8, 9, 1, 2, 3], то anchor начинается с 0 (nums[anchor] = 7) и затем устанавливается на anchor = 3 (nums[anchor] = 1). Независимо от значения anchor, мы записываем кандидата на ответ длиной i - anchor + 1, длина подмассива nums[anchor], nums[anchor+1], ..., nums[i], и наш ответ обновляется соответствующим образом.

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

😎 Решение:

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int ans = 0, anchor = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (i > 0 && nums[i-1] >= nums[i]) anchor = i;
            ans = max(ans, i - anchor + 1);
        }
        return ans;
    }
};

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

#hard
Задача: 675. Cut Off Trees for Golf Event

Вам необходимо срубить все деревья в лесу для проведения гольф-мероприятия. Лес представлен в виде матрицы m x n. В этой матрице:

- 0 означает, что ячейка непроходима.
- 1 представляет собой пустую проходимую ячейку.
- Число больше 1 представляет собой дерево в ячейке, и это число обозначает высоту дерева.

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

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

Начиная с точки (0, 0), верните минимальное количество шагов, необходимых для того, чтобы срубить все деревья. Если невозможно срубить все деревья, верните -1.

Примечание: Входные данные сформированы так, что нет двух деревьев с одинаковой высотой, и нужно срубить как минимум одно дерево.

Пример:

Input: forest = [[1,2,3],[0,0,4],[7,6,5]]
Output: 6
Explanation: Following the path above allows you to cut off the trees from shortest to tallest in 6 steps.

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

1⃣Начиная с (0, 0), для каждого дерева в порядке возрастания высоты будем вычислять расстояние от текущего местоположения до следующего дерева (и перемещаться туда), добавляя это расстояние к ответу.

2⃣Формулируем задачу как предоставление функции расстояния dist(forest, sr, sc, tr, tc), которая вычисляет расстояние от точки (sr, sc) до цели (tr, tc) с учетом препятствий, где dist[i][j] == 0. (Эта функция расстояния вернет -1, если путь невозможен.)

3⃣Далее следует код и анализ сложности, которые общие для всех трех подходов. Затем алгоритмы, представленные в наших подходах, будут сосредоточены только на предоставлении нашей функции dist.

😎 Решение:

class Solution {
public:
    int cutOffTree(vector<vector<int>>& forest) {
        vector<tuple<int, int, int>> trees;
        for (int r = 0; r < forest.size(); ++r) {
            for (int c = 0; c < forest[0].size(); ++c) {
                if (forest[r][c] > 1) {
                    trees.emplace_back(forest[r][c], r, c);
                }
            }
        }
        sort(trees.begin(), trees.end());

        int sr = 0, sc = 0, ans = 0;
        for (auto& tree : trees) {
            int tr, tc, height;
            tie(height, tr, tc) = tree;
            int d = dist(forest, sr, sc, tr, tc);
            if (d < 0) return -1;
            ans += d;
            sr = tr;
            sc = tc;
        }
        return ans;
    }

private:
    int dist(const vector<vector<int>>& forest, int sr, int sc, int tr, int tc) {
        // Implement the distance function here
        return 0;
    }
};

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

#hard
Задача: 312. Burst Balloons

Дано n воздушных шаров, пронумерованных от 0 до n - 1. Каждый шарик окрашен в число, представленное массивом nums. Вам нужно лопнуть все шарики.

Если вы лопаете шарик i, вы получите nums[i - 1] * nums[i] * nums[i + 1] монет. Если i - 1 или i + 1 выходит за границы массива, то считайте, что там находится шарик с числом 1.

Верните максимальное количество монет, которое можно собрать, лопая шарики с умом.

Пример:

Input: nums = [1,5]
Output: 10

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

1⃣Инициализация и подготовка данных
Добавьте по одному шару с числом 1 в начало и конец массива nums, чтобы упростить обработку граничных случаев. Определите функцию dp(left, right), которая будет возвращать максимальное количество монет, если лопнуть все шары на интервале [left, right] включительно.

2⃣Вычисление значений для всех интервалов
Для каждого интервала [left, right] и каждого индекса i в этом интервале: Вычислите максимальные монеты, которые можно получить, сначала лопая все шары кроме i, а затем лопая i. Обновите dp(left, right) максимальной суммой этих монет.

3⃣Возврат результата
Верните значение dp(1, n - 2), которое будет содержать максимальное количество монет, которое можно собрать, лопнув все шары с умом, исключая добавленные нами шары.

😎 Решение:

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<int> newNums(n + 2, 1);
        for (int i = 0; i < n; ++i) {
            newNums[i + 1] = nums[i];
        }
        
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        
        for (int length = 2; length < n + 2; ++length) {
            for (int left = 0; left < n + 2 - length; ++left) {
                int right = left + length;
                for (int i = left + 1; i < right; ++i) {
                    dp[left][right] = max(dp[left][right],
                                          newNums[left] * newNums[i] * newNums[right] + dp[left][i] + dp[i][right]);
                }
            }
        }
        
        return dp[0][n + 1];
    }
};

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

#hard
Задача: 632. Smallest Range Covering Elements from K Lists

У вас есть k списков отсортированных целых чисел в неубывающем порядке. Найдите наименьший диапазон, в который входит хотя бы одно число из каждого из k списков. Мы определяем, что диапазон [a, b] меньше диапазона [c, d], если b - a < d - c или a < c, если b - a == d - c.

Пример:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]

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

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

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

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

😎 Решение:

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        priority_queue<Element, vector<Element>, Compare> minHeap;
        int maxValue = INT_MIN;

        for (int i = 0; i < nums.size(); i++) {
            minHeap.push(Element(nums[i][0], i, 0));
            maxValue = max(maxValue, nums[i][0]);
        }

        int rangeStart = 0, rangeEnd = INT_MAX;

        while (minHeap.size() == nums.size()) {
            Element minElement = minHeap.top();
            minHeap.pop();
            if (maxValue - minElement.value < rangeEnd - rangeStart) {
                rangeStart = minElement.value;
                rangeEnd = maxValue;
            }

            if (minElement.col + 1 < nums[minElement.row].size()) {
                int value = nums[minElement.row][minElement.col + 1];
                minHeap.push(Element(value, minElement.row, minElement.col + 1));
                maxValue = max(maxValue, value);
            }
        }

        return {rangeStart, rangeEnd};
    }
};

struct Element {
    int value, row, col;
    Element(int v, int r, int c) : value(v), row(r), col(c) {}
};

struct Compare {
    bool operator()(const Element& a, const Element& b) {
        return a.value > b.value;
    }
};

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

#medium
Задача: 633. Sum of Square Numbers

Учитывая целое неотрицательное число c, решите, существуют ли два целых числа a и b такие, что a2 + b2 = c.

Пример:

Input: c = 5
Output: true

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

1⃣Проверка границ
Проверьте, если c меньше 0, немедленно верните false, так как сумма квадратов двух целых чисел не может быть отрицательной.

2⃣Инициализация указателей
Используйте два указателя a и b. Инициализируйте a на 0 и b на значение квадратного корня из c. Поиск решения: Используйте цикл для поиска a и b, таких что a^2 + b^2 == c: Если a^2 + b^2 равно c, верните true. Если a^2 + b^2 меньше c, увеличьте a на 1. Если a^2 + b^2 больше c, уменьшите b на 1.

3⃣Возвращение результата
Если цикл завершится без нахождения подходящих a и b, верните false.

😎 Решение:

class Solution {
public:
    bool judgeSquareSum(int c) {
        int a = 0;
        int b = (int) sqrt(c);
        while (a <= b) {
            int total = a * a + b * b;
            if (total == c) {
                return true;
            } else if (total < c) {
                a++;
            } else {
                b--;
            }
        }
        return false;
    }
};

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

#medium
Задача: 634. Find the Derangement of An Array

В комбинаторной математике отклонение - это перестановка элементов множества таким образом, что ни один элемент не оказывается на прежнем месте. Вам дано целое число n. Изначально имеется массив, состоящий из n целых чисел от 1 до n в порядке возрастания, верните количество отклонений, которые он может породить. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.

Пример:

Input: n = 3
Output: 2

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

1⃣Инициализация массива для хранения результатов: Создайте массив dp для хранения количества отклонений для каждого значения от 0 до n. Установите начальные значения: dp[0] = 1 и dp[1] = 0.

2⃣Вычисление количества отклонений: Используйте динамическое программирование для вычисления количества отклонений для каждого значения от 2 до n. Формула для вычисления: dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD.

3⃣Возвращение результата: Верните значение dp[n], которое будет количеством отклонений для n элементов, по модулю 10^9 + 7.

😎 Решение:

class Solution {
public:
    int countDerangements(int n) {
        const int MOD = 1000000007;
        if (n == 0) return 1;
        if (n == 1) return 0;
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = (long long)(i - 1) * (dp[i - 1] + dp[i - 2]) % MOD;
        }
        return dp[n];
    }
};

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

#medium
Задача: 635. Design Log Storage System

Вам дается несколько журналов, где каждый журнал содержит уникальный идентификатор и временную метку. Временная метка - это строка, имеющая следующий формат: Год:Месяц:День:Час:Минута:Секунда, например, 2017:01:01:23:59:59. Все домены - десятичные числа с нулевым добавлением. Реализация класса LogSystem: LogSystem() Инициализирует объект LogSystem. void put(int id, string timestamp) Сохраняет заданный журнал (id, timestamp) в вашей системе хранения.
int[] retrieve(string start, string end, string granularity) Возвращает идентификаторы журналов, временные метки которых находятся в диапазоне от start до end включительно. start и end имеют тот же формат, что и timestamp, а granularity означает, насколько точным должен быть диапазон (т. е. с точностью до дня, минуты и т. д.). Например, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", а granularity = "Day" означает, что нам нужно найти журналы в диапазоне от 1 января 2017 года до 2 января 2017 года включительно, а час, минуту и секунду для каждой записи журнала можно игнорировать.

Пример:

Input
["LogSystem", "put", "put", "put", "retrieve", "retrieve"]
[[], [1, "2017:01:01:23:59:59"], [2, "2017:01:01:22:59:59"], [3, "2016:01:01:00:00:00"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour"]]
Output
[null, null, null, null, [3, 2, 1], [2, 1]]

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

1⃣Инициализация и хранение журналов: Реализуйте метод put, который будет сохранять журнал с заданным id и timestamp в системе хранения.

2⃣Формирование диапазона: Реализуйте метод retrieve, который будет формировать диапазон временных меток на основе заданного start, end и granularity.

3⃣Фильтрация и возврат результатов: Используйте сформированный диапазон для фильтрации журналов и возврата идентификаторов тех журналов, чьи временные метки попадают в этот диапазон.

😎 Решение:

class LogSystem {
public:
    LogSystem() {
        granularity = {{"Year", 4}, {"Month", 7}, {"Day", 10}, {"Hour", 13}, {"Minute", 16}, {"Second", 19}};
    }

    void put(int id, string timestamp) {
        logs.push_back({id, timestamp});
    }

    vector<int> retrieve(string start, string end, string granularity) {
        int length = this->granularity[granularity];
        start = start.substr(0, length);
        end = end.substr(0, length);
        vector<int> result;
        for (const auto& log : logs) {
            string ts = log.timestamp.substr(0, length);
            if (start <= ts && ts <= end) {
                result.push_back(log.id);
            }
        }
        return result;
    }

private:
    struct Log {
        int id;
        string timestamp;
    };

    vector<Log> logs;
    unordered_map<string, int> granularity;
};

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

#medium
Задача: 636. Exclusive Time of Functions

На однопоточном процессоре выполняется программа, содержащая n функций. Каждая функция имеет уникальный ID от 0 до n-1. Вызовы функций хранятся в стеке вызовов: когда начинается вызов функции, ее ID заталкивается в стек, а когда вызов функции заканчивается, ее ID выгружается из стека. Функция, чей идентификатор находится в верхней части стека, является текущей выполняемой функцией. Каждый раз, когда функция запускается или завершается, мы пишем лог с идентификатором, началом или завершением и меткой времени. Вам предоставляется список logs, где logs[i] представляет собой i-е сообщение лога, отформатированное как строка "{function_id}:{"start" | "end"}:{timestamp}". Например, "0:start:3" означает, что вызов функции с идентификатором 0 начался в начале временной метки 3, а "1:end:2" означает, что вызов функции с идентификатором 1 завершился в конце временной метки 2. Обратите внимание, что функция может быть вызвана несколько раз, возможно, рекурсивно. Исключительное время функции - это сумма времен выполнения всех вызовов функции в программе. Например, если функция вызывается дважды, причем один вызов выполняется за 2 единицы времени, а другой - за 1 единицу, то эксклюзивное время равно 2 + 1 = 3. Верните эксклюзивное время каждой функции в массив, где значение по i-му индексу представляет собой эксклюзивное время для функции с идентификатором i.

Пример:

Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3,4]

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

1⃣Парсинг логов: Пройдитесь по каждому логу, чтобы распознать действие (start или end) и идентификатор функции вместе с временной меткой.

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

3⃣Обновление времени выполнения: Когда функция завершает выполнение, обновите ее эксклюзивное время и также учитывайте время выполнения вложенных функций.

😎 Решение:

class Solution {
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        stack<int> stack;
        vector<int> times(n, 0);
        int prevTime = 0;
        
        for (const string& log : logs) {
            stringstream ss(log);
            string fidStr, type, timeStr;
            getline(ss, fidStr, ':');
            getline(ss, type, ':');
            getline(ss, timeStr, ':');
            int fid = stoi(fidStr);
            int time = stoi(timeStr);
            
            if (type == "start") {
                if (!stack.empty()) {
                    times[stack.top()] += time - prevTime;
                }
                stack.push(fid);
                prevTime = time;
            } else {
                times[stack.top()] += time - prevTime + 1;
                stack.pop();
                prevTime = time + 1;
            }
        }
        
        return times;
    }
};

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

#easy
Задача: 637. Average of Levels in Binary Tree

Учитывая корень бинарного дерева, верните среднее значение узлов на каждом уровне в виде массива. Принимаются ответы в пределах 10-5 от фактического ответа.

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]

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

1⃣Обход дерева: Используйте обход в ширину (BFS) для обхода каждого уровня дерева.
2⃣Подсчет среднего значения: Для каждого уровня дерева подсчитайте сумму значений узлов и количество узлов, чтобы вычислить среднее значение.
3⃣Сохранение результата: Сохраните среднее значение каждого уровня в массив и верните его.

😎 Решение:

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> result;
        queue<TreeNode*> queue;
        queue.push(root);
        
        while (!queue.empty()) {
            long sum = 0;
            int count = queue.size();
            for (int i = 0; i < count; i++) {
                TreeNode* node = queue.front();
                queue.pop();
                sum += node->val;
                if (node->left) queue.push(node->left);
                if (node->right) queue.push(node->right);
            }
            result.push_back((double) sum / count);
        }
        
        return result;
    }
};

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

#medium
Задача: 638. Shopping Offers

В магазине LeetCode Store есть n предметов для продажи. Каждый товар имеет свою цену. Однако существуют специальные предложения, и специальное предложение состоит из одного или нескольких различных видов товаров с распродажной ценой. Вам дан целочисленный массив price, где price[i] - цена i-го товара, и целочисленный массив needs, где needs[i] - количество штук i-го товара, который вы хотите купить. Вам также дан массив special, где special[i] имеет размер n + 1, где special[i][j] - количество штук j-го товара в i-м предложении, а special[i][n] (т.е., Возвращает наименьшую цену, которую вы можете заплатить за определенный товар из заданных, где вы могли бы оптимально использовать специальные предложения. Вам не разрешается покупать больше товаров, чем вы хотите, даже если это снизит общую цену. Вы можете использовать любое из специальных предложений столько раз, сколько захотите.

Пример:

Input: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
Output: 14

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

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

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

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

😎 Решение:

class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        unordered_map<string, int> memo;
        return dfs(price, special, needs, memo);
    }

private:
    int dfs(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, unordered_map<string, int>& memo) {
        string key = serialize(needs);
        if (memo.find(key) != memo.end()) {
            return memo[key];
        }

        int minPrice = 0;
        for (int i = 0; i < needs.size(); i++) {
            minPrice += needs[i] * price[i];
        }

        for (vector<int>& offer : special) {
            vector<int> newNeeds(needs.size());
            bool valid = true;
            for (int i = 0; i < needs.size(); i++) {
                if (needs[i] < offer[i]) {
                    valid = false;
                    break;
                }
                newNeeds[i] = needs[i] - offer[i];
            }
            if (valid) {
                minPrice = min(minPrice, offer.back() + dfs(price, special, newNeeds, memo));
            }
        }

        memo[key] = minPrice;
        return minPrice;
    }

    string serialize(vector<int>& needs) {
        string key = "";
        for (int need : needs) {
            key += to_string(need) + ",";
        }
        return key;
    }
};

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

#hard
Задача: 639. Decode Ways II

Сообщение, содержащее буквы от 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". В дополнение к вышеуказанным преобразованиям кодированное сообщение может содержать символ "*", который может представлять любую цифру от "1" до "9" ("0" исключается). Например, кодированное сообщение "1*" может представлять любое из кодированных сообщений "11", "12", "13", "14", "15", "16", "17", "18" или "19". Декодирование "1*" эквивалентно декодированию любого из кодированных сообщений, которые оно может представлять. Если задана строка s, состоящая из цифр и символов '*', верните количество способов ее декодирования. Поскольку ответ может быть очень большим, верните его по модулю 109 + 7.

Пример:

Input: s = "*"
Output: 9

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

1⃣Инициализация: Создайте массив dp, где dp[i] представляет количество способов декодирования подстроки s[0:i]. Установите начальные значения dp[0] = 1 (пустая строка имеет один способ декодирования).

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

3⃣Модульное вычисление: Поскольку количество способов декодирования может быть большим, вычисляйте результаты по модулю 10^9 + 7.

😎 Решение:

class Solution {
public:
    int numDecodings(string s) {
        const int MOD = 1000000007;
        int n = s.size();
        vector<long> dp(n + 1, 0);
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            if (s[i - 1] == '*') {
                dp[i] = 9 * dp[i - 1];
            } else if (s[i - 1] != '0') {
                dp[i] = dp[i - 1];
            }

            if (i > 1) {
                if (s[i - 2] == '*') {
                    if (s[i - 1] == '*') {
                        dp[i] += 15 * dp[i - 2];
                    } else if (s[i - 1] <= '6') {
                        dp[i] += 2 * dp[i - 2];
                    } else {
                        dp[i] += dp[i - 2];
                    }
                } else if (s[i - 2] == '1') {
                    if (s[i - 1] == '*') {
                        dp[i] += 9 * dp[i - 2];
                    } else {
                        dp[i] += dp[i - 2];
                    }
                } else if (s[i - 2] == '2') {
                    if (s[i - 1] == '*') {
                        dp[i] += 6 * dp[i - 2];
                    } else if (s[i - 1] <= '6') {
                        dp[i] += dp[i - 2];
                    }
                }
            }

            dp[i] %= MOD;
        }

        return dp[n];
    }
};

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

#medium
Задача: 640. Solve the Equation

Решите заданное уравнение и верните значение 'x' в виде строки "x=#value". Уравнение содержит только операции '+', '-', переменную 'x' и ее коэффициент. Вы должны вернуть "No solution", если для уравнения нет решения, или "Infinite solutions", если для уравнения существует бесконечное количество решений. Если для уравнения существует ровно одно решение, мы убеждаемся, что значение 'x' является целым числом.

Пример:

Input: s = "*"
Output: 9

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

1⃣Разделение уравнения: Разделите уравнение на левую и правую части относительно знака равенства '='.

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

3⃣Решение уравнения: Используйте уравнение вида ax + b = cx + d, чтобы решить для 'x'. Если коэффициенты 'x' равны и числовые значения равны, уравнение имеет бесконечное количество решений. Если коэффициенты 'x' равны, но числовые значения различны, решения нет. В противном случае вычислите значение 'x'.

😎 Решение:

class Solution {
public:
    string solveEquation(string equation) {
        auto parse = [](const string& s) {
            int coeff = 0, constPart = 0, sign = 1, num = 0;
            int i = 0;
            while (i < s.size()) {
                if (s[i] == '+') {
                    sign = 1;
                    i++;
                } else if (s[i] == '-') {
                    sign = -1;
                    i++;
                } else if (isdigit(s[i])) {
                    num = 0;
                    while (i < s.size() && isdigit(s[i])) {
                        num = num * 10 + (s[i] - '0');
                        i++;
                    }
                    if (i < s.size() && s[i] == 'x') {
                        coeff += sign * num;
                        i++;
                    } else {
                        constPart += sign * num;
                    }
                } else if (s[i] == 'x') {
                    coeff += sign;
                    i++;
                }
            }
            return make_pair(coeff, constPart);
        };

        auto [leftCoeff, leftConst] = parse(equation.substr(0, equation.find('=')));
        auto [rightCoeff, rightConst] = parse(equation.substr(equation.find('=') + 1));

        int coeff = leftCoeff - rightCoeff;
        int constPart = rightConst - leftConst;

        if (coeff == 0) {
            return constPart == 0 ? "Infinite solutions" : "No solution";
        }
        return "x=" + to_string(constPart / coeff);
    }
};

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

#easy
Задача: 566. Reshape the Matrix

В MATLAB есть удобная функция под названием reshape, которая может преобразовать матрицу размером m x n в новую матрицу с другим размером r x c, сохраняя исходные данные.

Вам дана матрица m x n mat и два целых числа r и c, представляющие количество строк и столбцов желаемой преобразованной матрицы.

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

Если операция преобразования с заданными параметрами возможна и допустима, выведите новую преобразованную матрицу; в противном случае выведите исходную матрицу.

Пример:

Input: mat = [[1,2],[3,4]], r = 1, c = 4
Output: [[1,2,3,4]]

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

1⃣Проверить, можно ли преобразовать матрицу с заданными параметрами r и c. Это возможно, если произведение m * n равно произведению r * c. Если преобразование невозможно, вернуть исходную матрицу.

2⃣Создать новый массив для хранения преобразованной матрицы. Перебрать все элементы исходной матрицы и вставить их в новый массив в порядке обхода строк.

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

😎 Решение:

class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
        int m = mat.size(), n = mat[0].size();
        if (m * n != r * c) {
            return mat;
        }
        vector<vector<int>> reshapedMatrix(r, vector<int>(c));
        int row = 0, col = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                reshapedMatrix[row][col] = mat[i][j];
                col++;
                if (col == c) {
                    col = 0;
                    row++;
                }
            }
        }
        return reshapedMatrix;
    }
};

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

#medium
Задача: 641. Design Circular Deque

Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае.

Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

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

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

2⃣Операции вставки: Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры.

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

😎 Решение:

class MyCircularDeque {
public:
    MyCircularDeque(int k) : deque(k), front(0), rear(0), size(0), capacity(k) {}

    bool insertFront(int value) {
        if (isFull()) return false;
        front = (front - 1 + capacity) % capacity;
        deque[front] = value;
        size++;
        return true;
    }

    bool insertLast(int value) {
        if (isFull()) return false;
        deque[rear] = value;
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }

    bool deleteFront() {
        if (isEmpty()) return false;
        front = (front + 1) % capacity;
        size--;
        return true;
    }

    bool deleteLast() {
        if (isEmpty()) return false;
        rear = (rear - 1 + capacity) % capacity;
        size--;
        return true;
    }

    int getFront() {
        if (isEmpty()) return -1;
        return deque[front];
    }

    int getRear() {
        if (isEmpty()) return -1;
        return deque[(rear - 1 + capacity) % capacity];
    }

    bool isEmpty() {
        return size == 0;
    }

    bool isFull() {
        return size == capacity;
    }

private:
    vector<int> deque;
    int front;
    int rear;
    int size;
    int capacity;
};

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

#medium
Задача: 567. Permutation in String

Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае.

Другими словами, верните true, если одна из перестановок s1 является подстрокой s2.

Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

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

1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2.
2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1.
3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.

😎 Решение:

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int s1Len = s1.size(), s2Len = s2.size();
        if (s1Len > s2Len) return false;
        
        vector<int> s1Count(26, 0), s2Count(26, 0);
        for (int i = 0; i < s1Len; i++) {
            s1Count[s1[i] - 'a']++;
            s2Count[s2[i] - 'a']++;
        }
        
        for (int i = 0; i < s2Len - s1Len; i++) {
            if (s1Count == s2Count) return true;
            s2Count[s2[i] - 'a']--;
            s2Count[s2[i + s1Len] - 'a']++;
        }
        
        return s1Count == s2Count;
    }
};

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

#hard
Задача: 642. Design Search Autocomplete System

Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст.

Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

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

1⃣Инициализация и проверка состояний: Реализуйте конструктор для инициализации кольцевой двусторонней очереди заданного размера и методы для проверки пустоты и полноты очереди.
2⃣Операции вставки: Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры.
3⃣Операции удаления: Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди.

😎 Решение:

class AutocompleteSystem {
public:
    AutocompleteSystem(vector<string>& sentences, vector<int>& times) {
        root = new TrieNode();
        current = root;
        for (int i = 0; i < sentences.size(); ++i) {
            add(sentences[i], times[i]);
        }
    }

    vector<string> input(char c) {
        if (c == '#') {
            add(currentPrefix, 1);
            currentPrefix = "";
            current = root;
            return {};
        }

        currentPrefix += c;
        if (current->children.find(c) == current->children.end()) {
            current->children[c] = new TrieNode();
        }
        current = current->children[c];
        return search(current);
    }

private:
    struct TrieNode {
        unordered_map<char, TrieNode*> children;
        unordered_map<string, int> count;
    };

    TrieNode* root;
    TrieNode* current;
    string currentPrefix;

    void add(const string& sentence, int times) {
        TrieNode* node = root;
        for (char c : sentence) {
            if (node->children.find(c) == node->children.end()) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
            node->count[sentence] += times;
        }
    }

    vector<string> search(TrieNode* node) {
        priority_queue<pair<int, string>> pq;
        for (const auto& p : node->count) {
            pq.push({p.second, p.first});
            if (pq.size() > 3) {
                pq.pop();
            }
        }

        vector<string> result(pq.size());
        for (int i = pq.size() - 1; i >= 0; --i) {
            result[i] = pq.top().second;
            pq.pop();
        }
        return result;
    }
};
        this.prefix += c;
        let node = this.root;
        for (const char of this.prefix) {
            if (!node.children.has(char)) {
                return [];
            }
            node = node.children.get(char);
        }

        const pq = Array.from(node.count.entries()).sort((a, b) => {
            if (b[1] === a[1]) {
                return a[0].localeCompare(b[0]);
            } else {
                return b[1] - a[1];
            }
        });

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

#medium
Задача: 893. Groups of Special-Equivalent Strings

Вам дан массив строк одинаковой длины words. За один ход вы можете поменять местами любые два четных или любые два нечетных символа строки words[i]. Две строки words[i] и words[j] являются специально-эквивалентными, если после любого количества ходов words[i] == words[j].

Например, words[i] = "zzxy" и words[j] = "xyzz" являются специально-эквивалентными, потому что мы можем делать ходы "zzxy" -> "xzzy" -> "xyzz". Группа специально-эквивалентных строк из слов - это непустое подмножество слов, такое, что: каждая пара строк в группе специально-эквивалентна, и группа имеет максимально возможный размер (т.е, не существует строки words[i], не входящей в группу, такой, что words[i] является специально-эквивалентной каждой строке в группе). Верните количество групп специально-эквивалентных строк из слов.

Пример:

Input: words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
Output: 3

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

1⃣Для каждой строки в массиве words создать два новых списка: один из символов на четных позициях, другой из символов на нечетных позициях. Отсортировать оба списка и объединить их в одну строку, которая будет представлять каноническую форму строки.

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

3⃣Размер множества будет равен количеству групп специально-эквивалентных строк.

😎 Решение:

class Solution {
public:
    int numSpecialEquivGroups(vector<string>& words) {
        set<string> uniqueForms;
        
        for (string& word : words) {
            string evenChars, oddChars;
            for (int i = 0; i < word.size(); ++i) {
                if (i % 2 == 0) {
                    evenChars += word[i];
                } else {
                    oddChars += word[i];
                }
            }
            sort(evenChars.begin(), evenChars.end());
            sort(oddChars.begin(), oddChars.end());
            uniqueForms.insert(evenChars + oddChars);
        }
        
        return uniqueForms.size();
    }
};

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

#hard
Задача: 568. Maximum Vacation Days

LeetCode хочет предоставить одному из своих лучших сотрудников возможность путешествовать по n городам для сбора задач по алгоритмам. Однако, как говорится, "делу время, потехе час". Вы можете брать отпуска в некоторых конкретных городах и неделях. Ваша задача — спланировать поездку, чтобы максимально увеличить количество дней отпуска, которые вы сможете взять, соблюдая при этом определенные правила и ограничения.

Правила и ограничения:
Вы можете путешествовать только между n городами, обозначенными индексами от 0 до n-1. Изначально вы находитесь в городе с индексом 0 в понедельник.
Города связаны рейсами. Рейсы представлены матрицей n x n, называемой flights, представляющей статус авиалинии от города i до города j. Если рейса из города i в город j нет, flights[i][j] == 0; иначе flights[i][j] == 1. Также для всех i выполняется flights[i][i] == 0.
У вас есть k недель (каждая неделя состоит из семи дней) для путешествий. Вы можете летать не более одного раза в день и можете летать только утром каждого понедельника. Время полета настолько короткое, что его влияние не учитывается.
Для каждого города у вас есть ограниченные дни отпуска в разные недели, заданные матрицей n x k, называемой days. Значение days[i][j] представляет максимальное количество дней отпуска, которые вы можете взять в городе i на неделе j.
Даны две матрицы flights и days, верните максимальное количество дней отпуска, которые вы можете взять в течение k недель.

Пример:

Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation:
One of the best strategies is:
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day.
(Although you start at city 0, we could also fly to and start at other cities since it is Monday.)
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week : stay at city 2, and play 3 days and work 4 days.
Ans = 6 + 3 + 3 = 12.

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

1⃣Использовать функцию dfs (поиск в глубину), которая возвращает количество отпускных дней, которые можно взять, начиная с текущего города cur_city и текущей недели weekno. В каждом вызове функции проходить по всем городам и находить все города, которые связаны с текущим городом. Такой город обозначен 1 в соответствующей позиции flights[cur_city][i].

2⃣Для текущего города можно либо остаться в нем, либо поехать в связанный город. Обозначим город, в который меняется расположение, как j. После смены города нужно найти количество отпускных дней, которые можно взять, начиная с нового города и с новой недели. Это количество отпускных дней можно представить как: days[j][weekno] + dfs(flights, days, j, weekno + 1).

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

😎 Решение:

class Solution {
public:
    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
        int n = flights.size(), k = days[0].size();
        vector<vector<int>> memo(n, vector<int>(k, -1));
        return dfs(flights, days, memo, 0, 0);
    }

private:
    int dfs(vector<vector<int>>& flights, vector<vector<int>>& days, vector<vector<int>>& memo, int curCity, int weekNo) {
        int n = flights.size(), k = days[0].size();
        if (weekNo == k) return 0;
        if (memo[curCity][weekNo] != -1) return memo[curCity][weekNo];
        int maxVac = 0;
        for (int nextCity = 0; nextCity < n; nextCity++) {
            if (curCity == nextCity || flights[curCity][nextCity] == 1) {
                maxVac = max(maxVac, days[nextCity][weekNo] + dfs(flights, days, memo, nextCity, weekNo + 1));
            }
        }
        memo[curCity][weekNo] = maxVac;
        return maxVac;
    }
};

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

#easy
Задача: 643. Maximum Average Subarray I

Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.

Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000

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

1⃣Инициализация скользящего окна: Вычислите сумму первых k элементов массива nums. Это будет начальное значение максимальной суммы.
2⃣Перемещение окна: Перемещайте окно длиной k по массиву, добавляя следующий элемент и убирая предыдущий, чтобы поддерживать сумму текущего окна.
3⃣Обновление максимальной суммы: На каждом шаге обновляйте максимальную сумму, если текущая сумма больше, и в конце верните среднее значение этой суммы.

😎 Решение:

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int currentSum = accumulate(nums.begin(), nums.begin() + k, 0);
        int maxSum = currentSum;
        
        for (int i = k; i < nums.size(); i++) {
            currentSum += nums[i] - nums[i - k];
            maxSum = max(maxSum, currentSum);
        }
        
        return (double) maxSum / k;
    }
};

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