8000 20200925 · BoscoSuen/leetcode@cd2f5b6 · GitHub
[go: up one dir, main page]
Skip to content

Commit cd2f5b6

Browse files
BoscoSuenBoscoSuen
committed
20200925
1 parent 42f7ad6 commit cd2f5b6

File tree

3 files changed

+214
-0
lines changed

3 files changed

+214
-0
lines changed

‎Java/307.range-sum-query-mutable.java

Lines changed: 106 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,106 @@
1+
/*
2+
* @lc app=leetcode id=307 lang=java
3+
*
4+
* [307] Range Sum Query - Mutable
5+
*/
6+
7+
// @lc code=start
8+
class NumArray {
9+
/*
10+
Segment Tree
11+
time: O(n) for build O(h) or O(logn) for update/query
12+
space: O(n)
13+
*/
14+
class SegmentTreeNode {
15+
int start;
16+
int end;
17+
int sum;
18+
SegmentTreeNode left;
19+
SegmentTreeNode right;
20+
21+
public SegmentTreeNode(int start, int end) {
22+
this.start = start;
23+
this.end = end;
24+
this.left = null;
25+
this.right = null;
26+
this.sum = 0;
27+
}
28+
}
29+
30+
SegmentTreeNode root;
31+
32+
public NumArray(int[] nums) {
33+
root = build(nums, 0, nums.length - 1);
34+
}
35+
36+
public void update(int i, int val) {
37+
update(root, i, val);
38+
}
39+
40+
public int sumRange(int i, int j) {
41+
return query(root, i, j);
42+
}
43+
44+
private int query(SegmentTreeNode root, int start, int end) {
45+
if (root.start == root.end) {
46+
return root.sum;
47+
}
48+
int mid = (root.end - root.start) / 2 + root.start;
49+
if (end <= mid) {
50+
return query(root.left, start, end);
51+
} else if (start > mid) {
52+
return query(root.right, start, end);
53+
} else {
54+
return query(root.left, start, mid) + query(root.right, mid + 1, end);
55+
}
56+
}
57+
58+
private SegmentTreeNode build(int[] nums, int start, int end) {
59+
if (start > end) {
60+
return null;
61+
}
62+
SegmentTreeNode root = new SegmentTreeNode(start, end);
63+
if (start == end) {
64+
root.sum = nums[start];
65+
} else {
66+
int mid = (end - start) / 2 + start;
67+
root.left = build(nums, start, mid);
68+
root.right = build(nums, mid + 1, end);
69+
root.sum = (root.left == null ? 0 : root.left.sum) + (root.right == null ? 0 : root.right.sum);
70+
}
71+
return root;
72+
}
73+
74+
private void update(SegmentTreeNode root, int pos, int val) {
75+
if (root == null || pos < root.start || pos > root.end) {
76+
return;
77+
}
78+
if (root.start == root.end && root.start == pos) {
79+
root.sum = val;
80+
} else {
81+
int mid = (root.end - root.start) / 2 + root.start;
82+
if (pos <= mid) {
83+
update(root.left, pos, val);
84+
} else {
85+
update(root.right, pos, val);
86+
}
87+
root.sum = (root.left == null ? 0 : root.left.sum) + (root.right == null ? 0 : root.right.sum);
88+
}
89+
}
90+
}
91+
92+
/**
93+
* Your NumArray object will be instantiated and called as such:
94+
* NumArray obj = new NumArray(nums);
95+
* obj.update(i,val);
96+
* int param_2 = obj.sumRange(i,j);
97+
*/
98+
99+
/**
100+
* Your NumArray object will be instantiated and called as such:
101+
* NumArray obj = new NumArray(nums);
102+
* obj.update(i,val);
103+
* int param_2 = obj.sumRange(i,j);
104+
*/
105+
// @lc code=end
106+

