Задача: 210. Course Schedule II
Сложность: medium

Дано число numCourses и список пар prerequisites, где каждая пара [a, b] означает: чтобы взять курс a, нужно сначала пройти курс b.
Верните один из возможных порядков прохождения курсов.
Если пройти все курсы невозможно (из-за циклов) — верните пустой массив.

Пример:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3]

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

1⃣Построение графа и подготовка к DFS
Создаем список смежности adjList, где adjList[b] содержит все курсы, зависящие от b.
Каждый курс помечаем цветом:
WHITE = 1 — не посещён
GRAY = 2 — в процессе обработки
BLACK = 3 — полностью обработан

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

3⃣Формирование ответа
После завершения DFS по всем узлам формируем порядок курсов из стека (или массива) topologicalOrder, инвертируя его.

😎Решение:

cppКопироватьРедактироватьclass Solution {
public:
    int WHITE = 1;
    int GRAY = 2;
    int BLACK = 3;

    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        bool isPossible = true;
        map<int, int> color;
        map<int, vector<int>> adjList;
        vector<int> topologicalOrder;

        for (int i = 0; i < numCourses; i++) color[i] = WHITE;

        for (vector<int> relation : prerequisites) {
            int dest = relation[0];
            int src = relation[1];
            adjList[src].push_back(dest);
        }

        for (int i = 0; i < numCourses && isPossible; i++) {
            if (color[i] == WHITE) {
                dfs(i, color, adjList, isPossible, topologicalOrder);
            }
        }

        vector<int> order;
        if (isPossible) {
            order.resize(numCourses);
            for (int i = 0; i < numCourses; i++) {
                order[i] = topologicalOrder[numCourses - i - 1];
            }
        }
        return order;
    }

    void dfs(int node, map<int, int>& color, map<int, vector<int>>& adjList,
             bool& isPossible, vector<int>& topologicalOrder) {
        if (!isPossible) return;
        color[node] = GRAY;

        for (int neighbor : adjList[node]) {
            if (color[neighbor] == WHITE) {
                dfs(neighbor, color, adjList, isPossible, topologicalOrder);
            } else if (color[neighbor] == GRAY) {
                isPossible = false;
            }
        }

        color[node] = BLACK;
        topologicalOrder.push_back(node);
    }
};

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

Задача: 1199. Minimum Time to Build Blocks
Сложность: hard

Вам дан список блоков, где blocks[i] = t означает, что на строительство i-го блока требуется t единиц времени. Блок может быть построен только одним рабочим.
Рабочий может либо разделиться на двух рабочих (количество рабочих увеличивается на одного), либо построить блок и уйти домой. Оба решения требуют некоторого времени.
Время, затраченное на разделение одного рабочего на двух, задано целым числом split. Обратите внимание, что если два рабочих разделяются одновременно, они разделяются параллельно, поэтому затраты времени будут равны split.

Выведите минимальное время, необходимое для строительства всех блоков.

Изначально есть только один рабочий.

Пример:

Input: blocks = [1,2,3], split = 1
Output: 4
Explanation: Split 1 worker into 2, then assign the first worker to the last block and split the second worker into 2.
Then, use the two unassigned workers to build the first two blocks.
The cost is 1 + max(3, 1 + max(1, 2)) = 4.

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

1⃣Подготовка кучи строительного времени:
Инициализируйте кучу строительного времени, изначально содержащую все значения времени из массива blocks.

2⃣Обработка кучи:
Пока в куче больше одного элемента:
- извлеките минимальное значение из кучи, обозначим его как x.
- извлеките следующее минимальное значение из кучи, обозначим его как y.
- создайте новое время строительства, которое равно split + y, и вставьте его обратно в кучу.

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

😎 Решение:

#include <vector>
#include <queue>

class Solution {
public:
    int minBuildTime(std::vector<int>& blocks, int split) {
        std::priority_queue<int, std::vector<int>, std::greater<int>> pq(blocks.begin(), blocks.end());
        
        while (pq.size() > 1) {
            int x = pq.top(); pq.pop();
            int y = pq.top(); pq.pop();
            pq.push(split + y);
        }
        
        return pq.top();
    }
};

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

