正文

回溯（Backtracking）是一种深度优先搜索（DFS）的特殊形式，主要用于解决“排列、组合、切割、子集”等问题。它的核心在于试探与撤销。

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

fun backtrack(path: MutableList<T>, options: List<T>) {
    // 1. 终止条件：满足特定的结束条件
    if (isFinished(path)) {
        // 记得拷贝结果 (deep copy)，否则最终返回的列表都是空的
        res.add(ArrayList(path))
        return
    }

    // 2. 遍历候选列表
    for (option in options) {
        // 剪枝：过滤掉不符合条件的路径
        if (!isValid(option, path)) continue

        // 3. 做选择
        path.add(option)

        // 4. 递归进入下一层决策树
        backtrack(path, nextOptions)

        // 5. 撤销选择：回溯的核心步骤
        path.removeAt(path.size - 1)
    }
}

使用说明

1. 核心步骤：

   • 路径：记录已经做出的选择。
   • 选择列表：当前可以做的选择。
   • 结束条件：到达决策树叶子节点，结束递归。

2. 核心技巧：

   • 深度优先遍历：先从根节点出发，一直走到叶子节点。
   • 状态重置：在递归返回时，必须将当前节点的状态重置（撤销选择），以便在下一次循环中尝试其他路径。
   • 深拷贝：在保存结果时，必须使用 ArrayList(path)。

3. 常见变形：

   • 排列问题：需要使用 used 数组记录已选元素。
   • 组合/子集问题：通常需要一个 startIndex 来控制搜索范围，避免重复。
   • 剪枝优化：通过对数组预排序或提前退出循环来极大提升效率。

4. 注意点：

   • 回溯算法的时间复杂度通常很高（指数级），必须结合题目特点进行剪枝。
   • 注意处理重复元素（如“组合总和 II”）。

正文

动态规划（Dynamic Programming）的核心思想是将复杂问题分解为重复的子问题。自顶向下法（Top-Down）通常结合递归与备忘录（Memoization），这种方法也被称为“记忆化搜索”。

算法模板 (以斐波那契数列为例)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

fun solve(n: Int): Int {
    // 1. 初始化备忘录，通常设为 -1 或 null 表示未计算
    val memo = IntArray(n + 1) { -1 }
    return dp(n, memo)
}

private fun dp(n: Int, memo: IntArray): Int {
    // 2. 终止条件 / 基础情况 (Base Case)
    if (n == 0 || n == 1) return n
    
    // 3. 检查备忘录：如果已经计算过，直接返回结果
    if (memo[n] != -1) {
        return memo[n]
    }
    
    // 4. 状态转移：计算并将结果存入备忘录
    // 这里的逻辑根据具体题目而变，如 dp[n] = dp[n-1] + dp[n-2]
    memo[n] = dp(n - 1, memo) + dp(n - 2, memo)
    
    return memo[n]
}

使用说明

1. 核心逻辑：

   • 递归（自顶向下）：从最终目标出发，逐层分解直到最简单的基础情况。
   • 备忘录（记忆化）：为了避免重复计算（如斐波那契中多次计算同样的 f(n-2)），将结果保存在数组或哈希表中。

2. 核心优势：

   • 逻辑清晰：比自底向上的迭代（Tabulation）更容易推导出状态转移关系。
   • 按需计算：只计算解决原问题所需要的子问题，而迭代法通常会计算整个表格。

3. 适用场景：

   • 问题的状态转移方程非常明确。
   • 存在大量重叠子问题。
   • 递归树深度在可控范围内（避免栈溢出）。

4. 注意点：

   • 初始化：备忘录的初始值必须是一个在该问题结果中不可能出现的值。
   • 栈空间：如果 n 非常大（如超过 10,000），递归可能会引发 StackOverflowError，此时需改用自底向上的迭代法。
   • 状态设计：动态规划最难的是如何定义 dp 函数的含义。

正文

前缀树（Trie），又称字典树，是一种多叉树结构。它通过利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class TrieNode {
    // 1. 26个英文字母（或其他字符集）
    val children = arrayOfNulls<TrieNode>(26)
    // 2. 标记当前节点是否为一个单词的结束
    var isEndOfWord = false
}

class Trie {
    private val root = TrieNode()

    // 向前缀树中插入一个单词
    fun insert(word: String) {
        var node = root
        for (char in word) {
            val index = char - 'a'
            if (node.children[index] == null) {
                node.children[index] = TrieNode()
            }
            node = node.children[index]!!
        }
        node.isEndOfWord = true
    }

