Skip to content

Commit aaaf42c

Browse files
jgan123jgan123
committed
finish the week 7 homework
1 parent c66dba8 commit aaaf42c

9 files changed

Lines changed: 544 additions & 1 deletion

‎Week07/NOTE.md‎

Lines changed: 271 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,271 @@
1-
学习笔记
1+
学习笔记
2+
3+
# 第七周学习笔记
4+
5+
## 并查集代码模板
6+
```java
7+
// Java
8+
class UnionFind {
9+
private int count = 0;
10+
private int[] parent;
11+
public UnionFind(int n) {
12+
count = n;
13+
parent = new int[n];
14+
for (int i = 0; i < n; i++) {
15+
parent[i] = i;
16+
}
17+
}
18+
public int find(int p) {
19+
while (p != parent[p]) {
20+
parent[p] = parent[parent[p]];
21+
p = parent[p];
22+
}
23+
return p;
24+
}
25+
public void union(int p, int q) {
26+
int rootP = find(p);
27+
int rootQ = find(q);
28+
if (rootP == rootQ) return;
29+
parent[rootP] = rootQ;
30+
count--;
31+
}
32+
}
33+
```
34+
35+
## 双向BFS模板
36+
```java
37+
public <T> two-endedBFS(begin, end, Container) {
38+
if (Container.length == 0 || !Container.contains(end)) return NEGATIVE;
39+
Set<T> beginSet = new HashSet<>(), endSet = new HashSet<>();
40+
beginSet.add(begin);
41+
endSet.add(end);
42+
43+
Set<T> visited = new HashSet<>();
44+
int level = 0;
45+
46+
while(!beginSet.isEmpty() && !endSet.isEmpty()) {
47+
if (beginSet.size() > endSet.size()){
48+
Set<T> set = beginSet;
49+
beginSet = endSet;
50+
endSet = set;
51+
}
52+
Set<T> temp = new HashSet<>();
53+
for (T item: beginSet){
54+
T next = generate_nextLevel_nodes();
55+
if (endSet.contains(next)) return POSITIVE;
56+
if (Container.contains(next) && !visited.contains(next)){
57+
temp.add(next);
58+
visited.add(next);
59+
}
60+
// reverse node states
61+
}
62+
beginSet = temp;
63+
level++;
64+
}
65+
return NEGATIVE;
66+
}
67+
```
68+
69+
## A*代码模板
70+
```java
71+
//Java
72+
public class AStar
73+
{
74+
public final static int BAR = 1; // 障碍值
75+
public final static int PATH = 2; // 路径
76+
public final static int DIRECT_VALUE = 10; // 横竖移动代价
77+
public final static int OBLIQUE_VALUE = 14; // 斜移动代价
78+
79+
Queue<Node> openList = new PriorityQueue<Node>(); // 优先队列(升序)
80+
List<Node> closeList = new ArrayList<Node>();
81+
82+
/**
83+
* 开始算法
84+
*/
85+
public void start(MapInfo mapInfo)
86+
{
87+
if(mapInfo==null) return;
88+
// clean
89+
openList.clear();
90+
closeList.clear();
91+
// 开始搜索
92+
openList.add(mapInfo.start);
93+
moveNodes(mapInfo);
94+
}
95+
96+
97+
/**
98+
* 移动当前结点
99+
*/
100+
private void moveNodes(MapInfo mapInfo)
101+
{
102+
while (!openList.isEmpty())
103+
{
104+
Node current = openList.poll();
105+
closeList.add(current);
106+
addNeighborNodeInOpen(mapInfo,current);
107+
if (isCoordInClose(mapInfo.end.coord))
108+
{
109+
drawPath(mapInfo.maps, mapInfo.end);
110+
break;
111+
}
112+
}
113+
}
114+
115+
/**
116+
* 在二维数组中绘制路径
117+
*/
118+
private void drawPath(int[][] maps, Node end)
119+
{
120+
if(end==null||maps==null) return;
121+
System.out.println("总代价：" + end.G);
122+
while (end != null)
123+
{
124+
Coord c = end.coord;
125+
maps[c.y][c.x] = PATH;
126+
end = end.parent;
127+
}
128+
}
129+
130+
131+
/**
132+
* 添加所有邻结点到open表
133+
*/
134+
private void addNeighborNodeInOpen(MapInfo mapInfo,Node current)
135+
{
136+
int x = current.coord.x;
137+
int y = current.coord.y;
138+
// 左
139+
addNeighborNodeInOpen(mapInfo,current, x - 1, y, DIRECT_VALUE);
140+
// 上
141+
addNeighborNodeInOpen(mapInfo,current, x, y - 1, DIRECT_VALUE);
142+
// 右
143+
addNeighborNodeInOpen(mapInfo,current, x + 1, y, DIRECT_VALUE);
144+
// 下
145+
addNeighborNodeInOpen(mapInfo,current, x, y + 1, DIRECT_VALUE);
146+
// 左上
147+
addNeighborNodeInOpen(mapInfo,current, x - 1, y - 1, OBLIQUE_VALUE);
148+
// 右上
149+
addNeighborNodeInOpen(mapInfo,current, x + 1, y - 1, OBLIQUE_VALUE);
150+
// 右下
151+
addNeighborNodeInOpen(mapInfo,current, x + 1, y + 1, OBLIQUE_VALUE);
152+
// 左下
153+
addNeighborNodeInOpen(mapInfo,current, x - 1, y + 1, OBLIQUE_VALUE);
154+
}
155+
156+
157+
/**
158+
* 添加一个邻结点到open表
159+
*/
160+
private void addNeighborNodeInOpen(MapInfo mapInfo,Node current, int x, int y, int value)
161+
{
162+
if (canAddNodeToOpen(mapInfo,x, y))
163+
{
164+
Node end=mapInfo.end;
165+
Coord coord = new Coord(x, y);
166+
int G = current.G + value; // 计算邻结点的G值
167+
Node child = findNodeInOpen(coord);
168+
if (child == null)
169+
{
170+
int H=calcH(end.coord,coord); // 计算H值
171+
if(isEndNode(end.coord,coord))
172+
{
173+
child=end;
174+
child.parent=current;
175+
child.G=G;
176+
child.H=H;
177+
}
178+
else
179+
{
180+
child = new Node(coord, current, G, H);
181+
}
182+
openList.add(child);
183+
}
184+
else if (child.G > G)
185+
{
186+
child.G = G;
187+
child.parent = current;
188+
openList.add(child);
189+
}
190+
}
191+
}
192+
193+
194+
/**
195+
* 从Open列表中查找结点
196+
*/
197+
private Node findNodeInOpen(Coord coord)
198+
{
199+
if (coord == null || openList.isEmpty()) return null;
200+
for (Node node : openList)
201+
{
202+
if (node.coord.equals(coord))
203+
{
204+
return node;
205+
}
206+
}
207+
return null;
208+
}
209+
210+
211+
/**
212+
* 计算H的估值：“曼哈顿”法，坐标分别取差值相加
213+
*/
214+
private int calcH(Coord end,Coord coord)
215+
{
216+
return Math.abs(end.x - coord.x)
217+
+ Math.abs(end.y - coord.y);
218+
}
219+
220+
/**
221+
* 判断结点是否是最终结点
222+
*/
223+
private boolean isEndNode(Coord end,Coord coord)
224+
{
225+
return coord != null && end.equals(coord);
226+
}
227+
228+
229+
/**
230+
* 判断结点能否放入Open列表
231+
*/
232+
private boolean canAddNodeToOpen(MapInfo mapInfo,int x, int y)
233+
{
234+
// 是否在地图中
235+
if (x < 0 || x >= mapInfo.width || y < 0 || y >= mapInfo.hight) return false;
236+
// 判断是否是不可通过的结点
237+
if (mapInfo.maps[y][x] == BAR) return false;
238+
// 判断结点是否存在close表
239+
if (isCoordInClose(x, y)) return false;
240+
241+
242+
return true;
243+
}
244+
245+
246+
/**
247+
* 判断坐标是否在close表中
248+
*/
249+
private boolean isCoordInClose(Coord coord)
250+
{
251+
return coord!=null&&isCoordInClose(coord.x, coord.y);
252+
}
253+
254+
255+
/**
256+
* 判断坐标是否在close表中
257+
*/
258+
private boolean isCoordInClose(int x, int y)
259+
{
260+
if (closeList.isEmpty()) return false;
261+
for (Node node : closeList)
262+
{
263+
if (node.coord.x == x && node.coord.y == y)
264+
{
265+
return true;
266+
}
267+
}
268+
return false;
269+
}
270+
}
271+
```

