Задача: 209. Minimum Size Subarray Sum
Сложность: medium

Дан массив положительных целых чисел nums и целое число target.
Нужно найти минимальную длину подмассива, сумма которого больше или равна target.
Если такого подмассива не существует — вернуть 0.

Пример:

Input: target = 7, nums = [2,3,1,2,4,3] Output: 2
Пояснение: минимальный подмассив — [4,3]

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

1⃣Инициализация указателей и суммы окна:
Установим left = 0, sum = 0, res = INT_MAX. Указатели left и right формируют окно подмассива.

2⃣Проход по массиву (движение правого указателя):
На каждом шаге прибавляем nums[right] к текущей сумме.
Если sum >= target, пробуем сузить окно слева (двигаем left) и обновляем res.

3⃣Возврат ответа:
Если res не изменился — возвращаем 0, иначе — res.

😎 Решение:

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0, sumOfCurrentWindow = 0;
        int res = INT_MAX;

        for(right = 0; right < nums.size(); right++) {
            sumOfCurrentWindow += nums[right];

            while (sumOfCurrentWindow >= target) {
                res = min(res, right - left + 1);
                sumOfCurrentWindow -= nums[left];
                left++;
            }
        }

        return res == INT_MAX ? 0 : res;
    }
};

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

Задача: 1135. Connecting Cities With Minimum Cost
Сложность: medium

Есть n городов, пронумерованных от 1 до n. Вам даны целое число n и массив connections, где connections[i] = [xi, yi, costi] указывает, что стоимость соединения города xi и города yi (двунаправленное соединение) равна costi.

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

Стоимость - это сумма использованных стоимостей соединений.

Пример:

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.

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

1⃣Сортировка рёбер:
Отсортируйте все соединения (рёбра) в графе по их весам (стоимости) в порядке возрастания.

2⃣Итерация по рёбрам и объединение:
Используйте структуру данных Disjoint Set (Union-Find) для проверки циклов и объединения поддеревьев. Для каждого ребра проверьте, принадлежат ли его концы разным поддеревьям, и если да, объедините их, добавив ребро в минимальное остовное дерево (MST).

3⃣Проверка соединённости:
Подсчитайте количество рёбер в MST. Если оно меньше n-1, верните -1, так как соединить все города невозможно. Иначе верните суммарную стоимость рёбер в MST.

😎 Решение:

class DisjointSet {
    vector<int> parent;
public:
    DisjointSet(int n) : parent(n + 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }
};

class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& connections) {
        sort(connections.begin(), connections.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[2] < b[2];
        });

        DisjointSet disjointSet(n);
        int totalCost = 0;
        int edgesUsed = 0;

        for (const auto& connection : connections) {
            int x = connection[0];
            int y = connection[1];
            int cost = connection[2];

            if (disjointSet.find(x) != disjointSet.find(y)) {
                disjointSet.unionSet(x, y);
                totalCost += cost;
                edgesUsed++;
                if (edgesUsed == n - 1) {
                    return totalCost;
                }
            }
        }
        return edgesUsed == n - 1 ? totalCost : -1;
    }
};

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

Задача: 377. Combination Sum IV
Сложность: medium

Дан массив различных целых чисел nums и целое число target. Верните количество возможных комбинаций, которые в сумме дают target.

Тестовые случаи сгенерированы так, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [9], target = 3
Output: 0

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

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

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

3⃣Здесь, соответственно, мы определяем рекурсивную функцию под названием combs(remain), которая возвращает количество комбинаций, где каждая комбинация в сумме дает значение remain.

😎 Решение:

#include <vector>
#include <unordered_map>

class Solution {
private:
    std::unordered_map<int, int> memo;

public:
    int combinationSum4(std::vector<int>& nums, int target) {
        return combs(nums, target);
    }

private:
    int combs(std::vector<int>& nums, int remain) {
        if (remain == 0)
            return 1;
        if (memo.find(remain) != memo.end())
            return memo[remain];

        int result = 0;
        for (int num : nums) {
            if (remain - num >= 0)
                result += combs(nums, remain - num);
        }
        memo[remain] = result;
        return result;
    }
};

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

Задача: 328. Odd Even Linked List
Сложность: medium

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

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

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

Вы должны решить задачу с дополнительной сложностью по памяти O(1) и временной сложностью O(n).

Пример:

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

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

