LC 2055. Plates Between Candles 蜡烛之间的盘子

​https://leetcode.com/problems/plates-between-candles/

1func platesBetweenCandles(s string, queries [][]int) []int {
2    plates := make([]int, len(s))
3    candelsL := make([]int, len(s))
4    candelsR := make([]int, len(s))
5
6    candelsR[0] = -1
7    for i := 1; i < len(s); i++ {
8        if s[i] == '|' { // candel
9            plates[i] = plates[i-1]
10            candelsR[i] = i
11        } else { // plate
12            plates[i] = plates[i-1] + 1
13            candelsR[i] = candelsR[i-1]
14        }
15    }
16
17    candelsL[len(s)-1] = -1
18    for i := len(s)-2; i >= 0; i-- {
19        if s[i] == '|' { // candel
20            candelsL[i] = i
21        } else { // plate
22            candelsL[i] = candelsL[i+1]
23        }
24    }
25
26    result := make([]int, len(queries))
27    for i, q := range queries {
28        L := candelsL[q[0]]
29        R := candelsR[q[1]]
30
31        if L == -1 || R == -1 || L >= R {
32            result[i] = 0
33        } else {
34            result[i] = plates[R] - plates[L]
35        }
36    }
37
38    return result
39}

预处理前缀和，做到 O(1) 计算一个点右侧的最近蜡烛、左侧的最近蜡烛和两点之间的盘子数

动态规划

动态规划问题的一般形式就是求最值，求解动态规划的核心问题是穷举

1. 写出暴力解

2. 利用 memory table / 数组优化暴力解

LC 509. Fibonacci Number 斐波那契数

​https://leetcode.com/problems/fibonacci-number

递归解法

1func fib(n int) int {
2    if n == 0 || n == 1 {
3        return n
4    }
5    
6    return fib(n - 1) + fib(n - 2)
7}

迭代解法

1func fib(n int) int {
2    if n == 0 || n == 1 {
3        return n
4    }
5    
6    dp := make([]int, n + 1)
7    dp[1] = 1
8    
9    for i := 2; i <= n; i++ {
10        dp[i] = dp[i-1] + dp[i-2]
11    }
12    
13    return dp[n]
14}

迭代解法（进一步优化空间复杂度）

1func fib(n int) int {
2    if n == 0 || n == 1 {
3        return n
4    }
5    
6    a, b := 0, 1
7    
8    for i := 2; i <= n; i++ {
9        a, b = b, a + b
10    }
11    
12    return b
13}

LC 322. 零钱兑换

​https://leetcode.com/problems/coin-change

暴力解法（TLE）

1func coinChange(coins []int, amount int) int {    
2    t := change(coins, amount, 0)
3    if t == math.MaxInt {
4        return -1
5    }
6    return t
7}
8
9func change(coins []int, amount int, currentTimes int) int {
10    if amount == 0 {
11        return currentTimes
12    }
13    
14    minTimes := math.MaxInt
15    
16    for _, coin := range coins {
17        balance := amount - coin
18        if balance >= 0 {
19            minTimes = min(minTimes, change(coins, balance, currentTimes + 1))
20        }
21    }
22    
23
24    return minTimes
25}

动态规划

1func coinChange(coins []int, amount int) int {    
2    dp := make([]int, amount + 1)
3    
4    for x := 1; x <= amount; x++ {
5        minTimes := math.MaxInt
6        for _, coin := range coins {
7            balance := x - coin
8            if balance >= 0 && dp[balance] >= 0 {
9                minTimes = min(minTimes, dp[balance] + 1)
10            }
11        }
12        
13        if minTimes == math.MaxInt {
14            dp[x] = -1
15        } else {
16            dp[x] = minTimes
17        }
18    }
19    
20    // fmt.Println(dp)
21    
22    return dp[amount]
23}
24

进一步优化常数时间（利用 MAX 代替 IntMax 来减少 if）

