Skip to content

Commit c9492a8

Browse files
Simona0769Simona0769
committed
第四周学习笔记和作业
1 parent ee2cd49 commit c9492a8

9 files changed

Lines changed: 500 additions & 1 deletion

‎Week04/NOTE.md‎

100644100755
Lines changed: 72 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,72 @@
1-
学习笔记
1+
# 第四周学习笔记
2+
## 深度优先搜索 depth first search
3+
* 实现：递归，栈
4+
* 代码实现
5+
* 递归写法
6+
```
7+
let visited = new Set()
8+
function dfs(node, visited) {
9+
if (node in visited) {
10+
return
11+
}
12+
visited.add(node)
13+
// process current node here
14+
for (let i = 0; i < node.children.length; i ++) {
15+
if (!visited.has(node.children[i])) {
16+
dfs(node.children[i], visited)
17+
}
18+
}
19+
}
20+
```
21+
* 非递归写法
22+
```
23+
function dfs(tree) {
24+
if (tree.root === null) {
25+
return []
26+
}
27+
const [visited, stack] = [[], [tree.root]]
28+
while(stack.length > 0) {
29+
node = stack.pop()
30+
visited.push(node)
31+
32+
process(node)
33+
nodes = generate_related_nodes(node)
34+
stach.push(nodes)
35+
// other process work
36+
}
37+
}
38+
```
39+
*
40+
## 广度优先搜索 breadth first search
41+
* 实现： 队列
42+
* 代码实现
43+
```
44+
function bfs(graph, start, end) {
45+
queue = []
46+
queue.push(start)
47+
visited.add(start)
48+
49+
while queue:
50+
node = queue.pop()
51+
visited.add(node)
52+
process(node)
53+
nodes = generate_related_nodes(node)
54+
queue.push(nodes)
55+
// other processing work
56+
}
57+
```
58+
59+
## 贪心算法的实现和特性
60+
* 定义
61+
贪心算法（Greedy）是一种在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法
62+
*贪心u啊算法和动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能*
63+
* 区别
64+
* 贪心：当下做局部最优判断
65+
* 回溯：能够回退
66+
* 动态规划：最优判断 + 回退
67+
* 实际适用场景
68+
* 最优化问题，例如：图中的最小生成树、华夫曼编码
69+
* 辅助运算或者求结果不是特别精确的问题
70+
71+
* 编码适用场景
72+
问题能够分解成子问题来解决，子问题最优解能递推到最终问题的最优解。这种子问题最优解称为最优子结构

‎Week04/programming/assign-cookies.js‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
/**
2+
* @param {number[]} g
3+
* @param {number[]} s
4+
* @return {number}
5+
*/
6+
var findContentChildren = function(g, s) {
7+
g.sort((a, b) => a - b)
8+
s.sort((a, b) => a - b)
9+
let i = j = 0
10+
while(i < g.length && j < s.length) {
11+
if (s[j] >= g[i]) {
12+
j++
13+
i++
14+
} else {
15+
j ++
16+
}
17+
}
18+
return i
19+
};

‎Week04/programming/best-time-to-buy-and-sell-stock-ii.js‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
/**
2+
* @param {number[]} prices
3+
* @return {number}
4+
*/
5+
var maxProfit = function(prices) {
6+
let res = 0;
7+
for (let i = 1; i < prices.length; i ++) {
8+
if (prices[i] > prices[i - 1]) {
9+
res += prices[i] - prices[i - 1]
10+
}
11+
}
12+
return res
13+
};

‎Week04/programming/jump-game-ii.js‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
/**
2+
* 顺数
3+
* @param {number[]} nums
4+
* @return {number}
5+
*/
6+
var jump = function(nums) {
7+
let end = 0
8+
let maxPosition = 0
9+
let step = 0
10+
for(let i = 0; i < nums.length - 1; i++) {
11+
maxPosition = Math.max(maxPosition, nums[i] + i)
12+
if (i === end) {
13+
end = maxPosition
14+
step++
15+
}
16+
}
17+
return step
18+
};
19+
20+
/**
21+
* 倒数
22+
* @param {number[]} nums
23+
* @return {number}
24+
*/
25+
var jump = function(nums) {
26+
let position = nums.length - 1
27+
let step = 0
28+
while(position > 0) {
29+
for(let i = 0; i < nums.length - 1; i ++) {
30+
if (nums[i] >= position - i) {
31+
position = i
32+
step++
33+
break;
34+
}
35+
}
36+
}
37+
return step
38+
};