    // 搜索前缀树中是否存在一个完整的单词
    fun search(word: String): Boolean {
        var node = findNode(word)
        return node != null && node.isEndOfWord
    }

    // 搜索前缀树中是否存在以某个前缀开头的单词
    fun startsWith(prefix: String): Boolean {
        return findNode(prefix) != null
    }

    // 私有助手函数：根据前缀找到对应的末尾节点
    private fun findNode(prefix: String): TrieNode? {
        var node = root
        for (char in prefix) {
            val index = char - 'a'
            if (node.children[index] == null) {
                return null
            }
            node = node.children[index]!!
        }
        return node
    }
}

使用说明

1. 核心特性：

   • 高效前缀匹配：查找前缀或单词的时间复杂度仅与单词长度 $L$ 相关，即 $O(L)$。
   • 空间换时间：利用数组或哈希表存储子节点，虽然空间占用较大，但查询极快。

2. 适用场景：

   • 单词搜索：如“搜索提示”、“拼写检查”。
   • 字符串排序：字典树遍历本身就是一种排序。
   • 统计词频：可以在 TrieNode 中加入 count 字段。

3. 核心技巧：

   • children 数组：如果字符集固定（如 26 个字母），使用数组速度最快；如果不固定，可改用 HashMap。
   • **isEndOfWord**：必须在插入单词的最后一个字符节点处设为 true。

4. 注意点：

   • 注意处理空字符串的特殊情况。
   • 如果需要支持删除操作，通常采用引用计数或在 isEndOfWord 置为 false 后递归删除无用节点。

本篇解析 example-supervision-01.kt。探讨如何打破常规的异常取消联动。

1. 核心概念：SupervisorJob

默认情况下，子协程失败会导致父协程及所有兄弟协程被取消。使用 SupervisorJob 可以改变这一行为。

特点：

• 单向取消：父协程取消会触发子协程取消，但子协程失败不会导致父协程及其它兄弟协程取消。
• 责任自负：每个子协程必须自己处理自己的异常（通过 try-catch 或 CoroutineExceptionHandler）。

2. 代码解析

1
2
3
4
5

val supervisor = SupervisorJob()
with(CoroutineScope(coroutineContext + supervisor)) {
    val firstChild = launch { throw AssertionError() } // 第一个失败
    val secondChild = launch { /* ... */ } // 第二个依然存活
}

• 执行逻辑：即便第一个子协程崩溃了，第二个子协程依然在运行，不受任何影响。

3. 开发者感悟

SupervisorJob 是构建鲁棒系统的关键。在 Android 中，如果你有一个界面展示多个独立板块（如天气、新闻、广告），某个板块的数据加载失败不应该导致整个界面崩溃或停止更新。这就是“监督”机制的价值所在。

本篇解析 example-sync-01.kt。探讨在协程中使用普通变量进行并发累加时的错误。

1. 核心现象：数据丢失 (Race Condition)

当我们在多个并发协程中同时修改一个普通的全局变量时，会发生“竞态条件”。

代码解析

1
2
3
4
5
6
7

var counter = 0
withContext(Dispatchers.Default) {
    massiveRun {
        counter++
    }
}
// 预期：100000，实际：可能只有 70000 多

• 原因：counter++ 并不是一个原子操作。它包含了“读取-修改-写入”三个步骤。在多线程环境下，多个协程可能同时读取了旧值，导致部分加法操作被覆盖。

2. 开发者感悟

协程虽然轻量，但只要它运行在多线程调度器（如 Dispatchers.Default）上，就必须面对传统的多线程同步问题。永远不要假设协程内部的代码是天然线程安全的。

本篇解析 example-select-01.kt。探讨如何同时等待多个异步挂起函数。

1. 核心概念：select

select 表达式允许你同时等待多个挂起函数，并只响应第一个完成的任务。

特点：

• 多路复用：它可以同时监听多个 Channel。
• 偏好机制：如果多个子句同时准备就绪，select 通常会优先选择第一个。

2. 代码解析 (FizzBuzz 案例)

两个生产者分别以 500ms (fizz) 和 1000ms (buzz) 的频率产出数据。

1
2
3
4

select<Unit> { 
    fizz.onReceive { value -> println("fizz -> '$value'") }
    buzz.onReceive { value -> println("buzz -> '$value'") }
}

