以下文章有ChatGPT生成

多语言大模型（Multilingual LLM）越来越普及，但一个常见的问题是：模型处理非英语语言时，是直接在原语言上推理，还是先翻译成英语再处理？

简短回答：大多数主流模型并不会将输入翻译为英语后再推理，而是直接在原语言上进行理解与生成。

以下是详细解释。

1. 训练方式：直接多语言训练

当前主流大模型（如 GPT、Claude、Gemini、Mistral、LLaMA、BLOOM 等）在训练时使用了多语种语料，模型在训练阶段就学会了多语言的语法、词汇和语义表达：

• 不会将所有语料翻译成英语；
• 而是在训练过程中构建出一个“跨语言的共享语义空间”，在这个空间中不同语言的同义句会靠得很近；
• 因此，模型具备了直接理解和生成多语言的能力。

2. 英语的优势与“隐性中心化”

虽然模型支持多语言，但英语仍然是“最强语言”，原因包括：

• 英语在训练数据中占比通常高达 60%~90%；
• 模型参数对英语有更强的优化效果；
• 英语可能隐性地作为“锚点”来对齐其他语言的语义表示。

这种语义对齐并不是翻译行为，而是一种深层语义空间的统一。

3. 推理流程：不会翻译成英语再处理

当你用中文或其他语言提问时，模型不会走「中文 → 英文 → 推理 → 翻译成中文」这一路径，而是：

• 直接在中文语境中理解问题；
• 在语义空间中执行推理；
• 直接生成中文结果。

当然，部分三方插件可能人为引入翻译步骤，但这不是模型本身的机制。

4. 支持机制的实验证据

• 对比实验：模型处理法语、德语等非英语输入时，直接完成推理与生成，无中转行为。
• 语义嵌入对齐：多语言句子在语义空间中具有高度重合性。
• 激活层分析：输入非英语语言时，中间激活状态未显示出“语言切换”迹象。

5. 用英语输入表现是否更好？

是的。虽然模型支持多语言，但用英语输入通常效果最佳，尤其体现在知识完整性、表达清晰度、推理深度等方面：

为什么英语效果更好：

对比示例：

6. Prompt 编写建议

7. 实用技巧：英文 Prompt + 中文输出

模板：

1
2

[Your task in English]
Please answer in Chinese.

示例：

1
2

Write a short argumentative essay about how artificial intelligence is impacting the future of employment. Focus on both the opportunities and challenges it presents. Use logical reasoning and real-world examples.
Please answer in Chinese.

输出（模型生成中文）：

人工智能正在以惊人的速度改变就业的未来……（略）

8. 进阶策略：先生成英文，再翻译

对于需要最大限度保持内容质量的应用，可以：

1. 使用英文 Prompt；
2. 得到英文结果后，用模型翻译为中文；

1
2

Translate the following text into Chinese:
[英文生成内容]

适合精细控制内容质量的生产环境。

总结

延伸阅读

• Massively Multilingual Models (mT5)
• BLOOM: a 176B Multilingual LLM
• XGLM: Multilingual Autoregressive Language Model
• OpenAI: Language models as multilingual translators

🧠 一、费曼学习法（Feynman Technique）

核心理念：用教别人的方式来教自己。

📌 关键步骤：

1. 选择概念：挑选你想学的知识点。
2. 解释给小白听：用简单、口语化的语言讲解，好像在教一个完全不懂的人（比如小学生）。
3. 找出盲点：当你卡住或讲不清楚，说明你还没真正理解。
4. 回顾补全：回到原材料查漏补缺，搞清楚所有细节。
5. 重新讲解 & 简化：再次讲解，并尽量用更简单的语言表达。

✅ 核心关键：

“能讲清楚，才算真正学懂。”

🧩 二、西蒙学习法（Herbert Simon Learning Strategy）

（又称“问题解决导向学习”Problem-Solving Learning）

📌 关键特点：

1. 以问题为驱动：学习过程围绕真实问题展开，而不是被动接收知识。
2. 建立知识结构：通过已有的知识和逻辑推理解决新问题。
3. 重视反思与优化：每一次问题解决都伴随着策略的反思和迭代。

✅ 核心关键：

“用解决问题的方式构建知识体系。”

📝 三、康奈尔学习法（Cornell Note-taking System）

核心理念：结构化笔记提升理解与记忆。

📌 五大步骤：

1. 笔记区（右侧大块）：上课或阅读时记下主要内容。
2. 提问区（左侧小块）：课后写下问题、关键词或提示语，用于复习时自测。
3. 总结区（底部）：用自己的话总结整页笔记的核心。
4. 回顾复习：定期回看并测试自己，强化记忆。
5. 联结思考：不断将新知识与旧知识联系起来。

✅ 核心关键：

“记笔记不是为了记录，而是为了思考和复习。”

🔍 总结对比表

quick_worker 是一个用 Go 实现的轻量级异步批处理框架。它通过 channel 和 goroutine 构建了一个高效的生产者-消费者模型，支持按批量大小或超时触发数据处理，适合高并发、吞吐敏感的场景。

本文将围绕其核心并发模型进行分析，重点讨论：

• 是否存在 CPU 空转（Busy Waiting）问题
• select 和 channel 的阻塞特性
• 在什么情况下应考虑使用 sync.Cond 替代主动轮询

一、项目核心架构概览

quick_worker 的核心工作流程：

1. 数据投递：调用方通过 Produce 方法投递任务数据。
2. 缓冲通道：数据进入内部 dataChan 缓冲通道。
3. 消费者循环：独立的消费者 goroutine 执行 consume 方法，负责从通道中取出数据并批量处理。
4. 触发机制：处理可以由达到最大批量（maxBatchSize）或等待超时（maxWaitDuration）触发。
5. 退出控制：通过 doneChan 通知消费者优雅退出。

这一模型兼具性能与可靠性，典型用于日志聚合、异步队列、延迟任务聚合等场景。

二、关于 CPU 空转（Busy Waiting）问题的分析

1. 消费者循环是否会导致空转？

core/worker.go 中的主循环如下：

1
2
3
4
5
6
7
8
9
10

for {
    select {
    case data, ok := <-w.dataChan:
        // 接收并处理数据
    case <-timer.C:
        // 超时触发处理
    case <-w.doneChan:
        // 接收到退出信号
    }
}

该循环具有以下特性：

• select 是阻塞式的：当所有分支都不满足时，select 会自动挂起，不占用 CPU。
• 只要 dataChan 中没有数据、timer 没有到期、doneChan 没有信号，该 goroutine 会自然休眠。
• 结论：这段代码不会导致 CPU 空转，是标准的 Go 并发写法。

2. 生产者逻辑是否安全？

生产者调用 Produce 方法将数据投递进通道时，使用了非阻塞的 select：

1
2
3
4
5
6

select {
case w.dataChan <- data:
    // 投递成功
default:
    // 通道已满，放弃投递
}

这避免了阻塞与死循环，也没有任何 busy loop 行为。

3. 可能导致空转的场景分析

✅ 总结结论：

• quick_worker 中的核心并发逻辑是以阻塞式 channel + timer 驱动的。
• 消费者 goroutine 不存在任何 busy waiting。
• 项目天然避免了 CPU 空转问题，性能开销可控。

三、sync.Cond：在什么情况下必须使用它来避免 CPU 空转？

虽然 quick_worker 本身没有使用 sync.Cond，但了解它的用途对于设计其他复杂同步场景非常重要。

1. 什么是 CPU 空转？

CPU 空转（Busy Waiting）是指：线程在等待某个条件成立时，不阻塞、不 sleep，而是反复检查条件的状态，导致 CPU 被无意义地占用。

例如：

1
2
3

for !ready {
    // 空转：一直检查条件，浪费 CPU
}

这段代码没有任何阻塞操作，会让 CPU 持续忙碌。

2. 如何使用 sync.Cond 避免空转？

sync.Cond 提供了条件变量机制，允许我们在等待某个条件时挂起 goroutine，直到条件成立被显式唤醒。

示例：

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

var mu sync.Mutex
var cond = sync.NewCond(&mu)
var ready bool

// 等待方（消费者）
mu.Lock()
for !ready {
    cond.Wait() // 阻塞等待，自动释放锁，避免空转
}
mu.Unlock()

// 通知方（生产者）
mu.Lock()
ready = true
cond.Signal() // 或 cond.Broadcast()
mu.Unlock()

优点：

• Wait() 会阻塞 goroutine，而不是让它空转。
• Signal() 只唤醒一个等待者，Broadcast() 唤醒所有等待者。

3. 使用 sync.Cond 的典型场景

4. channel 和 sync.Cond 的选择建议

结论：

如果你在等待某个“条件”而非“数据”，又无法用 channel 表达，那么使用 sync.Cond 可以有效避免 busy loop。

四、总结

• quick_worker 项目使用阻塞式 select 循环，无 busy loop 行为，不存在 CPU 空转问题。
• Go 的 channel 和 timer 本身就是高效的阻塞机制，只要 select 内有阻塞分支，goroutine 就不会占用 CPU。
• 只有在使用 for + 条件判断 等原始自旋方式等待状态时，才需要引入 sync.Cond。
• sync.Cond 更适合资源池、复杂状态条件协作等无法使用 channel 描述的场景。

在现代软件开发中，高效的任务管理与并发处理是提升系统性能的关键。QuicKit 是一个基于 Java 的工具库，专注于并发任务调度、执行控制、重试机制等通用能力的封装。本文将深入介绍 QuicKit 的核心功能及其实现原理。