‎Week04/programming/jump-game.js‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
/**
2+
* 从头遍历
3+
* @param {number[]} nums
4+
* @return {boolean}
5+
*/
6+
var canJump = function(nums) {
7+
let reach = 0
8+
for(let i = 0; i < nums.length; i ++) {
9+
if (i > reach) {
10+
return false
11+
}
12+
reach = Math.max(reach, i + nums[i])
13+
}
14+
return true
15+
};
16+
17+
/**
18+
* 从尾遍历
19+
* @param {number[]} nums
20+
* @return {boolean}
21+
*/
22+
var canJump = function(nums) {
23+
const L = nums.length;
24+
let last = L - 1
25+
for(let i = L - 2; i >= 0; i--) {
26+
if (i + nums[i] >= last) {
27+
last = i
28+
}
29+
}
30+
return last === 0
31+
};

‎Week04/programming/lemonade-change.js‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
/**
2+
* @param {number[]} bills
3+
* @return {boolean}
4+
*/
5+
var lemonadeChange = function(bills) {
6+
let [five, ten] = [0, 0]
7+
for(let i = 0; i < bills.length; i ++) {
8+
const bill = bills[i]
9+
if (bill === 5) {
10+
five ++
11+
} else if (bill === 10) {
12+
if (five === 0) {
13+
return false
14+
} else {
15+
five--
16+
ten++
17+
}
18+
} else {
19+
if (five > 0 && ten > 0) {
20+
five--
21+
ten--
22+
} else if (five >= 3) {
23+
five -= 3
24+
} else {
25+
return false
26+
}
27+
}
28+
29+
}
30+
31+
return true
32+
};

‎Week04/programming/number-of-islands.js‎

