Skip to content

Commit fb0daad

Browse files
wisdompeakwisdompeak
committed
Merge branch 'master' of github.com:wisdompeak/LeetCode
2 parents 775d97c + d72b0c5 commit fb0daad

109 files changed

Lines changed: 3354 additions & 644 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎BFS/1136.Parallel-Courses/1136.Parallel-Courses.cpp‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2,11 +2,11 @@ class Solution {
22
public:
33
int minimumSemesters(int N, vector<vector<int>>& relations)
44
{
5-
vector<unordered_set<int>>next(N+1);
5+
vector<vector<int>>next(N+1);
66
vector<int>inDegree(N+1,0);
77
for (auto x:relations)
88
{
9-
next[x[0]].insert(x[1]);
9+
next[x[0]].push_back(x[1]);
1010
inDegree[x[1]] += 1;
1111
}
1212

‎BFS/1810.Minimum-Path-Cost-in-a-Hidden-Grid/1810.Minimum-Path-Cost-in-a-Hidden-Grid.cpp‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
/**
2+
* // This is the GridMaster's API interface.
3+
* // You should not implement it, or speculate about its implementation
4+
* class GridMaster {
5+
* public:
6+
* bool canMove(char direction);
7+
* int move(char direction);
8+
* boolean isTarget();
9+
* };
10+
*/
11+
typedef array<int,3> AI3;
12+
13+
class Solution {
14+
int visited[201][201];
15+
int cost[201][201];
16+
string d = "ULRD";
17+
int targetX, targetY;
18+
vector<pair<int,int>> dir = {{-1,0},{0,-1},{0,1},{1,0}};
19+
20+
public:
21+
int findShortestPath(GridMaster &master)
22+
{
23+
for (int i=0; i<201; i++)
24+
for (int j=0; j<201; j++)
25+
cost[i][j] = -1;
26+
27+
visited[100][100] = 1;
28+
dfs(master, 100, 100);
29+
30+
for (int i=0; i<201; i++)
31+
for (int j=0; j<201; j++)
32+
visited[i][j] = 0;
33+
34+
priority_queue<AI3,vector<AI3>, greater<>>pq;
35+
pq.push({0,100,100});
36+
37+
while (!pq.empty())
38+
{
39+
auto [c,x,y] = pq.top();
40+
pq.pop();
41+
visited[x][y] = 1;
42+
if (x==targetX && y==targetY)
43+
return c;
44+
45+
for (int k=0; k<4; k++)
46+
{
47+
int i = x+dir[k].first;
48+
int j = y+dir[k].second;
49+
if (cost[i][j]==-1) continue;
50+
if (i<0 || i>=200 || j<0|| j>=200) continue;
51+
if (visited[i][j]==1) continue;
52+
53+
pq.push({c+cost[i][j], i, j});
54+
}
55+
}
56+
57+
return -1;
58+
}
59+
60+
void dfs(GridMaster &master, int x, int y)
61+
{
62+
63+
if (master.isTarget())
64+
{
65+
targetX = x;
66+
targetY = y;
67+
}
68+
for (int k=0; k<4; k++)
69+
{
70+
int i = x+dir[k].first;
71+
int j = y+dir[k].second;
72+
if(visited[i][j]==1) continue;
73+
74+
if (master.canMove(d[k]))
75+
{
76+
int c = master.move(d[k]);
77+
visited[i][j] = 1;
78+
cost[i][j] = c;
79+
dfs(master, i,j);
80+
master.move(d[3-k]);
81+
}
82+
else
83+
{
84+
visited[i][j] = 1;
85+
}
86+
}
87+
}
88+
};

‎BFS/1810.Minimum-Path-Cost-in-a-Hidden-Grid/Readme.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
### 1810.Minimum-Path-Cost-in-a-Hidden-Grid
2+
3+
开辟一个200x200的二维矩阵。将起始点设置为(100,100)。先通过DFS走遍所有的格子，标记每个格子的cost和是否是障碍物，以及终点的位置。然后再从起点开始，用Dijkstra算法求得起点到终点的最小权重路径，

‎Binary_Search/1157.Online-Majority-Element-In-Subarray/1157.Online-Majority-Element-In-Subarray.cpp‎

Lines changed: 6 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -20,21 +20,18 @@ class MajorityChecker {
2020
{
2121
int num = q[i].second;
2222
int pos1 = lower_bound(Map[num].begin(), Map[num].end(), left) - Map[num].begin();
23-
int pos2 = upper_bound(Map[num].begin(), Map[num].end(), right) - Map[num].begin() - 1;
23+
int pos2 = upper_bound(Map[num].begin(), Map[num].end(), right) - Map[num].begin();
2424

25-
if (pos2-pos1+1>=threshold)
25+
if (pos2-pos1>=threshold)
2626
return num;
2727
else
28-
total -= pos2-pos1+1;
28+
total -= pos2-pos1;
29+
2930
if (total < threshold)
3031
return -1;
32+
if (Map[num].size() < threshold)
33+
return -1;
3134
}
3235
return -1;
3336
}
3437
};
35-
36-
/**
37-
* Your MajorityChecker object will be instantiated and called as such:
38-
* MajorityChecker* obj = new MajorityChecker(arr);
39-
* int param_1 = obj->query(left,right,threshold);
40-
*/

‎Binary_Search/1157.Online-Majority-Element-In-Subarray/1157.Online-Majority-Element-In-Subarray_SegTree.cpp‎

Lines changed: 74 additions & 110 deletions
Original file line numberDiff line numberDiff line change
@@ -1,140 +1,104 @@
11
class MajorityChecker {
2-
class SegTree
2+
class SegTreeNode
33
{
44
public:
5-
SegTree* left;
6-
SegTree* right;
7-
int val, count;
8-
int start,end;
9-
SegTree(int a, int b):start(a),end(b),val(0),count(0),left(NULL),right(NULL){}
5+
SegTreeNode* left;
6+
SegTreeNode* right;
7+
int start, end;
8+
int info, freqDiff;
9+
SegTreeNode(int a, int b):start(a),end(b),info(0),freqDiff(0),left(NULL),right(NULL){}
1010
};
11-
vector<int>arr;
12-
unordered_map<int,vector<int>>Map;
13-
public:
14-
SegTree* root;
15-
16-
MajorityChecker(vector<int>& arr)
17-
{
18-
this->arr = arr;
19-
root = buildTree(0, arr.size()-1);
20-
for (int i=0; i<arr.size(); i++)
21-
Map[arr[i]].push_back(i);
22-
}
23-
24-
int query(int left, int right, int threshold)
25-
{
26-
int key = 0, val = 0;
27-
searchTreeMajority(root, left, right, key, val);
28-
if (key == 0) return -1;
29-
30-
int pos1 = lower_bound(Map[key].begin(), Map[key].end(), left) - Map[key].begin();
31-
int pos2 = upper_bound(Map[key].begin(), Map[key].end(), right) - Map[key].begin() -1;
32-
33-
if (pos2-pos1+1 >= threshold)
34-
return key;
35-
else
36-
return -1;
37-
}
3811

39-
SegTree* buildTree(int a, int b)
40-
{
41-
SegTree* node = new SegTree(a,b);
42-
43-
if (a == b)
12+
void init(SegTreeNode* node, int a, int b) // init for range [a,b]
13+
{
14+
if (a==b)
4415
{
45-
node->val = arr[a];
46-
node->count = 1;
47-
return node;
16+
node->info = arr[a];
17+
node->freqDiff = 1;
18+
return;
4819
}
4920

5021
int mid = (a+b)/2;
51-
node->left = buildTree(a, mid);
52-
node->right = buildTree(mid+1, b);
53-
54-
if (node->left->val==node->right->val)
22+
if (node->left==NULL)
5523
{
56-
node->val = node->left->val;
57-
node->count = node->left->count + node->right->count;
24+
node->left = new SegTreeNode(a, mid);
25+
node->right = new SegTreeNode(mid+1, b);
5826
}
59-
else if (node->left->count > node->right->count)
27+
init(node->left, a, mid);
28+
init(node->right, mid+1, b);
29+
30+
if (node->left->info == node->right->info)
6031
{
61-
node->val = node->left->val;
62-
node->count = node->left->count - node->right->count;
32+
node->info = node->left->info;
33+
node->freqDiff = node->left->freqDiff + node->right->freqDiff;
6334
}
6435
else
6536
{
66-
node->val = node->right->val;
67-
node->count = node->right->count - node->left->count;
68-
}
69-
70-
if (node->count==0)
71-
node->val = 0;
72-
73-
return node;
37+
if (node->left->freqDiff >= node->right->freqDiff)
38+
{
39+
node->info = node->left->info;
40+
node->freqDiff = node->left->freqDiff - node->right->freqDiff;
41+
}
42+
else
43+
{
44+
node->info = node->right->info;
45+
node->freqDiff = node->right->freqDiff - node->left->freqDiff;
46+
}
47+
}
7448
}
7549

76-
77-
bool searchTreeMajority(SegTree* node, int a, int b, int& key, int& count)
50+
pair<int,int> queryRange(SegTreeNode* node, int a, int b)
7851
{
79-
if (node==NULL || a>b)
80-
return false;
81-
82-
if (node->start>b || node->end<a)
83-
return false;
84-
85-
if (a<=node->start && node->end<=b)
86-
{
87-
key = node->val;
88-
count = node->count;
89-
return key!=0;
90-
}
91-
92-
int key1, key2, count1, count2;
93-
int leftCheck = searchTreeMajority(node->left, a, b, key1, count1);
94-
int rightCheck = searchTreeMajority(node->right, a, b, key2, count2);
95-
96-
if (!leftCheck && !rightCheck)
97-
{
98-
key = 0;
99-
count = 0;
100-
}
101-
else if (!leftCheck && rightCheck)
52+
if (b < node->start || a > node->end )
10253
{
103-
key = key2;
104-
count = count2;
54+
return {0,0};
10555
}
106-
else if (leftCheck && !rightCheck)
56+
if (a <= node->start && b>=node->end)
10757
{
108-
key = key1;
109-
count = count1;
110-
}
58+
return {node->info, node->freqDiff};
59+
}
60+
61+
auto L = queryRange(node->left, a, b);
62+
auto R = queryRange(node->right, a, b);
63+
if (L.first==R.first)
64+
return {L.first, L.second+R.second};
11165
else
11266
{
113-
if (key1==key2)
114-
{
115-
key = key1;
116-
count = count1+count2;
117-
}
118-
else if (count1==count2)
119-
{
120-
key = 0;
121-
count = 0;
122-
}
123-
else if (count1>count2)
124-
{
125-
key = key1;
126-
count = count1-count2;
127-
}
67+
if (L.second>=R.second)
68+
return {L.first, L.second-R.second};
12869
else
129-
{
130-
key = key2;
131-
count = count2-count1;
132-
}
70+
return {R.first, R.second-L.second};
13371
}
134-
135-
return key!=0;
72+
}
73+
74+
SegTreeNode* root;
75+
vector<int> arr;
76+
unordered_map<int,vector<int>>Map;
77+
78+
public:
79+
MajorityChecker(vector<int>& arr)
80+
{
81+
this->arr = arr;
82+
int n = arr.size();
83+
root = new SegTreeNode(0, n-1);
84+
init(root, 0, n-1);
85+
86+
for (int i=0; i<arr.size(); i++)
87+
Map[arr[i]].push_back(i);
13688
}
13789

90+
int query(int left, int right, int threshold)
91+
{
92+
auto [val, freqDiff] = queryRange(root, left, right);
93+
94+
auto pos1 = lower_bound(Map[val].begin(), Map[val].end(), left);
95+
auto pos2 = upper_bound(Map[val].begin(), Map[val].end(), right);
96+
int count = pos2-pos1;
97+
if (count >= threshold)
98+
return val;
99+
else
100+
return -1;
101+
}
138102
};
139103

