又没早起，上海这疫情何时是个头啊😮💨
#动态规划
题目描述
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
提示：
0 < grid.length <= 200
0 < grid[0].length <= 200
|
解题思路
(1). 使用 BFS —— 爆内存；
(2). 使用 DFS —— 超时；
(3). 那就老老实实动态规划吧。
时间复杂度
O(M*N)
解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| func maxValue(grid [][]int) int {
dp := make([][]int, len(grid))
for i:=0; i<len(dp); i++ {
dp[i] = make([]int, len(grid[0]))
}
dp[0][0] = grid[0][0]
for i:=1; i<len(grid); i++ {
dp[i][0] = dp[i-1][0] + grid[i][0]
}
for i:=1; i<len(grid[0]); i++ {
dp[0][i] = dp[0][i-1] + grid[0][i]
}
for i:=1; i<len(grid); i++ {
for j:=1; j<len(grid[0]); j++ {
dp[i][j] = max(dp[i-1][j],dp[i][j-1])+grid[i][j]
}
}
return dp[len(grid)-1][len(grid[0])-1]
}
func max(a,b int) int {
if a > b {
return a
}
return b
}
|
#数组
题目描述
给定一个字符串数组 wordsDict 和两个字符串 word1 和 word2 ，返回列表中这两个单词之间的最短距离。
注意：word1 和 word2 是有可能相同的，并且它们将分别表示为列表中 两个独立的单词 。
1
2
3
4
5
6
7
8
9
10
11
12
13
| 示例 1：
输入：wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
输出：1
示例 2：
输入：wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes"
输出：3
提示：
1 <= wordsDict.length <= 105
1 <= wordsDict[i].length <= 10
wordsDict[i] 由小写英文字母组成
word1 和 word2 都在 wordsDict 中
|
解题思路
(1). 分两种情况讨论，当 word1 == word2 时 和 word1 != word2 时；
(2). 当 word1 == word2 时，遍历 wordDict，将 word1 的索引号用数组保存，之后再通过一次遍历，计算相邻索引号最小的差；
(3). 当 word1 != word2 时，通过两个标记 idx1 和 idx2，分别记录下每次出现 word1 和 word2 的索引号，然后通过一次遍历 wordDict，计算出最小的差。
时间复杂度
O(N)
解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| func shortestWordDistance(wordsDict []string, word1 string, word2 string) int {
idx1, idx2 := -1, -1
ret := math.MaxInt32
if word1 == word2 {
l := []int{}
for i:=0; i<len(wordsDict); i++ {
if wordsDict[i] == word1 {
l = append(l, i)
}
}
for i:=1; i<len(l); i++ {
ret = min(ret, l[i]-l[i-1])
}
return ret
}
for i:=0; i<len(wordsDict); i++ {
if wordsDict[i] == word1 {
idx1 = i
if idx2 != -1 {
ret = min(ret, abs(idx1,idx2))
}
} else if wordsDict[i] == word2 {
idx2 = i
if idx1 != -1 {
ret = min(ret, abs(idx1,idx2))
}
}
}
return ret
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func abs(a, b int) int {
if a > b {
return a-b
}
return b-a
}
|