1. 延迟任务调度：DelayQueueUtils

DelayQueueUtils 使用 HashedWheelTimer 实现延迟任务的高效调度。

实现原理：

• 时间轮机制：将时间划分为多个槽（slots），类似时钟的刻度。
• 任务分配：任务根据设定的延迟时间分配至对应槽中。
• 槽激活：时间轮旋转，当指针指向某个槽时，执行该槽内的所有任务。

✅ 优势：极大减少内存消耗和调度开销，适合高频延迟任务场景。

2. 执行频率控制：ExecutionFrequencyUtils

用于控制任务执行频率，防止系统被大量任务压垮。

实现原理：

• 任务分片：将任务列表切分为多个子任务，每批任务在一定时间间隔内执行。
• 频率限制：可配置每秒允许执行的任务数量，避免突发任务过载系统。

✅ 应用场景：接口限流、批量处理限速、系统保护。

3. 并行任务处理：ParallelTask

提供简洁高效的并行处理能力，充分利用多核 CPU 性能。

实现原理：

• 并行流：基于 Java 8 的 parallelStream() 并行处理任务。
• 线程池管理：使用 ExecutorService 管理线程，降低线程创建销毁开销。

✅ 适用场景：批量任务处理、并发计算、数据转换等。

4. 重试机制：RetryUtils

内置灵活的重试机制，应对任务失败后的自动恢复。

实现原理：

• 重试策略配置：通过 RetryerBuilder 设置重试次数、间隔、终止条件等。
• 异常捕获与处理：根据异常类型与策略自动判断是否重试。

✅ 典型用途：数据库重试、远程服务调用、临时异常容忍。

5. 读写锁封装：ReadWriteLockWrapper

封装 Java 原生 ReentrantReadWriteLock，简化并发数据访问控制。

实现原理：

• 读写分离：多个线程可同时读，写需独占。
• 锁降级支持：支持写锁降级为读锁，提升吞吐性能。

✅ 适用场景：缓存读取、配置中心、共享资源管理等。

总结

QuicKit 通过提供一系列高性能并发工具，极大简化了任务调度、线程管理与错误恢复的复杂性。无论你在构建分布式系统、服务中间件，还是日常业务逻辑开发，QuicKit 都是一个值得使用的并发基础组件库。

📦 项目地址：
👉 https://github.com/Kingson4Wu/QuicKit

📚 文档地址：
👉 https://deepwiki.com/Kingson4Wu/QuicKit

最近重新刷LeetCode，对一些算法基础和套路做下总结，以做备忘

简要分类总结

数据结构

• 数组（Array）
• 链表（Linked List）
• 哈希表（HashMap / HashSet）
• 堆（Heap）
  • 最大堆 / 最小堆
  • 常用于：优先队列、Top K、调度排序
• 栈 / 队列（Stack / Queue）
  • DFS 通常借助栈实现，BFS 借助队列
• 树（Tree）
  • 普通二叉树
  • 二叉搜索树（BST）
  • 平衡二叉树（AVL / 红黑树）
  • 字典树（Trie）
  • 线段树（Segment Tree）
  • 树状数组（Fenwick Tree）
  • 并查集
• 图（Graph）
  • 表示方式：邻接表、邻接矩阵
  • 有向图 / 无向图，带权图 / 无权图
  • 拓扑排序
    • Kahn 算法（BFS 实现）
    • DFS 逆后序（递归 + 回退）
    • 用于检测有向图中是否存在环、任务调度等
  • 最短路径算法：Dijkstra、Floyd、Bellman-Ford（带权图最短路径）
  • 最小生成树算法：Kruskal / Prim
  • 稠密图和稀疏图
    • 稠密图：边很多，接近“完全图”
    • 稀疏图：边很少，大多数节点之间没有直接连接

算法

• 遍历算法
  • 深度优先搜索（DFS）
    • 栈结构实现（递归或手动栈）
    • 回溯 （= DFS + 剪枝 + 状态恢复（回退））
      • 常用于：组合、排列、子集、数独、八皇后等问题
  • 广度优先搜索（BFS）
    • 队列结构实现，逐层遍历
• 排序（冒泡、快速、堆）
• 快慢指针/ 双指针
• 滑动窗口
• 单调栈 / 单调队列
• 二分查找
• 分治算法（Divide & Conquer）
• 贪心算法（Greedy）
• 动态规划（DP）
  • 背包问题（0-1 背包、子集背包、完全背包）
  • 子序列问题（LIS 最长递增子序列、LCS 最长公共子序列）
  • 区间 DP / 状态压缩 / 滚动数组
• 回溯算法（Backtracking）
  • 用于枚举所有可能解，如全排列、组合 / 子集

链表

• 与数组不同，链表在构建子链时不会增加额外的空间复杂度。因此可以放心地构造子链，无需考虑节点交换的问题，也不必执着于“原地交换”的思路。

• 使用哨兵节点是一种常见技巧，它可以避免处理头指针等特殊情况，在代码实现上更加简洁。

  • 链表内指定区间反转：
    给定一个单链表的头指针 head，以及两个整数 left 和 right（其中 left <= right），请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

  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

  func reverseBetween(head *ListNode, m int, n int) *ListNode { if m == n || head == nil { return head } // 哨兵节点，避免处理头指针的特殊情况 dummy := &ListNode{Next: head} pre := dummy // 1. 找到第 m-1 个节点 for i := 1; i < m; i++ { pre = pre.Next } // 2. 反转 m 到 n 之间的节点，采用头插法 start := pre.Next // 第 m 个节点 then := start.Next // 第 m+1 个节点 for i := 0; i < n-m; i++ { start.Next = then.Next then.Next = pre.Next pre.Next = then then = start.Next } return dummy.Next }

二叉树

• 二叉树遍历（先序、中序、后序）

  • 先序（中左右）、中序（左中右）、后序（左右中）
  • 包含递归与非递归两种实现方式
  • DFS：先序 / 中序 / 后序（递归 / 栈实现）
  • BFS：层序遍历（借助队列实现）

• 二叉查找树（Binary Search Tree，简称 BST）

  • 左子树所有节点的值均小于根节点，右子树所有节点的值均大于根节点（不允许等于）
  • 中序遍历结果是升序序列

• 完全二叉树

  • 如果一棵深度为 h 的二叉树，除了第 h 层，其它每一层的节点数都达到最大值，并且第 h 层的节点都尽量靠左排列，则该树是完全二叉树
  • 第 h 层可能包含 1 ~ 2^h 个节点
  • 堆（大顶堆 / 小顶堆）是一种基于完全二叉树的结构

• 平衡二叉树（Balanced Binary Tree）

  • 要么是空树，要么满足以下条件：左右子树的高度差的绝对值不超过 1，且左右子树也分别是平衡二叉树

二叉树遍历

• 树的遍历主要分为两类：

  • 广度优先遍历（BFS）：也称层序遍历，使用队列实现

  • 深度优先遍历（DFS）：包括先序、中序、后序三种形式，可使用递归或栈实现

    • 递归
    • 栈

• 深度优先遍历（DFS）说明

  • 使用递归实现 DFS 时，虽然代码中未显式使用栈，但其实是借助系统的 调用栈（Call Stack） 来进行函数的递归与回溯

先序遍历（前序）

• 栈实现流程：

  1. 循环条件：root != nil || len(stack) > 0
  2. 若 root != nil，访问节点、入栈、转向左子树
  3. 否则出栈、转向右子树

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

func (root *TreeNode) preorder() []int {
	res := []int{}
	if root == nil {
		return res
	}
	stack := []*TreeNode{}
	for root != nil || len(stack) > 0 {
		if root != nil {
			res = append(res, root.data)      // 访问当前节点
			stack = append(stack, root)       // 入栈
			root = root.Lchild                // 向左子树移动
		} else {
			root = stack[len(stack)-1]        // 出栈
			stack = stack[:len(stack)-1]
			root = root.Rchild                // 转向右子树
		}
	}
	return res
}

中序遍历

• 栈实现流程：

  1. 循环条件：root != nil || len(stack) > 0
  2. 若 root != nil，将当前节点入栈并转向左子树
  3. 否则出栈并访问节点
  4. 然后转向右子树

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

func (root *TreeNode) inorder() []int {
	res := []int{}
	if root == nil {
		return res
	}
	stack := []*TreeNode{}
	for root != nil || len(stack) > 0 {
		if root != nil {
			stack = append(stack, root)       // 入栈，等待回溯
			root = root.Lchild                // 向左走
		} else {
			root = stack[len(stack)-1]        // 出栈
			stack = stack[:len(stack)-1]
			res = append(res, root.data)      // 访问节点
			root = root.Rchild                // 转向右子树
		}
	}
	return res
}

• 示例题目：判断一棵二叉树是否为二叉搜索树

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

func isValidBST(root *TreeNode) bool {
    stack := []*TreeNode{}
    inorder := math.MinInt64
    for len(stack) > 0 || root != nil {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if root.Val <= inorder {
            return false
        }
        inorder = root.Val
        root = root.Right
    }
    return true
}

后序遍历

• 非递归实现关键：访问节点需保证其左右子树均已访问或为空

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

func (root *TreeNode) Postorder() []int {
	res := []int{}
	if root == nil {
		return res
	}
	stack := []*TreeNode{}
	var pre *TreeNode = nil
	stack = append(stack, root)

	for len(stack) > 0 {
		cur := stack[len(stack)-1]
		// 如果是叶子节点，或子节点已访问，则访问当前节点
		if (cur.Lchild == nil && cur.Rchild == nil) || (pre != nil && (pre == cur.Lchild || pre == cur.Rchild)) {
			res = append(res, cur.data)
			stack = stack[:len(stack)-1]
			pre = cur // 标记当前已访问
		} else {
			if cur.Rchild != nil {
				stack = append(stack, cur.Rchild)
			}
			if cur.Lchild != nil {
				stack = append(stack, cur.Lchild)
			}
		}
	}
	return res
}

删除二叉搜索树中的节点

• 删除节点的四种情况：

  1. 叶子节点（无子节点）

     • 直接删除，返回 nil。

  2. 只有左子树

     • 用左子节点替代当前节点，返回 root.Left。

  3. 只有右子树

     • 用右子节点替代当前节点，返回 root.Right。

  4. 左右子树都有

     • 找右子树中最小的节点（即后继 successor），
     • 用 successor 的值替代当前节点的值，
     • 然后在右子树中递归删除该 successor 节点。

• 情况 4 的说明：

  • **右子树的最小节点（successor）**不一定是叶子节点；
  • 它一定没有左子节点，但可能有右子节点。

1
2
3
4
5
6
7
8
9

  10                        11        
 /  \                      /  \
5    15                   5   15
    /                         /  
   11       -->             13
     \                     /  \  
     13                   12  14
    /  \
   12   14

• 什么是“递归删除 successor 节点”？

  • 当我们删除一个节点（设为 root）且其有左右子树时，选择右子树中最小节点（successor）作为替代；
  • 但此时右子树中仍存在原来的 successor 节点，因此需在右子树中递归删除该节点；
  • 这样才能确保整棵树依然符合**二叉搜索树（BST）**的性质。

实现示例

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

func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return nil
	}
	if key < root.Val {
		root.Left = deleteNode(root.Left, key)
		return root
	} else if key > root.Val {
		root.Right = deleteNode(root.Right, key)
		return root
	}
	//找到要删除的结点
	if root.Left == nil {
		return root.Right
	}
	if root.Right == nil {
		return root.Left
	}
	// 情况4：左右子树都有
	//需要找右子树的最小值的结点, 最小的一定在最左边
	successor := root.Right
	for successor.Left != nil {
		successor = successor.Left
	}
	successor.Right = deleteNode(root.Right, successor.Val)
	successor.Left = root.Left
	return successor
}

