{"type":"doc","content":[{"type":"extension","attrs":{"layout":"default","extensionType":"com.atlassian.confluence.macro.core","extensionKey":"toc","parameters":{"macroParams":{"style":{"value":"none"}},"macroMetadata":{"macroId":{"value":"4ce7a9c8-8ce8-406e-9f37-ef429ed01205"},"schemaVersion":{"value":"1"},"title":"Table of Contents"}},"localId":"1dce5507-da67-4a32-9ff1-54f22203255b"}},{"type":"heading","attrs":{"level":2},"content":[{"text":"双指针链表","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 373. Find K Pairs with Smallest Sums 查找和最小的 K 对数字","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/find-k-pairs-with-smallest-sums/"}},{"text":" ","type":"text"}]},{"type":"paragraph","content":[{"type":"status","attrs":{"color":"blue","style":"bold","text":"待复习","localId":"c79e23c5-4447-4761-bb14-fbdabfc92269"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func kSmallestPairs(nums1 []int, nums2 []int, k int) [][]int {\n result := make([][]int, 0, k)\n \n h_ := make(Heap, 0, k)\n h := &h_\n \n for _, num := range nums1 {\n heap.Push(h, []int{num, nums2[0], 0})\n }\n \n for i := 0; i < k; i++ {\n top := heap.Pop(h).([]int)\n result = append(result, []int{top[0], top[1]})\n \n if p := top[2] + 1; p < len(nums2) {\n heap.Push(h, []int{top[0], nums2[p], p})\n }\n }\n \n return result\n}\n\ntype Heap [][]int\n\nfunc (h Heap) Len() int { return len(h) }\nfunc (h Heap) Less(i, j int) bool { return h[i][0] + h[i][1] < h[j][0] + h[j][1] }\nfunc (h Heap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }\nfunc (h *Heap) Push(x any) {\n\t*h = append(*h, x.([]int))\n}\n\nfunc (h *Heap) Pop() any {\n\told := *h\n\tn := len(old)\n\tx := old[n-1]\n\t*h = old[0 : n-1]\n\treturn x\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 2. Add Two Numbers 两数相加","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/add-two-numbers/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"/**\n * Definition for singly-linked list.\n * type ListNode struct {\n * Val int\n * Next *ListNode\n * }\n */\nfunc addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {\n dummy := &ListNode{}\n \n h := dummy\n h1, h2 := l1, l2\n \n carry := 0\n for h1 != nil || h2 != nil {\n num1, num2 := 0, 0\n \n if h1 != nil && h2 != nil {\n num1, num2 = h1.Val, h2.Val\n h1 = h1.Next\n h2 = h2.Next\n } else if h1 != nil {\n num1 = h1.Val\n h1 = h1.Next\n } else {\n num2 = h2.Val\n h2 = h2.Next\n }\n \n result := num1 + num2 + carry\n if result >= 10 {\n result -= 10\n carry = 1\n } else {\n carry = 0\n }\n\n node := &ListNode{Val: result}\n h.Next = node\n h = node\n }\n \n if carry > 0 {\n node := &ListNode{Val: carry}\n h.Next = node\n h = node\n }\n \n return dummy.Next\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 445. Add Two Numbers II 两数相加 II","type":"text"}]},{"type":"paragraph","content":[{"text":"https://leetcode.com/problems/add-two-numbers-ii/","type":"text","marks":[{"type":"link","attrs":{"href":"https://leetcode.com/problems/add-two-numbers-ii/"}}]}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"/**\n * Definition for singly-linked list.\n * type ListNode struct {\n * Val int\n * Next *ListNode\n * }\n */\nfunc addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {\n nodes1 := fromList(l1)\n nodes2 := fromList(l2)\n \n result := add(nodes1, nodes2)\n \n return toList(result)\n}\n\nfunc add(nodes1, nodes2 []int) []int {\n result := make([]int, 0, 101)\n \n p1, p2 := 0, 0\n carry := 0\n \n for p1 < len(nodes1) || p2 < len(nodes2) || carry > 0 {\n val := carry\n if p1 < len(nodes1) {\n val += nodes1[p1]\n p1++\n }\n if p2 < len(nodes2) {\n val += nodes2[p2]\n p2++\n }\n \n if val >= 10 {\n val -= 10\n carry = 1\n } else {\n carry = 0\n }\n \n result = append(result, val)\n }\n \n return result\n}\n\nfunc fromList(h *ListNode) []int {\n nodes := make([]int, 0, 100)\n for h != nil {\n nodes = append(nodes, h.Val)\n h = h.Next\n }\n \n reverse(nodes)\n \n return nodes\n}\n\nfunc toList(nodes []int) *ListNode {\n reverse(nodes)\n \n dummy := &ListNode{}\n \n h := dummy\n for _, num := range nodes {\n h.Next = &ListNode{Val: num}\n h = h.Next\n }\n \n return dummy.Next\n}\n\nfunc reverse(arr []int) {\n i, j := 0, len(arr)-1\n for i < j {\n arr[i], arr[j] = arr[j], arr[i]\n i++\n j--\n }\n}","type":"text"}]},{"type":"heading","attrs":{"level":2},"content":[{"text":"丑数","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 313. Super Ugly Number 超级丑数","type":"text"}]},{"type":"paragraph","content":[{"text":"https://leetcode.com/problems/super-ugly-number/","type":"text","marks":[{"type":"link","attrs":{"href":"https://leetcode.com/problems/super-ugly-number/"}}]},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func nthSuperUglyNumber(n int, primes []int) int {\n h_ := make(IntHeap, 0, n)\n h := &h_\n \n heap.Push(h, 1)\n \n num := -1\n exists := make(map[int]struct{})\n \n for i := 0; i < n; i++ {\n num = heap.Pop(h).(int)\n \n for _, p := range primes {\n nn := num * p\n if nn < num || nn > math.MaxInt32 {\n continue\n }\n \n if _, exist := exists[nn]; exist {\n continue\n }\n exists[nn] = struct{}{}\n \n heap.Push(h, nn)\n }\n }\n \n return num\n}\n\n// An IntHeap is a min-heap of ints.\ntype IntHeap []int\n\nfunc (h IntHeap) Len() int { return len(h) }\nfunc (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }\nfunc (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }\n\nfunc (h *IntHeap) Push(x any) {\n\t// Push and Pop use pointer receivers because they modify the slice's length,\n\t// not just its contents.\n\t*h = append(*h, x.(int))\n}\n\nfunc (h *IntHeap) Pop() any {\n\told := *h\n\tn := len(old)\n\tx := old[n-1]\n\t*h = old[0 : n-1]\n\treturn x\n}\n","type":"text"}]},{"type":"paragraph","content":[{"text":"不使用 map 去重 - 而是使用合并 k 个有序链表（丑数 II）的思路","type":"text","marks":[{"type":"strong"}]}]},{"type":"paragraph","content":[{"type":"status","attrs":{"color":"blue","style":"bold","text":"待复习","localId":"4dec86e6-0286-47d0-a626-4fe77b0af01e"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func nthSuperUglyNumber(n int, primes []int) int {\n h_ := make(Heap, 0, n)\n h := &h_\n \n for _, p := range primes {\n heap.Push(h, [3]int{1, p, 0})\n }\n \n uglys := make([]int, 1, n)\n uglys[0] = 1\n \n \n for len(uglys) < n {\n top := heap.Pop(h).([3]int)\n num, p, pi := top[0], top[1], top[2]\n \n if num != uglys[len(uglys) - 1] {\n uglys = append(uglys, num)\n }\n \n heap.Push(h, [3]int{p * uglys[pi], p, pi+1})\n }\n \n return uglys[n-1]\n}\n\ntype Heap [][3]int\n\nfunc (h Heap) Len() int { return len(h) }\nfunc (h Heap) Less(i, j int) bool { return h[i][0] < h[j][0] }\nfunc (h Heap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }\n\nfunc (h *Heap) Push(x any) {\n\t*h = append(*h, x.([3]int))\n}\n\nfunc (h *Heap) Pop() any {\n\told := *h\n\tn := len(old)\n\tx := old[n-1]\n\t*h = old[0 : n-1]\n\treturn x\n}\n","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 1201. Ugly Number III 丑数 III","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/ugly-number-iii/"}},{"text":" ","type":"text"}]},{"type":"paragraph","content":[{"text":"合并有序链表解法 (TLE)","type":"text","marks":[{"type":"strong"}]}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func nthUglyNumber(n int, a int, b int, c int) int {\n h := &Heap{}\n \n heap.Push(h, [2]int{a, a})\n heap.Push(h, [2]int{b, b})\n heap.Push(h, [2]int{c, c})\n \n i := 0\n num := 0\n for i < n {\n top := heap.Pop(h).([2]int)\n v, factor := top[0], top[1]\n \n if v != num {\n num = v\n i++\n }\n \n heap.Push(h, [2]int{v + factor, factor})\n }\n \n return num\n}\n\ntype Heap [][2]int\n\nfunc (h Heap) Len() int { return len(h) }\nfunc (h Heap) Less(i, j int) bool { return h[i][0] < h[j][0] }\nfunc (h Heap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }\n\nfunc (h *Heap) Push(x any) {\n\t*h = append(*h, x.([2]int))\n}\n\nfunc (h *Heap) Pop() any {\n\told := *h\n\tn := len(old)\n\tx := old[n-1]\n\t*h = old[0 : n-1]\n\treturn x\n}","type":"text"}]},{"type":"paragraph","content":[{"text":"二分 + 集合解法","type":"text","marks":[{"type":"strong"}]}]},{"type":"paragraph","content":[{"type":"status","attrs":{"color":"blue","style":"bold","text":"待复习","localId":"1aee131b-622d-4cbc-bc73-94aa47375d68"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func nthUglyNumber(n int, a int, b int, c int) int {\n L, R := 1, int(2e9) + 1\n \n // 二分：找到 [L, R) 范围内满足 f() == n 的最小值\n \n for L < R {\n mid := L + (R - L) / 2\n \n if f(mid, a, b, c) >= n {\n R = mid\n } else { // <\n L = mid + 1\n }\n }\n \n return R\n}\n\nfunc f(num int, a, b, c int) int {\n setA := num / a\n setB := num / b\n setC := num / c\n \n lcmAB := lcm(a, b)\n \n setAB := num / lcmAB\n setAC := num / lcm(a, c)\n setBC := num / lcm(b, c)\n \n setABC := num / lcm(lcmAB, c)\n \n return setA + setB + setC - setAB - setAC - setBC + setABC\n}\n\nfunc lcm(a, b int) int {\n return a * b / gcd(a, b)\n}\n\nfunc gcd(a, b int) int {\n // assert a <= b\n if a > b { a, b = b, a }\n \n for a != 0 {\n a, b = b % a, a\n }\n \n return b\n}","type":"text"}]}],"version":1}