1func coinChange(coins []int, amount int) int {    
2    MAX := amount+1
3    dp := make([]int, amount + 1)
4    
5    for x := 1; x <= amount; x++ {
6        dp[x] = MAX
7        for _, coin := range coins {
8            balance := x - coin
9            if balance >= 0 {
10                dp[x] = min(dp[x], dp[balance] + 1)
11            }
12        }
13    }
14        
15    if dp[amount] >= MAX {
16        return -1
17    }
18    
19    return dp[amount]
20}
21

回溯

回溯算法和我们常说的 DFS 算法基本可以认为是同一种算法

抽象地说，解决一个回溯问题，实际上就是遍历一棵决策树的过程，树的每个叶子节点存放着一个合法答案。你把整棵树遍历一遍，把叶子节点上的答案都收集起来，就能得到所有的合法答案。

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。

LC 46. Permutations 全排列

​https://leetcode.com/problems/permutations

1func permute(nums []int) (result [][]int) {
2    backtrack(&result, nums, make([]int, 0, len(nums)), make(map[int]bool, len(nums)))
3    
4    return
5}
6
7func backtrack(result *[][]int, nums []int, current []int, used map[int]bool) {
8    if len(current) == len(nums) {
9        *result = append(*result, append([]int(nil), current...))
10        return
11    }
12    
13    for _, num := range nums {
14        if used[num] {
15            continue
16        }
17        
18        current = append(current, num)
19        used[num] = true
20        
21        backtrack(result, nums, current, used)
22        
23        current = current[:len(current)-1]
24        used[num] = false
25    }
26}

LC 51. N-Queens N 皇后

​https://leetcode.com/problems/n-queens/

1func solveNQueens(n int) (result [][]string) {
2    solve(&result, n, newBoard(n), 0)
3    return
4}
5
6func solve(result *[][]string, n int, board [][]byte, row int) {
7    if row == n {
8        *result = append(*result, flat(board))
9        return
10    }
11    
12    for col := 0; col < n; col++ {
13        if !isValid(board, row, col) {
14            continue
15        }
16        
17        board[row][col] = 'Q'
18        
19        solve(result, n, board, row+1)
20        
21        board[row][col] = '.'
22    }
23}
24
25func isValid(board [][]byte, row, col int) bool {
26    n := len(board)
27    
28    for i := 0; i <= row; i++ {
29		if board[i][col] == 'Q' {
30			return false
31		}
32	}
33    for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
34		if board[i][j] == 'Q' {
35			return false
36		}
37	}
38    for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
39		if board[i][j] == 'Q' {
40			return false
41		}
42	}
43    
44    return true
45}
46
47func newBoard(n int) [][]byte {
48    board := make([][]byte, n)
49    for i := range board {
50        board[i] = bytes.Repeat([]byte("."), n)
51    }
52    return board
53}
54
55func flat(board [][]byte) []string {
56    result := make([]string, len(board))
57    for i := range result {
58        result[i] = string(board[i])
59    }
60    return result
61}

LC 52. N-Queens II N 皇后 II

​https://leetcode.com/problems/n-queens-ii/

1func totalNQueens(n int) (result int) {
2    solve(&result, n, newBoard(n), 0)
3    return
4}
5
6func solve(result *int, n int, board [][]byte, row int) {
7    if row == n {
8        (*result)++
9        return
10    }
11    
12    for col := 0; col < n; col++ {
13        if !isValid(board, row, col) {
14            continue
15        }
16        
17        board[row][col] = 'Q'
18        
19        solve(result, n, board, row+1)
20        
21        board[row][col] = '.'
22    }
23}
24
25func isValid(board [][]byte, row, col int) bool {
26    n := len(board)
27    
28    for i := 0; i <= row; i++ {
29		if board[i][col] == 'Q' {
30			return false
31		}
32	}
33    for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
34		if board[i][j] == 'Q' {
35			return false
36		}
37	}
38    for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
39		if board[i][j] == 'Q' {
40			return false
41		}
42	}
43    
44    return true
45}
46
47func newBoard(n int) [][]byte {
48    board := make([][]byte, n)
49    for i := range board {
50        board[i] = bytes.Repeat([]byte("."), n)
51    }
52    return board
53}
54