树状数组（Fenwick Tree / Binary Indexed Tree）

• 适用场景：一维前缀和问题（如区间求和、频率统计等）

• 核心思想：

  • 利用二进制的最低位（lowbit）来定位负责某段区间的节点
  • 是一种空间压缩形式的前缀树结构

• 一种可动态维护序列前缀和的数据结构，支持以下操作：

  • **单点更新 update(i, v)**：将第 i 个位置的值增加 v（如本题中 v = 1）

  1 2 3 4 5 6

  func update(i int, v int) { for i <= n { // n 是树状数组的长度 bit[i] += v i += i & -i // 跳到下一个负责这个区间的节点 } }

  • **区间查询 query(i)**：查询区间 [1..i] 的前缀和

    • 通过跳跃式回溯累加，效率高

    1 2 3 4 5 6 7 8 9

    // 查询 bit[1] 到 bit[i] 的前缀和 func query(i int) int { res := 0 for i > 0 { res += bit[i] i -= i & -i // i & -i 取最低位的 1 } return res }

query(p) 的跳跃计算示意

• 树状数组 bit[] 示意如下：

• 查询 query(5) 实际执行过程如下：

  • 第一次：p = 5 → sum += bit[5] = 0 → p = 5 - 1 = 4
  • 第二次：p = 4 → sum += bit[4] = 3 → p = 4 - 4 = 0
  • 退出循环，结果为 sum = 3

• 实际加了哪些区间：

  • bit[5] → 表示 [5]
  • bit[4] → 表示 [1..4]
  • 所以 sum[1..5] = bit[5] + bit[4]

为什么 x & (-x) 能取得 x 的最低位 1？

• 原理：使用补码

  • -x = ^x + 1（按位取反再加 1）

1
2
3
4

x     = 00001100
-x    = 11110100
----------------
x & -x = 00000100  // 取出最低位的 1

• 补码运算确保 x & -x 恰好保留最低位的 1，其它位互斥

树状数组的安全构造方式

1
2
3
4
5

// 计算最小安全长度（为离散化后的数组保留空间）
func getSafeFenwickArraySize(n int) int {
    nextPowerOf2 := 1 << bits.Len(uint(n))
    return nextPowerOf2 + 1 // +1 处理边界
}

例题：315. 计算右侧小于当前元素的个数

• 题意：返回数组 counts，其中 counts[i] 表示 nums[i] 右侧比它小的元素数量
• 解法：树状数组 + 离散化优化空间

解题流程：

1. 离散化：将原数组值映射到连续整数范围（防止值域过大）

2. 从后向前遍历：

   • 查询当前数 前面比它小 的数的出现次数 → query(id - 1)
   • 更新当前数出现次数 → update(id)

3. 树状数组操作时间复杂度：O(log n)

实现代码：

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

func countSmaller(nums []int) []int {
    // 离散化映射：数值 -> 索引
    numToId := func(nums []int) map[int]int {
        set := make(map[int]struct{})
        for _, num := range nums {
            set[num] = struct{}{}
        }
        a := make([]int, 0, len(set))
        for num := range set {
            a = append(a, num)
        }
        sort.Ints(a)
        m := make(map[int]int)
        for i, num := range a {
            m[num] = i + 1  // 从 1 开始
        }
        return m
    }(nums)

    c := make([]int, len(nums)+5)
    lowBit := func(x int) int {
        return x & -x
    }
    query := func(pos int) int {
        ret := 0
        for pos > 0 {
            ret += c[pos]
            pos -= lowBit(pos)
        }
        return ret
    }
    update := func(pos int) {
        for pos < len(c) {
            c[pos]++
            pos += lowBit(pos)
        }
    }

    ans := make([]int, len(nums))
    for i := len(nums) - 1; i >= 0; i-- {
        id := numToId[nums[i]]
        ans[i] = query(id - 1)
        update(id)
    }
    return ans
}

线段树（Segment Tree）

• 适用场景：支持区间查询 + 单点或区间修改等

• 典型用途：

  • 区间最大值、最小值、区间和
  • 区间赋值、区间加法（懒标记 / Lazy Propagation）

• 结构特征：

  • 完全二叉树结构
  • 每个节点维护一个区间的信息
  • 父节点信息由左右子树合并而来

例题：699. 掉落的方块

• 问题：模拟落方块过程，返回每一步的最高高度
• 典型的线段树区间最大值更新与查询问题

解题流程：

1. 离散化所有坐标：防止空间浪费（坐标最大值可达 10^9）

2. 使用线段树维护每个区间的最大高度

3. 每次插入一个方块：

   • 查询当前 [left, right] 区间的最大高度 h
   • 更新该区间的值为 h + sideLength
   • 记录全局最大高度

并查集

例题：684. 冗余连接

• 在含有一个环的无向图中找出一条可删边使其变为树

解题流程：

• 使用并查集判断边是否构成环：
  • 初始化每个节点为不同集合；
    • 遍历 edges 中每条边 (u, v)：
      • 如果 u 与 v 已在同一集合中，说明这条边构成环 → 返回它；
      • 否则合并 u 和 v；
  • 因为题目要求返回「最后构成环的边」，只需从前往后遍历一次即可。

实现代码

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

func findRedundantConnection(edges [][]int) []int {
    parent := make([]int, len(edges)+1)
    for i := range parent {
        parent[i] = i
    }
    var find func(int) int
    find = func(x int) int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }
    union := func(from, to int) bool {
        x, y := find(from), find(to)
        if x == y {
            return false
        }
        parent[x] = y
        return true
    }
    for _, e := range edges {
        if !union(e[0], e[1]) {
            return e
        }
    }
    return nil
}

堆

基本性质与操作（以最大堆为例）

1. 最大堆的性质

   • 最大堆是一种完全二叉树，满足每个父节点的值都大于或等于其左右子节点的值。
   • 虽然逻辑结构为树，实际通常使用数组来实现。

2. 元素的插入与删除方式

   • 插入新节点：将元素追加到数组末尾，然后进行向上调整（Sift-Up），直到堆序性恢复。

   • 删除任意节点：将目标节点与数组最后一个元素交换，然后删除最后一个元素：

     • 若新值大于父节点 → 进行向上调整；
     • 若新值小于任一子节点 → 进行向下调整。

3. 特殊操作：删除堆顶（最大值）

   • 删除堆顶（即数组第一个元素）时，将最后一个元素移至根节点位置，再进行向下调整（Sift-Down），以恢复堆的结构。

4. 时间复杂度分析

   • 插入或删除操作中，最多需要调整一条从叶节点到根节点或从根节点到叶节点的路径，因此时间复杂度均为：

     ✅ O(log n)

5. 与二分查找的比较

   • 二分查找的时间复杂度也是：

     ✅ O(log n)

   • 不过它依赖于有序数组，而最大堆只维护局部有序结构（即每个父节点大于子节点）。两者在原理和应用场景上存在本质区别。

图

无向图

• 由两个部分组成：

  • 顶点（Vertices）：图中的节点。
  • 边（Edges）：连接两个顶点的线段。

• 边用集合表示：一条边连接两个顶点，用 {A, B} 表示（不区分方向），区别于有向图中的 (A, B)。
  度（Degree）：一个顶点的度是连接它的边的数量（不考虑方向）。

• 无向图可以表示为：

  • 顶点：{A, B, C}
  • 边：{{A, B}, {B, C}}

• 图形示意：

  • A —— B —— C

• 无向图的深度优先搜索（DFS）

  • 从某个顶点开始；
  • 标记为“已访问”；
  • 遍历它的邻居；
  • 对每一个未访问的邻居递归执行 DFS；
  • 如果遇到没有未访问邻居的死胡同，则回退。

• 递归实现 DFS：

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

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    print(start)  # 访问当前节点
    visited.add(start)

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 调用
dfs(graph, 'A')

• 非递归实现（使用栈）：

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

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node)
            visited.add(node)
            # 为了保持访问顺序，反转邻居顺序
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