‎Week07/Trie.js‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
/**
2+
* Initialize your data structure here.
3+
*/
4+
const TrieNode = function () {
5+
this.next = {};
6+
this.isEnd = false;
7+
}
8+
9+
var Trie = function() {
10+
this.root = new TrieNode();
11+
};
12+
13+
/**
14+
* Inserts a word into the trie.
15+
* @param {string} word
16+
* @return {void}
17+
*/
18+
Trie.prototype.insert = function(word) {
19+
if (!word) return false;
20+
let node = this.root;
21+
for (let i = 0; i < word.length; ++i) {
22+
if (!node.next[word[i]]) {
23+
node.next[word[i]] = new TrieNode();
24+
}
25+
node = node.next[word[i]];
26+
}
27+
node.isEnd = true;
28+
return true;
29+
};
30+
31+
/**
32+
* Returns if the word is in the trie.
33+
* @param {string} word
34+
* @return {boolean}
35+
*/
36+
Trie.prototype.search = function(word) {
37+
if (!word) return false;
38+
let node = this.root;
39+
for (let i = 0; i < word.length; ++i) {
40+
if (node.next[word[i]]) {
41+
node = node.next[word[i]];
42+
} else {
43+
return false;
44+
}
45+
}
46+
return node.isEnd;
47+
};
48+
49+
/**
50+
* Returns if there is any word in the trie that starts with the given prefix.
51+
* @param {string} prefix
52+
* @return {boolean}
53+
*/
54+
Trie.prototype.startsWith = function(prefix) {
55+
if (!prefix) return true;
56+
let node = this.root;
57+
for (let i = 0; i < prefix.length; ++i) {
58+
if (node.next[prefix[i]]) {
59+
node = node.next[prefix[i]];
60+
} else {
61+
return false;
62+
}
63+
}
64+
return true;
65+
};
66+
67+
/**
68+
* Your Trie object will be instantiated and called as such:
69+
* var obj = new Trie()
70+
* obj.insert(word)
71+
* var param_2 = obj.search(word)
72+
* var param_3 = obj.startsWith(prefix)
73+
*/

‎Week07/climbStairs.js‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
/**
2+
* 爬楼梯
3+
* @param {number} n
4+
* @return {number}
5+
*/
6+
var climbStairs = function(n) {
7+
if (n <= 2) return n;
8+
let f1 = 1, f2 = 2, f3 = 3;
9+
for (let i = 3; i <= n; ++i) {
10+
f3 = f2 + f1;
11+
f1 = f2;
12+
f2 = f3;
13+
}
14+
return f3;
15+
};

‎Week07/findCircleNum.js‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
/**
2+
* 朋友圈
3+
* @param {number[][]} M
4+
* @return {number}
5+
*/
6+
var findCircleNum = function(M) {
7+
let count = 0;
8+
let visited = new Array(M.length).fill(0);
9+
for (let i = 0; i < M.length; ++i) {
10+
if (visited[i] == 0) {
11+
dfs(M, visited, i);
12+
count++;
13+
}
14+
}
15+
function dfs(M, visited, i) {
16+
for (let j = 0; j < M[i].length; ++j) {
17+
if (M[i][j] == 1 && visited[j] == 0) {
18+
visited[j] = 1;
19+
dfs(M, visited, j);
20+
}
21+
}
22+
}
23+
return count;
24+
};

0 commit comments

Comments
 (0)