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