dfs_iterative(graph, 'A')

• 无向图 DFS 的注意事项：

  • 防止死循环：必须使用 visited 集合记录已访问节点，因为无向图的边是双向的，若不记录，会在 A-B-A-B 间无限循环。
  • 图不连通的情况：只对一个起点 DFS 无法遍历所有节点。可对所有节点进行一次 DFS。

1
2
3
4
5

def dfs_all(graph):
    visited = set()
    for node in graph:
        if node not in visited:
            dfs(graph, node, visited)

有向图

有向图的拓扑排序

• 拓扑排序（Topological Sorting）适用于 有向无环图（DAG，Directed Acyclic Graph）。其目标是将所有顶点排成一个线性序列，使得每条边 u → v 中，顶点 u 排在 v 的前面。

• 举例说明：

  • 学习顺序：先学 A，再学 B，最后学 C。
  • 任务依赖：任务 B 必须在任务 A 完成后执行。
  • 将任务抽象为节点，依赖关系为边，则问题转化为 DAG 的拓扑排序。

• 适用范围：

  • 必须是有向无环图（DAG）。
  • 若图中存在环，则无法进行拓扑排序。

• 拓扑排序的两种常用算法：

  • 方法一：Kahn 算法（入度表 + 队列）

    • 统计所有顶点的入度。
    • 将入度为 0 的顶点加入队列。
    • 从队列中取出顶点 u 加入结果序列。
    • 删除 u 指向的边（使相邻顶点 v 入度减 1）。
    • 若 v 入度变为 0，加入队列。
    • 重复以上过程直至队列为空。
    • 若最终结果序列包含所有节点，则拓扑排序成功；否则图中存在环。

  • 方法二：DFS 法（后序入栈）

    • 从未访问的节点开始 DFS。
    • 递归访问其所有后继节点。
    • 当前节点所有后继访问完成后，将其压入栈中。
    • 所有节点访问完成后，从栈顶依次弹出即为拓扑序列。

• 常见应用场景：

  • 编译器模块依赖分析
  • 项目任务调度
  • 数据处理管道排序
  • 课程安排问题（Leetcode 207、210）

Kahn 算法（Golang 实现）：

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
48
49
50
51
52
53
54
55
56
57
58
59

// 拓扑排序（Kahn 算法）
func topologicalSort(graph map[string][]string) ([]string, bool) {
  inDegree := make(map[string]int)
  var result []string

  // 初始化入度表
  for u := range graph {
    if _, ok := inDegree[u]; !ok {
      inDegree[u] = 0
    }
    for _, v := range graph[u] {
      inDegree[v]++
    }
  }

  // 入度为 0 的节点入队
  var queue []string
  for node, deg := range inDegree {
    if deg == 0 {
      queue = append(queue, node)
    }
  }

  // 拓扑排序
  for len(queue) > 0 {
    node := queue[0]
    queue = queue[1:]
    result = append(result, node)

    for _, neighbor := range graph[node] {
      inDegree[neighbor]--
      if inDegree[neighbor] == 0 {
        queue = append(queue, neighbor)
      }
    }
  }

  // 判断是否存在环
  if len(result) != len(inDegree) {
    return nil, false
  }
  return result, true
}

func main() {
  graph := map[string][]string{
    "A": {"B", "C"},
    "B": {"D"},
    "C": {"D"},
    "D": {},
  }

  order, ok := topologicalSort(graph)
  if !ok {
    fmt.Println("图中存在环，无法拓扑排序")
  } else {
    fmt.Println("拓扑排序结果：", order)
  }
}

• Kahn 算法的核心逻辑：

  • 每次只处理入度为 0 的节点，即“无依赖”的任务。
  • 处理后从图中移除该节点影响（即更新其邻接节点的入度）。
  • 保证每个节点的依赖都先被处理。

• 为什么 Kahn 算法只适用于 DAG？

  • 如果存在环，某些节点将永远无法变为入度 0，导致无法完成排序。
  • 若排序结果节点数 < 总节点数，说明图中存在环。

✅ 因此：Kahn 算法不仅能进行拓扑排序，还能用于判断图中是否存在环。

• Kahn 算法实质上是 BFS 的变种，关注“入度为 0”的节点而不是“邻接点”。

Kahn 算法 vs 广度优先搜索（BFS）

Kahn 算法 = BFS 的拓扑排序版本，核心是基于“入度为 0”的节点层层推进，保证拓扑顺序合法。

二分查找

1. for lower <= upper —— 闭区间版本 [lower, upper]

   • mid = (lower + upper) / 2（向下取整）

     • 如果 mid 满足条件（要往左找更小或更左的）：upper = mid - 1
     • 如果不满足条件（要往右找）：lower = mid + 1

   • 是否跳过了 mid？

     • 表面上看，upper = mid - 1 似乎跳过了 mid
     • 实际上，mid 已经被判断过，lower 没变，下一轮中 lower == mid
     • 循环仍会继续执行，直到 lower > upper 时退出

   • 示例分析：

     • 在数组 [3, 4, 5] 中查找“第一个大于等于 4 的数”
     • 初始区间为 [3, 5]，mid = 4
     • mid = 4 满足条件 → upper = 3
     • 下一轮区间为 [3, 3]，mid = 3
     • mid = 3 不满足条件 → lower = 4
     • 区间变为 [4, 3]，循环结束
     • 返回 lower = 4，即最小满足条件的值

2. for lower < upper —— 半开区间版本 [lower, upper)

   • 如果 mid 满足条件（要往左找）：upper = mid
   • 如果不满足条件：lower = mid + 1
   • 循环结束时 lower == upper，即为最小满足条件的位置

排序

冒泡排序

• 相邻元素两两比较并交换，使用双重循环；
• 若某次遍历中未发生任何交换，说明数组已有序，可提前结束；
• 代码示例：

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

func bubbleSort(arr []int) {
    n := len(arr)
    if n <= 1 {
        return
    }

    for i := 0; i < n; i++ {
        unChanged := true
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
                unChanged = false
            }
        }
        if unChanged {
            break
        }
    }
}

快速排序

• 通过一趟排序将序列划分为左右两个子区间，其中左边的元素都小于右边的元素，再分别对左右区间递归排序，从而实现整体有序。

• 分区逻辑说明（采用首元素为基准）：

  • 交替比较并交换元素值，最终确定基准值的位置；
  • 每步都需判断 low < high，不要遗漏；
  • high-- 与 low++ 的条件是与 temp（基准值）进行比较。

• TopK 剪枝优化（用于只需前K个元素的场景）：

  • 若 mid > k，递归处理左边；
  • 若 mid < k，递归处理右边。

• 分区函数定义模板：

1
2
3
4
5

func partition(arr []int, low, high int) int {
    // 首先从 high 开始比较，循环 high--，跳出后赋值；
    // 然后从 low 开始比较，同理；
    // 每步都要判断 low < high；
}

• 快速排序递归模板：

1
2
3
4

var quick func(arr []int, start, end int)
quick = func(arr []int, start, end int) {
    // ...
}

• 代码示例：

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
48
49
50
51
52

// 升序快速排序
func quickSort(arr []int) {
    var quick func(arr []int, start, end int)
    quick = func(arr []int, start, end int) {
        if start >= end {
            return
        }
        mid := partition(arr, start, end)
        quick(arr, start, mid)
        quick(arr, mid+1, end)
    }
    quick(arr, 0, len(arr)-1)
}

// 分区函数，low < high 判断不要漏！
func partition(arr []int, low, high int) int {
    temp := arr[low]
    for low < high {
        for low < high && arr[high] >= temp {
            high--
        }
        if low < high {
            arr[low] = arr[high]
        }

        for low < high && arr[low] < temp {
            low++
        }
        if low < high {
            arr[high] = arr[low]
        }
    }
    arr[low] = temp
    return low
}

// 前K个最小值
func quickSortTopK(arr []int, k int) {
    var quick func(arr []int, start, end, k int)
    quick = func(arr []int, start, end, k int) {
        if start >= end {
            return
        }
        mid := partition(arr, start, end)
        if mid > k {
            quick(arr, start, mid, k)
        } else if mid < k {
            quick(arr, mid+1, end, k)
        }
    }
    quick(arr, 0, len(arr)-1, k)
}

堆排序

1. 堆是一种完全二叉树结构；
2. 最大堆：父节点 ≥ 子节点；最小堆：父节点 ≤ 子节点；

