Go 算法与手撕代码：链表、数组、排序与大数据处理

package main

import "fmt"

// ListNode 单链表节点
type ListNode struct {
	Val  int
	Next *ListNode
}

// reverseIter 迭代反转：用 prev/cur/next 三个指针滚动
func reverseIter(head *ListNode) *ListNode {
	var prev *ListNode // prev 始终指向上一个已反转的节点
	cur := head        // cur 是当前正在处理的节点
	for cur != nil {
		next := cur.Next // ① 先存下后继，否则改完指针就找不到它了（防断链）
		cur.Next = prev  // ② 把当前节点指向上一个节点，完成"翻转"
		prev = cur       // ③ prev 前移一步
		cur = next       // ④ cur 前移一步
	}
	return prev // 循环结束时 cur 为 nil，prev 恰好是新头
}

// reverseRecur 递归反转：把"子链表的反转"当作已完成的前提
func reverseRecur(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head // 空链表或只有一个节点，直接返回（递归出口）
	}
	newHead := reverseRecur(head.Next) // 假设 head.Next 之后的部分已反转好
	head.Next.Next = head              // 让后一个节点回指当前节点
	head.Next = nil                   // 当前节点变成尾部，断掉原来的指向
	return newHead                    // 新的头始终是原链表的最后一个节点
}

// 构建 [1,2,3] 并打印
func main() {
	head := &ListNode{1, &ListNode{2, &ListNode{3, nil}}}
	r := reverseIter(head)
	for r != nil {
		fmt.Print(r.Val, " ")
		r = r.Next
	}
	// 输出: 3 2 1
}

package main

import (
	"fmt"
	"sort"
)

// threeSum 返回所有不重复的三元组，使三数之和为 0
func threeSum(nums []int) [][]int {
	sort.Ints(nums) // ① 排序是双指针的前提
	res := [][]int{}
	n := len(nums)

	for i := 0; i < n-2; i++ {
		// ② 跳过重复的 i，避免产生重复三元组
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		// ③ 剪枝：当前数与后面最小两数之和已 >0，后面只会更大
		if nums[i]+nums[i+1]+nums[i+2] > 0 {
			break
		}
		// ④ 剪枝：当前数与后面最大两数之和仍 <0，换更大的 i
		if nums[i]+nums[n-1]+nums[n-2] < 0 {
			continue
		}

		left, right := i+1, n-1
		for left < right {
			s := nums[i] + nums[left] + nums[right]
			if s == 0 {
				res = append(res, []int{nums[i], nums[left], nums[right]})
				// ⑤ 去重：跳过相同的 left 和 right
				for left < right && nums[left] == nums[left+1] {
					left++
				}
				for left < right && nums[right] == nums[right-1] {
					right--
				}
				left++
				right--
			} else if s < 0 {
				left++ // 和太小，左指针右移增大和
			} else {
				right-- // 和太大，右指针左移减小和
			}
		}
	}
	return res
}

func main() {
	fmt.Println(threeSum([]int{-1, 0, 1, 2, -1, -4}))
	// 输出: [[-1 -1 2] [-1 0 1]]
}

package main

import (
	"container/heap"
	"fmt"
)

// IntHeap 用 container/heap 实现最小堆
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 interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

// topK 返回最大的 k 个元素（不保证内部顺序）
func topK(nums []int, k int) []int {
	h := &IntHeap{}
	heap.Init(h)
	for _, v := range nums {
		heap.Push(h, v)
		if h.Len() > k {
			heap.Pop(h) // 堆始终保持 k 个元素，堆顶是其中最小的
		}
	}
	res := make([]int, 0, k)
	for h.Len() > 0 {
		res = append(res, heap.Pop(h).(int))
	}
	return res
}

func main() {
	fmt.Println(topK([]int{3, 1, 5, 2, 4}, 3)) // 最大3个: [5 4 3]（顺序不定）
}

package main

import "fmt"

// partition 按"大于 pivot 的放左边"分区，返回 pivot 最终下标
func partition(nums []int, left, right int) int {
	pivot := nums[right]
	i := left
	for j := left; j < right; j++ {
		if nums[j] > pivot { // 找第 K 大 → 大的在前
			nums[i], nums[j] = nums[j], nums[i]
			i++
		}
	}
	nums[i], nums[right] = nums[right], nums[i]
	return i
}