1⃣Инициализация указателей:
Создайте указатели odd и even для работы с нечетными и четными узлами, соответственно. Инициализируйте odd началом списка head, а even — следующим узлом head.next. Также создайте указатель evenHead для сохранения начала четного списка.

2⃣Разделение списка:
Используйте цикл для прохождения списка, перенаправляя нечетные узлы в oddList, а четные узлы в evenList. Обновляйте указатели odd и even в процессе итерации.

3⃣Соединение списков:
После окончания цикла соедините конец нечетного списка с началом четного списка, используя указатель evenHead.

😎 Решение:

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head) return nullptr;
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenHead = even;
        
        while (even && even->next) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};

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

Задача: 106. Construct Binary Tree from Inorder and Postorder Traversal
Сложность: medium

Даны два массива целых чисел: inorder и postorder, где inorder — это результат обхода в глубину слева направо, а postorder — результат обхода после обработки всех потомков узла. Постройте и верните бинарное дерево.

Пример:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] Output: [3,9,20,null,null,15,7]

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

1⃣Создайте хэш-таблицу (unordered_map), где ключ — значение из inorder, а значение — его индекс. Это нужно для быстрого поиска позиции корня.

2⃣Реализуйте рекурсивную функцию helper, принимающую левую и правую границы inorder. Если in_left > in_right, возвращаем nullptr.

3⃣Последний элемент в postorder — это текущий корень. Найдите его индекс в inorder. Рекурсивно постройте сначала правое поддерево, затем левое, и верните текущий корень.

😎 Решение:

class Solution {
    int post_idx;
    vector<int> postorder;
    vector<int> inorder;
    unordered_map<int, int> idx_map;

public:
    TreeNode* helper(int in_left, int in_right) {
        if (in_left > in_right) return NULL;
        
        int root_val = postorder[post_idx];
        TreeNode* root = new TreeNode(root_val);
        
        int index = idx_map[root_val];
        post_idx--;
        
        root->right = helper(index + 1, in_right);
        root->left = helper(in_left, index - 1);
        
        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        this->postorder = postorder;
        this->inorder = inorder;
        post_idx = postorder.size() - 1;

        int idx = 0;
        for (int val : inorder) {
            idx_map[val] = idx++;
        }

        return helper(0, inorder.size() - 1);
    }
};

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

Задача: 758. Bold Words in String
Сложность: medium

При наличии массива ключевых слов и строки a выделите все ключевые слова [i] жирным шрифтом. Все буквы между тегами <b> и </b> выделяются жирным шрифтом.

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

Пример:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"

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

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

2⃣Пройдите по каждому ключевому слову и отметьте соответствующие позиции в массиве флагов.

3⃣Постройте результирующую строку, добавляя теги <b> и </b> на основе массива флагов.

😎 Решение:

class Solution {
public:
    string addBoldTags(vector<string>& keywords, string s) {
        int n = s.size();
        vector<bool> bold(n, false);
        
        for (const string& word : keywords) {
            int start = s.find(word);
            while (start != string::npos) {
                for (int i = start; i < start + word.size(); i++) {
                    bold[i] = true;
                }
                start = s.find(word, start + 1);
            }
        }
        
        string result;
        int i = 0;
        while (i < n) {
            if (bold[i]) {
                result += "<b>";
                while (i < n && bold[i]) {
                    result += s[i];
                    i++;
                }
                result += "</b>";
            } else {
                result += s[i];
                i++;
            }
        }
        
        return result;
    }
};

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

Задача: 490. The Maze
Сложность: medium

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

Дан лабиринт размером m x n, начальная позиция шара и место назначения, где start = [startrow, startcol] и destination = [destinationrow, destinationcol]. Верните true, если шар может остановиться в месте назначения, иначе верните false.
Вы можете предположить, что границы лабиринта представляют собой стены. В приведённом ниже примере они не указаны.

Пример:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.

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

1⃣Инициализация и подготовка данных
Определите количество строк и столбцов в лабиринте (m и n). Создайте 2D массив visit для отслеживания посещённых ячеек. Запустите DFS (глубокий поиск) с начальной позиции.

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

3⃣Результат
Если любой вызов DFS возвращает true, завершите выполнение и верните true. Если ни один путь не приводит к цели, верните false.

😎 Решение:

