双指针链表

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
}