// kthLargest 返回第 k 大（k 从 1 开始）；会修改 nums
func kthLargest(nums []int, k int) int {
	target := k - 1 // 第 k 大对应降序数组下标 k-1
	left, right := 0, len(nums)-1
	for left <= right {
		p := partition(nums, left, right)
		if p == target {
			return nums[p]
		} else if p > target {
			right = p - 1
		} else {
			left = p + 1
		}
	}
	return -1
}

func main() {
	fmt.Println(kthLargest([]int{3, 1, 5, 2, 4}, 2)) // 第2大: 4
}

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

// sortChunk 把单个分块文件读入内存、排序、写回
func sortChunk(path string, lines []int) error {
	sort.Ints(lines) // 内存中排序（数据量需小于可用内存）
	f, err := os.Create(path)
	if err != nil {
		return err
	}
	defer f.Close()
	w := bufio.NewWriter(f)
	for _, v := range lines {
		fmt.Fprintln(w, v)
	}
	return w.Flush()
}

// mergeChunks 多路归并：每次从各块当前最小值中选最小，写入结果
func mergeChunks(outPath string, chunkPaths []string) error {
	readers := make([]*bufio.Scanner, len(chunkPaths))
	cur := make([]int, len(chunkPaths))   // 各路当前值
	valid := make([]bool, len(chunkPaths)) // 各路是否还有值
	for i, p := range chunkPaths {
		f, _ := os.Open(p)
		readers[i] = bufio.NewScanner(f)
		advance(readers[i], &cur[i], &valid[i])
		defer f.Close()
	}
	out, _ := os.Create(outPath)
	defer out.Close()
	w := bufio.NewWriter(out)
	defer w.Flush()

	for {
		// 选当前有效路中的最小值
		best, idx := 0, -1
		for i := range cur {
			if valid[i] && (idx == -1 || cur[i] < best) {
				best, idx = cur[i], i
			}
		}
		if idx == -1 {
			break // 全部耗尽
		}
		fmt.Fprintln(w, best)
		advance(readers[idx], &cur[idx], &valid[idx])
	}
	return nil
}

func advance(s *bufio.Scanner, v *int, ok *bool) {
	if s.Scan() {
		n, _ := strconv.Atoi(strings.TrimSpace(s.Text()))
		*v, *ok = n, true
	} else {
		*ok = false
	}
}

func main() {
	// 实际场景中按固定行数/字节数切分；此处仅示意调用
	_ = sortChunk
	_ = mergeChunks
}

package main

import "fmt"

// Bitmap 用位运算压缩存储"是否存在"
type Bitmap struct {
	bits []uint64
}

func NewBitmap(n int) *Bitmap {
	return &Bitmap{bits: make([]uint64, (n>>6)+1)}
}

func (b *Bitmap) Set(x int) {
	b.bits[x>>6] |= 1 << (x & 63) // 把第 x 位置 1
}

func (b *Bitmap) Has(x int) bool {
	return b.bits[x>>6]&(1<<(x&63)) != 0
}

func main() {
	bm := NewBitmap(1000000)
	bm.Set(42)
	fmt.Println(bm.Has(42), bm.Has(43)) // true false
}

package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 递归：前序
func preorder(root *TreeNode) []int {
	res := []int{}
	var dfs func(*TreeNode)
	dfs = func(n *TreeNode) {
		if n == nil {
			return
		}
		res = append(res, n.Val) // 先访问根
		dfs(n.Left)
		dfs(n.Right)
	}
	dfs(root)
	return res
}

// 迭代：中序（用栈模拟）
func inorderIter(root *TreeNode) []int {
	res := []int{}
	stack := []*TreeNode{}
	cur := root
	for cur != nil || len(stack) > 0 {
		for cur != nil {
			stack = append(stack, cur) // 一路压左
			cur = cur.Left
		}
		cur = stack[len(stack)-1] // 弹出最左
		stack = stack[:len(stack)-1]
		res = append(res, cur.Val) // 访问
		cur = cur.Right            // 转向右子树
	}
	return res
}

// 层序：队列实现（BFS）
func levelOrder(root *TreeNode) []int {
	res := []int{}
	if root == nil {
		return res
	}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		n := queue[0]
		queue = queue[1:]
		res = append(res, n.Val)
		if n.Left != nil {
			queue = append(queue, n.Left)
		}
		if n.Right != nil {
			queue = append(queue, n.Right)
		}
	}
	return res
}