Задача: 325. Maximum Size Subarray Sum Equals k
Сложность: medium

Дан целочисленный массив nums и целое число k. Верните максимальную длину подмассива, сумма которого равна k. Если такого подмассива не существует, верните 0.

Пример:

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

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

1⃣Инициализация переменных
Инициализируйте prefixSum как 0 для отслеживания префиксной суммы nums. Инициализируйте longestSubarray как 0 для отслеживания самой длинной подмассы с суммой k. Инициализируйте хеш-карту indices для хранения префиксных сумм и их индексов.

2⃣Итерация по массиву
На каждом индексе i, добавляйте nums[i] к prefixSum. Проверьте следующие условия: Если prefixSum == k, обновите longestSubarray как i + 1. Если prefixSum - k существует в indices, обновите longestSubarray, если текущая длина подмассива больше. Если текущий prefixSum еще не существует в indices, добавьте indices[prefixSum] = i.

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

😎 Решение:

#include <vector>
#include <unordered_map>

class Solution {
public:
    int maxSubArrayLen(std::vector<int>& nums, int k) {
        int prefixSum = 0;
        int longestSubarray = 0;
        std::unordered_map<int, int> indices;
        
        for (int i = 0; i < nums.size(); ++i) {
            prefixSum += nums[i];
            
            if (prefixSum == k) {
                longestSubarray = i + 1;
            }
            if (indices.find(prefixSum - k) != indices.end()) {
                longestSubarray = std::max(longestSubarray, i - indices[prefixSum - k]);
            }
            if (indices.find(prefixSum) == indices.end()) {
                indices[prefixSum] = i;
            }
        }
        
        return longestSubarray;
    }
};

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

Задача: 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
Сложность: hard

Дана бинарная матрица mat размером m x n. За один шаг вы можете выбрать одну ячейку и перевернуть её и всех её четырех соседей, если они существуют (Перевернуть означает изменить 1 на 0 и 0 на 1). Пара ячеек называется соседями, если они имеют общую границу.

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

Бинарная матрица - это матрица, в которой все ячейки равны 0 или 1.
Нулевая матрица - это матрица, в которой все ячейки равны 0.

Пример:

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.

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

1⃣Переберите все возможные варианты решений для первой строки матрицы. Каждое решение представляется массивом, где каждый элемент равен 0 или 1, указывая, перевернут ли соответствующий элемент в первой строке. Инициализируйте два бинарных массива для каждой строки: lastState[], содержащий значения предыдущей строки, и changed[], представляющий, были ли значения в текущей строке перевернуты при работе с предыдущей строкой.

2⃣Для каждой строки в матрице используйте следующий шаг для вычисления состояния, инициализированного как changed:
Для каждой позиции j в диапазоне [0, n - 1] текущей строки измените значение state[j] соответственно, если lastState[j] равно 1. Переверните state[j], state[j - 1] и state[j + 1], если они существуют. Увеличьте счетчик переворотов на 1.
Значения, которые будут перевернуты в следующей строке, точно равны lastState, а решение для следующей строки точно равно массиву state. Поэтому установите changed = lastState и lastState = state, затем переходите к следующей строке.

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

😎 Решение:

class Solution {
    int better(int x, int y) {
        return x < 0 || (y >= 0 && y < x) ? y : x;
    }

    int dfs(const vector<vector<int>>& mat, vector<int>& operations) {
        if (operations.size() == mat[0].size()) {
            vector<int> changed(mat[0].size());
            vector<int> last_state = operations;
            int maybe = 0;
            for (const vector<int>& row : mat) {
                vector<int> state = changed;
                for (int j = 0; j < row.size(); ++j) {
                    state[j] ^= row[j];
                    if (last_state[j]) {
                        state[j] ^= 1;
                        if (j) {
                            state[j - 1] ^= 1;
                        }
                        if (j + 1 < row.size()) {
                            state[j + 1] ^= 1;
                        }
                        ++maybe;
                    }
                }
                changed = last_state;
                last_state = state;
            }
            for (int x : last_state) {
                if (x) {
                    return -1;
                }
            }
            return maybe;
        }
        operations.push_back(0);
        const int maybe1 = dfs(mat, operations);
        operations.back() = 1;
        const int maybe2 = dfs(mat, operations);
        operations.pop_back();
        return better(maybe1, maybe2);
    }

public:
    int minFlips(vector<vector<int>>& mat) {
        vector<int> operations;
        return dfs(mat, operations);
    }
};

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

