Задача: 346. Moving Average from Data Stream
Сложность: easy

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

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

MovingAverage(int size) Инициализирует объект с размером окна size.
double next(int val) Возвращает скользящее среднее последних size значений потока.

Пример:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

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

1⃣Инициализация:
Инициализируйте объект с фиксированным размером окна size.
Используйте очередь или список для хранения значений в текущем окне.
Храните текущую сумму значений в окне.

2⃣Добавление нового значения:
Добавьте новое значение в очередь.
Обновите текущую сумму, добавив новое значение.
Если размер очереди превышает size, удалите самое старое значение и обновите сумму, вычтя это значение.

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

😎 Решение:

#include <queue>

class MovingAverage {
public:
    MovingAverage(int size) : size(size), sum(0) {}
    
    double next(int val) {
        q.push(val);
        sum += val;
        if (q.size() > size) {
            sum -= q.front();
            q.pop();
        }
        return (double) sum / q.size();
    }
    
private:
    int size;
    std::queue<int> q;
    int sum;
};

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

Задача: 461. Hamming Distance
Сложность: easy

Расстояние Хэмминга между двумя целыми числами — это количество позиций, в которых соответствующие биты различны.
Даны два целых числа x и y, верните расстояние Хэмминга между ними.

Пример:

Input: x = 3, y = 1
Output: 1

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

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

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

3⃣Пошаговый подсчет битов:
Выполните побитовое XOR между x и y.
Инициализируйте счетчик bitCount = 0.
Пока число не равно нулю:
Если текущий бит равен 1, увеличьте bitCount.
Сдвиньте число вправо на один бит.
Возвращайте bitCount.

😎 Решение:

class Solution {
public:
    int hammingDistance(int x, int y) {
        return __builtin_popcount(x ^ y);
    }
};

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

Задача: 898. Bitwise ORs of Subarrays
Сложность: medium

Если задан целочисленный массив arr, верните количество различных побитовых ИЛИ всех непустых подмассивов arr. Побитовое ИЛИ подмассива - это побитовое ИЛИ каждого целого числа в подмассиве. Побитовым ИЛИ подмассива одного целого числа является это целое число. Подмассив - это непрерывная непустая последовательность элементов в массиве.

Пример:

Input: arr = [0]
Output: 1

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

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

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

3⃣Вернуть размер множества.

😎 Решение:

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& arr) {
        unordered_set<int> result, current, next;
        for (int num : arr) {
            next = {num};
            for (int x : current) {
                next.insert(x | num);
            }
            current = next;
            result.insert(current.begin(), current.end());
        }
        return result.size();
    }
};

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

Задача: 981. Time Based Key-Value Store
Сложность: medium

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

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

TimeMap() Инициализирует объект структуры данных.
void set(String key, String value, int timestamp) Сохраняет ключ key с значением value в заданное время timestamp.
String get(String key, int timestamp) Возвращает значение, такое что set был вызван ранее с timestamp_prev <= timestamp. Если таких значений несколько, возвращается значение, связанное с наибольшим timestamp_prev. Если значений нет, возвращается "".

Пример:

Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]

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

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

2⃣В функции set() сохраните значение в позиции timestamp в корзине ключа keyTimeMap, т.е. keyTimeMap[key][timestamp] = value.

3⃣В функции get() итерируйтесь по всем временам в порядке убывания от timestamp до 1. Для любого времени во время итерации, если существует значение в корзине ключа, верните это значение. В противном случае, в конце верните пустую строку.

😎 Решение:

#include <unordered_map>
#include <string>

class TimeMap {
public:
    std::unordered_map<std::string, std::unordered_map<int, std::string>> keyTimeMap;

    TimeMap() {}

    void set(const std::string& key, const std::string& value, int timestamp) {
        keyTimeMap[key][timestamp] = value;
    }

    std::string get(const std::string& key, int timestamp) {
        if (!keyTimeMap.count(key)) {
            return "";
        }

        for (int currTime = timestamp; currTime >= 1; --currTime) {
            if (keyTimeMap[key].count(currTime)) {
                return keyTimeMap[key][currTime];
            }
        }

        return "";
    }
};

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

Задача: 295. Find Median from Data Stream
Сложность: hard

Пример:

Input: ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
Output: [null, null, null, 1.5, null, 2.0]

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

1⃣Используйте две кучи: max-heap (left) для хранения меньшей половины элементов и min-heap (right) для хранения большей половины. Это позволяет находить медиану за O(1) и вставлять за O(log n).

2⃣При добавлении числа:
Если left пуст или num <= top(left), добавьте его в left.
Иначе добавьте его в right.
После добавления сбалансируйте размеры куч: если одна куча больше другой более чем на 1 элемент, переместите элемент из большей в меньшую.