class Solution {
public:
    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        int m = maze.size(), n = maze[0].size();
        vector<vector<bool>> visit(m, vector<bool>(n, false));
        return dfs(m, n, maze, start, destination, visit);
    }

private:
    vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    bool dfs(int m, int n, vector<vector<int>>& maze, vector<int>& curr, vector<int>& destination, vector<vector<bool>>& visit) {
        if (visit[curr[0]][curr[1]]) return false;
        if (curr == destination) return true;
        visit[curr[0]][curr[1]] = true;
        for (auto [dx, dy] : directions) {
            int r = curr[0], c = curr[1];
            while (r >= 0 && r < m && c >= 0 && c < n && maze[r][c] == 0) {
                r += dx;
                c += dy;
            }
            vector<int> newCurr = {r - dx, c - dy};
            if (dfs(m, n, maze, newCurr, destination, visit)) return true;
        }
        return false;
    }
};

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

Задача: 645. Set Mismatch
Сложность: easy

У вас есть набор целых чисел s, который изначально содержит все числа от 1 до n. К сожалению, из-за какой-то ошибки одно из чисел в s продублировалось в другое число в наборе, что привело к повторению одного числа и потере другого. Вам дан целочисленный массив nums, представляющий состояние данных в этом наборе после ошибки. Найдите число, которое встречается дважды, и число, которое отсутствует, и верните их в виде массива.

Пример:

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

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

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

2⃣Определите отсутствующее число, используя сумму чисел от 1 до n и текущую сумму массива.

3⃣Верните дублированное и отсутствующее числа в виде массива.

😎 Решение:

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        unordered_set<int> numSet;
        int duplicate = -1;
        for (int num : nums) {
            if (!numSet.insert(num).second) {
                duplicate = num;
            }
        }
        int missing = (n * (n + 1)) / 2 - accumulate(numSet.begin(), numSet.end(), 0);
        return {duplicate, missing};
    }
};

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

Задача: 1168. Optimize Water Distribution in a Village
Сложность: hard

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

Для каждого дома i мы можем либо построить колодец внутри него непосредственно с затратами wells[i - 1] (обратите внимание на -1 из-за нумерации с нуля), либо провести воду из другого колодца с помощью трубы. Затраты на прокладку труб между домами даны в массиве pipes, где каждый pipes[j] = [house1j, house2j, costj] представляет собой стоимость соединения дома house1j и дома house2j с помощью трубы. Соединения двунаправленные, и между одними и теми же домами могут быть несколько допустимых соединений с разными затратами.

Верните минимальные оhttps://leetcode.com/problems/optimize-water-distribution-in-a-village/Figures/1168/PrimAlgDemo.gifбщие затраты на обеспечение всех домов водой.

Пример:

Input: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
Output: 3
Explanation: The image shows the costs of connecting houses using pipes.
The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.

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

1⃣Представление графа: Постройте список смежности для представления графа, где вершины и ребра соответствуют домам и трубам. Список смежности можно представить в виде списка списков или словаря списков.

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

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

😎 Решение:

class Solution {
public:
    int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> edgesHeap;
        vector<vector<pair<int, int>>> graph(n + 1);
        
        for (int i = 0; i < wells.size(); ++i) {
            graph[0].emplace_back(wells[i], i + 1);
            edgesHeap.emplace(wells[i], i + 1);
        }
        
        for (const auto& pipe : pipes) {
            int house1 = pipe[0], house2 = pipe[1], cost = pipe[2];
            graph[house1].emplace_back(cost, house2);
            graph[house2].emplace_back(cost, house1);
        }
        
        unordered_set<int> mstSet{0};
        int totalCost = 0;
        
        while (mstSet.size() < n + 1) {
            auto [cost, nextHouse] = edgesHeap.top(); edgesHeap.pop();
            if (mstSet.count(nextHouse)) continue;
            mstSet.insert(nextHouse);
            totalCost += cost;
            for (const auto& [nextCost, neighbor] : graph[nextHouse]) {
                if (!mstSet.count(neighbor)) {
                    edgesHeap.emplace(nextCost, neighbor);
                }
            }
        }
        
        return totalCost;
    }
};

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

class Solution {
public:
    int repeatedStringMatch(string A, string B) {
        int q = 1;
        string S = A;
        while (S.length() < B.length()) {
            S += A;
            q++;
        }
        if (S.find(B) != string::npos) return q;
        if ((S + A).find(B) != string::npos) return q + 1;
        return -1;
    }
};

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

