{"type":"doc","content":[{"type":"extension","attrs":{"layout":"default","extensionType":"com.atlassian.confluence.macro.core","extensionKey":"toc","parameters":{"macroParams":{"style":{"value":"none"}},"macroMetadata":{"macroId":{"value":"1e9808f4-df4f-4427-bd1d-045a6aa89287"},"schemaVersion":{"value":"1"},"title":"Table of Contents"}},"localId":"0658f940-f444-4b28-992c-1e23e42a7e34"}},{"type":"heading","attrs":{"level":2},"content":[{"text":"滑动窗口","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 220. Contains Duplicate III 存在重复元素 III","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/contains-duplicate-iii/description/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"java"},"content":[{"text":"class Solution {\n public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {\n TreeSet window = new TreeSet<>();\n\n int left = 0, right = 0;\n\n while (right < nums.length) {\n Integer ceiling = window.ceiling(nums[right]);\n if (ceiling != null && ceiling - nums[right] <= valueDiff) {\n return true;\n }\n Integer floor = window.floor(nums[right]);\n if (floor != null && nums[right] - floor <= valueDiff) {\n return true;\n }\n\n\n window.add(nums[right]);\n right++;\n\n if (right - left > indexDiff) {\n window.remove(nums[left]);\n left++;\n }\n }\n\n return false;\n }\n}","type":"text"}]},{"type":"heading","attrs":{"level":2},"content":[{"text":"二分搜索","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 852. 山脉数组的峰顶索引","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/peak-index-in-a-mountain-array/description/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func peakIndexInMountainArray(arr []int) int {\n // 找到 a >= a+1 的最小值\n L, R := 0, len(arr)-1\n for L < R {\n mid := L + (R - L) / 2\n\n if arr[mid] >= arr[mid+1] {\n R = mid\n } else {\n L = mid + 1\n }\n }\n\n return L\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"剑指 Offer 53 - I. 在排序数组中查找数字 I","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/description/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func countTarget(scores []int, target int) int {\n l := leftBound(scores, target)\n if l == len(scores) || scores[l] != target {\n return 0\n }\n r := leftBound(scores, target+1)\n\n return r - l\n}\n\nfunc leftBound(arr []int, target int) int {\n L, R := 0, len(arr)\n for L < R {\n mid := L + (R - L) / 2\n \n if arr[mid] >= target {\n R = mid\n } else {\n L = mid + 1\n }\n }\n return L\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"剑指 Offer 53 - II. 0～n-1 中缺失的数字","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/"}},{"text":" ","type":"text"}]},{"type":"paragraph","content":[{"text":"简单判断","type":"text","marks":[{"type":"strong"}]}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func takeAttendance(records []int) int {\n for i, x := range records {\n if i != x {\n return i\n }\n }\n\n return len(records)\n}","type":"text"}]},{"type":"paragraph","content":[{"text":"利用异或","type":"text","marks":[{"type":"strong"}]}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func takeAttendance(records []int) int {\n result := 0\n for _, x := range records {\n result ^= x\n }\n for i := 1; i <= len(records); i++ {\n result ^= i\n }\n return result\n}","type":"text"}]},{"type":"paragraph","content":[{"text":"利用二分","type":"text","marks":[{"type":"strong"}]}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func takeAttendance(records []int) int {\n n := len(records)\n if records[n-1] == n-1 {\n return n\n }\n\n L, R := 0, n\n for L < R {\n mid := L + (R - L) / 2\n if records[mid] != mid {\n R = mid\n } else {\n L = mid + 1\n }\n }\n return L\n}\n\n","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 33. 搜索旋转排序数组","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/search-in-rotated-sorted-array/description/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func search(nums []int, target int) int {\n L, R := 0, len(nums) - 1\n for L <= R {\n mid := L + (R - L) / 2\n\n if nums[mid] == target {\n return mid\n }\n\n if nums[mid] >= nums[L] {\n // 此时 L..mid 升序\n if nums[L] <= target && target <= nums[mid] {\n R = mid - 1\n } else {\n L = mid + 1\n }\n } else {\n // 此时 mid..R 升序\n if nums[mid] <= target && target <= nums[R] {\n L = mid + 1\n } else {\n R = mid - 1\n }\n }\n }\n\n return -1\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 81. 搜索旋转排序数组 II","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/search-in-rotated-sorted-array-ii/description/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func search(nums []int, target int) bool {\n L, R := 0, len(nums) - 1\n for L <= R {\n for L < R && nums[L] == nums[L+1] {\n L++\n }\n for L < R && nums[R] == nums[R-1] {\n R--\n }\n\n mid := L + (R - L) / 2\n\n if nums[mid] == target {\n return true\n }\n\n if nums[mid] >= nums[L] {\n // 此时 L..mid 升序\n if nums[L] <= target && target <= nums[mid] {\n R = mid - 1\n } else {\n L = mid + 1\n }\n } else {\n // 此时 mid..R 升序\n if nums[mid] <= target && target <= nums[R] {\n L = mid + 1\n } else {\n R = mid - 1\n }\n }\n }\n\n return false\n}","type":"text"}]},{"type":"paragraph"}],"version":1}

Browser not supported