LCCUP力扣春季赛
LCCUP（力扣杯赛春季赛）
第一题
思路
这道题上手并没有什么好的思路，那就直接上模拟。观察一下数据大小，只有$10^3$，那么时间复杂度$10^6$也就是$O(n^2)$是可以接受的。所以直接模拟。（我在此处直接调用了copy方法，灵神采用了更加简洁的方法append，底层原理是一致的）
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func supplyWagon(supplies []int) []int {
n := len(supplies)
for len(supplies) > n/2 {
mn := 2001
idx := -1
for i := 1; i < len(supplies); i++ {
if supplies[i]+supplies[i-1] < mn {
mn = supplies[i] + supplies[i-1]
idx = i
}
}
supplies[idx-1] += supplies[idx]
copy(supplies[idx:], supplies[idx+1:])
supplies = supplies[:len(supplies)-1]
}
return supplies
}
复杂度
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(1)$
第二题
思路
简单的字符串分割，然后使用map去重和统计，比较map在遍历中大小之差。
这道题我吃了两个虫子，第一遍没理解题意，第二遍没处理空串
""，大失败。
代码
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
func adventureCamp(expeditions []string) int {
mx := 0
ans := -1
start := map[string]struct{}{}
for _, str := range strings.Split(expeditions[0], "->") {
if str == "" {
continue
}
start[str] = struct{}{}
}
for i, expedition := range expeditions[1:] {
size := len(start)
for _, str := range strings.Split(expedition, "->") {
if str == "" {
continue
}
start[str] = struct{}{}
}
if tmp := len(start); tmp-size > mx {
mx = tmp - size
ans = i
}
}
if ans == -1 {
return -1
}
return ans + 1
}
复杂度
- 时间复杂度：$O(L)$（$L$是所有字符串的长度之和）
- 空间复杂度：$O(L)$
第三题
思路
扫描线，一看到这个就想到了前几天看到的扫描线。通过收集需要扫描的x线和需要扫描的y线，遍历全部正方形（当然，基于其数据量只有$100$个正方形）。
当然，灵神有更加科学的处理方法，详解见：https://leetcode.cn/problems/xepqZ5/solution/chi-san-hua-er-wei-chai-fen-by-endlessch-q43z/
代码
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
func fieldOfGreatestBlessing(forceField [][]int) int {
n := len(forceField)
newField := make([][4]float64, n)
xs := map[float64]struct{}{}
for i, ints := range forceField {
x, y, f := float64(ints[0]), float64(ints[1]), float64(ints[2])/2
newField[i] = [4]float64{x - f, y - f, x + f, y + f}
xs[x+f] = struct{}{}
xs[x-f] = struct{}{}
}
scanX := make([]float64, 0)
for x := range xs {
scanX = append(scanX, x)
}
sort.Float64s(scanX)
ans := 0
for _, x := range scanX {
scanY := map[float64]struct{}{}
for _, float64s := range newField {
x1, y1, x2, y2 := float64s[0], float64s[1], float64s[2], float64s[3]
if x1 <= x && x <= x2 {
scanY[y1] = struct{}{}
scanY[y2] = struct{}{}
}
}
for y := range scanY {
sum := 0
for _, float64s := range newField {
x1, y1, x2, y2 := float64s[0], float64s[1], float64s[2], float64s[3]
if x1 <= x && x <= x2 && y1 <= y && y <= y2 {
sum++
}
}
if sum > ans {
ans = sum
}
}
}
return ans
}
复杂度
- 时间复杂度：$O(n^3)$
- 空间复杂度：$O(n)$
第四题
思路
第一眼这不是BFS嘛，然后细读题目，发现需要解决几个具体问题：
- 返回的是加上了
DEBUFF后最少移动多少次，同时，守护者又是具有博弈心理的。因此，他更像是最大值的最小值（灵神有一个临场解法用到了这个）。 - 到终点需要一次跳跃，我们需要知道勇士在某一点时跳跃到哪一个点，这个是可以预计算出来的，方法是倒着的
BFS——从重点出发的全局BFS。 - 由于双方具有博弈心理，那么双方必须选择最优解。也就是说，勇士选择了一条前往终点的道路，那么，守护者必然在该道路上选择一个 “可跳跃到最恶心人地方的点” 发动跳跃：
- 可以跳到无法到达的角落（必选）
- 水平跳和竖直跳之间的最大值
第1个点可以由第3个点解决，第三个点其实可以抽象为最短关键路径，和LeetCode上一道原题很相似（1631. 最小体力消耗路径），可以使用 dijkstra 最短路计算（堆优化 + 最短距离去收录每一个迷宫格子）。
比赛当时第3个点想了一个半小时…
代码
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
type qNode struct {
i, j int
}
type hNode struct {
i, j, v int
}
var direct = [][]int\{\{0, -1}, {0, 1}, {1, 0}, {-1, 0\}\}
var cache [][]int
type Heap struct {
slice []*hNode
}
func (h *Heap) Push(x interface{}) {
h.slice = append(h.slice, x.(*hNode))
}
func (h *Heap) Pop() interface{} {
old := h.slice
l := len(old) - 1
v := old[l]
h.slice = old[:l]
return v
}
func (h *Heap) Len() int {
return len(h.slice)
}
func (h *Heap) Less(i, j int) bool {
return h.slice[i].v < h.slice[j].v
}
func (h *Heap) Swap(i, j int) {
h.slice[i], h.slice[j] = h.slice[j], h.slice[i]
}
func challengeOfTheKeeper(maze []string) int {
n := len(maze)
cache = make([][]int, n)
dis := make([][]int, n)
DIS := make([][]int, n)
ans := make([][]int, n)
// find start
start := &qNode{i: -1, j: -1}
end := &qNode{i: -1, j: -1}
for i := 0; i < n; i++ {
cache[i] = make([]int, n)
dis[i] = make([]int, n)
ans[i] = make([]int, n)
DIS[i] = make([]int, n)
for j := 0; j < n; j++ {
cache[i][j] = -1
dis[i][j] = math.MaxInt
DIS[i][j] = -1
if maze[i][j] == 'S' {
start.i = i
start.j = j
} else if maze[i][j] == 'T' {
end.i = i
end.j = j
}
}
}
if start.i == -1 || end.i == -1 {
return -1
}
queue := make([]*qNode, 0)
queue = append(queue, &qNode{end.i, end.j})
cache[end.i][end.j] = 0
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
for _, d := range direct {
if i, j := node.i+d[0], node.j+d[1]; 0 <= i && i < n && 0 <= j && j < n && maze[i][j] != '#' && cache[i][j] == -1 {
cache[i][j] = cache[node.i][node.j] + 1
queue = append(queue, &qNode{i, j})
}
}
}
if cache[start.i][start.j] == -1 {
return -1
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if maze[i][j] == '.' {
tmp := 0
if _i, _j := n-1-i, j; maze[_i][_j] != '#' {
if cache[_i][_j] == -1 {
tmp = math.MaxInt
}
tmp = max(tmp, cache[_i][_j])
}
if _i, _j := i, n-1-j; maze[_i][_j] != '#' {
if cache[_i][_j] == -1 {
tmp = math.MaxInt
}
tmp = max(tmp, cache[_i][_j])
}
dis[i][j] = tmp
} else {
dis[i][j] = math.MaxInt
}
}
}
dis[start.i][start.j] = 0
dis[end.i][end.j] = 0
// key way
hp := &Heap{}
heap.Push(hp, &hNode{start.i, start.j, 0})
for hp.Len() > 0 {
top := heap.Pop(hp).(*hNode)
if DIS[top.i][top.j] > -1 {
continue
}
DIS[top.i][top.j] = top.v
for _, d := range direct {
if i, j := top.i+d[0], top.j+d[1]; 0 <= i && i < n && 0 <= j && j < n && maze[i][j] != '#' && DIS[i][j] == -1 {
heap.Push(hp, &hNode{i, j, max(top.v, dis[i][j])})
}
}
}
//for i := 0; i < n; i++ {
// for j := 0; j < n; j++ {
// fmt.Print(DIS[i][j], " ")
// }
// fmt.Println()
//}
if DIS[end.i][end.j] == math.MaxInt {
return -1
} else {
return DIS[end.i][end.j]
}
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
复杂度
- 时间复杂度：$O(n^2\log(n^2))$
- 空间复杂度：$O(n^2)$
第五题
思路
借用了灵神的大体思想，
DFS（每行）深搜的内部再来一次DFS（每行中的每个元素）。
- 外层的
DFS：每一行每一行地去遍历，记录每一行的状态，因此存在两个参数，代表行号的$r$和代表一行状态的$rowMask$。由于这一部分会出现大面积地重复，因此可以使用记忆化搜索来优化。 - 内层的
DFS：固定该行的行号，根据该行前面棋子的状态，和上一行的状态，判断并选择，并改变该行的状态，也是一个递推。
难点：
如何决定状态？考虑到题意，我们推断并分析出了如下的自动机：
每个状态可以用三位的二进制表示（$0-7$），同时也能列出状态转移矩阵。
利用状态压缩来剪枝。
如何减少空间开销和时间开销？（放在复杂度中分析）
代码
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
func getSchemeCount(n int, m int, chessboard []string) int64 {
// auto
states := [8][2]int\{\{1, 2}, {3, 5}, {6, 4}, {3, 7}, {7, 4}, {6, 7}, {7, 5}, {7, 7\}\}
board := make([][]byte, n)
for i := 0; i < n; i++ {
board[i] = make([]byte, m)
for j := 0; j < m; j++ {
board[i][j] = chessboard[i][j]
}
}
if m > n {
board = rotate(n, m, board)
n, m = m, n
}
cache := make([][]int64, n)
for i := 0; i < n; i++ {
cache[i] = make([]int64, 1<<(m*3))
for j := 0; j < 1<<(m*3); j++ {
cache[i][j] = -1
}
}
var dfs1 func(r int, rowMask int) int64
var dfs2 func(r, c int, formerMask, rowMask int) int64
dfs1 = func(r int, rowMask int) int64 {
if r == n {
return 1
}
if cache[r][rowMask] != -1 {
return cache[r][rowMask]
}
cache[r][rowMask] = dfs2(r, 0, 0, rowMask)
return cache[r][rowMask]
}
dfs2 = func(r, c int, formerState, rowMask int) int64 {
if c == m {
return dfs1(r+1, rowMask)
}
switch board[r][c] {
case 'B':
if s1, s2 := states[formerState][0], states[rowMask>>(c*3)&7][0]; s1 == 7 || s2 == 7 {
return 0
} else {
return dfs2(r, c+1, s1, s2<<(c*3)|rowMask&(^(7<<(c*3))))
}
case 'R':
if s1, s2 := states[formerState][1], states[rowMask>>(c*3)&7][1]; s1 == 7 || s2 == 7 {
return 0
} else {
return dfs2(r, c+1, s1, s2<<(c*3)|rowMask&(^(7<<(c*3))))
}
case '?':
// .
sum := dfs2(r, c+1, formerState, rowMask)
// B
if s1, s2 := states[formerState][0], states[rowMask>>(c*3)&7][0]; s1 == 7 || s2 == 7 {
sum += 0
} else {
sum += dfs2(r, c+1, s1, s2<<(c*3)|rowMask&(^(7<<(c*3))))
}
// R
if s1, s2 := states[formerState][1], states[rowMask>>(c*3)&7][1]; s1 == 7 || s2 == 7 {
sum += 0
} else {
sum += dfs2(r, c+1, s1, s2<<(c*3)|rowMask&(^(7<<(c*3))))
}
return sum
default:
return dfs2(r, c+1, formerState, rowMask)
}
}
return dfs1(0, 0)
}
func rotate(n, m int, a [][]byte) (b [][]byte) {
b = make([][]byte, m)
for i := 0; i < m; i++ {
b[i] = make([]byte, n)
for j := 0; j < n; j++ {
b[i][j] = a[n-1-j][i]
}
}
return
}
复杂度
- 时间复杂度：$O(n\cdot24^m)$
- 空间复杂度：$O(n\cdot 8^m)$
空间复杂度比较好计算，我们开了一个cache，大小为$n \times (1 \ll (3 \times m))$，那么，稍作调整自然而然得出结论。
重点是时间复杂度，我们对二维都进行了一次搜索，固定每一行潜在$8^m$次搜索，每一行每一列有$3^m$次，所以总共有$n \times 8^m \times 3^m$。
那么如何控制复杂度呢？可见复杂度随着$m$的上升上升更快，所以我们要抑制$m$的增长。由于$mn \le 30$，所以当$m \ge 6$时，通过将棋盘旋转90度即可。
本文由作者按照 CC BY 4.0 进行授权