Задача: 478. Generate Random Point in a Circle
Сложность: medium

Дан радиус и положение центра окружности, реализуйте функцию randPoint, которая генерирует равномерно случайную точку внутри окружности.
Реализуйте класс Solution:
- Solution(double radius, double x_center, double y_center) инициализирует объект с радиусом окружности radius и положением центра (x_center, y_center).
- randPoint() возвращает случайную точку внутри окружности. Точка на окружности считается находящейся внутри окружности. Ответ возвращается в виде массива [x, y].

Пример:

Input
["Solution", "randPoint", "randPoint", "randPoint"]
[[1.0, 0.0, 0.0], [], [], []]
Output
[null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]

Explanation
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint(); // return [-0.02493, -0.38077]
solution.randPoint(); // return [0.82314, 0.38945]
solution.randPoint(); // return [0.36572, 0.17248]

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

1⃣ Генерируем равномерно случайные точки в квадрате S с длиной стороны 2R.

2⃣ Сохраняем все точки, которые находятся на расстоянии не более R от центра, и отклоняем все, которые дальше этого расстояния.

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

😎 Решение:

#include <cmath>
#include <cstdlib>
#include <vector>

class Solution {
    double rad, xc, yc;

public:
    Solution(double radius, double x_center, double y_center) : rad(radius), xc(x_center), yc(y_center) {}

    std::vector<double> randPoint() {
        double x0 = xc - rad;
        double y0 = yc - rad;

        while (true) {
            double xg = x0 + static_cast<double>(rand()) / RAND_MAX * rad * 2;
            double yg = y0 + static_cast<double>(rand()) / RAND_MAX * rad * 2;
            if (sqrt(pow(xg - xc, 2) + pow(yg - yc, 2)) <= rad) {
                return {xg, yg};
            }
        }
    }
};

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

Задача: 41. First Missing Positive
Сложность: hard

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

Пример:

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

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

1⃣Перебрать массив и попытаться разместить каждое число в правильной позиции: nums[i] должен быть равен i + 1

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

3⃣После расстановки — находим первый индекс, где nums[i] != i + 1. Возвращаем i + 1

😎 Решение:

int firstMissingPositive(std::vector<int>& nums) {
    for (int i = 0; i < nums.size(); ) {
        if (nums[i] <= 0 || nums[i] > nums.size()) {
            ++i;
            continue;
        }
        if (nums[i] == i + 1) {
            ++i;
            continue;
        }
        int j = nums[i];
        if (nums[j - 1] == nums[i]) {
            ++i;
            continue;
        }
        std::swap(nums[j - 1], nums[i]);
    }

    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }

    return nums.size() + 1;
}

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

Задача: 901. Online Stock Span
Сложность: medium

Разработайте алгоритм, который собирает ежедневные котировки цен на некоторые акции и возвращает размах цены этой акции за текущий день. Размах цены акции за один день - это максимальное количество дней подряд (начиная с этого дня и в обратном направлении), в течение которых цена акции была меньше или равна цене этого дня.

Например, если цены акции за последние четыре дня равны [7,2,1,2], а цена акции сегодня равна 2, то размах сегодняшнего дня равен 4, поскольку, начиная с сегодняшнего дня, цена акции была меньше или равна 2 в течение 4 дней подряд.
Также, если цена акции за последние четыре дня равна [7,34,1,2], а цена акции сегодня равна 8, то размах сегодняшнего дня равен 3, так как начиная с сегодняшнего дня цена акции была меньше или равна 8 в течение 3 дней подряд. Реализация класса StockSpanner: StockSpanner() Инициализирует объект класса. int next(int price) Возвращает размах цены акции, учитывая, что сегодняшняя цена равна price.

Пример:

Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]

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

1⃣Инициализировать стек для хранения пар значений (цена, размах) и переменную для текущего индекса.

2⃣Для метода next:
Установить начальный размах текущего дня равным 1.
Пока стек не пуст и верхний элемент стека имеет цену меньше или равную текущей цене:
Добавить размах верхнего элемента стека к текущему размаху.
Удалить верхний элемент стека.

3⃣Добавить текущую цену и размах на вершину стека.
Вернуть текущий размах.

😎 Решение:

class StockSpanner {
    stack<pair<int, int>> stk;

public:
    StockSpanner() {}

