双指针链表
LC 373. 查找和最小的 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. 两数相加
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. 两数相加 II
https://leetcode.com/problems/add-two-numbers-ii/