Задача: 760. Find Anagram Mappings
Сложность: easy

Вам даны два целочисленных массива nums1 и nums2, где nums2 - анаграмма nums1. Оба массива могут содержать дубликаты. Верните индексное отображение массива mapping из nums1 в nums2, где mapping[i] = j означает, что i-й элемент в nums1 появляется в nums2 по индексу j. Если ответов несколько, верните любой из них. Массив a является анаграммой массива b означает, что b создается путем случайного изменения порядка элементов в a.

Пример:

Input: nums1 = [12,28,46,32,50], nums2 = [50,12,32,46,28]
Output: [1,4,3,2,0]

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

1⃣Создайте словарь для хранения индексов элементов в nums2.

2⃣Пройдите по элементам массива nums1 и для каждого элемента найдите соответствующий индекс в nums2, используя словарь.

3⃣Верните массив индексов.

😎 Решение:

vector<int> anagramMapping(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, vector<int>> indexMap;
    for (int i = 0; i < nums2.size(); i++) {
        indexMap[nums2[i]].push_back(i);
    }
    
    vector<int> mapping;
    for (int num : nums1) {
        mapping.push_back(indexMap[num].back());
        indexMap[num].pop_back();
    }
    
    return mapping;
}

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

Задача: 1214. Two Sum BSTs
Сложность: medium

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

Пример:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

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

1⃣Создайте два пустых множества node_set1 и node_set2. Выполните обход дерева root1, добавляя значения каждого узла в node_set1, и выполните обход дерева root2, добавляя значения каждого узла в node_set2.

2⃣Итерация по элементам в node_set1: для каждого элемента value1 проверяйте, находится ли target - value1 в node_set2.

3⃣Если target - value1 находится в node_set2, верните true. Если после завершения итерации не найдено ни одной подходящей пары, верните false.

😎 Решение:

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

class Solution {
    void dfs(TreeNode* node, unordered_set<int>& nodeSet) {
        if (!node) return;
        dfs(node->left, nodeSet);
        nodeSet.insert(node->val);
        dfs(node->right, nodeSet);
    }

public:
    bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
        unordered_set<int> nodeSet1, nodeSet2;
        dfs(root1, nodeSet1);
        dfs(root2, nodeSet2);
        
        for (int value1 : nodeSet1) {
            if (nodeSet2.count(target - value1)) {
                return true;
            }
        }
        
        return false;
    }
};

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

Задача: 859. Buddy Strings
Сложность: easy

Даны две строки s и goal. Верните true, если вы можете поменять местами две буквы в s так, чтобы результат был равен goal, в противном случае верните false.

Обмен буквами определяется как взятие двух индексов i и j (нумерация с 0), таких что i != j, и обмен символов в s[i] и s[j].

Например, обмен символов на индексах 0 и 2 в строке "abcd" приводит к "cbad".

Пример:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

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

1⃣Если количество символов в строках s и goal разное, возвращаем false. Если s == goal, используем хеш-таблицу или массив из 26 элементов для хранения частоты каждого символа в строке s. Если какой-либо символ встречается более одного раза, можно поменять местами две одинаковые буквы, возвращаем true. Иначе возвращаем false.

2⃣Иначе, если s != goal, инициализируем firstIndex и secondIndex значениями -1 для хранения индексов символов в строке s, которые отличаются от символов в строке goal на тех же индексах. Итерируем по каждому индексу i в строке s: если символы s[i] и goal[i] разные, сохраняем текущий индекс. Если firstIndex == -1, обновляем firstIndex = i. Если firstIndex != -1, но secondIndex == -1, обновляем secondIndex = i. Если оба индекса уже обновлены, возвращаем false.