    int next(int price) {
        int span = 1;
        while (!stk.empty() && stk.top().first <= price) {
            span += stk.top().second;
            stk.pop();
        }
        stk.push({price, span});
        return span;
    }
};

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

Задача: 82. Remove Duplicates from Sorted List II
Сложность: medium

Дан head — начало отсортированного связного списка.
Удалите все узлы, содержащие повторяющиеся числа,
оставив только уникальные значения.
Верните отсортированный список без дубликатов.

Пример:

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

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

1⃣Создаем фиктивный узел sentinel, указывающий на head, и инициализируем указатель pred, который всегда указывает на последний узел перед группой дубликатов.

2⃣Проходим по списку: если текущий узел и следующий имеют одинаковое значение — пропускаем все такие узлы и связываем pred->next с первым уникальным после них.

3⃣Если текущий элемент не дублируется — просто передвигаем pred и продолжаем проход

😎 Решение:

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* sentinel = new ListNode(0, head);
        ListNode* pred = sentinel;
        while (head != NULL) {
            if (head->next != NULL && head->val == head->next->val) {
                while (head->next != NULL && head->val == head->next->val) {
                    head = head->next;
                }
                pred->next = head->next;
            } else {
                pred = pred->next;
            }
            head = head->next;
        }
        return sentinel->next;
    }
};

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

Задача: 499. The Maze III
Сложность: hard

В лабиринте есть мячик с пустыми пространствами (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".

😎 Решение:

#include <vector>
#include <queue>
#include <string>
#include <functional>

using namespace std;

struct State {
    int row, col, dist;
    string path;
    bool operator>(const State& other) const {
        return dist == other.dist ? path > other.path : dist > other.dist;
    }
};

class Solution {
public:
    string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
        int m = maze.size(), n = maze[0].size();
        vector<vector<int>> directions = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
        vector<string> textDirections = {"l", "u", "r", "d"};
        priority_queue<State, vector<State>, greater<State>> heap;
        vector<vector<bool>> seen(m, vector<bool>(n));
        heap.push({ball[0], ball[1], 0, ""});
        
        while (!heap.empty()) {
            auto [row, col, dist, path] = heap.top(); heap.pop();
            if (seen[row][col]) continue;
            if (row == hole[0] && col == hole[1]) return path;
            seen[row][col] = true;
            
            for (int i = 0; i < 4; ++i) {
                int r = row, c = col, d = 0;
                while (valid(r + directions[i][0], c + directions[i][1], maze)) {
                    r += directions[i][0]; c += directions[i][1]; d++;
                    if (r == hole[0] && c == hole[1]) break;
                }
                heap.push({r, c, dist + d, path + textDirections[i]});
            }
        }
        return "impossible";
    }
    
    bool valid(int row, int col, vector<vector<int>>& maze) {
        return row >= 0 && row < maze.size() && col >= 0 && col < maze[0].size() && maze[row][col] == 0;
    }
};

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

Задача: 1518. Water Bottles
Сложность: easy

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

Операция питья полной бутылки воды превращает её в пустую бутылку.

Даны два целых числа numBottles и numExchange. Верните максимальное количество бутылок с водой, которые вы можете выпить.

Пример:

Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

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

1⃣Инициализируйте переменную ответа consumedBottles значением 0.

2⃣Продолжайте выполнять следующие действия, пока количество numBottles больше или равно numExchange:
— Выпейте numExchange количество полных бутылок, т.е. добавьте numExchange к consumedBottles.
— Уменьшите numExchange от доступных полных бутылок numBottles.
— Обменяйте пустые бутылки на одну полную бутылку, т.е. увеличьте numBottles на одну.

3⃣Верните consumedBottles + numBottles.

😎 Решение:

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        int consumedBottles = 0;

        while (numBottles >= numExchange) {
            consumedBottles += numExchange;
            numBottles -= numExchange;
            numBottles++;
        }

        return consumedBottles + numBottles;
    }
};

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

Задача: 1482. Minimum Number of Days to Make m Bouquets
Сложность: medium

Вам дан массив целых чисел bloomDay, целое число m и целое число k.

Вам нужно сделать m букетов. Для создания букета необходимо использовать k соседних цветов из сада.
Сад состоит из n цветов, i-й цветок расцветет на bloomDay[i] и затем может быть использован ровно в одном букете.

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

Пример:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

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

