LC 2055. Plates Between Candles 蜡烛之间的盘子
https://leetcode.com/problems/plates-between-candles/
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
递归解法
func fib(n int) int {
if n == 0 || n == 1 {
return n
}
return fib(n - 1) + fib(n - 2)
}
迭代解法
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]
}
迭代解法（进一步优化空间复杂度）
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）
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
}
动态规划
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）
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
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
}
}