lcOrderedSet - 有序集合1
1 有序集合
泛指set, map, pirority_queue等能够按照key进行排序，然后使用lower_bound和upper_bound来进行log(n)复杂度查询的基础数据结构
(注意priority_queue仅能够在堆顶进行操作)
示例如下：
1 | set<int, std::less<int>> spareServers; |
2 具体示例
0363maxSumSubMatrix 最大子区域和
1 题目：
https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/
2 解题思路：
- 1 普通思路：一维前缀和，按行计算前缀和，使用m x n的矩阵存储，然后计算矩形区域，则只需要O(m)的计算复杂度
- 2 优化：二维前缀和，pre[i][j]存储的是0，0到i，j处的矩形区域和，那么计算方式为：
preMat2[i+1][j+1] = preMat2[i][j+1] + preMat2[i+1][j] - preMat2[i][j] + matrix[i][j];
- 3 使用二位前缀和去计算子区域的和，搜索子区域的方式：
- 3.1 对于每个子区域的上下边界搜索左右边界，上下左边界搜索复杂度为o(n^2), 而后搜索左右边界，对于每一个右边界O(n)，搜索左边界，什么样的左边界？left满足sum(up, down, 0, right) - k <= sum(up, down, 0, left), 也就是在[0, right]的范围内找到最小的大于sum(up, down, 0, right) - k的left，在遍历的过程中使用set存所有的sum(up, down, 0, right), 在这个set里面找left，使用lower_bound函数，只需要log(n)复杂度，于是总复杂度为 o(m^2 * nlog(n))
- 3.2 上述核心思想： 本来需要找right和left的对子，但是现在借助k，找left就变成在right的历史中搜索即可
- 3.2.1 原来思想：sum(up, down, 0, right) - sum(up, down, 0, left) <= k
- 3.2.2 新的思想：sum(up, down, 0, right) - k <= sum(up, down, 0, left)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41class Solution {
public:
static constexpr int matLen = 102;
vector<vector<int>> preMat; // 2d prefix sum
int m = -1;
int n = -1;
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
// cal 2d prefix sum
m = matrix.size();
n = matrix[0].size();
preMat.resize(m+1, vector<int>(n+1, 0));
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
preMat[i+1][j+1] = preMat[i][j+1] + preMat[i+1][j] - preMat[i][j] + matrix[i][j];
// cout << preMat[i+1][j+1] << endl;
}
}
// for each up and down, find max l,r
int res = INT_MIN;
for(int d = 0; d < m; ++d) {
for(int u = d; u >= 0; --u) {
set<int> lSet = {0};
for(int r = 0; r < n; ++r) {
int sumRight = sumRegion(u, d, 0, r);
set<int>::iterator lbPtr = lSet.lower_bound(sumRight - k);
lSet.insert(sumRight);
if(lbPtr != lSet.end()) {
res = max(res, sumRight - *lbPtr);
}
}
}
}
return res;
}
int sumRegion(int up, int down, int left, int right) {
return preMat[down+1][right+1] - preMat[down+1][left] - preMat[up][right+1] - preMat[up][left];
}
};
0699fallingSquares 掉落的方块
1 题目：
https://leetcode-cn.com/problems/falling-squares/
2 解题思路：
- 1 普通思路：使用一维数组模拟每个位置方块高度，复杂度为o(N^2)，由于N很大，所以会超时
- 2 优化：使用坐标压缩，将所有方块的边界存储在2000以内（因为一共就1000个方块），然后更新高度就按照2000以内去更新即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44class Solution {
public:
vector<int> fallingSquares(vector<vector<int>>& positions) {
// coordinate compression
set<int, std::less<int>> coords;
for(vector<int>& coord : positions) {
coords.insert(coord[0]);
coords.insert(coord[0] + coord[1] - 1);
}
unordered_map<int, int> borderToIdx;
int t = 0;
for(auto& i : coords) {
borderToIdx[i] = t++;
}
// cal heights
vector<int> heights(t);
vector<int> res;
int curHeightest = INT_MIN;
for(vector<int>& square : positions) {
int l = borderToIdx[square[0]];
int r = borderToIdx[square[0] + square[1] - 1];
int h = square[1];
int updatedHeight = update(l, r, h, heights);
curHeightest = max(curHeightest, updatedHeight);
res.emplace_back(curHeightest);
}
return res;
}
// update and return updated height of [l, r]
int update(int l, int r, int h, vector<int>& heights) {
int oldHeight = INT_MIN;
for(int i = l; i <= r; ++i) {
oldHeight = max(oldHeight, heights[i]);
}
int newHeight = INT_MIN;
for(int i = l; i <= r; ++i) {
heights[i] = oldHeight + h;
}
return oldHeight + h;
}
};
0715 Range 模块 rangeModule
1 题目：
https://leetcode-cn.com/problems/range-module/
2 解题思路：
- 1 普通思路：使用map记录这些离散的区间
- 1.1 添加、删除： 遍历map，看map的每一个区间和当前区间的关系，这样处理最为合适
- 1.2 查询：使用upper_bound查询到第一个（左侧）比目标的left小的区间，然后看目标的left和right是否在map对应的区间内部
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144class RangeModule {
public:
map<int, int, std::less<int>> intervals;
RangeModule() {
}
void addRange(int left, int right) {
if(intervals.size() == 0) {
intervals[left] = right;
print();
return ;
}
for(auto it = intervals.begin(); it != intervals.end(); ++it) {
if(it->first >= left) {
if(it->first > right) {
continue;
}
while(it != intervals.end() && it->second <= right) {
it = intervals.erase(it);
}
if(it == intervals.end()){
intervals[left] = right;
} else {
if(it->first <= right) {
int newRight = it->second;
intervals.erase(it);
intervals[left] = newRight;
}else {
intervals[left] = right;
}
}
print();
return;
} else { // it->first < left
if(it->second < left) {
continue;
}
int newLeft = it->first;
while(it != intervals.end() && it->second <= right) {
it = intervals.erase(it);
}
if(it == intervals.end()){
intervals[newLeft] = right;
} else {
if(it->first <= right) {
int newRight = it->second;
intervals.erase(it);
intervals[newLeft] = newRight;
}else {
intervals[newLeft] = right;
}
}
print();
return;
}
}
intervals[left] = right;
print();
}
bool queryRange(int left, int right) {
if(intervals.empty()) {
return false;
}
auto lBig = intervals.upper_bound(left);
if(lBig != intervals.begin()) {
--lBig;
return lBig->second >= right;
} else {
return false;
}
return false;
}
void removeRange(int left, int right) {
// for(auto it = intervals.begin(); it != intervals.end(); ++it) {
// for(int i = 0)
// }
auto lBig = intervals.lower_bound(left);
int newLeft = 0;
if(lBig != intervals.begin()) {
// cout << "d1.5" << endl;
--lBig;
if(right < lBig->second) {
intervals[right] = lBig->second;
intervals[lBig->first] = left;
print();
return ;
} else {
// cout << "d2" << endl;
if(lBig->second > left) {
// cout << "d2.5" << endl;
intervals[lBig->first] = left;
}
}
++lBig;
while (lBig != intervals.end() && lBig->second < right) {
lBig = intervals.erase(lBig);
}
if(lBig != intervals.end()) {
if(lBig->first < right) {
int secondRight = lBig->second;
intervals.erase(lBig);
intervals[right] = secondRight;
}
}
} else {
while (lBig != intervals.end() && lBig->second < right) {
lBig = intervals.erase(lBig);
}
if(lBig != intervals.end()) {
if(lBig->first < right) {
int secondRight = lBig->second;
intervals.erase(lBig);
intervals[right] = secondRight;
}
}
}
print();
}
void print() {
// cout << "-----st-----" << endl;
// for(auto it = intervals.begin(); it != intervals.end(); ++it) {
// cout << it->first << " " << it->second << endl;
// }
// cout << "-----ed-----" << endl;
}
};
/**
* Your RangeModule object will be instantiated and called as such:
* RangeModule* obj = new RangeModule();
* obj->addRange(left,right);
* bool param_2 = obj->queryRange(left,right);
* obj->removeRange(left,right);
*/
0850. 矩形面积 II
1 题目：
https://leetcode-cn.com/problems/rectangle-area-ii/solution
2 解题思路：
- 1 参考官方思路的扫描线：https://leetcode-cn.com/problems/rectangle-area-ii/solution/ju-xing-mian-ji-ii-by-leetcode/
- 2 总结过程：
- 2.1 将一个矩形看成x1,x2,y1,ST; x1,x2,y2,ED;的两条线
- 2.2 而后用active记录还没有遇到ED的那些矩形的第一个扫描线集合，每回新来了一根线，则将active中的所有线和当前线计算对应面面积加起来
- 2.3 当active中遇到了矩形的ED，则将active中对应的矩形的ST删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125class Solution {
public:
static constexpr long long bigPrime = 1000000007;
int rectangleArea(vector<vector<int>>& rectangles) {
// lines
int ST = 0;
int ED = 1;
vector<vector<int>> lines;
for(auto& vec : rectangles) {
lines.emplace_back(vector<int>{vec[0], vec[2], vec[1], ST});
lines.emplace_back(vector<int>{vec[0], vec[2], vec[3], ED});
}
// sort the lines by the y
sort(lines.begin(), lines.end(),
[](vector<int>& a, vector<int>& b) {
return a[2] < b[2];
});
// scan the lines
vector<vector<int>> actives;
long long res = 0;
int lastY = lines[0][2];
for(auto& line : lines) {
int curY = line[2], type = line[3], x1 = line[0], x2 = line[1];
int width = 0;
int actX = -1;
// actives: those opend lines, sorted by y
for(auto& act : actives) {
// cout << "act: " << act[0] << " " << act[1] << endl;
actX = max(actX, act[0]);
width += max(act[1] - actX, 0);
actX = max(actX, act[1]);
}
res += static_cast<long long>(width) * (curY - lastY) % bigPrime;
// cout << "w: " << width << endl;
// add new actives
if(type == ST) {
actives.emplace_back(vector<int>{x1, x2, curY, type});
// cout << "insert x1,2: " << x1 << " " << x2 << endl;
// sort the opend lines of the started points
sort(actives.begin(), actives.end(),
[](vector<int>& line1, vector<int>& line2) {
return line1[0] < line2[0];
});
} else {
// find the active and rm it
for(int i = 0; i < actives.size(); ++i) {
if(actives[i][0] == x1 && actives[i][1] == x2) {
actives.erase(actives.begin() + i);
// cout << "earse x1,2: " << x1 << " " << x2 << endl;
break;
}
}
}
lastY = curY;
}
return res % bigPrime;
}
vector<vector<int>> getSkyLine(vector<vector<int>>& buildings) {
function<bool(pair<int, int>&, pair<int, int>&)> cmp =
[](pair<int, int>& a, pair<int, int>& b) {
return a.second < b.second;
};
// <rightBound, height>
priority_queue<pair<int, int>, vector<pair<int, int>>, function<bool(pair<int, int>&, pair<int, int>&)> > queue(cmp);
vector<int> bounds;
vector<vector<int>> res;
int n = buildings.size();
for(int i = 0; i < n; ++i) {
bounds.emplace_back(buildings[i][0]);
bounds.emplace_back(buildings[i][1]);
}
sort(bounds.begin(), bounds.end(), std::less<int>());
// std::cout << "c1" << endl;
int j = 0;
for(auto& curBound : bounds) {
// std::cout << "c " << j << endl;
// push buildings lefter than curBound until one righter meet
while(j < buildings.size() && curBound >= buildings[j][0]) {
queue.push(make_pair(buildings[j][1], buildings[j][2]));
++j;
}
// std::cout << "c " << "adf" << endl;
// pop out those rec unrelevant
while(!queue.empty() && curBound >= queue.top().first) {
queue.pop();
}
int curBoundHeight = queue.empty() ? 0 : queue.top().second;
// if(res.size() == 0 || res.back()[1] != curBoundHeight) {
// res.emplace_back(vector<int>{curBound, curBoundHeight});
// }
if(res.size() == 0 || res.back()[1] != curBoundHeight) {
res.emplace_back(vector<int>{curBound, curBoundHeight});
}
}
return res;
}
void print(vector<vector<int>>& vec) {
for(auto& v : vec) {
for(auto& i : v) {
cout << i << " ";
}
cout << endl;
}
}
};
0895maxFreqStack 最大频率栈
1 题目：
https://leetcode-cn.com/problems/maximum-frequency-stack/
2 解题思路：map/hash栈
- 1 参考官方思路的扫描线：https://leetcode-cn.com/problems/maximum-frequency-stack/solution/zui-da-pin-lu-zhan-by-leetcode/
- 2 总结过程：
- 2.1 首先用map维持每一个变量的频率
- 2.1.1 维持方法： push中对应的key加一，pop对应的key减一
- 2.2 如何获得当前最大频率？
- 2.2.1 在每个变量push和pop的时候我们可以获得对应的key的频率，那么所有的key的频率变动都是在push和pop执行完成之后，那么只需要用一个变量maxFreq维持最大频率即可
- 2.3 知道最大频率，如何获得当前最大频率的变量？
- 2.3.1 使用map<频率，频率对应的数的集合>来记录即可，然后用2.2中使用maxFreq获取最大频率对应的数字的集合，那如何从这个集合中获取在栈顶的数据呢？map<频率，频率对应的数的集合>中 频率对应的数的集合 使用stack去存就好了，因为stack的栈顶总是存着最新来的数据
- 2.4 一个实例： 3，3，3都是push，那么在频率为1，2，3的栈中，很自然的都有一个3，自然体现在哪里呢？现在pop一下，频率为3对应的stack为空，然后最大频率变为2，然后2里面同样是3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44class FreqStack {
public:
int opNum;
map<int, int> opNumMap;
map<int, int> freqMap;
map<int, vector<int>*> groupByFreq;
int maxFreq;
FreqStack() {
}
void push(int val) {
// cout << "pushing st: with max freq: " << maxFreq << endl;
freqMap[val]++;
if(groupByFreq[freqMap[val]] == nullptr) {
groupByFreq[freqMap[val]] = new vector<int>();
}
groupByFreq[freqMap[val]]->emplace_back(val);
maxFreq = max(maxFreq, freqMap[val]);
// cout << "pushing done: " << val << "with maxFreq: " << maxFreq << endl;
}
int pop() {
// cout << "pop st with maxFreq: " << maxFreq << endl;
// find biggest frequency and most newly element to rm
int popRes = groupByFreq[maxFreq]->back();
groupByFreq[maxFreq]->pop_back();
if(groupByFreq[maxFreq]->size() == 0) {
delete groupByFreq[maxFreq];
groupByFreq[maxFreq] = nullptr;
--maxFreq;
}
// cout << "pop ed" << popRes << " with maxFreq: " << maxFreq << endl;
freqMap[popRes]--;
return popRes;
}
};
/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack* obj = new FreqStack();
* obj->push(val);
* int param_2 = obj->pop();
*/
- 2.1 首先用map维持每一个变量的频率
1606busiestServers 找到处理最多请求的服务器
1 题目：
https://leetcode-cn.com/problems/find-servers-that-handled-most-number-of-requests/
2 解题思路：
- 1 自然的思路：对于每一个到来的请求，我们将服务器分为两部分，一部分是空闲服务器，一部分是繁忙服务器
- 1.1 如何快速找到空闲服务器？我们用set记录空闲服务器即可，两次使用lower_bound完成cycle查询
- 1.2 如何记录繁忙服务器？在每一个请求到来以及处理完成，都可能出现繁忙服务器的改动和空闲服务器的改动，于是采用map<到期时间，相应服务器列表>来存储繁忙服务器
- 1.3 如何处理请求处理完成时的服务器从繁忙变为空闲？
- 1.3.1 采用小根堆存储当前所有繁忙服务器的到期时间，那么只需要在请求到来的时候，将所有比当前请求小的到期时间的繁忙服务器变为空闲即可
1 | class Solution { |