‎Java/803.bricks-falling-when-hit.java

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
/*
2+
* @lc app=leetcode id=803 lang=java
3+
*
4+
* [803] Bricks Falling When Hit
5+
*/
6+
7+
// @lc code=start
8+
/*
9+
union find, 对于剩下的bricks, 找到find(0)的数量，减去可以得到掉落砖块的数量
10+
由于之前掉落会改变后面的状态，hit从后往前更新，将之前的hit设置为2
11+
回滚的时候将2设置回1重新union，更新find(0)的值
12+
time:O(mn) for union O(mn * hits.length) find O(1) amortized time
13+
space: O(mn)
14+
*/
15+
class Solution {
16+
class UF {
17+
int[] parent;
18+
int[] size;
19+
20+
public UF(int n) {
21+
parent = new int[n];
22+
size = new int[n];
23+
Arrays.fill(size, 1);
24+
for (int i = 0; i < n; ++i) {
25+
parent[i] = i;
26+
}
27+
}
28+
29+
private void union(int x, int y) {
30+
int parentX = find(x);
31+
int parentY = find(y);
32+
if (parentX != parentY) {
33+
parent[parentY] = parentX;
34+
size[parentX] += size[parentY];
35+
}
36+
}
37+
38+
private int find(int x) {
39+
while (parent[x] != x) {
40+
parent[x] = parent[parent[x]];
41+
x = parent[x];
42+
}
43+
return x;
44+
}
45+
}
46+
UF uf;
47+
int m, n;
48+
public int[] hitBricks(int[][] grid, int[][] hits) {
49+
m = grid.length;
50+
n = grid[0].length;
51+
uf = new UF(m * n + 1);
52+
// set all hit to 2
53+
for (int[] hit : hits) {
54+
if (grid[hit[0]][hit[1]] == 1) {
55+
grid[hit[0]][hit[1]] = 2;
56+
}
57+
}
58+
for (int i = 0; i < m; ++i) {
59+
for (int j = 0; j < n; ++j) {
60+
if (grid[i][j] == 1) {
61+
unionGrid(uf, grid, i, j);
62+
}
63+
}
64+
}
65+
int[] res = new int[hits.length];
66+
int i = res.length - 1;
67+
int left = uf.size[uf.find(0)];
68+
while (i >= 0) {
69+
int hitR = hits[i][0];
70+
int hitC = hits[i][1];
71+
if (grid[hitR][hitC] == 2) {
72+
grid[hitR][hitC] = 1;
73+
unionGrid(uf, grid, hitR, hitC);
74+
int curLeft = uf.size[uf.find(0)];
75+
res[i] = Math.max(0, curLeft - left - 1); // 减去hit掉的那一个 或结果是0
76+
left = curLeft;
77+
}
78+
79+
--i;
80+
}
81+
return res;
82+
}
83+
84+
private void unionGrid(UF uf, int[][] grid, int r, int c) {
85+
int pos = getPosition(r, c);
86+
if (r == 0) uf.union(0, pos); // union to top
87+
int[] dirs = new int[]{1, 0, -1, 0, 1};
88+
for (int i = 0; i < 4; ++i) {
89+
int nextR = r + dirs[i];
90+
int nextC = c + dirs[i + 1];
91+
if (nextR >= 0 && nextC >= 0 && nextR < m && nextC < n && grid[nextR][nextC] == 1) {
92+
int nextPos = getPosition(nextR, nextC);
93+
uf.union(pos, nextPos);
94+
}
95+
}
96+
}
97+
98+
private int getPosition(int r, int c) {
99+
return n * r + c + 1;
100+
}
101+
}
102+
// @lc code=end
103+

‎README.md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -142,6 +142,10 @@
142142
[472. Concatenated Words](https://leetcode.com/problems/concatenated-words/) | [DFS + memo Solution(C++)](https://github.com/Yukinichi/leetcode/blob/master/Cpp/472.concatenated-words.cpp) \| [Trie Solution(Java)](https://github.com/Yukinichi/leetcode/blob/master/Java/472.concatenated-words.java)
143143
[489. Robot Room Cleaner](https://leetcode.com/problems/robot-room-cleaner/) | [模拟dfs, 注意当前robot朝向](https://github.com/Yukinichi/leetcode/blob/master/Java/489.robot-room-cleaner.java)
144144

145+
## Segment Tree
146+
| Problem | Solution
147+
:- | :-:
148+
[307. Range Sum Query - Mutable](https://leetcode.com/problems/range-sum-query-mutable/) | [Segment Tree模版](https://github.com/Yukinichi/leetcode/blob/master/Java/307.range-sum-query-mutable.java)
145149

146150
## Sliding Window
147151
| Problem | Solution
@@ -190,4 +194,5 @@
190194
| Problem | Solution
191195
:- | :-:
192196
[695. Max Area of Island](https://leetcode.com/problems/max-area-of-island/) | [Union Find](https://github.com/Yukinichi/leetcode/blob/master/Java/695.max-area-of-island.java) \| [DFS](https://github.com/Yukinichi/leetcode/blob/master/Cpp/695.max-area-of-island.cpp)
197+
[803. Bricks Falling When Hit](https://leetcode.com/problems/bricks-falling-when-hit/) | [Union Find](https://github.com/Yukinichi/leetcode/blob/master/Java/803.bricks-falling-when-hit.java)
193198
[952. Largest Component Size by Common Factor](https://leetcode.com/problems/largest-component-size-by-common-factor/) | [连接公因数的UF](https://github.com/Yukinichi/leetcode/blob/master/Java/952.largest-component-size-by-common-factor.java)

0 commit comments

Comments
 (0)
0