• 执行逻辑：无论哪个通道先发来消息，select 都会立即执行对应的代码块并结束本次选择。

3. 开发者感悟

select 就像是赛跑的裁判，谁先过终点线就判定谁赢，并立即结束比赛。在 Android 中，如果你从两个不同的服务器请求同一个数据，你可以用 select 来取最先返回的那个，从而提升用户体验。

本篇解析 example-channel-01.kt。探讨协程间如何进行异步通信。

1. 核心概念：什么是 Channel？

Channel 在概念上类似于 BlockingQueue。它允许一个协程向其中发送数据，另一个协程从中接收数据。

与队列的区别：

• 非阻塞挂起：不同于队列的阻塞（Blocking），Channel 的操作是挂起（Suspending）的。当通道满时，send 会挂起；当通道空时，receive 会挂起。

2. 核心参数：容量 (Capacity)

• **RENDEZVOUS (默认)**：会合通道（容量为 0）。发送者和接收者必须“手拉手”才能完成传递。如果没人收，发送者就挂起。
• UNLIMITED：无限容量。发送者永远不挂起。
• BUFFERED：缓冲通道。默认容量为 64，满时挂起。
• CONFLATED：合并通道。只保留最新值，旧值被覆盖，发送者永不挂起。

3. 开发者感悟

Channel 是实现“通过通信来共享内存”理念的核心。在 Android 中，如果你有一个后台任务在不断产出数据（如下载进度），而 UI 层需要异步接收，Channel 是非常稳健的选择。

本篇解析 example-compose-01.kt。探讨挂起函数在默认情况下的执行行为。

1. 核心现象：顺序执行

在协程内部，如果你只是简单地按行调用两个挂起函数，它们会按顺序执行。

代码解析

1
2
3
4
5
6

val time = measureTimeMillis {
    val one = doSomethingUsefulOne() // 耗时 1000ms
    val two = doSomethingUsefulTwo() // 耗时 1000ms
    println("The answer is ${one + two}")
}
// 结果：Completed in 2000+ ms

2. 开发者感悟

这是协程最自然的编程模型。代码读起来和同步代码一模一样，但底层是非阻塞的. 如果任务 A 的结果是任务 B 的输入，这种顺序执行就是你需要的。但如果任务 A 和 B 互不依赖，顺序执行就会浪费时间。

本篇解析 example-context-01.kt。学习如何指定协程运行的线程环境。

1. 核心概念：调度器 (Dispatchers)

调度器决定了协程在哪个线程或线程池中执行。

常见的调度器：

• **不传参数 (默认)**：继承父协程的上下文。如果在 runBlocking 中，通常是主线程。
• Dispatchers.Unconfined：非受限调度器，在调用者线程启动。
• Dispatchers.Default：默认调度器，用于计算密集型任务。
• newSingleThreadContext：为协程创建一个全新的专有线程。

2. 开发者感悟

调度器就像是协程的“发动机”。在 Android 中，最核心的技能就是：用 Dispatchers.IO 去加载数据，加载完后通过 Dispatchers.Main 切回主线程刷新界面。

本篇解析 example-exceptions-01.kt。探讨 launch 与 async 在异常处理上的本质差异。

1. 核心概念：自动传播 vs 向用户暴露

自动传播 (launch)

• 行为：异常被视为“未捕获”的。它会立即向上传播给父协程，最终由 Thread.uncaughtExceptionHandler 或 CoroutineExceptionHandler 处理。
• 特点：即使你 join 了这个任务，异常也会在后台静默抛出（并可能导致崩溃）。

向用户暴露 (async)

• 行为：异常被封装在返回的 Deferred 对象中。
• 特点：异常不会立即导致程序崩溃。只有当你显式调用 deferred.await() 时，异常才会被重新抛出。此时你可以使用 try-catch 来捕获它。

2. 代码解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// launch：报错立即向上传播
val job = GlobalScope.launch { 
    throw IndexOutOfBoundsException() 
}

// async：报错被暂存，直到 await()
val deferred = GlobalScope.async { 
    throw ArithmeticException() 
}
try {
    deferred.await() // 此时捕获异常
} catch (e: ArithmeticException) {
    println("Caught ArithmeticException")
}

3. 开发者感悟

理解这两者的区别至关重要。launch 适合“发射后不管”的后台任务；async 适合需要获取结果的任务。在 Android 中，如果你不希望一个后台请求失败导致整个应用崩溃，使用 async 并在 await 时处理异常是更安全的做法。