140104
/**

‎Binary_Search/1157.Online-Majority-Element-In-Subarray/Readme.md‎

Lines changed: 9 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -7,33 +7,16 @@
77
#### Segment Tree
88
本题也可以用线段树来实现，来实现高效地对任意区间内的majority元素的查询．
99

10-
和传统线段树一样，每个节点代表一个区间，并且不断向下二分，直至区间长度为１位置（叶子节点）．但此题最与众不同的技巧就是，每个节点的status记录的是：该区间内频次最高的元素（记录为val），以及val元素与其他非val元素的频次之差（记录为count).
10+
模板和基本型的线段树一样。每个节点需要存放两个信息，val表示该节点所在区间的majority candidate，另外freqDiff表示这个majority candidate在该区间的频次与其他元素的频次差的“最大可能值”。这个思想来自Boyer–Moore majority vote algorithm，可以参考```169.Majority Element```来理解。基本思想就是，如果一个属于majority的元素，与任何一个不属于majority的元素，两者同时消去，那么不影响数组剩下的元素里原本属于majority的元素的地位．
1111

12-
这个思想非常ｄｉａｏ，来自Boyer–Moore majority vote algorithm，可以联系```169.Majority Element```来理解．基本思想就是，如果一个属于majority的元素，与任何一个不属于majority的元素，两者同时消去，那么不影响数组剩下的元素里原本属于majority的元素的地位．
12+
假设区间d，下面二分了两个子区间d1和d2。在d1区间中的majority是val1，它的频次比其他元素多了diff1。同理在d2区间中的majority是val2，它的频次比其他元素多了diff2.首先我们要明确一个概念，d的majority一定只能是val1和val2中的一个。注意我们对于majority的定义是区间内频次大于50%的元素。显然，如果任何一个元素在两个子区间中都不占50%多数，那么在整个大区间中肯定也不会占50%多数。那么我们如何从d1和d2两个子区间的信息里得到区间d的majority呢？
13+
1. 如果val1==val2，那么毫无悬念，区间d的majority就是val1（或者val2）。它在整个区间里的频次优势或达到```diff = diff1+diff2```.
14+
2. 如果va1l!=val2，我们需要两个中间选择一个。
15+
(1) 如果diff1>diff2，则val1相比于val2更有可能是整个区间的majority。但是注意，不一定表示val1就一定真的是majority，因为这个区间可能根本没有majority，所以val1只是best majority candidate。那么对于val1而言，它在d区间内的频率优势如何计算呢？我们取diff的最大可能值：```diff1-diff2```.注意这是一个上限，即认为在d2区间内除了val1就是val2.只有这种情况下，val1才会继续保有最大的正数diff，即确立自己majority的地位。
16+
(2) 反之，如果diff1<diff2，那么我们就认为val2是整个区间的best majority candidate，对应的频率优势是```diff = diff2-diff1```.
1317

14-
假设区间d，下面二分了两个子区间d1和d2．如果在d1区间中的majority是val1,因为根据majority的定义，在d1的区间中val1必然必然比其他非val1元素的总个数还要多，记为count1. 同理，在另一个子区间中我们可以定义val2和count2. 显然，我们根据count1和count2的比较，就可以知道val1和val2谁是在区间d上的majority：
18+
通过上面递归的思想，我们就可以建立起一棵完全二叉树．每个节点代表的一个区间，并且记录了这个区间里的majority candidate的值val，diff表示在该区间内val的频次与非val的频次之差．再次强调，val不见得真的是该区间的majority。
1519

16-
(1) 如果count1>count2，则val1是majority，并且val1在ｄ上比其他元素的总频次还要高出count1-count2，因此记录```count=count1-count2```.
20+
我们基于这棵线段树，设计```queryRangeMajority(root,a,b)```来寻找区间[a,b]内的best majority candidate的数值val。这个query函数的思想和建树时候的递归逻辑一模一样。然后我们需要校验这个val是不是“真”的。怎么做呢？我们提前用hash表来存储所有数值是x的元素的index。用二分法在这些index中找到a和b的位置，这两个位置之差从而就可以知道[a,b]之前到底有多少个val。用这个数目与threshold来比较返回答案。
1721

18-
(2) 反之说明val2是majority,并且val2在ｄ上比其他元素的总频次还要高出count2-count1,```count=count2-count1```.
19-
20-
(3) 如果val1==val2，则更说明val1就是ｄ上的majority，并且它在频次上的优势会更大，变成```count=count2+count1```.
21-
22-
(4) 而如果val1!=val2，但是count1==count2，那就是说明在区间ｄ上并没有唯一的majority（记住majority的定义就是大于50%），因此对于该节点我们就置```val=0```, ```count=0```.
23-
24-
通过上面递归的思想，我们就可以建立起一棵完全二叉树．每个节点代表的一个区间，并且记录了这个区间里的majority（如果存在的话）的值val，并且val的频次要比非val的频次多count个．
25-
26-
然后我们处理query(left,right)时，就可以用这棵树的性质，递归处理得到[left,right]区间内的majority元素ｋｅｙ（如果存在的话）．然后再用二分搜索，在数组中元素ｋｅｙ的所出现的iｎｄｅｘ里（从小到大排列）找到left和right的位置，从而计算出ｋｅｙ实际在[left,right]区间内出现的频次，然后与threshold比较确定答案．
27-
28-
query的具体算法：
29-
30-
(1) 边界条件：如果节点是空指针，或者[left,right]区间与节点自身的区间完全不相交，则这个节点无法提供任何majority的信息，返回key=0, count=0.
31-
32-
(2) 边界条件：如果[left,right]区间完全包括了节点自身的区间完全不相交，则这个节点能够提供在自身区间内的majority的信息，即返回node->val和node->count.
33-
34-
(3) 其他情况（即两个区间只有部分相交，或者节点区间相对于[left,right]而言太大），都只能递归，让更短的子区间去处理．然后根据两个子区间反馈回来的key1,count1和key2,count2，进行合并处理，计算出自身区间内对于[left,right]的贡献．
35-
36-
举个例子，我们想求[3,5]区间内的majority，但root节点区间是[0,7]，宽度太大，所以自身节点的val和count都不能反应这么一个小区间上的情况．显然只能递归考察左节点[0,3]和右节点[4,7]．就这样左子树一路递归，最终返回到root的其实是下面的节点[3,3]带来的key1和count1；　同理右子树一路递归，最终返回到root的其实是下面的节点[4,5]带来的key2和count2．我们此时需要将这两部分归并，仿照上面buildTree的操作，确定root区间内真正应该考察的[3,5]这个子段的majority.
37-
38-
39-
[Leetcode Link](https://leetcode.com/problems/online-majority-element-in-subarray)
22+
[Leetcode Link](https://leetcode.com/problems/online-majority-element-in-subarray)

0 commit comments

Comments
 (0)