Skip to content

Commit 214d31a

Browse files
zlWorkStudyzlWorkStudy
committed
week07 note and hoomework
1 parent 865bd0f commit 214d31a

3 files changed

Lines changed: 383 additions & 1 deletion

File tree

‎Week07/NOTE.md‎

Lines changed: 0 additions & 1 deletion
This file was deleted.

‎Week07/week07-homework.md‎

Lines changed: 155 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,155 @@
1+
### <a href="https://leetcode-cn.com/problems/implement-trie-prefix-tree/">实现 Trie (前缀树)</a>
2+
```java
3+
class Trie {
4+
private boolean isEnd;
5+
private Trie[] next;
6+
/** Initialize your data structure here. */
7+
public Trie() {
8+
isEnd = false;
9+
next = new Trie[26];
10+
}
11+
12+
/** Inserts a word into the trie. */
13+
public void insert(String word) {
14+
if (word == null || word.length() == 0) return;
15+
Trie cur = this;
16+
char[] words = word.toCharArray();
17+
for (int i = 0; i < words.length; i++) {
18+
int n = words[i] - 'a';
19+
if (cur.next[n] == null) cur.next[n] = new Trie();
20+
cur = cur.next[n];
21+
}
22+
cur.isEnd = true;
23+
}
24+
25+
/** Returns if the word is in the trie. */
26+
public boolean search(String word) {
27+
Trie node = searchPrefix(word);
28+
return node != null && node.isEnd;
29+
}
30+
31+
/** Returns if there is any word in the trie that starts with the given prefix. */
32+
public boolean startsWith(String prefix) {
33+
Trie node = searchPrefix(prefix);
34+
return node != null;
35+
}
36+
37+
private Trie searchPrefix(String word) {
38+
if (word == null) return null;
39+
Trie cur = this;
40+
char[] words = word.toCharArray();
41+
for (int i = 0; i < words.length; i++) {
42+
cur = cur.next[words[i] - 'a'];
43+
if (cur == null) return null;
44+
}
45+
return cur;
46+
}
47+
}
48+
```
49+
<br/>
50+
51+
### <a href="https://leetcode-cn.com/problems/friend-circles/">朋友圈</a>
52+
```java
53+
class Solution {
54+
private int find(int[] parent, int p) {
55+
while (p != parent[p]) {
56+
parent[p] = parent[parent[p]];
57+
p = parent[p];
58+
}
59+
return p;
60+
}
61+
62+
private void union(int[] parent, int p, int q) {
63+
int rootP = find(parent, p);
64+
int rootQ = find(parent, q);
65+
if (rootP == rootQ) return;
66+
parent[rootP] = rootQ;
67+
}
68+
69+
public int findCircleNum(int[][] M) {
70+
int[] parent = new int[M.length];
71+
for (int i = 0; i < M.length; i++) {
72+
parent[i] = i;
73+
}
74+
for (int i = 0; i < M.length - 1; i++) {
75+
for (int j = i + 1; j < M.length; j++) {
76+
if (M[i][j] == 1) union(parent, i, j);
77+
}
78+
}
79+
int count = 0;
80+
for (int i = 0; i < parent.length; i++) {
81+
if (parent[i] == i) count++;
82+
}
83+
return count;
84+
}
85+
}
86+
```
87+
<br/>
88+
89+
### <a href="https://leetcode-cn.com/problems/number-of-islands/">岛屿数量</a>
90+
```java
91+
class Solution {
92+
public int numIslands(char[][] grid) {
93+
if (grid == null || grid[0].length == 0) return 0;
94+
int row = grid.length, col = grid[0].length, count = 0;
95+
// O(M * N)
96+
for (int i = 0; i < row; i++) {
97+
for (int j = 0; j < col; j++) {
98+
if (grid[i][j] == '1') {
99+
count++;
100+
dfs(grid, i, j);
101+
}
102+
}
103+
}
104+
return count;
105+
}
106+
107+
private void dfs(char[][] grid, int i, int j) {
108+
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') return;
109+
grid[i][j] = '0';
110+
int[][] dirs = {{0, 1}, {1,0}, {-1, 0}, {0, -1}};
111+
for (int[] dir : dirs) {
112+
dfs(grid, i + dir[0], j + dir[1]);
113+
}
114+
}
115+
}
116+
```
117+
<br/>
118+
119+
### <a href="https://leetcode-cn.com/problems/surrounded-regions/">被围绕的区域</a>
120+
```java
121+
class Solution {
122+
public void solve(char[][] board) {
123+
if (board == null || board.length == 0) return;
124+
int row = board.length, col = board[0].length;
125+
for (int i = 0; i < row; i++) {
126+
for (int j = 0; j < col; j++) {
127+
boolean isBoard = i == 0 || j == 0 || i == row - 1 || j == col - 1;
128+
if (isBoard && board[i][j] == 'O') {
129+
dfs(board, i, j);
130+
}
131+
}
132+
}
133+
for (int i = 0; i < row; i++) {
134+
for (int j = 0; j < col; j++) {
135+
if (board[i][j] == 'O') {
136+
board[i][j] = 'X';
137+
}
138+
if (board[i][j] == '#') {
139+
board[i][j] = 'O';
140+
}
141+
}
142+
}
143+
}
144+
145+
private void dfs(char[][] board, int i, int j) {
146+
if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') return;
147+
board[i][j] = '#';
148+
int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
149+
for (int[] dir : dirs) {
150+
dfs(board, i + dir[0], j + dir[1]);
151+
}
152+
}
153+
}
154+
```
155+
<br/>

