- 数组
- 448. 找到所有数组中消失的数字（原地标记法）">448. 找到所有数组中消失的数字（原地标记法）
- 287. 寻找重复数（原地标记法）">287. 寻找重复数（原地标记法）
- 442. 数组中重复的数据（原地标记法）">442. 数组中重复的数据（原地标记法）
- 48. 旋转图像（原地旋转）">48. 旋转图像（原地旋转）
- 240. 搜索二维矩阵 II（z字查找）">240. 搜索二维矩阵 II（z字查找）
- 769. 最多能完成排序的块（特殊）">769. 最多能完成排序的块（特殊）
- 566. 重塑矩阵（简单）">566. 重塑矩阵（简单）
- 栈和队列
- 232. 用栈实现队列（两个栈实现队列）">232. 用栈实现队列（两个栈实现队列）
- 225. 用队列实现栈（两个队列实现栈）">225. 用队列实现栈（两个队列实现栈）
- 20. 有效的括号(栈来存储括号)">20. 有效的括号(栈来存储括号)
- 单调栈
- 739. 每日温度">739. 每日温度
- 503. 下一个更大元素 II(循环数组)">503. 下一个更大元素 II(循环数组)
- 链表
- 146. LRU 缓存（哈希表+双端链表）">146. LRU 缓存（哈希表+双端链表）
- 优先队列
- 23. 合并K个升序链表（优先队列存储链表指针）">23. 合并K个升序链表（优先队列存储链表指针）
- 313. 超级丑数（动规）">313. 超级丑数（动规）
- 1606. 找到处理最多请求的服务器">1606. 找到处理最多请求的服务器
- 哈希表
- 1. 两数之和（简单哈希表）">1. 两数之和（简单哈希表）
- 217. 存在重复元素">217. 存在重复元素
- 697. 数组的度">697. 数组的度
- 128. 最长连续序列(字节面试题)">128. 最长连续序列(字节面试题)
- 5268. 找出两数组的不同(set即可)">5268. 找出两数组的不同(set即可)
- 890. 查找和替换模式（构建哈希表来映射）">890. 查找和替换模式（构建哈希表来映射）
- 304. 二维区域和检索 - 矩阵不可变（dp+前缀和）">304. 二维区域和检索 - 矩阵不可变（dp+前缀和）
- 560. 和为 K 的子数组（哈希表+前缀和）">560. 和为 K 的子数组（哈希表+前缀和）
- 线段树（模板）
- 红黑树
- 6066. 统计区间中的整数数目（可以使用set二分查找）">6066. 统计区间中的整数数目（可以使用set二分查找）
- 6066. 统计区间中的整数数目（可以使用set二分查找）">6066. 统计区间中的整数数目（可以使用set二分查找）
数组
448. 找到所有数组中消失的数字（原地标记法）
可以使用哈希表，但是有性能更加优越的方法。
直接对原数组进行标记。出现过，则转化为负值，这样即标记了，又保留了原本的特征。
class Solution {public:vector<int> findDisappearedNumbers(vector<int>& nums) {vector<int> ret;for (auto& num : nums) {int a = abs(num)-1;if(nums[a] > 0){nums[a] = -nums[a];}}for (int i = 0; i < nums.size(); i++) {if (nums[i] > 0) {ret.push_back(i + 1);}}return ret;}};
287. 寻找重复数（原地标记法）
- 使用索引来代表元素
原地标记
class Solution {public:int findDuplicate(vector<int>& nums) {int n = nums.size();for(int i = 0; i <n; i++){int a = abs(nums[i]);if(nums[a] < 0){return a;}nums[a] = -nums[a];}return 0;}};
floyd判圈法（快慢指针）
我们对 \textit{nums}nums 数组建图，每个位置 ii 连一条 i\rightarrow \textit{nums}[i]i→nums[i] 的边。由于存在的重复的数字 \textit{target}target，因此 \textit{target}target 这个位置一定有起码两条指向它的边，因此整张图一定存在环，且我们要找到的 \textit{target}target 就是这个环的入口，那么整个问题就等价于 142. 环形链表 II。
class Solution {public:int findDuplicate(vector<int>& nums) {int slow = 0, fast = 0;do {slow = nums[slow];fast = nums[nums[fast]];} while (slow != fast);slow = 0;while (slow != fast) {slow = nums[slow];fast = nums[fast];}return slow;}};
442. 数组中重复的数据（原地标记法）
class Solution {public:vector<int> findDuplicates(vector<int>& nums) {vector<int> ret;for(int i = 0; i < nums.size(); i++) {int tmp = abs(nums[i])-1;if(nums[tmp] > 0) {nums[tmp] = -nums[tmp];} else {ret.push_back(tmp+1);}}return ret;}};
48. 旋转图像（原地旋转）
这里的循环下标选取非常关键
原地旋转
class Solution {public:void rotate(vector<vector<int>>& matrix) {int temp = 0, n = matrix.size()-1 ;for(int i = 0; i <= n/2 ; ++i){for(int j = i; j < n-i; ++j){temp = matrix[j][n-i];matrix[j][n-i] = matrix[i][j];matrix[i][j] = matrix[n-j][i];matrix[n-j][i] = matrix[n-i][n-j];matrix[n-i][n-j] = temp;}}}};//这里的两个循环的值的选取非常讲究//注意仔细研究
240. 搜索二维矩阵 II（z字查找）
选取一个中间值，如果大于它则左移
小于他则上移或者下移。
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(); if( m == 0){ return false; } int n = matrix[0].size(); int i = m - 1, j = 0; while(i >= 0 && j < n ){ if(matrix[i][j] == target) return true; else if (matrix[i][j]> target) --i; else ++j; } return false; } }; //从右上角来进行判断，理论来说左下角应该也行769. 最多能完成排序的块（特殊）
从左往右遍历，同时记录当前的最大值，每当当前最大值等于数组位置时，就可以试做多一次分割
class Solution { public: int maxChunksToSorted(vector<int>& arr) { int n = arr.size(), maxs = 0, res = 0; for(int i = 0; i < n; i++){ maxs = max(arr[i], maxs); if(maxs == i){ res++; } } return res; } };566. 重塑矩阵（简单）
class Solution { public: vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) { int n = mat.size(), m = mat[0].size(); vector<vector<int>> res; vector<int> vec; if(n*m != r*c) { return mat; } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ vec.push_back(mat[i][j]); if(vec.size() == c){ res.push_back(vec); vec.clear(); } } } return res; } };栈和队列
232. 用栈实现队列（两个栈实现队列）
通过一个栈来使得另一个栈翻转 ```cpp class MyQueue { private: stack
sta1; stack sta2; public: MyQueue() { }
void push(int x) {
while(!sta2.empty()){ sta1.push(sta2.top()); sta2.pop(); } sta1.push(x); while(!sta1.empty()){ sta2.push(sta1.top()); sta1.pop(); }}
int pop() {
int a = sta2.top(); sta2.pop(); return a;}
int peek() {
return sta2.top();}
bool empty() {
return sta2.empty();} };
/**
- Your MyQueue object will be instantiated and called as such:
- MyQueue* obj = new MyQueue();
- obj->push(x);
- int param_2 = obj->pop();
- int param_3 = obj->peek();
- bool param_4 = obj->empty();
*/
```
225. 用队列实现栈（两个队列实现栈）
- 使用一个栈来进行辅助操作
- 一个队列存储当前进去的数据，然后把存储栈的形式的队列全部存入这个队列。实现队列的最前端为最新的数据。
这样就实现了先进先出。 ```cpp class MyStack { public: queue
queue1; queue queue2; /* Initialize your data structure here. / MyStack() {
}
/* Push element x onto stack. / void push(int x) {
queue2.push(x); while (!queue1.empty()) { queue2.push(queue1.front()); queue1.pop(); } swap(queue1, queue2);}
/* Removes the element on top of the stack and returns that element. / int pop() {
int r = queue1.front(); queue1.pop(); return r;}
/* Get the top element. / int top() {
int r = queue1.front(); return r;}
/* Returns whether the stack is empty. / bool empty() {
return queue1.empty();} };
<a name="pMfpO"></a>
### [155. 最小栈](https://leetcode-cn.com/problems/min-stack/)（栈维护最小值）
一个栈实现普通功能，一个栈来维护最小值，栈顶存储最小值
```cpp
class MinStack {
private:
stack<int> sta1;
stack<int> sta2;
public:
MinStack() {
}
void push(int val) {
sta1.push(val);
if(sta2.empty()||sta2.top()>=val){
sta2.push(val);
}
}
void pop() {
if(sta2.top() == sta1.top()){
sta2.pop();
}
sta1.pop();
}
int top() {
return sta1.top();
}
int getMin() {
return sta2.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
20. 有效的括号(栈来存储括号)
class Solution {
public:
bool isValid(string s) {
stack<char> str;
int n = s.size();
for(int i = 0; i < n; i++){
if(s[i] == '('||s[i] == '{'||s[i] == '[')
str.push(s[i]);
else {
if(str.empty())//
return false;
if(s[i] == ')'&&str.top()=='('||s[i] == '}'&&str.top()=='{'||s[i] == ']'&&str.top()=='['){//括号对上了，出栈
str.pop();
} else {//括号对不上，直接false
return false;
}
}
}
return str.empty();
}
};
//每当遇到左括号便放入栈内，遇到右括号就判断是不是与左括号是同一类，是的话则取出左括号，不是则为无效字符串
单调栈
739. 每日温度
- 使用一个栈来存储数组的下标，也就是天数
- 栈顶到栈底始终是从小到大的
如果出现一个大于栈顶的元素，则使用while来进行循环判断
class Solution { public: vector<int> dailyTemperatures(vector<int>& T) { int n = T.size(); vector<int> ans(n, 0); stack<int> sta; for(int i = 0; i < n; i++){ while(!sta.empty()){//这里的这个小循环很重要，出现转机时清一清栈 int pre = sta.top(); if(T[i] <= T[pre]){ break; } ans[pre] = i - pre; sta.pop(); } sta.push(i); } return ans; } }; //单调栈，存储的是日期，根据pre与当前日期的大小来判断是否输入ans中。 //比之前日期的温度高则当前日期减去之前日期存入ans中，温度低则不管直接跳出， //每个日期都存入栈中。503. 下一个更大元素 II(循环数组)
解决循环数组的方式就是将数组循环两次
class Solution { public: vector<int> nextGreaterElements(vector<int>& nums) { int n = nums.size(); vector<int> ret(n, -1); stack<int> stk; for (int i = 0; i < n * 2 - 1; i++) { while (!stk.empty() && nums[stk.top()] < nums[i % n]) { ret[stk.top()] = nums[i % n]; stk.pop(); } stk.push(i % n); } return ret; } };链表
146. LRU 缓存（哈希表+双端链表）
使用哈希表来存储key和对应的链表的迭代器位置。
- 链表存储pair类型的值
- 每次操作都将当前的元素挪到队头。
使用双端链表是为了方便从头部插入，以及从尾部删除
class LRUCache { unordered_map<int,list<pair<int,int>>::iterator> hash;//哈希表里面存储的是双端链表的迭代器 list<pair<int , int>> cache; int size; public: LRUCache(int capacity):size(capacity) { } int get(int key) { auto it = hash.find(key);//find函数的返回值是迭代器如果没有找到就是末尾迭代器end() if(it == hash.end()){ return -1; } cache.splice(cache.begin(), cache, it->second);//将使用过得数据挪到头部，不能使用swap，因为会破坏原来的结构，会把原来处于第二个位置的元素换到后面。 return it->second->second; } void put(int key, int value) { auto it = hash.find(key); if(it != hash.end()){//如果队列里面存在要插入的值 it->second->second = value; cache.splice(cache.begin(), cache, it->second);//将使用过得数据插入到头部 return; } cache.insert(cache.begin() , make_pair(key, value));//从头部插入 hash[key] = cache.begin(); if(cache.size() > size){//超出容量的时候，删除尾部的值，erase掉hash表中的值。 hash.erase(cache.back().first); cache.pop_back(); } } };优先队列
23. 合并K个升序链表（优先队列存储链表指针）
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: struct Cmop{ bool operator() (ListNode* l1, ListNode*l2){ return l1->val > l2->val; } }; //为什么要用仿函数的方法来写，这里是定义一个仿函数，重载了小括号，相当于更改了比较方式 ListNode* mergeKLists(vector<ListNode*>& lists) { if(lists.empty()) return nullptr; priority_queue<ListNode * , vector<ListNode*>, Cmop> q;//建立一个优先队列q，按照头节点的val来排序，第二个参数是实现优先队列的底层容器 for(ListNode * list: lists){ if(list) { q.push(list); } } ListNode *dummy = new ListNode(0), *cur = dummy; while(!q.empty()){ cur->next = q.top(); q.pop(); cur = cur->next; if(cur->next){//如果链表不为空就把头链表的下一个节点推进去 q.push(cur->next); } } return dummy->next;//这里直接返回的是dummy->next非常关键 } }; //priority_queue<Type, Container, Functional> 优先队列的参数，其中Type是数据类别，Container是容器类别 //Functiona是函数，也是比较的方式 //排序自定义的数据类型，因此要重载运算符，使用仿函数 //仿函数不是函数而是类313. 超级丑数（动规）
其实用优先队列写的超时了，但是可以锻炼以下。
class Solution { public: struct cmp { bool operator ()(const pair<long,int>& a,const pair<long, int>& b){ return a.first>b.first; } }; int nthSuperUglyNumber(int n, vector<int>& primes) { int m = primes.size(); int res = 1; priority_queue<pair<long , int>, vector<pair<long , int>>, cmp> q; for(int i = 0; i < n-1; i++){ for(int j = 0; j < m; j++){ q.push(pair<long, int>((long)primes[j]*res, j)); } while(res == q.top().first) { q.pop(); } res = q.top().first; } return res; } };1606. 找到处理最多请求的服务器
用一个set集合来存储空闲的队列，方便随时删除
- 用一个优先队列busy来存储工作的队列，存储工作结束时间以及编号
- 用一个requests来对应服务器处理的请求数据。
模拟真正服务器的运行。
class Solution { public: vector<int> busiestServers(int k, vector<int> &arrival, vector<int> &load) { set<int> available;//存放空闲服务器编号的集合，空闲队列 for (int i = 0; i < k; i++) { available.insert(i); } priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> busy;//工作队列，正在处理请求的服务器处理事件编号和时间 vector<int> requests(k);//对应服务器处理的请求数目 for (int i = 0; i < arrival.size(); i++) { while (!busy.empty() && busy.top().first <= arrival[i]) {//busy不为空，而且结束事件小于新任务的到达时间。 //把尽可能多的服务器放进空闲队列，满足i%k的要求 available.insert(busy.top().second);//将服务器编号插入空闲队列中。 busy.pop(); } if (available.empty()) {//如果空闲队列为空就直接跳到下一次循环。 continue; } auto p = available.lower_bound(i % k);//通过二分法在空闲队列中查找第一个大于等于i%k的服务器 if (p == available.end()) {//没找到就是用第一个服务器 p = available.begin(); } requests[*p]++;//对应服务器处理请求数目+1 busy.emplace(arrival[i] + load[i], *p);//将当前的服务器再次插入工作队列。 available.erase(p);//空闲队列中删除 } int maxRequest = *max_element(requests.begin(), requests.end()); vector<int> ret; for (int i = 0; i < k; i++) { if (requests[i] == maxRequest) { ret.push_back(i); } } return ret; } };哈希表
1. 两数之和（简单哈希表）
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> hash; for(int i = 0; i < nums.size(); i++){ auto it = hash.find(target - nums[i]); if(it != hash.end()){ return {it->second, i}; } hash[nums[i]] = i; } return {}; } };217. 存在重复元素
class Solution { public: bool containsDuplicate(vector<int>& nums) { unordered_map<int,int> hash; int n = nums.size(); for(int i = 0; i < n; i++){ if(hash[nums[i]] > 0){ return true; } hash[nums[i]]++; } return false; } };697. 数组的度
哈希表的键为元素的值，值为元素的频率与第一次出现的位置，最后一次出现的位置的vector；
class Solution { public: int findShortestSubArray(vector<int>& nums) { unordered_map<int, vector<int>> mp; int n = nums.size(); for (int i = 0; i < n; i++) { if (mp.count(nums[i])) { mp[nums[i]][0]++; mp[nums[i]][2] = i; } else { mp[nums[i]] = {1, i, i}; } } int maxNum = 0, minLen = 0; for (auto& [_, vec] : mp) { if (maxNum < vec[0]) { maxNum = vec[0]; minLen = vec[2] - vec[1] + 1; } else if (maxNum == vec[0]) { if (minLen > vec[2] - vec[1] + 1) { minLen = vec[2] - vec[1] + 1; } } } return minLen; } };128. 最长连续序列(字节面试题)
使用哈希表存储每一个值
- 外层的for循环遍历每一个值，里层的while循环只有当元素是最开始一个的时候才进入。
实际空间相当于n+n，即为O（n）;
class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> num_set; for (const int& num : nums) { num_set.insert(num); } int longestStreak = 0; for (const int& num : num_set) { if (!num_set.count(num - 1)) {//只有当当前的元素前面没有连续元素的情况下才会进入while int currentNum = num; int currentStreak = 1; while (num_set.count(currentNum + 1)) { currentNum += 1; currentStreak += 1; } longestStreak = max(longestStreak, currentStreak); } } return longestStreak; } };5268. 找出两数组的不同(set即可)
class Solution { public: vector<vector<int>> findDifference(vector<int> &nums1, vector<int> &nums2) { set<int> s1, s2; for (auto i : nums1) s1.insert(i); for (auto i : nums2) s2.insert(i); vector<int> ans1, ans2; for (auto i : s1) if (s2.find(i) == s2.end()) ans1.push_back(i); for (auto i : s2) if (s1.find(i) == s1.end()) ans2.push_back(i); return vector<vector<int>>{ans1, ans2}; } };890. 查找和替换模式（构建哈希表来映射）
```cpp class Solution { bool match(string &word, string &pattern) {
unordered_map<char, char> mp; unordered_set<char> hashset; for (int i = 0; i < word.length(); ++i) { char x = word[i], y = pattern[i]; if (!mp.count(x)&&!hashset.count(y)) { mp[x] = y; hashset.insert(y); } else if (mp[x] != y) { // word 中的同一字母必须映射到 pattern 中的同一字母上 return false; } } return true;}
public:
vector
<a name="JOqof"></a>
## 前缀和
<a name="g6zuC"></a>
### [303. 区域和检索 - 数组不可变](https://leetcode-cn.com/problems/range-sum-query-immutable/)
```cpp
class NumArray {
public:
vector<int> sums;
NumArray(vector<int>& nums) {
int n = nums.size();
sums.resize(n + 1);
for (int i = 0; i < n; i++) {
sums[i + 1] = sums[i] + nums[i];
}
}
int sumRange(int i, int j) {
return sums[j + 1] - sums[i];
}
};
304. 二维区域和检索 - 矩阵不可变（dp+前缀和）
用动态规划计算出每个矩阵的前缀和，直接返回即可
class NumMatrix { private: vector<vector<int>> matrix1; public: NumMatrix(vector<vector<int>>& matrix):matrix1(matrix.size()+1, vector<int>(matrix[0].size()+1)) { for(int i = 1; i <= matrix.size(); i++){ for(int j = 1; j <= matrix[0].size();j++){ if(i == 1){ matrix1[i][j] = matrix1[i][j-1] + matrix[i-1][j-1]; } else if(j == 1){ matrix1[i][j] = matrix1[i-1][j] + matrix[i-1][j-1]; } else { matrix1[i][j] = matrix1[i][j-1]+matrix1[i-1][j]-matrix1[i-1][j-1]+matrix[i-1][j-1]; } } } } int sumRegion(int row1, int col1, int row2, int col2) { return matrix1[row2+1][col2+1]-matrix1[row1][col2+1]-matrix1[row2+1][col1]+matrix1[row1][col1]; } };
560. 和为 K 的子数组（哈希表+前缀和）
- 就是使用前缀和之后
使用哈希表。类似两数只和，不过这里是两数之差
class Solution { public: int subarraySum(vector<int>& nums, int k) { int count = 0, pusm = 0; unordered_map<int,int> hash; hash[0] = 1 ; //注意这里 for(int i : nums){ pusm += i; count += hash[pusm - k]; ++hash[pusm]; } return count; } }; //这里的想法非常巧妙，每个位置的前面的子串之和只要等于k就一定是属于有效的字串，就算前缀和与前面的某个地方相等 //也不会出现干扰的情况，脑袋里的想法要分的清除，子集之间没有交叉线段树（模板）
初始化
vector<int> segmentTree;//线段树数组 int n;建树操作
void build(int node, int s, int e, vector<int> &nums) {//node为下标，s和e分别为线段树的左右边界，nums为初始化的数组 if (s == e) { segmentTree[node] = nums[s]; return; } int m = s + (e - s) / 2; build(node * 2 + 1, s, m, nums); build(node * 2 + 2, m + 1, e, nums); segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2]; }change操作
void change(int index, int val, int node, int s, int e) {//修改操作，node为线段树索引，index为要修改的数字索引，s和e是左右边界 if (s == e) {//找到指定点 segmentTree[node] = val; return; } int m = s + (e - s) / 2; if (index <= m) { change(index, val, node * 2 + 1, s, m); } else { change(index, val, node * 2 + 2, m + 1, e); } segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2]; }range计算区间和
int range(int left, int right, int node, int s, int e) {//求和 if (left == s && right == e) { return segmentTree[node]; } int m = s + (e - s) / 2; if (right <= m) { return range(left, right, node * 2 + 1, s, m); } else if (left > m) { return range(left, right, node * 2 + 2, m + 1, e); } else { return range(left, m, node * 2 + 1, s, m) + range(m + 1, right, node * 2 + 2, m + 1, e); } }结合上面所有
class NumArray { public: vector<int> tr; int n; NumArray(vector<int>& nums):n(nums.size()), tr(nums.size()*4) { build(0, 0, n-1, nums); } void build(int index, int l , int r, vector<int>& nums) { if(l == r) { tr[index] = nums[l]; return; } int mid = l + (r - l)/2; build(index*2+1, l ,mid, nums); build(index*2+2, mid+1, r, nums); tr[index] = tr[index*2+1] + tr[index*2+2]; } void change(int index, int i, int l, int r, int value) { if( l == r) { tr[index] = value; return; } int m = l + (r - l)/2; if(i <= m) { change(index*2+1, i, l, m, value); } else { change(index*2+2, i, m+1, r, value); } tr[index] = tr[index*2+1] + tr[index*2+2]; } int getsum(int index, int start, int end, int l ,int r) { if(start == l&&r == end) { return tr[index]; } int m = l + (r - l)/2; if(end <= m) { return getsum(index*2+1, start, end, l, m); } else if(start > m) { return getsum(index*2+2, start, end, m+1, r); } else { return getsum(index*2+1, start, m, l, m) + getsum(index*2+2, m+1, end, m+1, r); } } void update(int index, int val) { change(0, index, 0, n-1, val); } int sumRange(int left, int right) { return getsum(0, left, right, 0, n-1); } };307. 区域和检索 - 数组可修改
一个经典的线段树题目
千万注意下标从1开始！！！！！！！！！
千万注意传进来的所有下标都要+1！！！！！ ```cpp class NumArray { private: vector
segmentTree; int n; void build(int node, int s, int e, vector
&nums) { if (s == e) { segmentTree[node] = nums[s]; return; } int m = s + (e - s) / 2; build(node * 2 + 1, s, m, nums); build(node * 2 + 2, m + 1, e, nums); segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2];}
void change(int index, int val, int node, int s, int e) {
if (s == e) { segmentTree[node] = val; return; } int m = s + (e - s) / 2; if (index <= m) { change(index, val, node * 2 + 1, s, m); } else { change(index, val, node * 2 + 2, m + 1, e); } segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2];}
int range(int left, int right, int node, int s, int e) {
if (left == s && right == e) { return segmentTree[node]; } int m = s + (e - s) / 2; if (right <= m) { return range(left, right, node * 2 + 1, s, m); } else if (left > m) { return range(left, right, node * 2 + 2, m + 1, e); } else { return range(left, m, node * 2 + 1, s, m) + range(m + 1, right, node * 2 + 2, m + 1, e); }}
public:
NumArray(vector
void update(int index, int val) {
change(index, val, 0, 0, n - 1);
}
int sumRange(int left, int right) {
return range(left, right, 0, 0, n - 1);
}
};
<a name="KE3bC"></a>
## <br />
<a name="aZkr4"></a>
## 线段树模板（动态开点+懒标记）
- 之所以动态开点是因为值域达到1e9，常规的线段树是开4*n的空间，这里就超出空间了。因此只有当前节点用到的时候才开点，采用动态开点的方式。
- 懒标记是因为区间更新的复杂度太高，可以将要更新的值存在懒标记lz中，等待合适的时候一起更新，能够非常有效的降低复杂度。
```cpp
struct Node {//线段树节点
int v, lz, ls, rs;
Node(): v(0), lz(0), ls(0), rs(0) {}//lz应该是懒标记，ls，rs分别是左孩子和右孩子。v是值
};
class SegTree {
vector<Node> tr;
int cnt;//拥有一个cnt来进行动态开点
void push_down(int p) {
if (!tr[p].ls) tr[p].ls = ++cnt, tr.emplace_back(Node{});
if (!tr[p].rs) tr[p].rs = ++cnt, tr.emplace_back(Node{});
if (!tr[p].lz) return;//如果懒标记不存在，则直接返回。
int lz = tr[p].lz; // 子节点需要增加的高度，父节点一般更新了。
tr[tr[p].ls].v += lz;
tr[tr[p].rs].v += lz;
tr[tr[p].ls].lz += lz;
tr[tr[p].rs].lz += lz;
tr[p].lz = 0;
}
void push_up(int p) {
tr[p].v = max(tr[tr[p].ls].v, tr[tr[p].rs].v);//取到左右子节点最大的val，因此此处不是求和，而是求最大访问次数
}
public:
SegTree(): tr(1), cnt(0) {}
void modify(int l, int r, int L, int R, int v, int p = 0) { // 给[l,r]加v
if (l <= L && r >= R) {//给的区间l和r包含tr[p]代表的区间L和R
tr[p].lz += v, tr[p].v += v;//值加上去，同时懒标记。
//懒标记，子节点还没有更新，在下次查询以及区间修改时更新。
return;
}
int mid = (L + R - 1) / 2;
push_down(p);//像子节点递归之前需要传递懒标记
if (mid >= l) modify(l, r, L, mid, v, tr[p].ls);
if (mid < r) modify(l, r, mid + 1, R, v, tr[p].rs);
push_up(p);
}
int query(int l, int r, int L, int R, int p = 0) { // 查询[l,r]最值
if (l <= L && r >= R) return tr[p].v;//如果包住了，就代表找到了
int mid = (L + R - 1) / 2, ret = 0;
push_down(p);
if (mid >= l) ret = max(ret, query(l, r, L, mid, tr[p].ls));
if (mid < r) ret = max(ret, query(l, r, mid + 1, R, tr[p].rs));
return ret;
}
};
729. 我的日程安排表 I
// 动态开点(区间最值)
// modify:给区间[l,r]加v
// query:查询[l,r]最值
struct Node {//线段树节点
int v, lz, ls, rs;
Node(): v(0), lz(0), ls(0), rs(0) {}//lz应该是懒标记，ls，rs分别是左孩子和右孩子。v是值
};
class SegTree {
vector<Node> tr;
int cnt;//拥有一个cnt来进行动态开点
void push_down(int p) {
if (!tr[p].ls) tr[p].ls = ++cnt, tr.emplace_back(Node{});
if (!tr[p].rs) tr[p].rs = ++cnt, tr.emplace_back(Node{});
if (!tr[p].lz) return;//如果懒标记不存在，则直接返回。
int lz = tr[p].lz; // 子节点需要增加的高度，父节点一般更新了。
tr[tr[p].ls].v += lz;
tr[tr[p].rs].v += lz;
tr[tr[p].ls].lz += lz;
tr[tr[p].rs].lz += lz;
tr[p].lz = 0;
}
void push_up(int p) {
tr[p].v = max(tr[tr[p].ls].v, tr[tr[p].rs].v);//取到左右子节点最大的val，因此此处不是求和，而是求最大访问次数
}
public:
SegTree(): tr(1), cnt(0) {}
void modify(int l, int r, int L, int R, int v, int p = 0) { // 给[l,r]加v
if (l <= L && r >= R) {//给的区间l和r包含tr[p]代表的区间L和R
tr[p].lz += v, tr[p].v += v;//值加上去，同时懒标记。
//懒标记，子节点还没有更新，在下次查询以及区间修改时更新。
return;
}
int mid = (L + R - 1) / 2;
push_down(p);//像子节点递归之前需要传递懒标记
if (mid >= l) modify(l, r, L, mid, v, tr[p].ls);
if (mid < r) modify(l, r, mid + 1, R, v, tr[p].rs);
push_up(p);
}
int query(int l, int r, int L, int R, int p = 0) { // 查询[l,r]最值
if (l <= L && r >= R) return tr[p].v;//如果包住了，就代表找到了
int mid = (L + R - 1) / 2, ret = 0;
push_down(p);
if (mid >= l) ret = max(ret, query(l, r, L, mid, tr[p].ls));
if (mid < r) ret = max(ret, query(l, r, mid + 1, R, tr[p].rs));
return ret;
}
};
class MyCalendar {
public:
SegTree seg;
int M = 1e9;
MyCalendar() {
}
bool book(int start, int end) {
int ok = seg.query(start, end - 1, 0, 1e9);
if (ok) return false;//如果不为0，就代表之前已经出现了重叠的区间
seg.modify(start, end - 1, 0, 1e9, 1);
return true;
}
};
731. 我的日程安排表 II
上一题的模板稍微改动一点就能够把这一题写了
struct Node {//线段树节点
int v, lz, ls, rs;
Node(): v(0), lz(0), ls(0), rs(0) {}//lz应该是懒标记，ls，rs分别是左孩子和右孩子。v是值
};
class SegTree {
vector<Node> tr;
int cnt;//拥有一个cnt来进行动态开点
void push_down(int p) {
if (!tr[p].ls) tr[p].ls = ++cnt, tr.emplace_back(Node{});
if (!tr[p].rs) tr[p].rs = ++cnt, tr.emplace_back(Node{});
if (!tr[p].lz) return;//如果懒标记不存在，则直接返回。
int lz = tr[p].lz; // 子节点需要增加的高度，父节点一般更新了。
tr[tr[p].ls].v += lz;
tr[tr[p].rs].v += lz;
tr[tr[p].ls].lz += lz;
tr[tr[p].rs].lz += lz;
tr[p].lz = 0;
}
void push_up(int p) {
tr[p].v = max(tr[tr[p].ls].v, tr[tr[p].rs].v);//取到左右子节点最大的val，因此此处不是求和，而是求最大访问次数
}
public:
SegTree(): tr(1), cnt(0) {}
void modify(int l, int r, int L, int R, int v, int p = 0) { // 给[l,r]加v
if (l <= L && r >= R) {//给的区间l和r包含tr[p]代表的区间L和R
tr[p].lz += v, tr[p].v += v;//值加上去，同时懒标记。
//懒标记，子节点还没有更新，在下次查询以及区间修改时更新。
return;
}
int mid = (L + R - 1) / 2;
push_down(p);//像子节点递归之前需要传递懒标记
if (mid >= l) modify(l, r, L, mid, v, tr[p].ls);
if (mid < r) modify(l, r, mid + 1, R, v, tr[p].rs);
push_up(p);
}
int query(int l, int r, int L, int R, int p = 0) { // 查询[l,r]最值
if (l <= L && r >= R) return tr[p].v;//如果包住了，就代表找到了
int mid = (L + R - 1) / 2, ret = 0;
push_down(p);
if (mid >= l) ret = max(ret, query(l, r, L, mid, tr[p].ls));
if (mid < r) ret = max(ret, query(l, r, mid + 1, R, tr[p].rs));
return ret;
}
};
class MyCalendarTwo {
public:
SegTree seg;
MyCalendarTwo() {
}
bool book(int start, int end) {
int ok = seg.query(start, end -1, 0, 1e9);
if(ok == 2) return false;
else {
seg.modify(start, end-1, 0, 1e9, 1);
return true;
}
}
};
732. 我的日程安排表 III
上一题的模板稍微改动一点就能够把这一题写了
struct Node {//线段树节点
int v, lz, ls, rs;
Node(): v(0), lz(0), ls(0), rs(0) {}//lz应该是懒标记，ls，rs分别是左孩子和右孩子。v是值
};
class SegTree {
vector<Node> tr;
int cnt;//拥有一个cnt来进行动态开点
void push_down(int p) {
if (!tr[p].ls) tr[p].ls = ++cnt, tr.emplace_back(Node{});
if (!tr[p].rs) tr[p].rs = ++cnt, tr.emplace_back(Node{});
if (!tr[p].lz) return;//如果懒标记不存在，则直接返回。
int lz = tr[p].lz; // 子节点需要增加的高度，父节点一般更新了。
tr[tr[p].ls].v += lz;
tr[tr[p].rs].v += lz;
tr[tr[p].ls].lz += lz;
tr[tr[p].rs].lz += lz;
tr[p].lz = 0;
}
void push_up(int p) {
tr[p].v = max(tr[tr[p].ls].v, tr[tr[p].rs].v);//取到左右子节点最大的val，因此此处不是求和，而是求最大访问次数
}
public:
SegTree(): tr(1), cnt(0) {}
void modify(int l, int r, int L, int R, int v, int p = 0) { // 给[l,r]加v
if (l <= L && r >= R) {//给的区间l和r包含tr[p]代表的区间L和R
tr[p].lz += v, tr[p].v += v;//值加上去，同时懒标记。
//懒标记，子节点还没有更新，在下次查询以及区间修改时更新。
return;
}
int mid = (L + R - 1) / 2;
push_down(p);//像子节点递归之前需要传递懒标记
if (mid >= l) modify(l, r, L, mid, v, tr[p].ls);
if (mid < r) modify(l, r, mid + 1, R, v, tr[p].rs);
push_up(p);
}
int query(int l, int r, int L, int R, int p = 0) { // 查询[l,r]最值
if (l <= L && r >= R) return tr[p].v;//如果包住了，就代表找到了
int mid = (L + R - 1) / 2, ret = 0;
push_down(p);
if (mid >= l) ret = max(ret, query(l, r, L, mid, tr[p].ls));
if (mid < r) ret = max(ret, query(l, r, mid + 1, R, tr[p].rs));
return ret;
}
};
class MyCalendarThree {
public:
SegTree seg;
int maxs =0;
MyCalendarThree() {
}
int book(int start, int end) {
seg.modify(start, end-1, 0, 1e9, 1);
maxs = max(seg.query(start, end-1, 0, 1e9), maxs);
return maxs;
}
};
1229. 安排会议日程
线段树解法
效率很低，但是是通用解
struct Node {//线段树节点
int v, lz, ls, rs;
Node(): v(0), lz(0), ls(0), rs(0) {}//lz应该是懒标记，ls，rs分别是左孩子和右孩子。v是值
};
class SegTree {
vector<Node> tr;
int cnt;//拥有一个cnt来进行动态开点
void push_down(int p) {
if (!tr[p].ls) tr[p].ls = ++cnt, tr.emplace_back(Node{});
if (!tr[p].rs) tr[p].rs = ++cnt, tr.emplace_back(Node{});
if (!tr[p].lz) return;//如果懒标记不存在，则直接返回。
int lz = tr[p].lz; // 子节点需要增加的高度，父节点一般更新了。
tr[tr[p].ls].v += lz;
tr[tr[p].rs].v += lz;
tr[tr[p].ls].lz += lz;
tr[tr[p].rs].lz += lz;
tr[p].lz = 0;
}
void push_up(int p) {
tr[p].v = min(tr[tr[p].ls].v, tr[tr[p].rs].v);//因为这里要求区间内所有元素都为2，所以应该取最小值
}
public:
SegTree(): tr(1), cnt(0) {}
void modify(int l, int r, int L, int R, int v, int p = 0) { // 给[l,r]加v
if (l <= L && r >= R) {//给的区间l和r包含tr[p]代表的区间L和R
tr[p].lz += v, tr[p].v += v;//值加上去，同时懒标记。
//懒标记，子节点还没有更新，在下次查询以及区间修改时更新。
return;
}
int mid = (L + R - 1) / 2;
push_down(p);//像子节点递归之前需要传递懒标记
if (mid >= l) modify(l, r, L, mid, v, tr[p].ls);
if (mid < r) modify(l, r, mid + 1, R, v, tr[p].rs);
push_up(p);
}
int query(int l, int r, int L, int R, int p = 0) { // 查询[l,r]最值
if (l <= L && r >= R) return tr[p].v;//如果包住了，就代表找到了
int mid = (L + R - 1) / 2, ret = INT_MAX;//ret初始化为最大值。
push_down(p);
if (mid >= l) ret = min(ret, query(l, r, L, mid, tr[p].ls));//根据题目要求取最小值。
if (mid < r) ret = min(ret, query(l, r, mid + 1, R, tr[p].rs));
return ret;
}
};
class Solution {
public:
vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
SegTree segtree;
vector<int> ends;
for(int i = 0; i < slots1.size(); i++) {
segtree.modify(slots1[i][0], slots1[i][1], 0, 1e9, 1);
ends.push_back(slots1[i][0]);
}
for(int i = 0; i < slots2.size(); i++) {
segtree.modify(slots2[i][0], slots2[i][1], 0, 1e9, 1);
ends.push_back(slots2[i][0]);
}
sort(ends.begin(), ends.end());
for(int i = 0; i < ends.size(); i++) {
if(segtree.query(ends[i], ends[i]+duration, 0, 1e9) == 2) {
return {ends[i], ends[i]+duration};
}
}
return {};
}
};
双指针+排序+贪心
效率高，但是不太好想。
class Solution {
public:
// 排序 + 双指针
static bool cmp(vector<int> &a, vector<int> &b) {return a[0] < b[0];}
vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
int m = slots1.size(), n = slots2.size();
sort(slots1.begin(), slots1.end(), cmp); // 按照区间开始时间排序
sort(slots2.begin(), slots2.end(), cmp);
int i = 0, j = 0, start, end;
while (i < m && j < n) {
start = max(slots1[i][0], slots2[j][0]); // 空闲区间的开始
end = min(slots1[i][1], slots2[j][1]); // 空闲区间的结束
if (end - start >= duration) { // 空闲时间可以满足需要
return {start, start + duration}; // 返回最早的一个区间
}
slots1[i][1] < slots2[j][1] ? i++ : j++;//根据end来移动双指针
}
return {}; // 找不到满足条件的区间
}
};
699. 掉落的方块
- 这题依然可以套上面的模板，但是因为计算目标不一样，因此需要一些调整。
这题计算方式和上面的题目不同，因为这一题，不只是重叠的区间会增加。在根节点下所有范围的节点都应该变为根节点当前的最大节点。区别在于modify里面
之前
这里因为区间并不为一个整体，如果1~3 和 2~4 都为1，重叠起来，只有2~3为2 ，因此懒标记存储的是增加的值。
void modify(int l, int r, int L, int R, int v, int p = 0) { // 给[l,r]加v if (l <= L && r >= R) {//给的区间l和r包含tr[p]代表的区间L和R tr[p].lz += v, tr[p].v += v;//值加上去，同时懒标记。 //懒标记，子节点还没有更新，在下次查询以及区间修改时更新。 return; } int mid = (L + R - 1) / 2; push_down(p);//像子节点递归之前需要传递懒标记 if (mid >= l) modify(l, r, L, mid, v, tr[p].ls); if (mid < r) modify(l, r, mid + 1, R, v, tr[p].rs); push_up(p); }现在
这里因为一个区间代表一个方块是不可分割的，如果如果1~3 和 2~4 都为1，重叠起来2~4都为2，因此懒标记存储的应该是这个区域里面的最大值。这里是直接覆盖原值，而不是相加
void modify(int l, int r, int L, int R, int v, int p = 0) { // 给[l,r]加v if (l <= L && r >= R) {//给的区间l和r包含tr[p]代表的区间L和R tr[p].v = v;//这里直接覆盖，所有在方块范围的值全部覆盖，也就是说父节点的所有儿子节点全部覆盖为最大值。 tr[p].lz = tr[p].v; //懒标记，子节点还没有更新，在下次查询以及区间修改时更新。 return; } int mid = (L + R - 1) / 2; push_down(p);//像子节点递归之前需要传递懒标记 if (mid >= l) modify(l, r, L, mid, v, tr[p].ls); if (mid < r) modify(l, r, mid + 1, R, v, tr[p].rs); push_up(p); }题解
struct Node {//线段树节点 int v, lz, ls, rs; Node(): v(0), lz(0), ls(0), rs(0) {}//lz应该是懒标记，ls，rs分别是左孩子和右孩子。v是值 }; class SegTree { public: vector<Node> tr; int cnt;//拥有一个cnt来进行动态开点 void push_down(int p) { if (!tr[p].ls) tr[p].ls = ++cnt, tr.emplace_back(Node{}); if (!tr[p].rs) tr[p].rs = ++cnt, tr.emplace_back(Node{}); if (!tr[p].lz) return;//如果懒标记不存在，则直接返回。 int lz = tr[p].lz; // 子节点需要增加的高度，父节点一般更新了。 tr[tr[p].ls].v = lz; tr[tr[p].rs].v = lz; tr[tr[p].ls].lz = lz; tr[tr[p].rs].lz = lz; tr[p].lz = 0; } void push_up(int p) { tr[p].v = max(tr[tr[p].ls].v, tr[tr[p].rs].v);//取到左右子节点最大的val，因此此处不是求和，而是求最大访问次数 } public: SegTree(): tr(1), cnt(0) {} void modify(int l, int r, int L, int R, int v, int p = 0) { // 给[l,r]加v if (l <= L && r >= R) {//给的区间l和r包含tr[p]代表的区间L和R tr[p].v = v;//值加上去，同时懒标记 tr[p].lz = tr[p].v; //懒标记，子节点还没有更新，在下次查询以及区间修改时更新。 return; } int mid = (L + R - 1) / 2; push_down(p);//像子节点递归之前需要传递懒标记 if (mid >= l) modify(l, r, L, mid, v, tr[p].ls); if (mid < r) modify(l, r, mid + 1, R, v, tr[p].rs); push_up(p); } int query(int l, int r, int L, int R, int p = 0) { // 查询[l,r]最值 if (l <= L && r >= R) return tr[p].v;//如果包住了，就代表找到了 int mid = (L + R - 1) / 2, ret = 0; push_down(p); if (mid >= l) ret = max(ret, query(l, r, L, mid, tr[p].ls)); if (mid < r) ret = max(ret, query(l, r, mid + 1, R, tr[p].rs)); return ret; } }; class Solution { public: vector<int> fallingSquares(vector<vector<int>>& positions) { vector<int> ret; SegTree seg; int maxs = 0; for(auto it : positions) { int cur = seg.query(it[0], it[0]+it[1]-1, 0, 1e8+1e6); seg.modify(it[0], it[0]+it[1]-1, 0, 1e8+1e6,cur + it[1]); maxs = max(maxs, seg.query(it[0], it[0]+it[1]-1, 0, 1e8+1e6)); ret.push_back(maxs); } return ret; } };红黑树
6066. 统计区间中的整数数目（可以使用set二分查找）
周赛的第四题，没写出来。
思路很重要，使用set容器，红黑树作为底层，因为元素是排序的状态可以使用lower_bound二分查找。红黑树可以自动对插入的元素进行排序，因为是排序的状态因此可以用二分法进行操作。 ```cpp class CountIntervals { typedef pair
int ans = 0; set
st;//顺序容器，可以使用二分查找。
public: CountIntervals() { }
void add(int left, int right) {
int L = left, R = right;
auto it = st.lower_bound(pii(left - 1, -2e9));//二分查找第一个右端点大于等于left-1的节点。
while (it != st.end()) {
if (it->second > right + 1) break;//如果当前节点的左端点大于add的右端点则跳出。
L = min(L, it->second);//找出最大的L和R
R = max(R, it->first);
ans -= it->first - it->second + 1;//减去当前节点的值
st.erase(it++);//删除当前节点的值。
}
ans += R - L + 1;//加上合并之后的节点的范围。
st.insert(pii(R, L));//插入合并之后的节点，问题在于插入之后能够自动排序。
}
int count() {
return ans;
}
};
<a name="YviZF"></a>
### [715. Range 模块](https://leetcode.cn/problems/range-module/)
- 线段树超时
- 一道非常细节的困难题，借用线段树的思想，定义map固定每个区间，key是右边界，value是左边界，在add中，最重要的步骤是合并重合的小区间为一个大区间，这就需要定义好l和r，不断寻找重合区间的最大右边界和最小左边界，并删除其中的小区间，最后将大区间放入map中，query函数实现起来更为简单，同样找右边界大于left的区间，判断区间是否全包围，没有返回false，全包围返回true。remove函数需要考虑三种情况，一种区间左边出了一点，一种区间右边出了一点，一种全在删除区间内，第一种情况需要新建一个区间在map中，以前的区间要和全删除区间一起删除，第二种直接更改区间即可，因为key没有变，代码如下：
- **看两个区间能不能合并就看前一个的尾巴和后面一个的头部能不能交叉。**
- **看区间删除完全删除就看删除区间的尾巴是否大于当前区间的尾巴，如果大于，则完全删除，然后迭代删除后面的区间。如果小于或等于则代表右边还能留有空白，并break；**
- **map<int,int> 里面存储的右边界以及左边界，每个元素都应该是不能合并的，也就是不想交的。如果相交的都会合并。**
```cpp
class RangeModule {
private:
map<int, int> mp;
public:
RangeModule() {
}
void addRange(int left, int right) {
int l = left, r = right;
// 找到刚好大于等于l的区间
auto p = mp.lower_bound(left);
// 合并重合区间
while(p != mp.end() && p->second <= right) {
l = min(p->second, l);
r = max(p->first, r);
auto temp = p;
p ++;
mp.erase(temp->first);
}
mp[r] = l;
}
bool queryRange(int left, int right) {
// 找到大于等于left的区间
auto temp = mp.lower_bound(left);
if(temp == mp.end()) return false;
if(temp->second <= left && temp->first >= right) return true;
return false;
}
void removeRange(int left, int right) {
// 找到大于等于left的区间
auto p = mp.lower_bound(left + 1);
while(p != mp.end() && p->second <= right) {
// 左边有可用区间
if(p->second < left) {
mp[left] = p->second;
}
// 右边有可用区间
if(p->first > right) {
mp[p->first] = right;
break;
} else {// 否则全部删除
auto temp = p;
p ++;
mp.erase(temp->first);
}
}
}
};
若有收获，就点个赞吧
0 人点赞