3⃣Если обновлен только firstIndex, возвращаем false. Иначе, все символы обеих строк одинаковы, кроме двух индексов. Поэтому s[firstIndex] должен быть равен goal[secondIndex], и s[secondIndex] должен быть равен goal[firstIndex], чтобы строки стали равны после обмена.

😎 Решение:

class Solution {
public:
    bool buddyStrings(string s, string goal) {
        if (s.size() != goal.size()) return false;
        if (s == goal) {
            vector<int> freq(26, 0);
            for (char ch : s) {
                if (++freq[ch - 'a'] > 1) return true;
            }
            return false;
        }

        int firstIndex = -1, secondIndex = -1;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] != goal[i]) {
                if (firstIndex == -1) firstIndex = i;
                else if (secondIndex == -1) secondIndex = i;
                else return false;
            }
        }

        return secondIndex != -1 &&
               s[firstIndex] == goal[secondIndex] &&
               s[secondIndex] == goal[firstIndex];
    }
};

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

Задача: 16. 3Sum Closest
Сложность: medium

Дан массив целых чисел nums и целое число target.
Найди такую тройку чисел в массиве, сумма которых наиболее близка к target, и верни эту сумму.
Гарантируется, что только одно решение существует.

Пример:

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

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

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

2⃣Для каждого числа nums[i], зафиксировать его и искать пару чисел в подмассиве справа с помощью двух указателей (front, back), чтобы сумма тройки была ближе всего к target.

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

😎 Решение:

class Solution { 
public: 
    int threeSumClosest(vector<int>& nums, int target) { 
        sort(nums.begin(), nums.end()); 
        int sum = nums[0] + nums[1] + nums[2]; 
        int sum1 = 0; 
        
        for (int i = 0; i < nums.size(); i++) { 
            int front = i + 1; 
            int back = nums.size() - 1; 
            
            while (front < back) { 
                sum1 = nums[i] + nums[front] + nums[back]; 
                
                if (abs(sum1 - target) <= abs(sum - target)) { 
                    sum = sum1; 
                } 
                
                if (sum1 > target)  
                    back--; 
                else if (sum1 < target)  
                    front++; 
                else 
                    return sum1; 
            } 
        } 
        return sum; 
    } 
};

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

Задача: 1026. Maximum Difference Between Node and Ancestor
Сложность: medium

Учитывая корень бинарного дерева, найдите максимальное значение v, для которого существуют различные вершины a и b, где v = |a.val - b.val| и a является предком b. Вершина a является предком b, если: любой ребенок a равен b или любой ребенок a является предком b.

Пример:

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7

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

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

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

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

😎 Решение:

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

class Solution {
public:
    int maxAncestorDiff(TreeNode* root) {
        return dfs(root, root->val, root->val);
    }
    
private:
    int dfs(TreeNode* node, int min_val, int max_val) {
        if (!node) return max_val - min_val;
        min_val = min(min_val, node->val);
        max_val = max(max_val, node->val);
        int left = dfs(node->left, min_val, max_val);
        int right = dfs(node->right, min_val, max_val);
        return max(left, right);
    }
};

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

Задача: 1261. Find Elements in a Contaminated Binary Tree
Сложность: medium

Дано двоичное дерево со следующими правилами: root.val == 0 Если treeNode.val == x и treeNode.left != null, то treeNode.left.val == 2 * x + 1 Если treeNode.val == x и treeNode.right != null, то treeNode.right.val == 2 * x + 2 Теперь двоичное дерево загрязнено, то есть все treeNode.val были изменены на -1. Реализация класса FindElements: FindElements(TreeNode* root) Инициализирует объект с загрязненным двоичным деревом и восстанавливает его. bool find(int target) Возвращает true, если целевое значение существует в восстановленном двоичном дереве.

Пример:

Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output
[null,false,true]

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

1⃣Восстановление дерева: Начните с корневого узла, установите его значение на 0. Затем рекурсивно восстановите значения для всех узлов, используя правила left.val = 2 * parent.val + 1 и right.val = 2 * parent.val + 2.

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

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

😎 Решение:

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

class FindElements {
public:
    TreeNode* root;
    unordered_set<int> values;

    FindElements(TreeNode* root) {
        this->root = root;
        root->val = 0;
        values.insert(0);
        recover(root);
    }
    
