学习目标
读完本文你应该能：
- 用「状态 + 选择」的框架独立写出动态规划四连题（完全背包 / 0-1 背包 / 子集和 / 子数组和为 K）。
- 手写二分查找的三种形态（标准、左边界、右边界），并说清
left <= right与left < right的取舍。 - 用最小堆或分治法合并 K 个有序链表；对链表做排序、去重、找倒数第 K 个、转平衡 BST。
- 用层序数组（含 nil）重建二叉树，并写出右视图、之字形遍历。
- 手写 Trie、并查/哈希表、LinkedHashMap，以及并发交替打印奇偶数。
- 用 Fisher-Yates 与拒绝抽样生成无重复随机数组。
类比先行：下面每一节都会先用「生活直觉」把问题讲明白，再上代码。代码里的注释重点解释 为什么这样写，而不只是「做了什么」。
一、动态规划四题连讲
1. 完全背包：最少硬币数 + 输出具体组合
直觉：把「凑出金额 amount」想象成往存钱罐里投硬币。每投一枚面值为 c 的硬币，剩余要凑的钱就少 c，而硬币数 +1。我们要在所有投法中找「硬币数最少」的那条路。因为同一种硬币可以无限用（完全背包），所以内循环从小到大扫。
状态定义：dp[i] = 凑出金额 i 所需的最少硬币数。
状态转移：dp[i] = min(dp[i], dp[i-c] + 1)，对每个硬币 c 都试一次。
graph LR A["dp[0]=0 起点"] --> B["选一枚硬币 c"] B --> C["dp[i] = min(dp[i], dp[i-c]+1)"] C --> D["i 从小到大扫（可重复选）"]
// coinChange 返回凑出 amount 的最少硬币数，无法凑出返回 -1
func coinChange(coins []int, amount int) int {
dp := make([]int, amount+1)
for i := 1; i <= amount; i++ {
dp[i] = amount + 1 // 初始化为一个不可能的大值（上界是全部用 1 元）
}
dp[0] = 0 // 凑 0 元需要 0 枚硬币，这是递推的「地基」
// 外循环枚举硬币，内循环从小到大：同一硬币可被多次选用（完全背包）
for _, c := range coins {
for i := c; i <= amount; i++ {
if dp[i-c]+1 < dp[i] {
dp[i] = dp[i-c] + 1
}
}
}
if dp[amount] > amount {
return -1 // 没有被更新过，说明凑不出
}
return dp[amount]
}
输出具体组合：再开一个 choice[i] 数组记录「凑成 i 用的最后一枚硬币」，最后从 amount 往回跳即可回溯路径。
// coinChangeWithCoins 返回最少硬币数以及具体组合（顺序无所谓）
func coinChangeWithCoins(coins []int, amount int) ([]int, int) {
dp := make([]int, amount+1)
choice := make([]int, amount+1) // choice[i] 记录凑成 i 的最后一枚硬币
for i := 1; i <= amount; i++ {
dp[i] = amount + 1
}
for _, c := range coins {
for i := c; i <= amount; i++ {
if dp[i-c]+1 < dp[i] {
dp[i] = dp[i-c] + 1
choice[i] = c
}
}
}
if dp[amount] > amount {
return nil, -1
}
count := dp[amount]
res := []int{}
for amount > 0 {
c := choice[amount]
res = append(res, c)
amount -= c // 不断「减去最后一枚硬币」回溯出整条路径
}
return res, count
}
复杂度：时间 O(coins * amount)，空间 O(amount)。
2. 0-1 背包
直觉：每个物品「要么拿、要么不拿」，且只能拿一次。如果还像完全背包那样从小到大扫，同一物品会被重复拿。解决办法是内循环从大到小扫——这样用到 dp[w-c] 时，它还是「上一轮（没考虑当前物品）」的旧值，从而保证不重复选。
状态定义：dp[w] = 容量 w 下能装的最大价值。
状态转移：dp[w] = max(dp[w], dp[w-weight]+value)。
// knapsack01 返回容量 capacity 内能装的最大价值
func knapsack01(weights, values []int, capacity int) int {
n := len(weights)
dp := make([]int, capacity+1)
for i := 0; i < n; i++ {
// 倒序遍历是 0-1 背包的灵魂：保证每件物品只被选一次
for w := capacity; w >= weights[i]; w-- {
if dp[w-weights[i]]+values[i] > dp[w] {
dp[w] = dp[w-weights[i]] + values[i]
}
}
}
return dp[capacity]
}
复杂度：时间 O(n * capacity)，空间 O(capacity)。
3. 子集和（能否选出若干数凑出 target）
直觉：这其实是 0-1 背包的布尔版——dp[s] 表示能否凑出和 s。常见变体是「数组能否分成和相等的两部分」，等价于「能否凑出总和的一半」。
// canPartition 判断数组能否被分成两个和相等的子集
func canPartition(nums []int) bool {
sum := 0
for _, v := range nums {
sum += v
}
if sum%2 != 0 {
return false // 奇数总和无法平分
}
target := sum / 2
dp := make([]bool, target+1)
dp[0] = true // 凑出 0 永远可行（什么都不选）
for _, v := range nums {
// 同样倒序，避免同一数字被重复使用
for s := target; s >= v; s-- {
dp[s] = dp[s] || dp[s-v]
}
}
return dp[target]
}
复杂度：时间 O(n * target)，空间 O(target)。
4. 子数组和为 K（前缀和 + 哈希表）
直觉：与其枚举所有子数组（O(n²)），不如维护「前缀和」prefix。若 [0..j] 的前缀和是 p，而之前某处 [0..i] 的前缀和是 p-K，那么 (i, j] 这段的和正好是 K。用哈希表记录「每个前缀和出现过几次」，边走边查 prefix-K 即可。
// subarraySum 返回和为 k 的连续子数组个数
func subarraySum(nums []int, k int) int {
prefix := 0
count := 0
m := map[int]int{0: 1} // 前缀和 0 出现 1 次，处理从下标 0 开始的子数组
for _, v := range nums {
prefix += v
// 如果存在前缀和 = prefix-k，则中间这段和为 k
if c, ok := m[prefix-k]; ok {
count += c
}
m[prefix]++ // 把当前前缀和计入哈希表
}
return count
}
复杂度：时间 O(n)，空间 O(n)。
二、二分查找
直觉：二分就像你翻一本很厚的词典找词——每次都翻到中间，判断目标在左半还是右半，然后丢掉另一半。关键在于「边界怎么收」和「循环条件用 <= 还是 <」。
graph TD S["left, right"] --> M["mid = left + (right-left)/2"] M -->|"nums[mid] == target"| F["标准：直接返回"] M -->|"nums[mid] < target"| R1["left = mid+1 往右"] M -->|"nums[mid] > target"| R2["right = mid-1 往左"]
标准写法（查找任意等于 target 的位置）
// binarySearch 找到返回下标，找不到返回 -1
func binarySearch(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right { // 闭区间 [left, right]，当 left>right 时区间为空
mid := left + (right-left)/2 // 这样写防止 (left+right) 溢出
if nums[mid] == target {
return mid
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
查找左边界（第一个等于 target 的位置）
// leftBound 返回 target 第一次出现的位置，不存在返回 -1
func leftBound(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
right = mid - 1 // 找到后继续向左压缩，贪心地找更左的
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
if left < len(nums) && nums[left] == target {
return left
}
return -1
}
查找右边界（最后一个等于 target 的位置）
// rightBound 返回 target 最后一次出现的位置，不存在返回 -1
func rightBound(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
left = mid + 1 // 找到后继续向右压缩
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
if right >= 0 && nums[right] == target {
return right
}
return -1
}
应用小结：用 <= + 收缩时 ±1 是最不容易出 bug 的模板；求左右边界只是「命中后往哪边再挤一步」的区别。x 的平方根、搜索旋转排序数组、在排序数组中找第一个 >= target 的位置 都是同一套模板。
三、N 个有序链表合并
直觉：K 个指针各自指着一条链表的当前最小候选，谁最小就取谁。如果每次都扫一遍 K 个指针（O(K)），总复杂度 O(KN) 偏慢。更聪明的做法是把 K 个「当前候选」放进最小堆，每次 O(logK) 取出最小值，再把它的下一个节点补进堆。
graph TD L1["链表1: 1→4→5"] --> H["最小堆（顶部最小）"] L2["链表2: 1→3→4"] --> H L3["链表3: 2→6"] --> H H --> O["结果: 1→1→2→3→4→4→5→6"]
package main
import "container/heap"
type ListNode struct {
Val int
Next *ListNode
}
// 以下是 container/heap 接口实现，让 []*ListNode 变成最小堆
type MinHeap []*ListNode
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Val < h[j].Val } // 按 Val 升序
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(*ListNode)) }
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
// mergeKLists 用最小堆合并 K 个有序链表
func mergeKLists(lists []*ListNode) *ListNode {
h := &MinHeap{}
heap.Init(h)
// 先把每条链表的头节点入堆
for _, l := range lists {
if l != nil {
heap.Push(h, l)
}
}
dummy := &ListNode{} // 哨兵节点，省去处理头指针为空的判断
cur := dummy
for h.Len() > 0 {
node := heap.Pop(h).(*ListNode) // 弹出当前最小
cur.Next = node
cur = cur.Next
if node.Next != nil {
heap.Push(h, node.Next) // 把该链的下一个候选补进堆
}
}
return dummy.Next
}
分治写法（把 K 个链表两两合并，复用合并两个有序链表）：
// mergeKListsDivide 分治合并：不断折半，直到只剩一个链表
func mergeKListsDivide(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
return divide(lists, 0, len(lists)-1)
}
func divide(lists []*ListNode, l, r int) *ListNode {
if l == r {
return lists[l] // 只有一个链表，直接返回
}
mid := l + (r-l)/2
left := divide(lists, l, mid)
right := divide(lists, mid+1, r)
return mergeTwo(left, right) // 合并两个有序链表
}
func mergeTwo(a, b *ListNode) *ListNode {
dummy := &ListNode{}
cur := dummy
for a != nil && b != nil {
if a.Val < b.Val {
cur.Next = a
a = a.Next
} else {
cur.Next = b
b = b.Next
}
cur = cur.Next
}
if a != nil {
cur.Next = a
} else {
cur.Next = b
}
return dummy.Next
}
复杂度：最小堆 O(N logK)，分治 O(N logK)（N 为总节点数）。
四、链表排序与去重
1. 链表排序（归并排序）
直觉：数组好排序是因为能随机下标访问、方便取中点；链表只能顺序走，所以用「快慢指针」找中点把链断开，递归地排左右两半，再合并——这就是链表的归并排序，稳定且 O(n log n)。
graph TD A["4→2→1→3"] --> B["快慢指针找中点，断开"] B --> C["4→2 | 1→3"] C --> D["各自排序后合并"] D --> E["1→2→3→4"]
// sortList 自顶向下归并排序链表
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head // 0 或 1 个节点天然有序
}
slow, fast := head, head
var prev *ListNode
for fast != nil && fast.Next != nil {
prev = slow
slow = slow.Next
fast = fast.Next.Next
}
prev.Next = nil // 在中点前断开，分成两条独立链表
left := sortList(head)
right := sortList(slow)
return mergeTwo(left, right) // mergeTwo 见上一节
}
2. 有序链表去重
// deleteDuplicates 删除有序链表中重复的元素（保留一个）
func deleteDuplicates(head *ListNode) *ListNode {
cur := head
for cur != nil && cur.Next != nil {
if cur.Val == cur.Next.Val {
cur.Next = cur.Next.Next // 跳过重复节点
} else {
cur = cur.Next
}
}
return head
}
3. 有序数组去重（原地，双指针）
直觉：慢指针 i 始终指向「已整理区间的最后一个不重复元素」，快指针 j 负责向前探路，遇到不同的就挪到 i 后面。
// removeDuplicates 原地删除排序数组中的重复项，返回新长度
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
i := 0
for j := 1; j < len(nums); j++ {
if nums[j] != nums[i] {
i++
nums[i] = nums[j] // 把不同值搬到前面
}
}
return i + 1 // 有效长度为 i+1
}
复杂度：排序 O(n log n)；去重均为 O(n)，数组去重额外空间 O(1)。
五、倒数第 K 个节点 & 升序链表转平衡 BST
1. 倒数第 K 个节点
直觉：经典「快慢指针」——让快指针先走 K 步，然后快慢一起走，快指针到尾时，慢指针恰好停在倒数第 K 个。
// getKthFromEnd 返回倒数第 k 个节点（1-based）
func getKthFromEnd(head *ListNode, k int) *ListNode {
fast, slow := head, head
for i := 0; i < k; i++ {
if fast == nil {
return nil // k 超过链表长度
}
fast = fast.Next
}
for fast != nil {
fast = fast.Next
slow = slow.Next
}
return slow
}
2. 升序链表转平衡二叉搜索树
直觉：平衡 BST 要求左右子树节点数尽量相等，所以每次都要取「正中间」元素做根。链表没有随机访问，于是用快慢指针找中点当根，左半部分递归建左子树，右半部分递归建右子树。
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// sortedListToBST 把升序链表转为高度平衡的 BST
func sortedListToBST(head *ListNode) *TreeNode {
if head == nil {
return nil
}
slow, fast := head, head
var prev *ListNode
for fast != nil && fast.Next != nil {
prev = slow
slow = slow.Next
fast = fast.Next.Next
}
root := &TreeNode{Val: slow.Val} // 中点做根
if prev != nil {
prev.Next = nil // 断开左半部分
root.Left = sortedListToBST(head)
}
root.Right = sortedListToBST(slow.Next) // 右半部分
return root
}
复杂度：找倒数第 K 个 O(n)；建 BST O(n log n)（每次找中点 O(n)，递归深度 log n）。
六、二叉树：右视图与之字形遍历
直觉：这俩都是「层序遍历（BFS）」的变体。右视图 = 每一层最后一个被访问到的节点；之字形 = 偶数层从左往右、奇数层从右往左（或反过来），本质是在收集每层时决定是否反转顺序。
graph TD R["1"] --> L2["2"] R --> R2["3"] L2 --> L3["4"] L2 --> R3["5"] R2 --> R4["6"]
右视图
// rightSideView 返回从右侧能看到的节点值（每层最右一个）
func rightSideView(root *TreeNode) []int {
var res []int
if root == nil {
return res
}
queue := []*TreeNode{root}
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
if i == size-1 {
res = append(res, node.Val) // 本层最后一个入结果
}
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
}
return res
}
之字形层序遍历
// zigzagLevelOrder 之字形（Z 形）层序遍历
func zigzagLevelOrder(root *TreeNode) [][]int {
var res [][]int
if root == nil {
return res
}
queue := []*TreeNode{root}
level := 0
for len(queue) > 0 {
size := len(queue)
row := make([]int, size)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
idx := i
if level%2 == 1 {
idx = size - 1 - i // 奇数层反向填入
}
row[idx] = node.Val
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
res = append(res, row)
level++
}
return res
}
复杂度：两者均为 O(n)，每个节点进出队一次。
七、根据数组（含 nil 节点）重建二叉树与层次遍历
直觉：题目常给一个「层序 + 用 nil 表示空」的数组，例如 [1,2,nil,3] 表示根 1、左 2、右空、2 的左孩子 3。这种表示法天然就是层序，所以用一个队列按层把节点挂上去即可重建；反过来做层序遍历，也能把树还原成同样的数组。
graph TD A["数组 [1,2,nil,3]"] --> B["层序建树"] B --> C["1 的左=2, 右=nil; 2 的左=3"] C --> D["层序遍历还原回 [1,2,nil,3]"]
// buildFromLevelOrder 由层序数组（nil 表示空节点）重建二叉树
func buildFromLevelOrder(vals []*int) *TreeNode {
if len(vals) == 0 || vals[0] == nil {
return nil
}
root := &TreeNode{Val: *vals[0]}
queue := []*TreeNode{root}
i := 1
for len(queue) > 0 && i < len(vals) {
node := queue[0]
queue = queue[1:]
// 挂左孩子
if i < len(vals) && vals[i] != nil {
node.Left = &TreeNode{Val: *vals[i]}
queue = append(queue, node.Left)
}
i++
// 挂右孩子
if i < len(vals) && vals[i] != nil {
node.Right = &TreeNode{Val: *vals[i]}
queue = append(queue, node.Right)
}
i++
}
return root
}
// levelOrder 把二叉树按层序输出为含 nil 的数组（便于对比还原）
func levelOrder(root *TreeNode) []*int {
var res []*int
if root == nil {
return res
}
queue := []*TreeNode{root}
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
if node == nil {
res = append(res, nil)
continue
}
v := node.Val
res = append(res, &v)
queue = append(queue, node.Left, node.Right) // 即使为空也入队，保留结构
}
// 去掉末尾无意义的 nil（最底层右侧的空指针）
for len(res) > 0 && res[len(res)-1] == nil {
res = res[:len(res)-1]
}
return res
}
复杂度：建树与遍历都是 O(n)。
八、前缀树 Trie
直觉：Trie 像一本按字母分层排布的通讯录——根节点是空，第一层是所有单词的首字母，往下依次挂后续字母。要查「是否存在以某前缀开头的单词」，只需顺着字母一层层往下走；走不通就说明没有。它把「前缀匹配」从 O(M*N) 降到 O(键长)。
graph TD root["● 根"] --> c["c"] c --> a["a"] a --> t["t 结束"] root --> d["d"] d --> o["o"] o --> g["g 结束"]
type TrieNode struct {
children map[rune]*TrieNode
isEnd bool // 标记到此是否为一个完整单词
}
type Trie struct {
root *TrieNode
}
func NewTrie() *Trie {
return &Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}
}
// Insert 插入一个单词
func (t *Trie) Insert(word string) {
node := t.root
for _, ch := range word {
if _, ok := node.children[ch]; !ok {
node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
}
node = node.children[ch] // 沿路径下走，没有就新建
}
node.isEnd = true // 单词结尾打标记
}
// Search 判断完整单词是否存在
func (t *Trie) Search(word string) bool {
node := t.searchPrefix(word)
return node != nil && node.isEnd
}
// StartsWith 判断是否存在以 prefix 为前缀的单词
func (t *Trie) StartsWith(prefix string) bool {
return t.searchPrefix(prefix) != nil
}
// searchPrefix 沿前缀走，返回终点节点（走不通返回 nil）
func (t *Trie) searchPrefix(prefix string) *TrieNode {
node := t.root
for _, ch := range prefix {
if _, ok := node.children[ch]; !ok {
return nil
}
node = node.children[ch]
}
return node
}
复杂度：插入、查找、前缀匹配均为 O(L)（L 为字符串长度），与单词总数无关——这是 Trie 的核心优势。
九、并发手撕：交替打印奇偶数
直觉：两个 goroutine 要「你一下我一下」地打印，关键是谁先说话、说完通知对方。用两个 channel 互相发信号：奇数协程打印完通知偶数协程，偶数协程打印完再通知奇数协程，形成乒乓。注意把 channel 设为带缓冲（容量 1），避免最后一步「没人接收」的死锁。
sequenceDiagram participant Main participant Odd participant Even Main->>Odd: 发初始信号 Odd->>Even: 打印奇数后发信号 Even->>Odd: 打印偶数后发信号 Note over Odd,Even: 循环直到 n
package main
import (
"fmt"
"sync"
)
// printOddEven 交替打印 1..n 的奇偶数（先奇后偶）
func printOddEven(n int) {
odd := make(chan struct{}, 1) // 缓冲 1：避免最后一步发送无人接收而死锁
even := make(chan struct{}, 1)
var wg sync.WaitGroup
wg.Add(2)
go func() {
defer wg.Done()
for i := 1; i <= n; i += 2 {
<-odd // 等奇数信号
fmt.Println(i) // 打印奇数
even <- struct{}{}
}
}()
go func() {
defer wg.Done()
for i := 2; i <= n; i += 2 {
<-even // 等偶数信号
fmt.Println(i) // 打印偶数
odd <- struct{}{}
}
}()
odd <- struct{}{} // 主协程点火：先让奇数打印
wg.Wait()
}
为什么用缓冲 channel：若用无缓冲，最后偶数协程打印完 n 后向 odd 发信号，而奇数协程此时循环已结束、不再接收，发送会永久阻塞 → 死锁。缓冲 1 让这次发送直接落入缓冲区、立即返回，协程安全退出。
十、实现 HashMap 与有序哈希（LinkedHashMap）
1. 基础 HashMap：set/get + 扩容
直觉：HashMap 就是「数组 + 链表」。对 key 算哈希拿到桶下标，冲突的元素用链表串起来。当元素太多（负载因子过高）时，桶太挤、链表变长，查找退化成 O(n)，于是翻倍容量、把所有元素重新哈希（rehash）。
type entry struct {
key string
value int
next *entry // 拉链法解决冲突
}
type MyHashMap struct {
buckets []*entry
size int
capacity int
}
func NewHashMap(capacity int) *MyHashMap {
return &MyHashMap{buckets: make([]*entry, capacity), capacity: capacity}
}
// hash 简单字符串哈希，再对容量取模定位桶
func (m *MyHashMap) hash(key string) int {
h := 0
for _, c := range key {
h = h*31 + int(c)
}
if h < 0 {
h = -h
}
return h % m.capacity
}
// Set 插入或更新
func (m *MyHashMap) Set(key string, value int) {
if m.size >= m.capacity*7/10 { // 负载因子 0.7 触发扩容
m.resize()
}
idx := m.hash(key)
for e := m.buckets[idx]; e != nil; e = e.next {
if e.key == key {
e.value = value // 已有 key 直接更新
return
}
}
// 头插法加入新节点
m.buckets[idx] = &entry{key: key, value: value, next: m.buckets[idx]}
m.size++
}
// Get 取值
func (m *MyHashMap) Get(key string) (int, bool) {
idx := m.hash(key)
for e := m.buckets[idx]; e != nil; e = e.next {
if e.key == key {
return e.value, true
}
}
return 0, false
}
// resize 翻倍容量并重新哈希
func (m *MyHashMap) resize() {
old := m.buckets
m.capacity *= 2
m.buckets = make([]*entry, m.capacity)
m.size = 0
for _, head := range old {
for e := head; e != nil; e = e.next {
m.Set(e.key, e.value) // 复用 Set 完成重新哈希
}
}
}
2. 有序哈希表（LinkedHashMap 思路）
直觉：普通 HashMap 遍历顺序不确定。若想「按插入顺序」遍历，就额外维护一条双向链表记录先后关系，再用 map 做 O(1) 查找，链表负责保序。
type lnode struct {
key string
value int
prev *lnode
next *lnode
}
type LinkedHashMap struct {
m map[string]*lnode
head *lnode // 哨兵头（最旧）
tail *lnode // 哨兵尾（最新）
}
func NewLinkedHashMap() *LinkedHashMap {
head := &lnode{}
tail := &lnode{}
head.next = tail
tail.prev = head
return &LinkedHashMap{m: make(map[string]*lnode), head: head, tail: tail}
}
func (l *LinkedHashMap) addToTail(n *lnode) {
n.prev = l.tail.prev
n.next = l.tail
l.tail.prev.next = n
l.tail.prev = n
}
func (l *LinkedHashMap) remove(n *lnode) {
n.prev.next = n.next
n.next.prev = n.prev
}
func (l *LinkedHashMap) Put(key string, value int) {
if n, ok := l.m[key]; ok {
n.value = value // 已存在则更新，保持原位
return
}
n := &lnode{key: key, value: value}
l.m[key] = n
l.addToTail(n) // 新 key 挂到链表尾部（最新）
}
func (l *LinkedHashMap) Get(key string) (int, bool) {
if n, ok := l.m[key]; ok {
return n.value, true
}
return 0, false
}
// Keys 按插入顺序返回所有 key
func (l *LinkedHashMap) Keys() []string {
var res []string
for n := l.head.next; n != l.tail; n = n.next {
res = append(res, n.key)
}
return res
}
复杂度：HashMap 平均 O(1)（最坏 O(n)，靠扩容维持在常数附近）；LinkedHashMap 同样 O(1) 且保序。
十一、生成无重复随机数组（Fisher-Yates + 拒绝抽样）
直觉：要「洗牌」，最公平的办法是 Fisher-Yates——从后往前，每次随机挑一个前面的元素与当前位置交换，保证每个排列等概率。如果你要的只是「从大池子里抽少量不重复样本」，则可用拒绝抽样：随机生成一个数，重复就丢掉重抽，直到凑够。
graph LR A["初始 1..n"] --> B["从后往前随机交换"] B --> C["得到均匀打乱的排列"] C --> D["或：拒绝抽样抽 k 个不重复"]
package main
import (
"math/rand"
"time"
)
// generateUniqueRandom 用 Fisher-Yates 生成 1..n 的无重复随机排列
func generateUniqueRandom(n int) []int {
rng := rand.New(rand.NewSource(time.Now().UnixNano()))
arr := make([]int, n)
for i := 0; i < n; i++ {
arr[i] = i + 1
}
// 从最后一个开始，与 [0, i] 中随机一个交换
for i := n - 1; i > 0; i-- {
j := rng.Intn(i + 1)
arr[i], arr[j] = arr[j], arr[i]
}
return arr
}
// rejectionSample 在 [0, max) 中随机抽 k 个不重复整数（拒绝抽样）
func rejectionSample(max, k int) []int {
rng := rand.New(rand.NewSource(time.Now().UnixNano()))
seen := make(map[int]bool)
res := []int{}
for len(res) < k {
x := rng.Intn(max)
if !seen[x] { // 没出现过才收下，重复则丢弃重试
seen[x] = true
res = append(res, x)
}
// 若 k 接近 max，拒绝率会升高，此时应改用 Fisher-Yates 再取前 k 个
}
return res
}
复杂度：Fisher-Yates O(n)；拒绝抽样期望 O(k)（当 k << max 时高效，否则退化为接近 O(max)）。
十二、自测题与动手练习
- 完全背包变形：把「最少硬币数」改成「组合数」——给定硬币和
amount，求凑出amount的方案总数（注意内外循环顺序会影响是组合数还是排列数，为什么？）。 - 二分边界：给定一个按非递减排序、但被旋转过的数组（如
[4,5,6,7,0,1,2]），用二分在O(log n)内找最小值，并说明与标准二分的边界差异。 - 链表：给定两个用链表表示的非负整数（如
2->4->3与5->6->4，低位在前），写出相加函数，返回7->0->8。要求先讲清进位处理，再写代码。 - 二叉树：实现「二叉树的最大路径和」（路径可拐弯，不一定过根），并分析为什么需要在递归里返回「单侧最大贡献」而非整条路径和。
- Trie 进阶：在本文 Trie 基础上增加
Delete(word)方法，要求删除后正确清理不再被任何单词使用的节点，并避免误删共享前缀。 - 并发：把「交替打印奇偶数」改成「三个协程按 1、2、3 循环打印到 n」，用 channel 传递「轮到谁」的信号，注意退出条件防死锁。
- 设计：用本文 HashMap 思路实现一个支持
LRU（最近最少使用）淘汰的缓存：Get/Put均为O(1)，容量满时淘汰最久未使用项。
十三、本章小结
- 动态规划本质是「状态 + 选择」：完全背包内循环从小到大（可重复选），0-1/子集和从大到小（不重复选）；子数组和为 K 用前缀和 + 哈希把
O(n²)打到O(n)。 - 二分查找一套模板走天下，左右边界只是「命中后往哪边再挤一步」；务必用
left + (right-left)/2防溢出。 - 链表题大多靠双指针（快慢、前后）、递归与哨兵节点；归并排序和 K 路合并是高频组合。
- 二叉树层序遍历（BFS）是右视图、之字形、层序建树的共同底座；重建优先认准「层序数组 + nil」或「前/中/后序」的组合。
- Trie 把前缀匹配降为
O(键长)；HashMap 靠数组 + 拉链 + 扩容维持在O(1)；LinkedHashMap 用双向链表保序。 - 并发手撕核心是「用 channel 当信号量乒乓传递」，别忘了缓冲/退出条件防止死锁。
- 随机无重复优先 Fisher-Yates；只在
k << 池子时用拒绝抽样。
把这些套路各自手写三遍，面试现场就能做到「看到题先说直觉，再画状态/结构，最后边写边讲 why」。
复习提示：
- 动态规划核心：找状态 + 找转移方程；背包问题记住"完全背包正序、0-1背包倒序"。
- 二分查找模板：标准写法找任意位置，左边界/右边界只改
left+1或right-1的方向。 - Trie 删节点：删除后要检查子节点是否为空，避免误删共享前缀——这是面试官常追问的细节。
- 并发交替打印：channel 传信号是核心思路，退出条件防死锁是必考点。
- 上一篇是基础手撕（链表、排序、TopK），这一篇是进阶（DP、Trie、HashMap），两篇结合使用效果最佳。