1⃣Инициализация:
Инициализируйте start как 0 и end как максимальное значение в массиве bloomDay.
Введите вспомогательную функцию getNumOfBouquets для подсчета количества букетов, которые можно сделать на определенный день.

2⃣Поиск минимального числа дней:
Выполняйте бинарный поиск, пока start меньше или равен end:
- рассчитайте mid как среднее значение между start и end.
- используйте getNumOfBouquets, чтобы определить, сколько букетов можно сделать на mid день.
- если количество букетов больше или равно m, сохраните mid как возможное решение и переместите end влево.
- иначе переместите start вправо.

3⃣Возвращение результата:
Верните найденное минимальное количество дней или -1, если сделать m букетов невозможно.

😎 Решение:

class Solution {
private:
    int getNumOfBouquets(vector<int>& bloomDay, int mid, int k) {
        int numOfBouquets = 0, count = 0;
        for (int day : bloomDay) {
            if (day <= mid) {
                count++;
            } else {
                count = 0;
            }
            if (count == k) {
                numOfBouquets++;
                count = 0;
            }
        }
        return numOfBouquets;
    }

public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        if (bloomDay.size() < m * k) return -1;
        int start = 0, end = *max_element(bloomDay.begin(), bloomDay.end());
        int minDays = -1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (getNumOfBouquets(bloomDay, mid, k) >= m) {
                minDays = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return minDays;
    }
};

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

Задача: 583. Delete Operation for Two Strings
Сложность: medium

Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми.
На одном шаге можно удалить ровно один символ в любой строке.

Пример:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

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

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

2⃣ Заполнение массива:
Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки.

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

😎 Решение:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<int> dp(n + 1, 0);

        for (int i = 0; i <= m; ++i) {
            vector<int> temp(n + 1, 0);
            for (int j = 0; j <= n; ++j) {
                if (i == 0 || j == 0) {
                    temp[j] = i + j;
                } else if (word1[i - 1] == word2[j - 1]) {
                    temp[j] = dp[j - 1];
                } else {
                    temp[j] = 1 + min(dp[j], temp[j - 1]);
                }
            }
            dp = temp;
        }

        return dp[n];
    }
};

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

Задача: 1416. Restore The Array
Сложность: hard

Программа должна была напечатать массив целых чисел. Программа забыла напечатать пробелы, и массив напечатан как строка цифр s, и всё, что мы знаем, это что все числа в массиве были в диапазоне [1, k] и в массиве нет ведущих нулей.

Учитывая строку s и целое число k, верните количество возможных массивов, которые могут быть напечатаны как s с использованием упомянутой программы. Так как ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]

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

1⃣Создать массив dp размера m + 1, чтобы хранить значения dfs(x).

2⃣Для получения значения dfs(start), если dp[start] не равно нулю, вернуть его значение. Иначе:
Если s[start] == 0, вернуть 0.
Если start = m, вернуть 1.
Инициализировать count = 0, чтобы считать количество возможных массивов.
Перебрать все возможные конечные индексы end, и если s[start ~ end] представляет допустимое число, продолжить рекурсивный вызов dfs(end + 1) и обновить count как count += dfs(end + 1).
Обновить dp[start] значением dfs(start).

3⃣Вернуть dfs(0).

😎 Решение:

class Solution {
public:
    int mod = 1_000_000_007;

    int dfs(vector<int>& dp, int start, const string& s, int k) {
        if (dp[start] != 0) return dp[start];
        if (start == s.size()) return 1;
        if (s[start] == '0') return 0;

        long count = 0;
        for (int end = start; end < s.size(); ++end) {
            string currNumber = s.substr(start, end - start + 1);
            if (stol(currNumber) > k) break;
            count = (count + dfs(dp, end + 1, s, k)) % mod;
        }

        dp[start] = count;
        return count;
    }

    int numberOfArrays(string s, int k) {
        vector<int> dp(s.size() + 1);
        return dfs(dp, 0, s, k);
    }
};

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

Задача: 540. Single Element in a Sorted Array
Сложность: medium

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

Пример:

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

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

1⃣Начиная с первого элемента, итерируемся через каждый второй элемент, проверяя, является ли следующий элемент таким же, как текущий. Если нет, то текущий элемент — это искомый элемент.

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

3⃣Возвращаем найденный элемент.

😎 Решение:

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        for (int i = 0; i < nums.size() - 1; i += 2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums.back();
    }
};

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