3⃣Для вычисления медианы:
Если размеры куч равны, верните среднее двух верхних элементов.
Если одна куча больше, верните её верхний элемент как медиану.

😎 Решение:

#include <queue>

class MedianFinder {
private:
    priority_queue<int> left; // max-heap
    priority_queue<int, vector<int>, greater<int>> right; // min-heap

public:
    MedianFinder() {}

    void addNum(int num) {
        if (left.empty() || num <= left.top()) {
            left.push(num);
        } else {
            right.push(num);
        }

        if (left.size() > right.size() + 1) {
            right.push(left.top());
            left.pop();
        } else if (right.size() > left.size()) {
            left.push(right.top());
            right.pop();
        }
    }

    double findMedian() {
        if (left.size() == right.size()) {
            return (left.top() + right.top()) / 2.0;
        } else {
            return left.top();
        }
    }
};

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

Задача: 1402. Reducing Dishes
Сложность: hard

Шеф-повар собрал данные об уровне удовлетворенности от своих n блюд. Шеф может приготовить любое блюдо за 1 единицу времени.

Коэффициент удовольствия от блюда определяется как время, затраченное на приготовление этого блюда вместе с предыдущими блюдами, умноженное на уровень удовлетворенности от этого блюда, то есть time[i] * satisfaction[i].

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

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

Пример:

Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.

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

1⃣Отсортируйте массив satisfaction в порядке возрастания.

2⃣Создайте таблицу мемоизации memo размером N x N и инициализируйте все значения -1, что будет означать, что ответ для всех состояний еще не рассчитан.

3⃣Реализуйте функцию, которая вызывается с параметрами index = 0 и time = 1, чтобы найти ответ: Если достигнут конец массива, т.е. index == satisfaction.length, верните 0, так как больше нет блюд для приготовления и нельзя получить дополнительное значение. Если значение в массиве memo для пары {index, time} не равно -1, верните это значение, так как это подразумевает, что данная подзадача уже была решена; поэтому рекурсивный вызов не требуется, и можно вернуть сохраненное значение из таблицы memo. Рассчитайте максимум из двух вариантов: добавьте значение коэффициента для данного блюда satisfaction[index] * time к рекурсивному результату с index = index + 1 и time = time + 1. Пропустите текущее блюдо и сделайте рекурсивный вызов для index = index + 1 и time = time.

😎 Решение:

class Solution {
public:
    int findMaxSatisfaction(vector<int>& satisfaction, vector<vector<int>>& memo, int index, int time) {
        if (index == satisfaction.size()) return 0;
        if (memo[index][time] != -1) return memo[index][time];

        return memo[index][time] = max(satisfaction[index] * time + findMaxSatisfaction(satisfaction, memo, index + 1, time + 1),
                                       findMaxSatisfaction(satisfaction, memo, index + 1, time));
    }

    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.begin(), satisfaction.end());
        vector<vector<int>> memo(satisfaction.size() + 1, vector<int>(satisfaction.size() + 1, -1));
        return findMaxSatisfaction(satisfaction, memo, 0, 1);
    }
};

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

Задача: 297. Serialize and Deserialize Binary Tree
Сложность: hard

Пример:

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

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

1⃣Сериализация дерева
Обход в порядке префикс (root → left → right).
Если узел пустой, записываем "null,", иначе — значение узла и рекурсивно сериализуем левое и правое поддерево.

2⃣Десериализация строки
Разбиваем строку по запятой и преобразуем в массив.
Рекурсивно создаём дерево, доставая элементы из начала массива. Если встречается "null" — возвращаем nullptr.

3⃣Обратимость
Алгоритм гарантирует, что deserialize(serialize(root)) восстановит дерево без потерь.

😎 Решение:

#include <string>
#include <sstream>
#include <vector>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Codec {
public:
    void rserialize(TreeNode* root, std::string& str) {
        if (root == nullptr) {
            str += "null,";
        } else {
            str += std::to_string(root->val) + ",";
            rserialize(root->left, str);
            rserialize(root->right, str);
        }
    }

    std::string serialize(TreeNode* root) {
        std::string str;
        rserialize(root, str);
        return str;
    }

    TreeNode* rdeserialize(std::vector<std::string>& data) {
        if (data[0] == "null") {
            data.erase(data.begin());
            return nullptr;
        }

        TreeNode* root = new TreeNode(std::stoi(data[0]));
        data.erase(data.begin());
        root->left = rdeserialize(data);
        root->right = rdeserialize(data);
        return root;
    }

    TreeNode* deserialize(std::string data) {
        std::vector<std::string> dataArray;
        std::string item;
        std::istringstream ss(data);
        while (std::getline(ss, item, ',')) {
            dataArray.push_back(item);
        }
        return rdeserialize(dataArray);
    }
};

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

Задача: 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;
    }
};

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