    void recover(TreeNode* node) {
        if (node->left != nullptr) {
            node->left->val = 2 * node->val + 1;
            values.insert(node->left->val);
            recover(node->left);
        }
        if (node->right != nullptr) {
            node->right->val = 2 * node->val + 2;
            values.insert(node->right->val);
            recover(node->right);
        }
    }
    
    bool find(int target) {
        return values.find(target) != values.end();
    }
};

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

Задача: 17. Letter Combinations of a Phone Number
Сложность: medium

Дана строка, содержащая цифры от 2 до 9. Необходимо вернуть все возможные комбинации букв, которые может представлять эта строка, согласно клавиатуре мобильного телефона.
Цифра 1 не используется, и для неё нет соответствующих букв.

Пример:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

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

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

2⃣На каждом шаге рекурсивно добавляем буквы для текущей цифры к текущей строке.

3⃣Когда строка достигла длины исходных digits — добавляем комбинацию в результат.

😎 Решение:

class Solution { 
public: 
    void find(string digits, vector<string> v, vector<string>& res, string s, int k) { 
        if (k >= digits.size()) { 
            res.push_back(s); 
            return; 
        } 
        int a = digits[k] - '0'; 
        for (int i = 0; i < v[a].size(); i++) { 
            s += v[a][i]; 
            find(digits, v, res, s, k + 1); 
            s.pop_back(); 
        } 
    } 
    
    vector<string> letterCombinations(string digits) { 
        vector<string> res; 
        if (digits.empty()) return res; 
        vector<string> v = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 
        string s = ""; 
        find(digits, v, res, s, 0); 
        return res; 
    } 
};

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

Задача: 507. Perfect Number
Сложность: easy

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

Дано целое число n, верните true, если n является совершенным числом, в противном случае верните false.

Пример:

Input: num = 28
Output: true
Explanation: 28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, and 14 are all divisors of 28.

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

1⃣Инициализация
Если число num меньше или равно 0, вернуть false. Инициализируйте переменную sum значением 0.

2⃣Поиск делителей и вычисление суммы
Переберите числа от 1 до квадратного корня num. Если число является делителем num, добавьте его к sum. Если делитель не равен квадратному корню num, добавьте к sum также результат деления num на делитель.

3⃣Проверка на совершенное число
Вычтите num из sum. Если результат равен num, вернуть true, иначе вернуть false.

😎 Решение:

 class Solution {
public:
    bool checkPerfectNumber(int num) {
        if (num <= 0) return false;
        int sum = 0;
        for (int i = 1; i * i <= num; ++i) {
            if (num % i == 0) {
                sum += i;
                if (i * i != num) {
                    sum += num / i;
                }
            }
        }
        return sum - num == num;
    }
};

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

Задача: 715. Range Module
Сложность: hard

Модуль Range - это модуль, который отслеживает диапазоны чисел. Создайте структуру данных для отслеживания диапазонов, представленных в виде полуоткрытых интервалов, и запросов к ним. Полуоткрытый интервал [left, right) обозначает все вещественные числа x, где left <= x < right. Реализуйте класс RangeModule: RangeModule() Инициализирует объект структуры данных. void addRange(int left, int right) Добавляет полуоткрытый интервал [left, right), отслеживая каждое вещественное число в этом интервале. Добавление интервала, который частично перекрывает отслеживаемые в данный момент числа, должно добавить все числа в интервале [left, right), которые еще не отслеживаются. boolean queryRange(int left, int right) Возвращает true, если каждое действительное число в интервале [left, right) отслеживается в данный момент, и false в противном случае. void removeRange(int left, int right) Прекращает отслеживание каждого действительного числа, отслеживаемого в данный момент в полуоткрытом интервале [left, right).

Пример:

Input
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output
[null, null, null, true, false, true]

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

1⃣Инициализируйте класс RangeModule с пустым списком диапазонов.

2⃣Для метода addRange(left, right) добавьте новый диапазон, объединяя его с существующими перекрывающимися диапазонами. Для метода queryRange(left, right) проверьте, полностью ли данный диапазон содержится в отслеживаемых диапазонах.