• 实现步骤：

  1. 调整堆（自上而下）：

     • 函数签名：adjust(nums []int, root int, length int)
     • 从当前根节点开始，比较左右子节点，找出较大者与根交换，递归向下直到无需调整。

  2. 初始化堆：

     • 从最后一个非叶子节点（length/2）开始，依次向上调整；

  3. 堆排序过程：

     • 每次将堆顶元素与末尾交换，再对堆顶进行调整；
     • 排序范围逐步缩小，直到全部有序。

• 最大堆调整函数：

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

func adjust(nums []int, root, length int) {
    child := root*2 + 1

    for child < length {
        if child+1 < length && nums[child+1] > nums[child] {
            child++
        }

        if nums[child] <= nums[root] {
            break
        }

        nums[child], nums[root] = nums[root], nums[child]
        root = child
        child = root*2 + 1
    }
}

• 代码示例：

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

func heapSort(nums []int) {
    // 初始化堆（自底向上）
    for i := len(nums) / 2; i >= 0; i-- {
        adjust(nums, i, len(nums))
    }

    // 排序过程
    for i := len(nums) - 1; i > 0; i-- {
        nums[i], nums[0] = nums[0], nums[i]
        adjust(nums, 0, i)
    }
}

/** 最大堆取 TopK（前K大）且有序 */
func heapSortTopK(nums []int, k int) []int {
    // 初始化最大堆
    for i := len(nums) / 2; i >= 0; i-- {
        adjust(nums, i, len(nums))
    }

    // 取出前K大元素
    for i := len(nums) - 1; i > len(nums)-1-k; i-- {
        nums[i], nums[0] = nums[0], nums[i]
        adjust(nums, 0, i)
    }

    return nums[len(nums)-k:]
}

⚠️注意事项：

• 初始化堆：自底向上遍历构建，但每个节点的调整是自上而下；
• 排序时：堆顶与尾部交换，再调整堆顶；
• adjust 函数中需确保越界处理、优先选择较大子节点交换；

贪心算法（Greedy）

• 贪心算法：通过局部最优解实现全局最优

• 55. 跳跃游戏

  • 给定一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
  • 判断你是否能够到达最后一个下标

• 遍历数组，并实时维护「最远可以到达的位置」

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

  func canJump(nums []int) bool { mostIndex := 0 for i := 0; i < len(nums); i++ { if i <= mostIndex { mostIndex = max(mostIndex, i+nums[i]) if mostIndex >= len(nums)-1 { return true } } else { break } } return false }

• 45. 跳跃游戏 II

  • 计算到达最后一个位置的最小跳跃次数

• 贪心 + 正向查找「可达的最远位置」

  • 每次在当前跳跃的范围内，选择可以跳得最远的位置，作为下一跳的终点

• 贪心策略的正确性：

  • 在当前跳跃范围内尽量跳得远，可以最大化下一跳的「选择空间」
  • 避免走回头路或多跳一次的情况

• 为什么不遍历到最后一个元素？

  • 跳到最后一个位置时，必然是在前一步完成跳跃

  • 如果访问 i == len(nums) - 1，可能导致「多跳一步」

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

    func jump(nums []int) int { end, farthest := 0, 0 steps := 0 for i := 0; i < len(nums)-1; i++ { farthest = max(farthest, i+nums[i]) if i == end { steps++ end = farthest } } return steps } func max(a, b int) int { if a > b { return a } return b }

动态规划（Dynamic Programming）

• 动态规划的本质：通过穷举所有可能解法来寻找最优解。

  • 常见的穷举方式有两种：回溯算法和动态规划。回溯是暴力尝试每种可能，动态规划则利用状态转移方程推导各个状态。
  • 动态规划相比暴力穷举更高效，其核心优势在于：利用状态转移 + 记忆，消除重复计算的子问题（重叠子问题）。

• 动态规划问题通常具有大量重叠子问题，直接穷举效率极低，因此需借助以下两种优化方式：

  • 使用 备忘录（记忆化递归） 或 DP table（递推表格） 来避免重复计算；
  • 其中，记忆化递归为自顶向下，DP table 为自底向上。

• 动态规划 = 穷举 + 剪枝

• 动态规划的标准解题流程：

  1. 明确“状态”和“选择”；
  2. 定义 dp 数组或函数的含义；
  3. 写出状态转移方程（递推关系）。

• 常通过状态压缩优化空间复杂度，例如将 O(N^2) 降为 O(N)。

背包问题（Knapsack）

✅ 分类依据：每个物品的使用次数是否受限

🎯 拓展理解：

• 0-1 背包 = 最经典模型，用于资源受限问题。
• 子集和问题 = 判断“是否可以凑出某个值”，不关心价值。
• 完全背包 = 每种物品无限可选，常见于无限物品、找零等问题。

0-1 背包问题

• 题目描述

  • 给定一个容量为 W 的背包，以及 N 个物品，每个物品有：重量 wt[i] 和价值 val[i]
  • 每种物品只能选择一次，求在不超过总容量 W 的前提下，最大可获得的总价值。

• 解题思路

  • 状态定义：dp[i][w] 表示前 i 个物品中，容量为 w 的背包所能达到的最大价值。

  • 状态转移：

    1 2 3 4

    if w < wt[i-1]: dp[i][w] = dp[i-1][w] else: dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt[i-1]] + val[i-1])

  • 初始化：

    • dp[0][..] = 0：没有物品可选，价值为 0；
    • dp[..][0] = 0：背包容量为 0，价值也为 0。

• 代码实现

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

func knapsack(W int, wt, val []int) int {
    N := len(wt)
    dp := make([][]int, N+1)
    for i := range dp {
        dp[i] = make([]int, W+1)
    }

    for i := 1; i <= N; i++ {
        for w := 1; w <= W; w++ {
            if w < wt[i-1] {
                dp[i][w] = dp[i-1][w]
            } else {
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt[i-1]] + val[i-1])
            }
        }
    }
    return dp[N][W]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

子集背包问题（Subset Sum）

• Leetcode 416. 分割等和子集

  • 给定一个只包含正整数的非空数组 nums，判断是否可以将其分割为两个子集，且两个子集的元素和相等。
  • 转换为背包问题：给一个容量为 sum / 2 的背包，判断是否可以从数组中选出若干数字恰好装满它。

• 解题思路

  • 状态定义：dp[i][j] 表示前 i 个数中，是否存在子集和为 j。
  • 状态转移：

  1 2 3 4

  if j < nums[i]: dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i]]

  • 初始化：

    • dp[..][0] = true：背包容量为 0，总能装满；
    • dp[0][nums[0]] = true：只有一个数且恰好等于容量；

  • 剪枝条件：

    • 若 sum 为奇数，直接返回 false；
    • 若某元素大于 sum / 2，可提前跳过。

• 二维数组实现

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

func canPartition(nums []int) bool {
    sum := 0
    for _, num := range nums {
        sum += num
    }
    if sum%2 != 0 {
        return false
    }
    target := sum / 2
    N := len(nums)

    dp := make([][]bool, N)
    for i := range dp {
        dp[i] = make([]bool, target+1)
    }

    for i := 0; i < N; i++ {
        dp[i][0] = true
    }
    if nums[0] <= target {
        dp[0][nums[0]] = true
    }

    for i := 1; i < N; i++ {
        for j := 1; j <= target; j++ {
            if j < nums[i] {
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i]]
            }
        }
    }

    return dp[N-1][target]
}

• 状态压缩：一维优化版本（倒序）

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

func canPartition(nums []int) bool {
    sum := 0
    for _, num := range nums {
        sum += num
    }
    if sum%2 != 0 {
        return false
    }
    target := sum / 2

    dp := make([]bool, target+1)
    dp[0] = true

    for _, num := range nums {
        for j := target; j >= num; j-- {
            dp[j] = dp[j] || dp[j - num]
        }
    }

    return dp[target]
}

完全背包问题（Unbounded Knapsack）

• Leetcode 518. 零钱兑换 II

  • 给定一个背包容量为 amount，以及一个物品数组 coins（可重复使用），求有多少种不同的方法可以凑出该金额。

• 解题思路

  • 状态定义：dp[i][j] 表示使用前 i 种硬币，凑出金额 j 的方法数。

  • 状态转移：

    1 2 3 4

    if j < coins[i-1]: dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]]

  • 初始化：

    • dp[0][..] = 0：没有硬币无法组成正金额；
    • dp[..][0] = 1：金额为 0，只有 1 种凑法（什么都不选）。

• 二维数组实现

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

func change(amount int, coins []int) int {
    n := len(coins)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, amount+1)
        dp[i][0] = 1
    }

    for i := 1; i <= n; i++ {
        for j := 0; j <= amount; j++ {
            if j < coins[i-1] {
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]]
            }
        }
    }
    return dp[n][amount]
}

• 一维数组优化（正序遍历）

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

func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1

    for _, coin := range coins {
        for j := coin; j <= amount; j++ {
            dp[j] += dp[j - coin]
        }
    }

    return dp[amount]
}

回溯

• 适用于排列、组合、子集等构造类枚举问题

通用回溯模板总结

1. 排列（Permutation）

1.1 无重复元素 — 基础排列（46. 全排列）

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

func permute(nums []int) [][]int {
    var res [][]int
    var path []int
    used := make([]bool, len(nums))

    var dfs func()
    dfs = func() {
        if len(path) == len(nums) {
            res = append(res, append([]int(nil), path...))
            return
        }
        for i := 0; i < len(nums); i++ {
            if used[i] {
                continue
            }
            used[i] = true
            path = append(path, nums[i])
            dfs()
            path = path[:len(path)-1]
            used[i] = false
        }
    }
    dfs()
    return res
}

