双指针链表
LC 373. Find K Pairs with Smallest Sums 查找和最小的 K 对数字
https://leetcode.com/problems/find-k-pairs-with-smallest-sums/
func kSmallestPairs(nums1 []int, nums2 []int, k int) [][]int { result := make([][]int, 0, k) h_ := make(Heap, 0, k) h := &h_ for _, num := range nums1 { heap.Push(h, []int{num, nums2[0], 0}) } for i := 0; i < k; i++ { top := heap.Pop(h).([]int) result = append(result, []int{top[0], top[1]}) if p := top[2] + 1; p < len(nums2) { heap.Push(h, []int{top[0], nums2[p], p}) } } return result } type Heap [][]int func (h Heap) Len() int { return len(h) } func (h Heap) Less(i, j int) bool { return h[i][0] + h[i][1] < h[j][0] + h[j][1] } func (h Heap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *Heap) Push(x any) { *h = append(*h, x.([]int)) } func (h *Heap) Pop() any { old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x }
LC 2. Add Two Numbers 两数相加
https://leetcode.com/problems/add-two-numbers/
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { dummy := &ListNode{} h := dummy h1, h2 := l1, l2 carry := 0 for h1 != nil || h2 != nil { num1, num2 := 0, 0 if h1 != nil && h2 != nil { num1, num2 = h1.Val, h2.Val h1 = h1.Next h2 = h2.Next } else if h1 != nil { num1 = h1.Val h1 = h1.Next } else { num2 = h2.Val h2 = h2.Next } result := num1 + num2 + carry if result >= 10 { result -= 10 carry = 1 } else { carry = 0 } node := &ListNode{Val: result} h.Next = node h = node } if carry > 0 { node := &ListNode{Val: carry} h.Next = node h = node } return dummy.Next }
LC 445. Add Two Numbers II 两数相加 II
https://leetcode.com/problems/add-two-numbers-ii/
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { nodes1 := fromList(l1) nodes2 := fromList(l2) result := add(nodes1, nodes2) return toList(result) } func add(nodes1, nodes2 []int) []int { result := make([]int, 0, 101) p1, p2 := 0, 0 carry := 0 for p1 < len(nodes1) || p2 < len(nodes2) || carry > 0 { val := carry if p1 < len(nodes1) { val += nodes1[p1] p1++ } if p2 < len(nodes2) { val += nodes2[p2] p2++ } if val >= 10 { val -= 10 carry = 1 } else { carry = 0 } result = append(result, val) } return result } func fromList(h *ListNode) []int { nodes := make([]int, 0, 100) for h != nil { nodes = append(nodes, h.Val) h = h.Next } reverse(nodes) return nodes } func toList(nodes []int) *ListNode { reverse(nodes) dummy := &ListNode{} h := dummy for _, num := range nodes { h.Next = &ListNode{Val: num} h = h.Next } return dummy.Next } func reverse(arr []int) { i, j := 0, len(arr)-1 for i < j { arr[i], arr[j] = arr[j], arr[i] i++ j-- } }
丑数
LC 313. Super Ugly Number 超级丑数
https://leetcode.com/problems/super-ugly-number/
func nthSuperUglyNumber(n int, primes []int) int { h_ := make(IntHeap, 0, n) h := &h_ heap.Push(h, 1) num := -1 exists := make(map[int]struct{}) for i := 0; i < n; i++ { num = heap.Pop(h).(int) for _, p := range primes { nn := num * p if nn < num || nn > math.MaxInt32 { continue } if _, exist := exists[nn]; exist { continue } exists[nn] = struct{}{} heap.Push(h, nn) } } return num } // An IntHeap is a min-heap of ints. type IntHeap []int func (h IntHeap) Len() int { return len(h) } func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *IntHeap) Push(x any) { // Push and Pop use pointer receivers because they modify the slice's length, // not just its contents. *h = append(*h, x.(int)) } func (h *IntHeap) Pop() any { old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x }
不使用 map 去重 - 而是使用合并 k 个有序链表（丑数 II）的思路
func nthSuperUglyNumber(n int, primes []int) int { h_ := make(Heap, 0, n) h := &h_ for _, p := range primes { heap.Push(h, [3]int{1, p, 0}) } uglys := make([]int, 1, n) uglys[0] = 1 for len(uglys) < n { top := heap.Pop(h).([3]int) num, p, pi := top[0], top[1], top[2] if num != uglys[len(uglys) - 1] { uglys = append(uglys, num) } heap.Push(h, [3]int{p * uglys[pi], p, pi+1}) } return uglys[n-1] } type Heap [][3]int func (h Heap) Len() int { return len(h) } func (h Heap) Less(i, j int) bool { return h[i][0] < h[j][0] } func (h Heap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *Heap) Push(x any) { *h = append(*h, x.([3]int)) } func (h *Heap) Pop() any { old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x }
LC 1201. Ugly Number III 丑数 III
https://leetcode.com/problems/ugly-number-iii/
合并有序链表解法 (TLE)
func nthUglyNumber(n int, a int, b int, c int) int { h := &Heap{} heap.Push(h, [2]int{a, a}) heap.Push(h, [2]int{b, b}) heap.Push(h, [2]int{c, c}) i := 0 num := 0 for i < n { top := heap.Pop(h).([2]int) v, factor := top[0], top[1] if v != num { num = v i++ } heap.Push(h, [2]int{v + factor, factor}) } return num } type Heap [][2]int func (h Heap) Len() int { return len(h) } func (h Heap) Less(i, j int) bool { return h[i][0] < h[j][0] } func (h Heap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *Heap) Push(x any) { *h = append(*h, x.([2]int)) } func (h *Heap) Pop() any { old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x }
二分 + 集合解法
待复习
func nthUglyNumber(n int, a int, b int, c int) int { L, R := 1, int(2e9) + 1 // 二分：找到 [L, R) 范围内满足 f() == n 的最小值 for L < R { mid := L + (R - L) / 2 if f(mid, a, b, c) >= n { R = mid } else { // < L = mid + 1 } } return R } func f(num int, a, b, c int) int { setA := num / a setB := num / b setC := num / c lcmAB := lcm(a, b) setAB := num / lcmAB setAC := num / lcm(a, c) setBC := num / lcm(b, c) setABC := num / lcm(lcmAB, c) return setA + setB + setC - setAB - setAC - setBC + setABC } func lcm(a, b int) int { return a * b / gcd(a, b) } func gcd(a, b int) int { // assert a <= b if a > b { a, b = b, a } for a != 0 { a, b = b % a, a } return b }