‎Week07/week07-note.md‎

Lines changed: 228 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,228 @@
1+
### 并查集
2+
#### 模板
3+
```java
4+
/**
5+
* 1.find: 确定元素子集
6+
* 2.union: 合并两个子集
7+
* 3.makeSet: 简历单元素集合
8+
* 路径压缩优化: 认老大, 减少深度
9+
*/
10+
class unionFind {
11+
private int count = 0;
12+
private int[] parent;
13+
public unionFind(int n) {
14+
count = n;
15+
parent = new int[n];
16+
for (int i = 0; i < n; i++) {
17+
parent[i] = i;
18+
}
19+
}
20+
21+
public int find(int p) {
22+
while (p != parent[p]) {
23+
// 路径压缩
24+
parent[p] = parent[parent[p]];
25+
p = parent[p];
26+
}
27+
return p;
28+
}
29+
30+
public void union(int p, int q) {
31+
int rootP = find(p);
32+
int rootQ = find(q);
33+
if (rootP == rootQ) return;
34+
parent[rootP] = rootQ;
35+
count--;
36+
}
37+
}
38+
```
39+
<br/>
40+
41+
### A*
42+
#### 模板
43+
```java
44+
/**
45+
* BFS + 优先级
46+
*/
47+
public class AStar {
48+
public final static int BAR = 1; // 障碍值
49+
public final static int PATH = 2; // 路径
50+
public final static int DIRECT_VALUE = 10; // 横竖移动代价
51+
public final static int OBLIQUE_VALUE = 14; // 斜移动代价
52+
53+
Queue<Node> openList = new PriorityQueue<Node>(); // 优先队列(升序)
54+
List<Node> closeList = new ArrayList<Node>();
55+
56+
/**
57+
* 开始算法
58+
*/
59+
public void start(MapInfo mapInfo) {
60+
if(mapInfo==null) return;
61+
// clean
62+
openList.clear();
63+
closeList.clear();
64+
// 开始搜索
65+
openList.add(mapInfo.start);
66+
moveNodes(mapInfo);
67+
}
68+
69+
70+
/**
71+
* 移动当前结点
72+
*/
73+
private void moveNodes(MapInfo mapInfo) {
74+
while (!openList.isEmpty()) {
75+
Node current = openList.poll();
76+
closeList.add(current);
77+
addNeighborNodeInOpen(mapInfo,current);
78+
if (isCoordInClose(mapInfo.end.coord)) {
79+
drawPath(mapInfo.maps, mapInfo.end);
80+
break;
81+
}
82+
}
83+
}
84+
85+
/**
86+
* 在二维数组中绘制路径
87+
*/
88+
private void drawPath(int[][] maps, Node end) {
89+
if(end==null||maps==null) return;
90+
System.out.println("总代价：" + end.G);
91+
while (end != null) {
92+
Coord c = end.coord;
93+
maps[c.y][c.x] = PATH;
94+
end = end.parent;
95+
}
96+
}
97+
98+
99+
/**
100+
* 添加所有邻结点到open表
101+
*/
102+
private void addNeighborNodeInOpen(MapInfo mapInfo,Node current) {
103+
int x = current.coord.x;
104+
int y = current.coord.y;
105+
// 左
106+
addNeighborNodeInOpen(mapInfo,current, x - 1, y, DIRECT_VALUE);
107+
// 上
108+
addNeighborNodeInOpen(mapInfo,current, x, y - 1, DIRECT_VALUE);
109+
// 右
110+
addNeighborNodeInOpen(mapInfo,current, x + 1, y, DIRECT_VALUE);
111+
// 下
112+
addNeighborNodeInOpen(mapInfo,current, x, y + 1, DIRECT_VALUE);
113+
// 左上
114+
addNeighborNodeInOpen(mapInfo,current, x - 1, y - 1, OBLIQUE_VALUE);
115+
// 右上
116+
addNeighborNodeInOpen(mapInfo,current, x + 1, y - 1, OBLIQUE_VALUE);
117+
// 右下
118+
addNeighborNodeInOpen(mapInfo,current, x + 1, y + 1, OBLIQUE_VALUE);
119+
// 左下
120+
addNeighborNodeInOpen(mapInfo,current, x - 1, y + 1, OBLIQUE_VALUE);
121+
}
122+
123+
124+
/**
125+
* 添加一个邻结点到open表
126+
*/
127+
private void addNeighborNodeInOpen(MapInfo mapInfo,Node current, int x, int y, int value) {
128+
if (canAddNodeToOpen(mapInfo,x, y)) {
129+
Node end=mapInfo.end;
130+
Coord coord = new Coord(x, y);
131+
int G = current.G + value; // 计算邻结点的G值
132+
Node child = findNodeInOpen(coord);
133+
if (child == null) {
134+
int H=calcH(end.coord,coord); // 计算H值
135+
if(isEndNode(end.coord,coord)) {
136+
child=end;
137+
child.parent=current;
138+
child.G=G;
139+
child.H=H;
140+
} else {
141+
child = new Node(coord, current, G, H);
142+
}
143+
openList.add(child);
144+
} else if (child.G > G) {
145+
child.G = G;
146+
child.parent = current;
147+
openList.add(child);
148+
}
149+
}
150+
}
151+
152+
153+
/**
154+
* 从Open列表中查找结点
155+
*/
156+
private Node findNodeInOpen(Coord coord) {
157+
if (coord == null || openList.isEmpty()) return null;
158+
for (Node node : openList) {
159+
if (node.coord.equals(coord)) {
160+
return node;
161+
}
162+
}
163+
return null;
164+
}
165+
166+
/**
167+
* 计算H的估值：“曼哈顿”法，坐标分别取差值相加
168+
*/
169+
private int calcH(Coord end,Coord coord) {
170+
return Math.abs(end.x - coord.x)
171+
+ Math.abs(end.y - coord.y);
172+
}
173+
174+
/**
175+
* 判断结点是否是最终结点
176+
*/
177+
private boolean isEndNode(Coord end,Coord coord) {
178+
return coord != null && end.equals(coord);
179+
}
180+
181+
182+
/**
183+
* 判断结点能否放入Open列表
184+
*/
185+
private boolean canAddNodeToOpen(MapInfo mapInfo,int x, int y) {
186+
// 是否在地图中
187+
if (x < 0 || x >= mapInfo.width || y < 0 || y >= mapInfo.hight) return false;
188+
// 判断是否是不可通过的结点
189+
if (mapInfo.maps[y][x] == BAR) return false;
190+
// 判断结点是否存在close表
191+
if (isCoordInClose(x, y)) return false;
192+
193+
return true;
194+
}
195+
196+
197+
/**
198+
* 判断坐标是否在close表中
199+
*/
200+
private boolean isCoordInClose(Coord coord) {
201+
return coord!=null&&isCoordInClose(coord.x, coord.y);
202+
}
203+
204+
205+
/**
206+
* 判断坐标是否在close表中
207+
*/
208+
private boolean isCoordInClose(int x, int y) {
209+
if (closeList.isEmpty()) return false;
210+
for (Node node : closeList) {
211+
if (node.coord.x == x && node.coord.y == y) {
212+
return true;
213+
}
214+
}
215+
return false;
216+
}
217+
}
218+
219+
```
220+
221+
### 红黑树 AVL
222+
```
223+
旋转
224+
左旋
225+
右旋
226+
左右旋
227+
右左旋
228+
```

0 commit comments

Comments
 (0)