1.2 有重复元素 — 排列 II（47. 全排列 II）

• 相较于 46，需增加：

  • 排序以便判断相邻重复
  • 重复剪枝：跳过已访问前一个相同元素

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

func permuteUnique(nums []int) [][]int {
    sort.Ints(nums)
    var res [][]int
    var path []int
    used := make([]bool, len(nums))

    var dfs func()
    dfs = func() {
        if len(path) == len(nums) {
            res = append(res, append([]int(nil), path...))
            return
        }
        for i := 0; i < len(nums); i++ {
            if used[i] {
                continue
            }
            //只能先用同一组重复数字的“第一个”，不能先用后面的。
			//如果现在选择了后一个重复元素，就会导致重复排列。
			//!used[i-1]表明前一个相同的还没用，所以你这边就别先用了
            if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
                continue
            }
            used[i] = true
            path = append(path, nums[i])
            dfs()
            path = path[:len(path)-1]
            used[i] = false
        }
    }
    dfs()
    return res
}

2. 组合 / 子集（Combination / Subset）

本质都是选取元素的子集，区别主要在题意和输出要求。

2.1 无重复元素 — 子集 I（78. 子集）

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

func subsets(nums []int) [][]int {
    var res [][]int
    var path []int

    var dfs func(start int)
    dfs = func(start int) {
        res = append(res, append([]int(nil), path...))
        for i := start; i < len(nums); i++ {
            path = append(path, nums[i])
            dfs(i + 1)
            path = path[:len(path)-1]
        }
    }
    dfs(0)
    return res
}

2.2 有重复元素 — 子集 II（90. 子集 II）

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

func subsetsWithDup(nums []int) [][]int {
    sort.Ints(nums)
    var res [][]int
    var path []int

    var dfs func(start int)
    dfs = func(start int) {
        res = append(res, append([]int(nil), path...))
        for i := start; i < len(nums); i++ {
            if i > start && nums[i] == nums[i-1] {
                continue
            }
            path = append(path, nums[i])
            dfs(i + 1)
            path = path[:len(path)-1]
        }
    }
    dfs(0)
    return res
}

子集的另一种方式：不使用 for 循环（显式选与不选）

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

func subsetsDfs(nums []int) [][]int {
    var res [][]int
    var set []int

    var dfs func(int)
    dfs = func(cur int) {
        if cur == len(nums) {
            res = append(res, append([]int(nil), set...))
            return
        }
        // 选择当前
        set = append(set, nums[cur])
        dfs(cur + 1)
        // 撤销选择
        set = set[:len(set)-1]
        // 不选择当前
        dfs(cur + 1)
    }
    dfs(0)
    return res
}

总结要点

扩展说明

• 全局变量 vs 参数传递：

  • 全局变量：书写更简洁，多个函数共享更方便。
  • 参数传递：封装更清晰，递归状态更独立，减少副作用。

• for 循环的角色：

  • 回溯中 for 循环用于枚举“选项”。
  • 不要在 for 中处理“不选”的逻辑，不然会重复或乱序。

举例：组合总和（39. Combination Sum）

• 元素可重复使用，需遍历所有可行组合

✅ 推荐写法：for 中只做“选”的动作

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

func combinationSum(candidates []int, target int) [][]int {
    var res [][]int
    var path []int

    var dfs func(start, target int)
    dfs = func(start, target int) {
        if target == 0 {
            res = append(res, append([]int(nil), path...))
            return
        }
        for i := start; i < len(candidates); i++ {
            if target >= candidates[i] {
                path = append(path, candidates[i])
                dfs(i, target - candidates[i])
                path = path[:len(path)-1]
            }
        }
    }
    dfs(0, target)
    return res
}

🚫 不推荐写法：用“选/不选”逻辑递归（逻辑复杂，易错）

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

func combinationSum(candidates []int, target int) [][]int {
    var res [][]int
    var path []int

    var dfs func(index, target int)
    dfs = func(index, target int) {
        if target == 0 {
            res = append(res, append([]int(nil), path...))
            return
        }
        if index == len(candidates) || target < 0 {
            return
        }
        // 选当前
        path = append(path, candidates[index])
        dfs(index, target - candidates[index])
        path = path[:len(path)-1]
        // 不选当前
        dfs(index + 1, target)
    }
    dfs(0, target)
    return res
}

DFS 模板的两种核心模式

模式一：组合型问题（需 for 循环）

• 子集、组合、排列等
• 每一步从当前位置开始向后枚举选项

1
2
3
4
5

for i := start; i < len(nums); i++ {
    path = append(path, nums[i])
    dfs(i + 1)
    path = path[:len(path)-1]
}

模式二：构造型问题（不需 for 循环）

• 例如：电话号码字母组合、迷宫路径、树遍历等
• 每层只能处理一个“位置”的合法选项，当前层不枚举后面

示例：17. 电话号码的字母组合

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

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }
    phoneMap := map[rune]string{
        '2': "abc", '3': "def", '4': "ghi", '5': "jkl",
        '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz",
    }
    var res []string
    var dfs func(index int, str string)
    dfs = func(index int, str string) {
        if index == len(digits) {
            res = append(res, str)
            return
        }
        for _, ch := range phoneMap[rune(digits[index])] {
            dfs(index + 1, str + string(ch))
        }
    }
    dfs(0, "")
    return res
}

总结结构图

1
2
3
4
5

回溯问题分类
├── 排列类：顺序重要，used + path
├── 组合类：顺序不重要，start 起点控制，元素不可重复
├── 子集类：所有组合（选 or 不选）
└── 构造类：必须填满所有位置，如数字组合/字符串构造等

✅ 判断是否需要 for：是否在当前层“枚举选项”

• 有枚举（子集/组合/排列）：需要 for
• 无枚举（构造型）：不需要 for

典型问题

TopK

• 不要求有序：使用快速选择算法（基于快速排序思想）；也可以使用堆结构

• 要求有序：使用堆

  • 最大堆：用于求前 K 个最大值
  • 最小堆：用于求前 K 个最小值

快慢指针

• 19. 删除链表的倒数第 N 个节点
  快指针先走 N 步，然后快慢指针一起前进，快指针到达末尾时，慢指针刚好指向待删除节点的前一个节点
• 141. 环形链表
  快慢指针，快指针每次走两步，慢指针每次走一步；若存在环，两者最终会相遇
• 142. 环形链表 II
  快慢指针相遇后，快指针从头开始，慢指针继续前进；再次相遇点即为入环点
• 234. 回文链表
  快慢指针找到链表中点，同时将前半部分链表原地反转；再从中点与反转后的链表逐一比较，判断是否回文
• 287. 寻找重复数
  使用 Floyd 判圈算法，将数组视为链表结构；第一次快慢指针相遇后，将其中一个指针重新指向起点，两个指针再次相遇时即为重复数字（环的入口）

双指针

• 160. 相交链表
  两指针分别从两个链表头出发，走到末尾后切换至对方链表头继续走；若相交，则最终会在交点相遇；若无交点，则会同时为 null 结束

经典题目

缓存

• 146. LRU 缓存（HashMap + 双向链表）

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

  type LRUCache struct { data map[int]*LinkedNode head *LinkedNode tail *LinkedNode count int capacity int } type LinkedNode struct { key int val int pre *LinkedNode next *LinkedNode }

  • data: 使用 HashMap 存储 key 与节点指针的映射
  • 双向链表: 头部表示最近访问节点，新加入或访问的节点会被移动到头部，尾部为最久未使用节点，便于淘汰

• 460. LFU 缓存（双 Hash + 双向链表）

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

  type LFUCache struct { keyToValFreq map[int]*LFUNode freqToKeysHead map[int]*LFUNode freqToKeysTail map[int]*LFUNode minFreq int capacity int size int } type LFUNode struct { key int val int freq int pre *LFUNode next *LFUNode }

  • keyToValFreq: 记录每个 key 的值和频率
  • freqToKeys: 按照频率映射到对应频率的链表（内部按 LRU 顺序）
  • minFreq: 当前缓存中的最小访问频率
  • 注意 put 操作中若 key 已存在，需要更新其值和频率！

打家劫舍

• 198. 打家劫舍（相邻房屋不能偷）

  • 动态规划
  • dp[i] 表示前 i 间房屋能偷到的最大金额
  • 状态转移方程：dp[i] = max(dp[i-2] + nums[i], dp[i-1])

• 213. 打家劫舍 II（房屋围成一圈）

  • 环状结构，首尾不能同时选择
  • 拆分为两种情况：(0, n-2) 和 (1, n-1)，分别计算最大值，取较大者

• 2560. 打家劫舍 IV（给定偷 k 间房的条件，求最小窃取能力）

  • 题考的是：在不能偷相邻房子的条件下，选择至少 k 个房子，求所有方案中「最大金额最小」的那种偷法的最大单间金额（即窃取能力）的最小值。
  • 二分 + 贪心
  • 在 [min(nums), max(nums)] 范围内二分 x，判断是否存在方案在不相邻的前提下偷到 k 间房且每间 ≤ x
  • 最小可行的 x 即为答案

• 337. 打家劫舍 III（树形结构）

  • 二叉树结构，不能偷父子节点
  • 返回两个值：偷当前节点与不偷当前节点的最大值
  • 后序遍历递归实现