Lines changed: 143 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,143 @@
1+
/**
2+
* 深度优先-递归
3+
* @param {character[][]} grid
4+
* @return {number}
5+
*/
6+
var numIslands = function(grid) {
7+
let result = 0;
8+
9+
if (!grid || grid.length <= 0) {
10+
return 0
11+
}
12+
const nr = grid.length
13+
const nc = grid[0].length
14+
15+
const dfsHelper = (grid, r, c) => {
16+
17+
if (r < 0 || c < 0 || r >=nr || c >= nc || grid[r][c] === '0') {
18+
return
19+
}
20+
21+
grid[r][c] = '0'
22+
dfsHelper(grid, r, c - 1)
23+
dfsHelper(grid, r, c + 1)
24+
dfsHelper(grid, r - 1, c)
25+
dfsHelper(grid, r + 1, c)
26+
}
27+
28+
for (let i = 0; i < nr; i ++) {
29+
for (let j = 0; j < nc; j ++) {
30+
if (grid[i][j] === '1') {
31+
++result;
32+
dfsHelper(grid, i, j)
33+
}
34+
}
35+
}
36+
37+
return result
38+
39+
};
40+
41+
/**
42+
* 深度优先-迭代
43+
* @param {character[][]} grid
44+
* @return {number}
45+
*/
46+
var numIslands = function(grid) {
47+
let result = 0;
48+
49+
if (!grid || grid.length <= 0) {
50+
return 0
51+
}
52+
const nr = grid.length
53+
const nc = grid[0].length
54+
55+
const dfsHelper = (grid, r, c) => {
56+
const visited = new Map()
57+
const stack = []
58+
if (grid[r][c] === '1') {
59+
stack.push({r, c})
60+
}
61+
62+
while(stack.length > 0) {
63+
const node = stack.pop()
64+
const r = node.r
65+
const c = node.c
66+
visited.set(`${r}-${c}`, true)
67+
grid[r][c] = '0'
68+
69+
if (r - 1 >= 0 && grid[r - 1][c] === '1' && !visited.has(`${r - 1}-${c}`)) {
70+
stack.push({ r: r - 1, c})
71+
}
72+
if ( r + 1 < nr && grid[r + 1][c] === '1' && !visited.has(`${r + 1}-${c}`)) {
73+
stack.push({ r: r + 1, c})
74+
}
75+
if (c - 1 >= 0 && grid[r][c - 1] === '1' && !visited.has(`${r}-${c - 1}`)) {
76+
stack.push({ r, c: c - 1})
77+
}
78+
if ( c + 1 < nc && grid[r][c + 1] === '1' && !visited.has(`${r}-${c + 1}`)) {
79+
stack.push({ r, c: c + 1})
80+
}
81+
}
82+
}
83+
84+
for (let i = 0; i < nr; i ++) {
85+
for (let j = 0; j < nc; j ++) {
86+
if (grid[i][j] === '1') {
87+
++result;
88+
dfsHelper(grid, i, j)
89+
}
90+
}
91+
}
92+
93+
return result
94+
95+
};
96+
97+
/**
98+
* 广度优先 -- 不知道为什么总是超时
99+
* @param {character[][]} grid
100+
* @return {number}
101+
*/
102+
var numIslands = function(grid) {
103+
let result = 0
104+
if (!grid || grid.length <= 0) {
105+
return result
106+
}
107+
const nr = grid.length
108+
const nc = grid[0].length
109+
const bfsHelper = (grid, r, c) => {
110+
const queue = []
111+
if (grid[r][c] === '1') {
112+
queue.push({r, c})
113+
}
114+
115+
while(queue.length > 0) {
116+
const node = queue.shift()
117+
const {r, c} = node
118+
// visited.set(`${r}-${c}`, true)
119+
grid[r][c] = '0'
120+
if (r - 1 >= 0 && grid[r - 1][c] === '1') {
121+
queue.push({ r: r - 1, c})
122+
}
123+
if ( r + 1 < nr && grid[r + 1][c] === '1' ) {
124+
queue.push({ r: r + 1, c})
125+
}
126+
if (c - 1 >= 0 && grid[r][c - 1] === '1' ) {
127+
queue.push({ r, c: c - 1})
128+
}
129+
if ( c + 1 < nc && grid[r][c + 1] === '1') {
130+
queue.push({ r, c: c + 1})
131+
}
132+
}
133+
}
134+
for(let i = 0; i < nr; i ++) {
135+
for(let j = 0; j < nc; j ++) {
136+
if (grid[i][j] === '1') {
137+
++result
138+
bfsHelper(grid, i, j)
139+
}
140+
}
141+
}
142+
return result
143+
};

‎Week04/programming/walking-robot-simulation.js‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
/**
2+
* @param {number[]} commands
3+
* @param {number[][]} obstacles
4+
* @return {number}
5+
*/
6+
var robotSim = function(commands, obstacles) {
7+
const dx = [0, 1, 0, -1]
8+
const dy = [1, 0, -1, 0]
9+
let di = x = y = 0
10+
const obstaclesMap = new Map()
11+
for(let i = 0; i < obstacles.length; i ++) {
12+
obstaclesMap.set(`${obstacles[i][0]}-${obstacles[i][1]}`, true)
13+
}
14+
let res = 0
15+
commands.forEach(command => {
16+
if (command === -2) {
17+
di = (di + 3) % 4
18+
} else if (command === -1) {
19+
di = (di + 1) % 4
20+
} else {
21+
for(let j = 1; j <= command; j ++) {
22+
const _x = x + dx[di]
23+
const _y = y + dy[di]
24+
if (!obstaclesMap.has(`${_x}-${_y}`)) {
25+
x = _x
26+
y = _y
27+
res = Math.max(res, x*x + y*y)
28+
}
29+
}
30+
}
31+
})
32+
33+
return res
34+
};

0 commit comments

Comments
 (0)