3⃣Для метода removeRange(left, right) удалите указанный диапазон, разбивая существующие диапазоны на соответствующие части.

😎 Решение:

class RangeModule {
public:
    RangeModule() {}

    void addRange(int left, int right) {
        vector<pair<int, int>> newRanges;
        int i = 0;
        while (i < ranges.size() && ranges[i].second < left) {
            newRanges.push_back(ranges[i]);
            i++;
        }
        while (i < ranges.size() && ranges[i].first <= right) {
            left = min(left, ranges[i].first);
            right = max(right, ranges[i].second);
            i++;
        }
        newRanges.push_back({left, right});
        while (i < ranges.size()) {
            newRanges.push_back(ranges[i]);
            i++;
        }
        ranges = newRanges;
    }

    bool queryRange(int left, int right) {
        for (auto& range : ranges) {
            if (range.first <= left && right <= range.second) {
                return true;
            }
        }
        return false;
    }

    void removeRange(int left, int right) {
        vector<pair<int, int>> newRanges;
        for (auto& range : ranges) {
            if (range.first < left) {
                newRanges.push_back({range.first, min(range.second, left)});
            }
            if (right < range.second) {
                newRanges.push_back({max(range.first, right), range.second});
            }
        }
        ranges = newRanges;
    }

private:
    vector<pair<int, int>> ranges;
};

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

Задача: CodeTestcaseTest ResultTest Result1187. Make Array Strictly Increasing
Сложность: hard

Даны два целочисленных массива arr1 и arr2. Верните минимальное количество операций (возможно, ноль), необходимых для того, чтобы сделать arr1 строго возрастающим.

В одной операции вы можете выбрать два индекса 0 <= i < arr1.length и 0 <= j < arr2.length и выполнить присваивание arr1[i] = arr2[j].

Если нет способа сделать arr1 строго возрастающим, верните -1.

Пример:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

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

1⃣Сначала отсортируйте массив arr2 и инициализируйте хэш-таблицу dp для хранения промежуточных результатов. Определите функцию dfs(i, prev), которая вычисляет минимальное количество операций для сортировки массива arr1, начиная с индекса i, при условии, что предыдущий элемент равен prev. Если результат для (i, prev) уже существует в dp, то просто верните сохраненное значение.

2⃣Внутри функции dfs инициализируйте переменную cost значением float('inf'). Если arr1[i] больше, чем prev, обновите значение cost результатом вызова dfs(i + 1, arr1[i]). Используйте бинарный поиск, чтобы найти индекс idx наименьшего значения в arr2, которое больше prev. Если такой индекс существует, обновите значение cost результатом минимального значения между текущим значением cost и 1 + dfs(i + 1, arr2[idx]).

3⃣После всех вычислений обновите dp[(i, prev)] значением cost и верните cost. В конце вызовите dfs(0, -1) и верните его значение, если оно не равно float('inf'); в противном случае верните -1.

😎 Решение:

class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        sort(arr2.begin(), arr2.end());
        int answer = dfs(0, -1, arr1, arr2);
        return answer < 2001 ? answer : -1;
    }
    
private:
    unordered_map<pair<int, int>, int, hash_pair> dp;
    
    int dfs(int i, int prev, vector<int>& arr1, vector<int>& arr2) {
        if (i == arr1.size()) return 0;
        pair<int, int> key = {i, prev};
        if (dp.count(key)) return dp[key];
        
        int cost = 2001;
        if (arr1[i] > prev) {
            cost = dfs(i + 1, arr1[i], arr1, arr2);
        }
        int idx = bisectRight(arr2, prev);
        if (idx < arr2.size()) {
            cost = min(cost, 1 + dfs(i + 1, arr2[idx], arr1, arr2));
        }
        
        dp[key] = cost;
        return cost;
    }
    
    int bisectRight(const vector<int>& arr, int value) {
        int left = 0, right = arr.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] <= value) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    struct hash_pair {
        template <class T1, class T2>
        size_t operator()(const pair<T1, T2>& p) const {
            auto hash1 = hash<T1>{}(p.first);
            auto hash2 = hash<T2>{}(p.second);
            return hash1 ^ hash2;
        }
    };
};

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