课程表

• 207. 课程表

  • 判断有向图是否存在环
  • 使用拓扑排序（Kahn 算法）
  • 若排序后的节点数 == numCourses，说明可完成全部课程

会议室

• 253. 会议室 II（计算最少需要多少间会议室）

  • 将所有会议按开始时间排序
  • 使用最小堆记录正在进行的会议的结束时间
  • 遇到新的会议时，检查是否能复用已结束的会议室
  • 最后堆的大小即为最少会议室数

• 2402. 会议室 III（找出被安排次数最多的会议室编号）（如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间 相同 ）

  • 所有会议按开始时间排序

  • 构造两个最小堆：

    • 空闲会议室（按编号）
    • 占用会议室（按结束时间 + 编号）

  • 每轮会议安排时：

    • 如果无空闲会议室，则延期
    • 记录每个会议室的使用次数

  • 最终返回使用次数最多的会议室中编号最小者

买卖股票

• 309. 最佳买卖股票时机含冷冻期

  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

  • 三种状态转移：

    • f[i][0]: 第 i 天持有股票
    • f[i][1]: 第 i 天卖出股票（进入冷冻期）
    • f[i][2]: 第 i 天未持股（非冷冻期）

  • 状态转移方程：

    • f[i][0] = max(f[i-1][0], f[i-1][2] - prices[i])
    • f[i][1] = f[i-1][0] + prices[i]
    • f[i][2] = max(f[i-1][1], f[i-1][2])

  • 最终答案：max(f[n-1][1], f[n-1][2])

高楼扔鸡蛋

• 887. 鸡蛋掉落

  • 给定 k 个鸡蛋和 n 层楼，找出确定临界楼层所需的最少操作次数（最坏情况下）

  • 定义：f(t, k) 表示在最多尝试 t 次、拥有 k 个鸡蛋的情况下，最多能测试的楼层数

    • 转移方程：f(t, k) = 1 + f(t-1, k-1) + f(t-1, k)

  • 最终寻找最小的 t，使得 f(t, k) >= n

  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

  func superEggDrop(k int, n int) int { ans := math.MaxInt32 dp := make([][]int, n+1) for i := 1; i <= n; i++ { dp[i] = make([]int, k+1) } for i := 1; i <= n; i++ { dp[i][1] = i } for j := 1; j <= k; j++ { dp[1][j] = 1 } if n == 1 { return 1 } i := 2 for i <= n { for j := 1; j <= k; j++ { dp[i][j] = 1 + dp[i-1][j-1] + dp[i-1][j] } if dp[i][k] >= n { ans = i break } i++ } return ans }

后记

• 学习总被寄予理解的希望，现实却常逼我们回归重复与记忆的路径。掌握技巧、熟悉模板，也许并不光鲜，却是应对复杂世界最有效的方式之一。
• 然而熟练，何尝不是另一种形式的“背”呢。

AI – “基于数据的规律发现系统”

• “人工智能（AI）”这个名字，其实是一种历史性命名，也是一种拟人化的表达。它给人一种错觉，仿佛机器在模仿或复制人类的智能。然而，从技术本质上看，今天的人工智能主要依赖于数据驱动的模式识别和规律学习，更准确地说，它是一种“基于数据的规律发现系统”。无论是人类还是机器，学习的对象都是客观存在的规律，只是各自的方法不同。规律本身并不依赖于学习者，它们存在于自然和社会系统之中，等待被发现。机器学习的意义，不在于赋予机器“像人一样的智能”，而在于它可以在极大规模和复杂度下识别人类难以企及的模式，这种能力甚至在某些领域已经超越了人类。然而，AI虽能拟合规律，却不具备理解、动机和意识，因此我们说它“智能”仍属工程性描述，而非哲学意义上的智能。从这个角度看，“人工智能”这一术语在一定程度上是误导性的，如果要更准确地描述其本质，也许“规律学习系统”或“模式发现机器”更贴切，但这类表述在传播和产业化上显然不如“AI”简洁有力。因此，当前的术语是一种权衡：技术准确性让位于传播效率。我们需要清醒地认识到，AI不是在“思考”，它只是以统计和优化的方式，从数据中提取规律，并按特定目标进行预测或生成。

附录

AI这个名字其实并不准确
人工智能
其实是通过数据来学习规律
跟人没有关系
只是人或机器用他们的方式去学习，
不管你人类或机器学不学习
规律就在那里，只是表现形式不一样，但规律的本质是一样的，
而且有些规律人类也学不会，超过人的能力
所以叫人工智能是片面的表达
应该叫智能规律，或规律学习？


——

当然，以下是对原文的整理和简要总结：

⸻

整理后的表达：

“人工智能（AI）”这个名称其实并不准确。所谓人工智能，本质上只是通过数据来学习和提取规律的过程，与人类的思维或意识没有直接关系。无论是人还是机器，学习的只是客观存在的规律，而这些规律本身独立于学习主体，始终存在，只是表现形式不同而已。

机器和人只是用不同的方式去接近这些规律，有些规律甚至超出了人类的认知能力，只有机器才能捕捉到。因此，用“人工智能”来命名这种技术是片面的，更准确的表达也许应该是“智能规律”或“规律学习”。

⸻

简要总结观点：

这段文字认为，“人工智能”这一术语带有误导性，因为它强调了“人”而忽略了技术的本质：对客观规律的学习和拟合。作者主张，AI其实是一种“规律学习”系统，不应被简单等同于模仿人类智能。

近期帮朋友做一个需求，需要将某个Rust项目的一部分功能移植到Java中，使Java应用能使用

方案1: 直接将Rust翻译成Java代码

前置准备：将Rust项目跑通，方便通过debug对照执行细节，从而一步步翻译成Java代码
希望借助AI的力量帮忙完成

• 借助AI的方案如下：
  • 首先，我已经跑通了需要抽取的功能的相关测试用例
  • 然后，让AI帮忙将涉及这些功能相关的代码抽取成单独的Rust项目（结果还是很乱七八糟）
  • 大概是因为上下文内容太多的关系，AI执行任务的效果很差
  • 没办法，于是自己拆分代码，让AI软件帮忙根据代码块逐个进行转化，结果效果是好了很多，能帮助不少，不过这样效率太低，而且AI有时候也经常出错，需要自己慢慢调整
  • 看来AI目前在一次性的转化大量代码的效率和准确性还是不够
  • 本次程序员该懒就懒的宗旨，我决定另辟蹊径，采用方案2

方案2: 直接将相关功能的Rust功能编译成动态库，由Java直接调用

省去翻译代码的重复工作
需要构建不同平台的动态库
Java代码在加载前需要判断环境加载相应的动态库
使用Github Action来构建各种平台的动态库
Java端充分测试，Java8应用测试，Java9以上模块化系统是否可用测试，Windows等其他平台测试

以下由AI（ChatGPT）帮我完成的文章

使用Java调用Rust构建的动态库

引言

在最近的一个项目中，我需要将一个Rust项目中的部分功能迁移到Java应用中，供Java系统调用。为了简化过程，我决定绕过将Rust代码完全转化为Java的复杂任务，而是直接通过Rust构建动态库，再通过Java来调用。这种方法不仅减少了代码转换的工作量，还利用了Rust的高性能特点，提高了Java应用的效率。

方案1: 直接将Rust翻译成Java代码

前置准备

为了开始这个过程，我首先确保了Rust项目能够成功运行，并且通过调试工具逐步分析每个功能的执行细节。这是为了确保我可以一步步将Rust的实现逻辑转化为Java代码。

使用AI进行代码转换

最初，我尝试借助AI工具自动化地将Rust代码转换为Java代码。以下是我使用AI进行代码转换的过程：

• 我首先跑通了相关的测试用例，确保所有需要移植的功能都能正常工作。
• 然后，我让AI帮助抽取与这些功能相关的Rust代码，并转化成单独的Rust项目。但由于上下文过多，AI的效果并不理想，生成的代码混乱且不完整。
• 之后，我将代码拆分成更小的部分，让AI逐一处理，虽然效果有所改善，但这种方式依旧效率低下，且AI经常会出错，导致我不得不花大量时间修正。

这一过程中，我意识到AI在一次性大规模转化代码时的准确性和效率仍然有待提升。最终，我决定放弃这条路，转而尝试另一种更直接的方案——方案2。

方案2: 直接将Rust功能编译成动态库，由Java调用

思路与优势

与其将Rust代码翻译成Java代码，我决定直接将Rust的功能编译成动态库（.dll 或 .so），然后在Java中通过JNI（Java Native Interface）调用这些动态库。这样可以避免代码翻译过程中的麻烦，并且能够充分利用Rust在性能上的优势。

构建Rust动态库

在实现这一方案时，我需要做以下几个步骤：

1. 编译Rust代码为动态库：通过Rust的cargo工具，将Rust代码编译成适用于不同平台的动态库。这需要为每个平台生成相应的二进制文件，如Windows下的.dll，Linux下的.so，以及MacOS下的.dylib。

2. 使用Github Actions自动化构建：为了支持多平台的动态库构建，我使用了Github Actions来自动化构建过程。这样，无论是Windows、Linux还是MacOS，都会根据需要自动生成对应的动态库，极大地简化了跨平台的构建工作。

3. Java端加载动态库：Java通过JNI加载Rust编译出的动态库，并调用其中的函数。在加载时，Java代码会先检测当前运行环境，根据操作系统加载相应的库文件。