func main() {
	//       1
	//      / \
	//     2   3
	root := &TreeNode{1, &TreeNode{2, nil, nil}, &TreeNode{3, nil, nil}}
	fmt.Println(preorder(root))  // [1 2 3]
	fmt.Println(inorderIter(root)) // [2 1 3]
	fmt.Println(levelOrder(root))  // [1 2 3]
}

package main

import "fmt"

// searchRotate 在循环有序数组中查找 target，返回下标，找不到返回 -1
func searchRotate(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)/2 // 防溢出写法
		if nums[mid] == target {
			return mid
		}
		// 判断左半段 [low, mid] 是否完全有序
		if nums[low] <= nums[mid] {
			// 左半有序：看 target 是否落在左半区间
			if target >= nums[low] && target < nums[mid] {
				high = mid - 1
			} else {
				low = mid + 1
			}
		} else {
			// 右半段 [mid, high] 有序：看 target 是否落在右半区间
			if target > nums[mid] && target <= nums[high] {
				low = mid + 1
			} else {
				high = mid - 1
			}
		}
	}
	return -1
}

func main() {
	fmt.Println(searchRotate([]int{4, 5, 6, 1, 2, 3}, 2)) // 4
	fmt.Println(searchRotate([]int{4, 5, 6, 1, 2, 3}, 0)) // -1
}

package main

import "fmt"

// quickSort 递归快排（原地）
func quickSort(nums []int, left, right int) {
	if left >= right {
		return
	}
	p := partitionQS(nums, left, right)
	quickSort(nums, left, p-1)
	quickSort(nums, p+1, right)
}

func partitionQS(nums []int, left, right int) int {
	pivot := nums[right]
	i := left
	for j := left; j < right; j++ {
		if nums[j] < pivot { // 小的放左边
			nums[i], nums[j] = nums[j], nums[i]
			i++
		}
	}
	nums[i], nums[right] = nums[right], nums[i]
	return i
}

func main() {
	a := []int{5, 3, 8, 1, 2, 6}
	quickSort(a, 0, len(a)-1)
	fmt.Println(a) // [1 2 3 5 6 8]
}

package main

import "fmt"

// heapSort 堆排序（升序，用最大堆）
func heapSort(nums []int) {
	n := len(nums)
	// ① 自底向上建堆：从最后一个非叶子节点开始下沉
	for i := n/2 - 1; i >= 0; i-- {
		siftDown(nums, i, n)
	}
	// ② 反复把堆顶（最大）换到末尾，再调整
	for end := n - 1; end > 0; end-- {
		nums[0], nums[end] = nums[end], nums[0]
		siftDown(nums, 0, end) // 堆大小缩小为 end
	}
}

// siftDown 下沉：将下标 i 的元素调整到合适位置以维持最大堆
func siftDown(nums []int, i, n int) {
	for {
		l, r := i*2+1, i*2+2
		largest := i
		if l < n && nums[l] > nums[largest] {
			largest = l
		}
		if r < n && nums[r] > nums[largest] {
			largest = r
		}
		if largest == i {
			break // 已满足堆性质
		}
		nums[i], nums[largest] = nums[largest], nums[i]
		i = largest
	}
}

func main() {
	b := []int{5, 3, 8, 1, 2, 6}
	heapSort(b)
	fmt.Println(b) // [1 2 3 5 6 8]
}

第1次: 100 → 33 | 33 | 34   称 33 vs 33
       若平衡 → 异常在剩余的 34 里；否则在较轻那 33 里
第2次: ~34  → 11 | 11 | 12
第3次: ~12  → 4  | 4  | 4   称 4 vs 4
第4次: ~4   → 1  | 1  | 2   ← 实际上 4 还需 2 次

package main

import "fmt"

// weighTimes 已知轻重时，最少称量次数 = ceil(log3(n))
func weighTimes(n int) int {
	t, base := 0, 1
	for base < n {
		base *= 3
		t++
	}
	return t
}

func main() {
	fmt.Println(weighTimes(27)) // 3：27 枚已知轻重，3 次足够
	fmt.Println(weighTimes(100)) // 5：100 枚需 5 次
}