Задача: 1133. Largest Unique Number
Сложность: easy

Вам Дан целочисленный массив nums, верните наибольшее целое число, которое встречается только один раз. Если ни одно целое число не встречается один раз, верните -1.

Пример:

Input: nums = [5,7,3,9,4,9,8,3,1]
Output: 8
Explanation: The maximum integer in the array is 9 but it is repeated. The number 8 occurs only once, so it is the answer.

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

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

2⃣Пройдите по массиву и заполните хеш-таблицу количеством каждого числа.

3⃣Инициализируйте результат значением -1. Пройдите по хеш-таблице и если значение ключа равно 1, установите результат равным максимальному значению между ключом и текущим результатом. Верните результат.

😎 Решение:

class Solution {
public:
    int largestUniqueNumber(vector<int>& nums) {
        unordered_map<int, int> count;
        
        for (int num : nums) {
            count[num]++;
        }
        
        int result = -1;
        for (auto& entry : count) {
            if (entry.second == 1) {
                result = max(result, entry.first);
            }
        }
        
        return result;
    }
};

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

Задача: 1380. Lucky Numbers in a Matrix
Сложность: easy

Дана матрица m x n из различных чисел, верните все счастливые числа в матрице в любом порядке.

Счастливое число — это элемент матрицы, который является минимальным элементом в своей строке и максимальным в своем столбце.

Пример:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column.

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

1⃣Сохраните минимум каждой строки в список rowMin и максимум каждого столбца в список colMax.

2⃣Итерируйте по каждому числу в матрице и проверяйте, равно ли оно rowMin[i] и colMax[j].

3⃣Если число удовлетворяет условию, добавьте его в список luckyNumbers и верните luckyNumbers.

😎 Решение:

class Solution {
public:
    vector<int> luckyNumbers (vector<vector<int>>& matrix) {
        int N = matrix.size(), M = matrix[0].size();

        vector<int> rowMin;
        for (int i = 0; i < N; i++) {
            int rMin = INT_MAX;
            for (int j = 0; j < M; j++) {
                rMin = min(rMin, matrix[i][j]);
            }
            rowMin.push_back(rMin);
        }

        vector<int> colMax;
        for (int i = 0; i < M; i++) {
            int cMax = INT_MIN;
            for (int j = 0; j < N; j++) {
                cMax = max(cMax, matrix[j][i]);
            }
            colMax.push_back(cMax);
        }

        vector<int> luckyNumbers;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j]) {
                    luckyNumbers.push_back(matrix[i][j]);
                }
            }
        }

        return luckyNumbers;
    }
};

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

Задача: 748. Shortest Completing Word
Сложность: easy

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

Пример:

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"

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

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

2⃣Пройти по массиву words, проверяя каждое слово на соответствие требованиям.

3⃣Найти самое короткое завершающее слово среди подходящих.

😎 Решение:

class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        unordered_map<char, int> licenseCount = getCharCount(licensePlate);
        
        string result;
        for (const string& word : words) {
            if (isCompletingWord(word, licenseCount)) {
                if (result.empty() || word.length() < result.length()) {
                    result = word;
                }
            }
        }
        return result;
    }
    
private:
    unordered_map<char, int> getCharCount(const string& s) {
        unordered_map<char, int> count;
        for (char c : s) {
            if (isalpha(c)) {
                count[tolower(c)]++;
            }
        }
        return count;
    }
    
    bool isCompletingWord(const string& word, const unordered_map<char, int>& licenseCount) {
        unordered_map<char, int> wordCount;
        for (char c : word) {
            wordCount[c]++;
        }
        for (const auto& entry : licenseCount) {
            if (wordCount[entry.first] < entry.second) {
                return false;
            }
        }
        return true;
    }
};

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

Задача: 1043. Partition Array for Maximum Sum
Сложность: medium

Если задан целочисленный массив arr, разбейте его на (смежные) подмассивы длины не более k. После разбиения значения каждого подмассива меняются так, чтобы стать максимальным значением этого подмассива. Верните наибольшую сумму заданного массива после разбиения. Тестовые примеры генерируются таким образом, чтобы ответ умещался в 32-битное целое число.