4. 平台兼容性测试：为了确保Java能够顺利调用Rust动态库，我在多个平台上进行了充分的测试。这包括：

   • 在Java 8环境下进行功能测试。
   • 验证在Java 9及以上版本的模块化系统下，Java与Rust动态库的兼容性。
   • 测试在Windows、Linux和MacOS等不同平台下的表现。

方案优势

• 减少工作量：不需要将Rust代码完全翻译为Java代码，避免了翻译过程中的复杂性和错误。
• 高效的性能：Rust的性能优势得以保留，Java通过调用Rust动态库，可以在性能上得到显著提升。
• 跨平台支持：通过自动化构建不同平台的动态库，Java应用能够轻松支持Windows、Linux、MacOS等多种操作系统。

总结

通过将Rust功能编译成动态库并在Java中调用，我成功地绕过了将Rust代码完全转化为Java的复杂过程，同时还能够充分利用Rust的性能优势。虽然在构建过程中涉及到平台适配和自动化构建，但这一方案的灵活性和高效性使其成为解决问题的最佳选择。对于有类似需求的开发者来说，这无疑是一个值得尝试的方案。

帮助朋友的公司搭建内部知识库的原型
简单记录一下相关技术

• 目前看权限管理都很不精细，只在固定角色上进行控制，用于内部团队管理仍不是很方便

• 文档嵌入效果一般，可能要研究里面一些复杂的选项用法，或者寻求其他方案

• 除了dify，还有很多其他开源的知识库系统，比如 Cherry Studio、MaxKB、FastGPT、AnythingLLM、Ragflow等

• dify功能很多，anythingllm功能较少，Cherry Studio 就是个人知识库

• 所谓的各种助手其实就是提示词模版

扩展

• 传统RAG通常依赖单次检索，这可能不足以处理需要逐步构建上下文的复杂查询
• 向量相似性检索依赖知识库中明确提及的信息，可能无法捕捉隐含或关系信息。相比之下，知识图谱（如GraphRAG）通过利用数据结构中的关系，能更好地处理需要全面理解数据集的全局查询

网上资料摘要
一些个人理解

大模型交互的核心：提示词工程

以下基于个人理解，并通过claude优化（2025-02-26）

• 提示词（Prompt）是大模型的输入，也是调用大模型能力的接口，用以激发或引导大模型生成特定类型的回答。
• 提示词工程的目的是尽量把任务说清楚，让大模型能充分理解我们的意图，以按照正确的方向回答问题。
• 在不微调大模型的情况下，外部与大模型交互的唯一途径就是提示工程。即便是已经微调过的大模型，后续与其沟通的唯一途径仍是通过提供提示词，尽管微调可能改变模型对提示词的响应方式。
• 所谓的RAG、短期记忆（对话历史）、长期记忆等功能，都是基于提示工程这一与大模型交互的路径作为切入点，建立的其他优化策略和架构。

ICIO框架（Prompt包含的要素）

• 从原理出发 - 提示词如何影响大模型的输出
• 核心思想，是通过明确定义任务的各个方面，来提高AI响应时的效率和准确性。
• 在ICIO的框架的设计中，Prompt可能包含四要素：
  • Instruction（指令）：这是最重要的部分，它直接告诉模型需要执行的具体任务。
  • Context（上下文/背景）：上下文提供了任务执行所需的背景信息，帮助模型理解任务的情景和环境。
  • Input Data（输入数据）：输入数据是模型需要处理的具体信息。
  • Output Indicator（输出指示器）：输出指示器告诉模型用户期望的输出类型或格式。
• 其中除了指令以外，其他要素都是可选的，说明指令对于大模型来说是最重要的，其他要素都是对指令的补充。
• 优质的Prompt，可以清晰地传达用户的意图

Prompt五大框架

• 大模型Prompt技巧全解析
• RTF框架
  • R-Role(角色)、R-Role(角色)、F-Format(格式)
• 思考链模式
  • 适合一些复杂的任务处理
  • 要使用这种模式，只需要在末尾添加”让我们逐步思考”即可
• RISEN框架
  • R-Role:大模型扮演的角色
  • I-Instructions: 指示命令，和Task-任务差不多
  • S-Steps: 步骤
  • E-End Goal: 最终目标
  • N-Narrowing(Constraints): 缩小范围(约束条件)，和RTF框架中的Format有异曲同工之妙
  • 该框架主要适合
    • 撰写具有特定约束的任务(例如博客文章)
    • 有明确指导方针的任务（例如商业计划）
• RODES框架
  • R-Role: 角色、O - Objective: 目标、D - Details: 详细的细节、E - Examples: 示例、S - Sense Check: 感官检查
• 密度链模式
  • 使用递归来创建越来越好的输出的提示，与普通提示生成的 GPT-4 摘要相比，它生成的摘要更加密集且更适合人们理解
  • 适合：总结、改进您最喜欢的提示、通过递归生成可用的长格式内容

打造高效Prompt的两大核心原则

• 大模型Prompt技巧全解析
• 原则一：编写明确和具体的指令
  • 策略1：使用分隔符清晰界定输入部分
  • 策略2：要求结构化输出
  • 策略3：要求模型检查条件是否满足
  • 策略4：Few-shot prompting（少样本提示）
• 原则二：给予模型充足的思考时间
  • 策略1：明确完成任务所需的步骤
  • 策略2：引导模型在得出结论前充分思考方案

Prompt技术剖析与应用

• 大模型Prompt技巧全解析
• 一、零样本提示（Zero-Shot Prompting）
• 二、少样本提示（Few-Shot Prompting）
  • 在零样本提示效果不佳时发挥作用
• 三、思维链提示（Chain-of-Thought Prompting）
  • 与少样本提示结合，增强效果，尤其适用于算术、常识推理等任务，帮助模型更有条理地处理问题
• 四、自我一致性（Self-Consistency）
  • 主要用于优化思维链提示中的推理路径选择
  • 核心思想是通过提供多个少样本推理示例，让模型从多样的推理结果中筛选出最一致的答案，增强模型在算术和常识推理任务中的可靠性
• 五、生成知识提示（Generated Knowledge Prompting）
  • 主要用于解决模型在处理需要额外知识的任务时出现的局限性
  • 个人理解：一种特殊的RAG罢了
• 六、链式提示（Prompt Chaining）
  • 将复杂任务拆解为多个子任务，通过逐个子任务生成提示并传递结果的方式来实现复杂任务的有序处理
• 七、思维树（ToT）
  • 为了帮助模型应对复杂的探索性任务而设计
  • 通过维护一棵思维树，让模型在解决问题时能够生成和评估中间思维步骤，并结合搜索算法进行系统性探索
• 八、检索增强生成（RAG）
  • 将信息检索与文本生成相结合，专门用于处理知识密集型任务
  • 通过检索相关文档来为模型提供额外的知识支持，从而缓解模型的“幻觉”问题
• 九、自动推理并使用工具（ART）
  • 使模型能够自动生成包含推理步骤的程序，并在需要时调用外部工具
• 十、自动提示工程师（APE）
  • 自动生成和筛选任务指令
  • 利用大型语言模型生成指令候选项，再依据评估分数选择最佳指令，从而提升提示生成的效率与效果
• 十一、Active-Prompt
  • 用于解决思维链示例有效性的问题
  • 通过先查询模型生成多个答案，计算不确定度后挑选最不确定的问题由人类注释示例，再用新示例推断其他问题，从而优化模型对不同任务的适应性
• 十二、方向性刺激提示（Directional Stimulus Prompting）
  • 通过训练策略 LM 生成引导提示，增强对模型生成结果的掌控力。例如文本摘要任务
• 十三、PAL（程序辅助语言模型）
  • 让模型生成程序来解决问题，借助编程运行时提升解决复杂问题的能力
• 十四、ReAct 框架
  • ReAct 框架使模型交错生成推理轨迹和操作，提升答案的可靠性与可解释性
• 十五、自我反思（Reflexion）
  • 包含参与者、评估者和自我反思三个模型，旨在帮助模型从错误中学习并提升性能

Reference

• 从原理出发 - 提示词如何影响大模型的输出
  • 大模型如何理解Prompt
    • 基于Transformer的解码器的大模型
    • 最核心的两层
      • 掩码多头自注意力层（Masked Multi Self Attention Layers，对应Transformer的Masked Multi-Head Attention，简称MHA）
      • 前置反馈网络层（Feed Forward Networks Layers，简称FFN）
    • Prompt会影响自注意力层对上下文信息的捕捉
    • 自注意力机制
      • 它的核心思想是模仿人类的注意力，即在处理大量信息时，能够聚焦于当前任务最相关的部分，而忽略其他不太重要的信息
• 大模型Prompt技巧全解析
• LLM相关技术简单了解
• 大型语言模型的提示注入
  • 三种防范此类漏洞的方法
    • 可以在提示中添加指令
    • 使用对抗性探测器添加第二层保护
    • 对模型进行微调，使其更符合用户需求，同时提供最高级别的保护，防止提示注入和窃取

基于书籍简单记录要点

• 从L3到L4的跨越是一个从被动到自主的分水岭，在这个跨越过程中，Agent将成为关键的驱动力

Reference

• 《大模型应用开发 动手做AI Agent》
• AIGC生成式人工智能的五个进阶层次
• AIGC：生成式人工智能的5个层次
• 2024年大模型Multi-agent多智能体应用技术：AutoGen, MetaGPT, XAgent, AutoAgents，crewAI