双指针链表
LC 373. Find K Pairs with Smallest Sums 查找和最小的 K 对数字
https://leetcode.com/problems/find-k-pairs-with-smallest-sums/
...
| Code Block |
|---|
|
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/
| Code Block |
|---|
|
/**
* 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/
| Code Block |
|---|
|
/**
* 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/
| Code Block |
|---|
|
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）的思路
| Code Block |
|---|
|
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)
| Code Block |
|---|
|
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
} |
二分 + 集合解法
| Code Block |
|---|
|
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
} |