LC 2055. Plates Between Candles 蜡烛之间的盘子
https://leetcode.com/problems/plates-between-candles/
| Code Block |
|---|
|
func platesBetweenCandles(s string, queries [][]int) []int {
plates := make([]int, len(s))
candelsL := make([]int, len(s))
candelsR := make([]int, len(s))
candelsR[0] = -1
for i := 1; i < len(s); i++ {
if s[i] == '|' { // candel
plates[i] = plates[i-1]
candelsR[i] = i
} else { // plate
plates[i] = plates[i-1] + 1
candelsR[i] = candelsR[i-1]
}
}
candelsL[len(s)-1] = -1
for i := len(s)-2; i >= 0; i-- {
if s[i] == '|' { // candel
candelsL[i] = i
} else { // plate
candelsL[i] = candelsL[i+1]
}
}
result := make([]int, len(queries))
for i, q := range queries {
L := candelsL[q[0]]
R := candelsR[q[1]]
if L == -1 || R == -1 || L >= R {
result[i] = 0
} else {
result[i] = plates[R] - plates[L]
}
}
return result
} |
预处理前缀和，做到 O(1) 计算一个点右侧的最近蜡烛、左侧的最近蜡烛和两点之间的盘子数
动态规划
动态规划问题的一般形式就是求最值，求解动态规划的核心问题是穷举
写出暴力解
利用 memory table / 数组优化暴力解
LC 509. Fibonacci Number 斐波那契数
https://leetcode.com/problems/fibonacci-number
递归解法
| Code Block |
|---|
|
func fib(n int) int {
if n == 0 || n == 1 {
return n
}
return fib(n - 1) + fib(n - 2)
} |
迭代解法
| Code Block |
|---|
|
func fib(n int) int {
if n == 0 || n == 1 {
return n
}
dp := make([]int, n + 1)
dp[1] = 1
for i := 2; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
} |
迭代解法（进一步优化空间复杂度）
| Code Block |
|---|
func fib(n int) int {
if n == 0 || n == 1 {
return n
}
a, b := 0, 1
for i := 2; i <= n; i++ {
a, b = b, a + b
}
return b
} |
LC 322. 零钱兑换
https://leetcode.com/problems/coin-change
暴力解法（TLE）
| Code Block |
|---|
|
func coinChange(coins []int, amount int) int {
t := change(coins, amount, 0)
if t == math.MaxInt {
return -1
}
return t
}
func change(coins []int, amount int, currentTimes int) int {
if amount == 0 {
return currentTimes
}
minTimes := math.MaxInt
for _, coin := range coins {
balance := amount - coin
if balance >= 0 {
minTimes = min(minTimes, change(coins, balance, currentTimes + 1))
}
}
return minTimes
} |
动态规划
| Code Block |
|---|
|
func coinChange(coins []int, amount int) int {
dp := make([]int, amount + 1)
for x := 1; x <= amount; x++ {
minTimes := math.MaxInt
for _, coin := range coins {
balance := x - coin
if balance >= 0 && dp[balance] >= 0 {
minTimes = min(minTimes, dp[balance] + 1)
}
}
if minTimes == math.MaxInt {
dp[x] = -1
} else {
dp[x] = minTimes
}
}
// fmt.Println(dp)
return dp[amount]
}
|
进一步优化常数时间（利用 MAX 代替 IntMax 来减少 if）
| Code Block |
|---|
|
func coinChange(coins []int, amount int) int {
MAX := amount+1
dp := make([]int, amount + 1)
for x := 1; x <= amount; x++ {
dp[x] = MAX
for _, coin := range coins {
balance := x - coin
if balance >= 0 {
dp[x] = min(dp[x], dp[balance] + 1)
}
}
}
if dp[amount] >= MAX {
return -1
}
return dp[amount]
}
|
回溯
回溯算法和我们常说的 DFS 算法基本可以认为是同一种算法
抽象地说，解决一个回溯问题，实际上就是遍历一棵决策树的过程，树的每个叶子节点存放着一个合法答案。你把整棵树遍历一遍，把叶子节点上的答案都收集起来，就能得到所有的合法答案。
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。
LC 46. Permutations 全排列
https://leetcode.com/problems/permutations
| Code Block |
|---|
|
func permute(nums []int) (result [][]int) {
backtrack(&result, nums, make([]int, 0, len(nums)), make(map[int]bool, len(nums)))
return
}
func backtrack(result *[][]int, nums []int, current []int, used map[int]bool) {
if len(current) == len(nums) {
*result = append(*result, append([]int(nil), current...))
return
}
for _, num := range nums {
if used[num] {
continue
}
current = append(current, num)
used[num] = true
backtrack(result, nums, current, used)
current = current[:len(current)-1]
used[num] = false
}
} |
LC 51. N-Queens N 皇后
https://leetcode.com/problems/n-queens/
| Code Block |
|---|
|
func solveNQueens(n int) (result [][]string) {
solve(&result, n, newBoard(n), 0)
return
}
func solve(result *[][]string, n int, board [][]byte, row int) {
if row == n {
*result = append(*result, flat(board))
return
}
for col := 0; col < n; col++ {
if !isValid(board, row, col) {
continue
}
board[row][col] = 'Q'
solve(result, n, board, row+1)
board[row][col] = '.'
}
}
func isValid(board [][]byte, row, col int) bool {
n := len(board)
for i := 0; i <= row; i++ {
if board[i][col] == 'Q' {
return false
}
}
for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
if board[i][j] == 'Q' {
return false
}
}
for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
if board[i][j] == 'Q' {
return false
}
}
return true
}
func newBoard(n int) [][]byte {
board := make([][]byte, n)
for i := range board {
board[i] = bytes.Repeat([]byte("."), n)
}
return board
}
func flat(board [][]byte) []string {
result := make([]string, len(board))
for i := range result {
result[i] = string(board[i])
}
return result
} |
LC 52. N-Queens II N 皇后 II
https://leetcode.com/problems/n-queens-ii/
| Code Block |
|---|
func totalNQueens(n int) (result int) {
solve(&result, n, newBoard(n), 0)
return
}
func solve(result *int, n int, board [][]byte, row int) {
if row == n {
(*result)++
return
}
for col := 0; col < n; col++ {
if !isValid(board, row, col) {
continue
}
board[row][col] = 'Q'
solve(result, n, board, row+1)
board[row][col] = '.'
}
}
func isValid(board [][]byte, row, col int) bool {
n := len(board)
for i := 0; i <= row; i++ {
if board[i][col] == 'Q' {
return false
}
}
for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
if board[i][j] == 'Q' {
return false
}
}
for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
if board[i][j] == 'Q' {
return false
}
}
return true
}
func newBoard(n int) [][]byte {
board := make([][]byte, n)
for i := range board {
board[i] = bytes.Repeat([]byte("."), n)
}
return board
}
|