{"type":"doc","content":[{"type":"extension","attrs":{"layout":"default","extensionType":"com.atlassian.confluence.macro.core","extensionKey":"toc","parameters":{"macroParams":{"style":{"value":"none"}},"macroMetadata":{"macroId":{"value":"ea2e445b-440e-451a-8133-86a449470d5e"},"schemaVersion":{"value":"1"},"title":"Table of Contents"}},"localId":"ae242fd9-4b92-4abd-a1b3-aa6383b6f2c1"}},{"type":"heading","attrs":{"level":2},"content":[{"text":"二分搜索","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 240. Search a 2D Matrix II 搜索二维矩阵 II","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/search-a-2d-matrix-ii/"}},{"text":" ","type":"text"}]},{"type":"paragraph","content":[{"text":"（不是二分）","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func searchMatrix(matrix [][]int, target int) bool {\n m, n := len(matrix), len(matrix[0])\n\n i, j := 0, n-1\n\n for i < m && j >= 0 {\n v := matrix[i][j]\n if v == target {\n return true\n }\n\n if v < target {\n i++\n } else {\n j--\n }\n }\n\n return false\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 392. Is Subsequence 判断子序列","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/is-subsequence/description/"}},{"text":" ","type":"text"}]},{"type":"paragraph","content":[{"text":"（不是二分）","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func isSubsequence(s string, t string) bool {\n if s == \"\" {\n return true\n }\n\n j := 0\n for i := 0; i < len(t); i++ {\n if t[i] == s[j] {\n j++\n\n if j == len(s) {\n return true\n }\n }\n }\n return false\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 792. Number of Matching Subsequences 匹配子序列的单词数","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/number-of-matching-subsequences/description/"}},{"text":" ","type":"text"}]},{"type":"paragraph","content":[{"text":"暴力（没有超时）","type":"text","marks":[{"type":"strong"}]}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func numMatchingSubseq(s string, words []string) int {\n count := 0\n for _, word := range words {\n if isSubsequence(word, s) {\n count++\n }\n }\n return count\n}\n\nfunc isSubsequence(s string, t string) bool {\n if s == \"\" {\n return true\n }\n\n j := 0\n for i := 0; i < len(t); i++ {\n if t[i] == s[j] {\n j++\n\n if j == len(s) {\n return true\n }\n }\n }\n return false\n}","type":"text"}]},{"type":"paragraph","content":[{"text":"预处理 + 二分","type":"text","marks":[{"type":"strong"}]}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func numMatchingSubseq(s string, words []string) int {\n chars := getCharIndexes(s)\n \n count := 0\n for _, word := range words {\n if isSubsequence(chars, word) {\n count++\n }\n }\n return count\n}\n\nfunc getCharIndexes(s string) [][]int {\n result := make([][]int, 26)\n for i := range s {\n idx := charToIdx(s[i])\n \n result[idx] = append(result[idx], i)\n }\n return result\n}\n\nfunc charToIdx(c byte) int {\n return int(c - 'a')\n}\n\nfunc isSubsequence(s [][]int, word string) bool {\n j := -1\n\n for i := 0; i < len(word); i++ {\n j = search(s[charToIdx(word[i])], j)\n if j == -1 {\n return false\n }\n }\n\n return true\n}\n\nfunc search(arr []int, prevIndex int) int {\n target := prevIndex + 1\n\n L, R := 0, len(arr)-1\n for L < R {\n mid := L + (R - L) / 2\n if arr[mid] >= target {\n R = mid\n } else {\n L = mid + 1\n }\n }\n\n if R < 0 || R >= len(arr) {\n return -1\n }\n if arr[R] <= prevIndex {\n return -1\n }\n\n return arr[R]\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 658. 找到 K 个最接近的元素","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/find-k-closest-elements/description/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func findClosestElements(arr []int, k int, x int) []int {\n ii := leftBound(arr, x)\n if ii == len(arr) {\n return arr[len(arr)-k:len(arr)]\n }\n\n result := make([]int, 0, k)\n\n i, j := ii-1, ii // a < b\n\n for len(result) < k {\n if i < 0 {\n result = append(result, arr[j:j+k-len(result)]...)\n break\n }\n if j >= len(arr) {\n result = append(result, arr[i+1-k+len(result):i+1]...,\n )\n break\n }\n\n if x-arr[i] <= arr[j]-x {\n result = append(result, arr[i])\n i--\n } else {\n result = append(result, arr[j])\n j++\n }\n }\n\n sort.Ints(result)\n\n return result\n}\n\nfunc leftBound(arr []int, x int) int {\n L, R := 0, len(arr)\n for L < R {\n mid := L + (R - L) / 2\n if arr[mid] >= x {\n R = mid\n } else {\n L = mid + 1\n }\n }\n return R\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 35. Search Insert Position 搜索插入位置","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/search-insert-position/description/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func searchInsert(nums []int, target int) int {\n L, R := 0, len(nums)\n for L < R {\n mid := L + (R - L) / 2\n if nums[mid] >= target {\n R = mid\n } else {\n L = mid + 1\n }\n }\n return R\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 162. Find Peak Element 寻找峰值","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/find-peak-element/description/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func findPeakElement(nums []int) int {\n L, R := 0, len(nums)\n for L < R {\n mid := L + (R -L) / 2\n\n if mid == len(nums)-1 || nums[mid] > nums[mid + 1] {\n R = mid\n } else {\n L = mid + 1\n }\n }\n\n return R\n}","type":"text"}]}],"version":1}