Пример:

Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84

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

1⃣Инициализация:
Создаем массив dp, где dp[i] будет хранить наибольшую сумму подмассива, заканчивающегося в позиции i.

2⃣Заполнение массива dp:
Проходим по массиву arr и для каждой позиции i пытаемся разбить подмассив длины до k и обновить dp[i] с максимальной возможной суммой.

3⃣Поддержание максимального значения в подмассиве:
Для каждого подмассива длины 1 до k, вычисляем максимальное значение в этом подмассиве и обновляем dp[i].

😎 Решение:

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& arr, int k) {
        int n = arr.size();
        vector<int> dp(n, 0);
        
        for (int i = 0; i < n; ++i) {
            int max_val = 0;
            for (int j = 1; j <= k; ++j) {
                if (i - j + 1 >= 0) {
                    max_val = max(max_val, arr[i - j + 1]);
                    if (i - j >= 0) {
                        dp[i] = max(dp[i], dp[i - j] + max_val * j);
                    } else {
                        dp[i] = max(dp[i], max_val * j);
                    }
                }
            }
        }
        
        return dp[n - 1];
    }
};

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

Задача: 201. Bitwise AND of Numbers Range
Сложность: medium

Даны два целых числа left и right, обозначающие диапазон [left, right].
Нужно вернуть результат побитового AND всех чисел в этом диапазоне (включительно).

Пример:

Input: left = 5, right = 7 Output: 4

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

1⃣Пока left < right, сдвигаем оба числа вправо (>>= 1), пока они не станут равны. Это находит общий префикс битов.

2⃣Подсчитываем количество сдвигов — это количество младших битов, которые могут изменяться в диапазоне, и обнуляются при AND.

3⃣После этого сдвигаем результат left обратно влево (<< shift) — возвращаем биты на место.

😎 Решение:

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m < n) {
            m >>= 1;
            n >>= 1;
            ++shift;
        }
        return m << shift;
    }
};

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

Задача: 1269. Number of Ways to Stay in the Same Place After Some Steps
Сложность: hard

У вас есть указатель на индекс 0 в массиве размера arrLen. На каждом шаге вы можете перемещаться на 1 позицию влево, на 1 позицию вправо в массиве или оставаться на том же месте (указатель ни в коем случае не должен находиться за пределами массива). Учитывая два целых числа steps и arrLen, верните количество способов, при которых указатель все еще находится на индексе 0 после ровно шагов. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: steps = 3, arrLen = 2
Output: 4

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

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

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

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

😎 Решение:

class Solution {
public:
    int numWays(int steps, int arrLen) {
        const int mod = 1e9 + 7;
        int max_pos = min(arrLen - 1, steps);
        vector<int> dp(max_pos + 1, 0);
        dp[0] = 1;
        for (int step = 0; step < steps; ++step) {
            vector<int> new_dp(max_pos + 1, 0);
            for (int i = 0; i <= max_pos; ++i) {
                new_dp[i] = dp[i] % mod;
                if (i > 0) new_dp[i] = (new_dp[i] + dp[i - 1]) % mod;
                if (i < max_pos) new_dp[i] = (new_dp[i] + dp[i + 1]) % mod;
            }
            dp = new_dp;
        }
        return dp[0];
    }
};

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

Задача: 1271. Hexspeak
Сложность: easy

Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR".

Пример:

Input: num = "257"
Output: "IOI"

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

1⃣Преобразуйте десятичное число в шестнадцатеричную строку в верхнем регистре.

2⃣Замените все вхождения цифры '0' на букву 'O', а цифры '1' на букву 'I'

3⃣Проверьте, что преобразованная строка содержит только допустимые символы. Если это так, верните строку, иначе верните "ERROR".

😎 Решение:

class Solution {
public:
    string toHexString(string num) {
        stringstream ss;
        ss << hex << uppercase << stol(num);
        string hexStr = ss.str();
        for (char& c : hexStr) {
            if (c == '0') c = 'O';
            else if (c == '1') c = 'I';
            else if (string("ABCDEFIO").find(c) == string::npos) return "ERROR";
        }
        return hexStr;
    }
};

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