拉巴力的纸皮箱


  • 首页

  • 标签

  • 归档

  • 关于

  • 搜索

刷leetcode总结的算法基础和套路

发表于 2025-07-09

最近重新刷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.Val 替换 root.Val;
    • 但此时右子树中仍存在原来的 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
29
30
31
32
33
34
func deleteNode(root *TreeNode, key int) *TreeNode {
if root == nil {
return nil
}

if key < root.Val {
root.Left = deleteNode(root.Left, key)
} else if key > root.Val {
root.Right = deleteNode(root.Right, key)
} else {
// 找到要删除的节点
if root.Left == nil {
return root.Right
}
if root.Right == nil {
return root.Left
}

// 情况4:左右子树都有
successor := findMin(root.Right)
root.Val = successor.Val // 用 successor 的值替换当前节点
root.Right = deleteNode(root.Right, successor.Val) // 递归删除 successor
}

return root
}

// 找最小值节点(即最左侧节点)
func findMin(node *TreeNode) *TreeNode {
for node.Left != nil {
node = node.Left
}
return node
}
  • 在这种“值替换 + 递归删除”的处理方式中:

    • 当前节点 root 并未被物理删除,而是通过值替换实现“变身”;
    • 真正被删除的是 successor 节点对象。
  • 这种策略的优点是:

    1. 不需要修改复杂的指针或维护父节点信息;
    2. 删除 successor 只涉及右子树,逻辑简单;
    3. 最终仍保持 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
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
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

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
parent := root

// 找 successor,并记录其父节点
for successor.Left != nil {
parent = successor
successor = successor.Left
}

// 删除 successor 节点
if parent != root {
// successor 没有左孩子,可能有右孩子;
// 将 parent.Left 指向 successor 的右子树
parent.Left = successor.Right
// successor 接管原 root 的右子树
successor.Right = root.Right
}

// 若 successor 就是 root.Right(即 parent == root)
// 只需令 successor.Left 指向 root.Left
successor.Left = root.Left

// 返回 successor 作为新的子树根
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[] 示意如下:
下标(i) bit[i] 表示的区间
1 2 sum(1)
2 1 sum(1..2)
3 0 sum(3)
4 3 sum(1..4)
5 0 sum(5)
6 0 sum(5..6)
7 0 sum(7)
8 ? sum(1..8)
  • 查询 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 的点 一层一层,按邻接点
使用数据结构 队列(Queue) 队列(Queue)
访问顺序 所有无依赖的点先访问 当前点的所有邻居先访问
主要用途 拓扑排序 / 检测环 遍历所有可达节点

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,即为最小满足条件的位置

跳跃游戏

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

  • 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
      }

排序

冒泡排序

  • 相邻元素两两比较并交换,使用双重循环;
  • 若某次遍历中未发生任何交换,说明数组已有序,可提前结束;
  • 代码示例:
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 函数中需确保越界处理、优先选择较大子节点交换;

动态规划(Dynamic Programming)

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

    • 常见的穷举方式有两种:回溯算法和动态规划。回溯是暴力尝试每种可能,动态规划则利用状态转移方程推导各个状态。
    • 动态规划相比暴力穷举更高效,其核心优势在于:利用状态转移 + 记忆,消除重复计算的子问题(重叠子问题)。
  • 动态规划问题通常具有大量重叠子问题,直接穷举效率极低,因此需借助以下两种优化方式:

    • 使用 备忘录(记忆化递归) 或 DP table(递推表格) 来避免重复计算;
    • 其中,记忆化递归为自顶向下,DP table 为自底向上。
  • 动态规划 = 穷举 + 剪枝

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

    1. 明确“状态”和“选择”;
    2. 定义 dp 数组或函数的含义;
    3. 写出状态转移方程(递推关系)。
  • 常通过状态压缩优化空间复杂度,例如将 O(N^2) 降为 O(N)。

背包问题(Knapsack)

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]
}

回溯

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

通用回溯模板总结

题型 递归参数 关键点 重复处理策略 代码模板示例(Go 伪码简化)
排列(Permutation) 无需起点 需要标记已使用元素 used[] 排序 + used + 跳过相邻重复元素 见 排列 II 模板
组合 / 子集(Combination / Subset) 需要起点 控制遍历起点,防止重复使用前面元素 排序 + 跳过同层相邻重复元素 见 组合 II / 子集 II 模板

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
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
}
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
}

总结要点

特征 排列(Permutation) 组合 / 子集(Combination / Subset)
是否用 used 是 否(一般)
是否排序 有重复元素时必须排序 同左
是否有起点参数 无需(但可选) 必须有,通常为 start
去重策略 i > 0 && nums[i]==nums[i-1] && !used[i-1] i > start && nums[i]==nums[i-1] 跳过
递归形式 dfs() / dfs(index) dfs(start int)

扩展说明

  • 全局变量 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 间房的条件,求最小窃取能力)

    • 二分 + 贪心
    • 在 [min(nums), max(nums)] 范围内二分 x,判断是否存在方案在不相邻的前提下偷到 k 间房且每间 ≤ x
    • 最小可行的 x 即为答案
  • 337. 打家劫舍 III(树形结构)

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

课程表

  • 207. 课程表

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

会议室

  • 253. 会议室 II(计算最少需要多少间会议室)

    • 将所有会议按开始时间排序
    • 使用最小堆记录正在进行的会议的结束时间
    • 遇到新的会议时,检查是否能复用已结束的会议室
    • 最后堆的大小即为最少会议室数
  • 2402. 会议室 III(找出被安排次数最多的会议室编号)

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

    • 构造两个最小堆:

      • 空闲会议室(按编号)
      • 占用会议室(按结束时间 + 编号)
    • 每轮会议安排时:

      • 如果无空闲会议室,则延期
      • 记录每个会议室的使用次数
    • 最终返回使用次数最多的会议室中编号最小者

买卖股票

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

    • 三种状态转移:

      • 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本质的反思

发表于 2025-05-31

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

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

附录

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


——

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

⸻

整理后的表达:

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

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

⸻

简要总结观点:

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

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

发表于 2025-03-23

近期帮朋友做一个需求,需要将某个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的性能优势。虽然在构建过程中涉及到平台适配和自动化构建,但这一方案的灵活性和高效性使其成为解决问题的最佳选择。对于有类似需求的开发者来说,这无疑是一个值得尝试的方案。

开源知识库系统试用

发表于 2025-02-26

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

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

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

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

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

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

扩展

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

关于大模型的Prompt

发表于 2025-02-25

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

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

以下基于个人理解,并通过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相关技术简单了解
  • 大型语言模型的提示注入
    • 三种防范此类漏洞的方法
      • 可以在提示中添加指令
      • 使用对抗性探测器添加第二层保护
      • 对模型进行微调,使其更符合用户需求,同时提供最高级别的保护,防止提示注入和窃取

大模型应用开发AI Agent要点记录

发表于 2025-02-21

基于书籍简单记录要点

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


Reference

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

基于大模型的RAG应用开发要点记录

发表于 2025-02-20

基于书籍简单记录要点


  • 一种借助“外挂”的提示工程

  • 最核心的思想:给大模型补充外部知识以提高生成质量

  • 大模型的 RAG 应用中,最常见的检索方式是借助基于向量的语义检索来获得相关的数据块,并根据其相似度排序,最后输出最相关的前 K 个数据块(简称top_K)

  • 自然语言处理中用于把各种形式的信息转换成向量表示的模型叫嵌入模型

  • 基于向量的语义检索就是通过计算查询词与已有信息向量的相似度(如余弦相似度),找出与查询词在语义上最接近的信息。

  • 如果大模型是一个优秀学生,正在参加一门考试,那么 RAG 和微调的区别如下。

    • RAG:在考试时给他提供某个领域的参考书,要求他现学现用,并给出答案。
    • 微调:在考试前一天对他进行辅导,使他成为某个领域的专家,然后让他参加考试。
  • 大模型与 Prompt 并不只在最后生成结果时才需要,在 RAG 应用流程的很多阶段都需要用到它们,比如在生成摘要、查询转换、查询路由、智能体推理、响应评估等很多阶段,都需要利用设计的Prompt 来让大模型完成任务。

  • 与查询引擎相关的几个关键组件如下。

    • (1)VectorIndexRetriever:向量索引检索器。用于完成相关知识的检索,基于索引来完成,输出多个相关 Node。
    • (2)Synthesizer:响应生成器。借助大模型来完成 Prompt 组装,并根据响应生成模式的要求来生成响应结果。
    • (3)NodePostProcessor:节点后处理器。通常用于在检索完成之后,对检索器输出的 Node 列表做补充处理,比如重排序。
  • Agent 就是通过 AI 模型驱动,能够自主地理解、规划、执行,并最终完成任务的 AI 程序。Agent 与大模型的区别类似于人与大脑的区别:大脑指挥人的行动,但是只有人才是执行任务的完整体。

  • Agent 就是在大模型作为智慧大脑的基础上实现记忆(Memory)、自我规划(Planning)、使用工具(Tool)等能力,从而开发一个具有自主认知与行动能力的完全“智能体”。

  • 与 RAG 应用相比,Data Agent 具备以下能力。

    • (1)兼具 RAG 应用的数据检索与查询生成能力。
    • (2)通过观察环境与任务目标推理出完成下一个数据任务的步骤。
    • (3)通过调用外部服务工具(API)完成复杂任务,并返回执行结果。
    • (4)具备长期记忆能力(如使用向量库)与短期记忆(一次任务中的交互历史等)能力。
  • 与 RAG 应用相比,Data Agent 的主要增强之处如下。

    • (1)规划与推理出完成任务的步骤的能力。
    • (2)定义与使用工具的能力。

LlamaIndex 框架整体结构

  • (1)Core Framework:这是 LlamaIndex 的核心框架,实现了 LlamaIndex 框 架中大量可扩展的基础组件与工具组件。
  • (2)Integrations:这是在 Core Framework 基础上由官方或者第三方提供的 大量扩展组件。这些组件大大扩充了 LlamaIndex 框架的兼容能力与应用场景, 包括各种类型的数据加载器、大语言模型与嵌入模型、向量库、Agent 工具等。
  • (3)Templates:这是官方或者第三方提供的更上层的应用模板。开发者可 以基于这些模板来修改和开发自己的应用。
  • (4)Eval Datasets:评估数据集。这是一些用于测试评估的现成数据集。 一个数据集通常包含两个部分:一部分是用于开发 RAG 应用的原始知识数据 集;另一部分是用于评估 RAG 应用的测试数据集。

LlamaIndex 的向量存储索引和传统数据库(如 MySQL)的索引的区别

  • From Grok3 (2025-02-24)

传统数据库索引(如 MySQL) vs 向量存储索引

1. 传统数据库索引(B-树、哈希索引等)

  • 目的:加速精确匹配或范围查询,比如在 WHERE id = 5 或 WHERE age > 30 时快速定位数据。
  • 数据结构:通常基于 B-树、B+树 或哈希表,存储的是原始数据(如整数、字符串)的某种排序或映射。
  • 存储内容:索引本身不保存完整数据,而是指向数据库中实际数据的引用(行指针)。
  • 使用场景:结构化数据的高效检索。

2. LlamaIndex 的向量存储索引

  • 目的:支持语义相似性搜索,比如找到与“人工智能是什么”语义最接近的文档。
  • 数据结构:基于向量空间的高效搜索结构(如 FAISS、HNSW、Annoy),存储的是文本的嵌入向量(高维浮点数数组)。
  • 存储内容:索引里直接保存的是嵌入向量(通常还会关联原始文本或其引用),而不仅仅是指针。这种嵌入向量本身就是数据的某种“表示”。
  • 使用场景:非结构化数据(如文本、图像)的语义搜索。

所以你说得对,向量存储索引和 MySQL 的索引在设计目标和实现上完全不同。传统索引是为了快速定位具体值,而向量存储索引是为了快速找到“最相似”的内容。

为什么叫“向量存储索引”而不是“向量存储数据”?

  • “索引”在这里的含义:

    • 在向量搜索领域,“索引”指的是一个经过优化的数据结构,用于加速向量之间的相似性计算和检索。它不只是存数据,而是以某种方式组织数据(比如 FAISS 用聚类或倒排索引),让查询效率更高。
    • 比如 FAISS 可能会把向量分桶(clustering),HNSW 用图结构连接向量,这些都是“索引”的体现。
  • 为什么不叫“向量存储数据”:

    • “数据”听起来像是原始的、未经组织的存储,比如直接把向量一股脑扔进数据库。而“索引”强调的是结构化和查询优化。
    • LlamaIndex 的向量存储索引不仅存了向量,还为快速检索做了预处理(比如降维、构建树或图)。它是个功能性工具,而不仅是数据的容器。
  • 命名习惯:

    • 在向量搜索和机器学习领域,像 FAISS、Annoy、HNSW 这些工具都叫“索引”(index),因为它们的核心是构建一个可搜索的结构。LlamaIndex 沿用了这种惯例。

举个类比

  • MySQL 的 B-树索引就像图书馆的卡片目录,按书名首字母排序,帮你快速找到某本书。
  • LlamaIndex 的向量存储索引更像是推荐系统,根据你喜欢的书,找到内容相似的其他书,靠的是“向量空间的距离”而不是精确匹配。

总结

LlamaIndex 的向量存储索引确实和 MySQL 的索引差别很大,它更像是一个专门为高维向量设计的“搜索加速器”。叫“索引”是因为它不仅存向量,还组织向量以提升查询效率,而不是简单的数据存储。


关于RAG的优化:个人结合深度强化学习的思考

  • 对于RAG应用,优化方法有很多。我的想法是,把这些优化方法想象成一堆‘工具’,然后用强化学习这个‘聪明助手’来挑出最好用的组合。

  • “优化策略”变成了“工具”,“强化学习”变成了“聪明助手”,“奖励函数”简化为“任务需求”

  • From ChatGPT

  • 你表达的意思可以理解为:你试图用一个类比来形象地说明深度强化学习在RAG(Retrieval-Augmented Generation)系统优化中的角色与价值。

  • 具体地说:

    • RAG优化方法很多,比如检索器选择、reranker排序、embedding优化、prompt设计等,这些在你眼中就像一堆**“工具”**。
    • 这些工具的使用方式组合非常多,所以你不想手动去调优,而是引入一个“聪明助手”——也就是强化学习智能体,来自动地组合和选择最合适的优化策略。
    • 任务需求(比如更高的准确率、更好的用户体验)就变成了强化学习中的奖励函数,引导智能体不断试错、学习,找到最优解法。
  • 所以你的思路是用深度强化学习作为一种元优化方法,来学习在不同场景下该怎么调配RAG的各类优化手段,从而达到最好的表现。

  • 这是一个很有潜力的方向,本质上是将强化学习用作策略搜索或控制器,帮助系统自动适配复杂环境下的参数和策略组合。你可以进一步细化这个设想,比如:

    • 工具组合的action space怎么定义?
    • 每种任务需求下的reward如何设计?
    • 环境如何模拟或构建,才能训练出泛化能力强的“助手”?

扩展

如果嵌入模型知道“你好”和“再见”的向量,它可以将“你好再见”转化为一个向量吗?

  • From Grok3 (2025-02-25)
  • 嵌入模型可以将“你好再见”转化为向量。
  • 对于词嵌入模型(如 Word2Vec 或 GloVe),通常通过平均或相加“你好”和“再见”的向量来生成短语向量。
  • 对于句嵌入模型(如 BERT 或 Ada-002),模型可以直接处理“你好再见”序列,生成反映上下文关系的向量。

RAG的相关原理

  • From Grok3 (2025-02-25)– 基于自身理解由Grok优化

  • 文本向量化:在RAG中,知识库中的文档会被分割成适当的文本片段(例如句子或段落),然后使用预训练模型对这些片段整体进行向量化,生成语义丰富的稠密向量。这一过程不同于传统的单词嵌入,目的是捕捉整个片段的语义信息。

  • 向量检索:当用户提出问题时,系统会将问题同样向量化,并在向量数据库中查询与问题语义最相似的文本片段。这些检索结果是原始文档中的真实内容,而不是由模型生成的文本。

  • 上下文整合与生成:检索到的文本片段会以纯文本形式插入到一个提示模板中,作为上下文连同用户的问题一起输入到生成模型中。生成模型(如大语言模型)基于这些上下文生成最终的回答。

其他

  • 精通RAG架构:从0到1,基于LLM+RAG构建生产级企业知识库

    • 向量数据库对比
    • 如何选择嵌入模型:https://huggingface.co/spaces/mteb/leaderboard
  • 微软推出CoRAG:通过迭代推理提升AI检索能力

    • CoRAG 的核心创新在于其动态查询重构机制。该模型不再依赖单次检索,而是根据中间推理状态迭代优化查询。这一过程确保了每个阶段检索到的信息都与上下文相关,进而逐步构建出更完整的最终答案。
  • 用 LLM 快速构建实用知识图谱

    • 如果你用图数据库来检索信息,那么这种方式被称为 GraphRAG,它是知识图谱在 RAG 中的具体应用
    • 向量相似性检索依赖于知识库中的明确提及,只有明确提到的信息才会被检索出来。而知识图谱则能通过整体数据来推理出更多信息
    • 使用 Langchain 的实验功能 LLMGraphTransformer,如果是 LlamaIndex,可以尝试它的 KnowledgeGraphIndex。
    • LLM 可以从纯文本中提取图谱信息,并将其存储到像 Neo4J 这样的数据库
  • “无”中生有:基于知识增强的RAG优化实践

    • 感觉做这个东西就是在不停找各种优化方法反复尝试看效果,而且目前还处于很乱的早起阶段
  • 微软推出的 LazyGraphRAG

    • 传统方法(如基于向量的 RAG)在处理局部化任务时表现良好,例如从特定文本片段中检索直接答案。然而,当涉及需要全面理解数据集的全局性查询时,这些方法往往难以胜任。
    • 相比之下,图支持的 RAG 系统通过利用数据结构中的关系,可以更好地解决此类更广泛的问题。然而,与图 RAG 系统相关的高索引成本,使其难以被成本敏感的场景所接受。因此,在可扩展性、经济性和质量之间实现平衡,仍然是现有技术的关键瓶颈。
    • 相比之下,图支持的 RAG 系统通过利用数据结构中的关系,可以更好地解决此类更广泛的问题。然而,与图 RAG 系统相关的高索引成本,使其难以被成本敏感的场景所接受。因此,在可扩展性、经济性和质量之间实现平衡,仍然是现有技术的关键瓶颈。
    • LazyGraphRAG 将 VectorRAG 与 GraphRAG 相结合,“同时克服了二者的各自局限性”。
  • DeepSearcher深度解读:Agentic RAG的出现,传统RAG的黄昏

    • https://github.com/zilliztech/deep-searcher
    • 所谓Agentic RAG,是一种融合智能代理(Agent)能力的RAG架构。通过动态规划、多步骤推理和自主决策机制,Agentic RAG可以在复杂任务中实现闭环的检索-加工-验证-优化
    • Agentic RAG相比传统RAG有着三大优势:
      • (1)被动响应变为主动响应;
      • (2)单次的关键词检索,升级为多轮的动态调整检索,并拥有自我修正能力;
      • (3)适用场景,从最基础的简单事实问答,升级为复杂推理、复杂报告生成等开放域任务。
    • 长期来看,Agentic RAG必定会取代传统RAG。一方面,传统RAG对需求的响应还停留在非常基础的阶段,另一方面,现实中,我们大部分的需求表达背后,都是有隐含逻辑的,并不能被一步检索到位,必须通过推理-反思-迭代-优化来对其进行拆解与反馈。
    • VS Graph RAG
      • Graph RAG主要聚焦于对存在连接关系的文档展开查询,在处理多跳类问题上表现出色。
      • 例如,当导入一部长篇小说时,它能够精准抽取各个人物之间错综复杂的关系。其运作方式是在文档导入环节,就对实体间关系进行抽取。因此,这一过程会大量消耗大模型的token资源 。
      • 而在查询阶段,不论是否是查询图中某些节点的信息,都会进行图结构的搜索,这使得这一框架不太灵活。
      • 反观Agentic RAG,它的资源消耗模式与Graph RAG恰好相反。在数据导入阶段,Agentic RAG无需执行额外特殊操作,而在回答用户提问时,才会产生较多大模型的token消耗。
  • 高阶RAG技巧:探索提升RAG系统性能的不同技巧

    • 索引优化技术(如数据预处理和分块)专注于格式化外部数据以提高其效率和可搜索性。
    • 预检索技术旨在通过重写、重新格式化或将查询路由到专用流水线来优化用户查询本身。
    • 检索优化策略通常侧重于在检索阶段优化搜索结果。
    • 检索后优化策略旨在通过各种技术提高生成结果的准确性,包括对检索结果进行重新排序、增强或压缩(检索)上下文以及操纵提示或生成模型 (LLM)。
  • KBLAM 是在 RAG(Retrieval-Augmented Generation) 和 知识图谱增强推理 的基础上发展而来。它的关键点是:

    • 利用结构化知识(如三元组:subject–predicate–object)进行多跳推理
    • 结合语言模型对自然语言的理解能力,实现可控的知识推理流程

Reference

  • 《基于大模型的RAG应用开发与优化——构建企业级LLM应用》

LangChain要点记录

发表于 2025-02-19

基于书籍简单记录要点

LangChain 提供了多种模板供选择

  • LangChain 提供了以下格式化 SQL 提示词模板(翻译):
1. 你是一个 PostgreSQL 专家。给定一个输人问题,首先创建一个语法正确的 PostgreSQL查询来运行,然后查看查询结果,扑返回针对输人问题的答案。
2. 除非用户明确指定了要返回的结果数量,否则应使用 PostgreSQL 的LIMIT 子句来限制查询结果,最多返回top.k条记录。你可以对结果进行排序,以返回数据库中最有信息价值的数据。
3. 绝对不要查询表中的所有列。你只能在询回答问题所需的列。用双引号(")将每个列名包裹起来,表示官们是界定的标识符。
4. 注意只使用你在表巾可以看到的列名,不要责询不存在的列。此外,要注意哪一列在哪个表中。
5. 如果问题涉及“今天”,请注意使用 CURRENT_DATE 函数获取当前日期。

使用以下格式:

问题:这里的问题
SQL查询:要运行的 SQL 查询
SQL结果:SQL 查询的结果
答案:这里的最终答案

只使用以下表:

(table_info)

问题:{input}

  • 想象一下,如果没有 LangChain 提供的这个提示词模板,当你要开始编写一段SQL查询代码时,会走多少弯路?LLM 应用开发的最后1公里,其意义是确保开发者无须为了一个小细节而多走弯路,正如居民无须跑很远坐公交车一样,每一个关键的细节都能得到及时而准确的处理,使得整个开发过程更为高效。

记忆提示词

  • 创建提示词是最重要的环节。在创建的过程中你可以理解为什么加人记忆组件后,“聊天备忘录”有了内容,让链组件有了“记忆”。使用提示词模板包装器,自定义一个提示词模板字符串。

  • 提示词内容分为四部分:

    • 一是对模型的指导词:“请你回答问题的时候,依据文档内容和聊天记录回答,如果在其中找不到相关信息或者答案,请回答不知道。”;
    • 二是使用问题检索到的相关文档内容;“文档内容是:{context}”;三是记忆组件输出的记忆内容:“聊天记录是:{chat_history}”;四是用户的输人:“Human:(human _input)”
      template = "n*你是说中文的 chatbot.
      请你回答问题的时候,依据文持内容和脚天记录回答,如果在其中找不到相关信息戒着答案,请回答
      不知道。
      文档内容是:{context)
      聊天记录是:{chat_history)
      Human: (human_input)
      Chatbot:"""
      
  • LangChain 框架由以下开发库组成。

    • (1)LangChain-Core:基础抽象和 LangChain 表达语言(LCEL)。
    • (2)LangChain-Community:组件及内置的大量第三方技术集成模块,一般被封装为合作伙伴模块(例如 LangChain-openai)。
    • (3)LangChain:构成应用架构的上层核心组件,包括 Chains、Agents 等。
    • (4)Templates:官方提供的一些常见的应用模板。
    • (5)LangServe:将 LangChain 链部署为 REST API 的平台。
    • (6)LangSmith:帮助开发者跟踪调试、测试、评估和监控大模型应用的在线平台。

其他

  • Langchain agent是怎么找到search工具并使用的

    • 可以正确识别和调用它,因为它主要是通过 description 语义匹配,而不是看 name 的具体字符串。
    • 但 name 仍然有一定作用,比如:LLM 可能会参考 name 来做初步判断;调试时 name 可以帮助你看日志,知道 Agent 选了哪个工具
  • LLM本身没有内在记忆,每个查询都是独立进行的

    • 所谓的记忆和检索增强生成(RAG)是通过外部手段实现的,即将相关信息添加到提示词模板中

扩展

Langchain是怎么做到通过分析语义找到对应工具的

  • From ChatGPT (2025-02-18)

LangChain 通过 LLM(大模型)+ ReAct 框架 来分析语义并选择工具。它的核心逻辑是让 LLM 先思考,再决定用哪个工具,并按照工具的格式调用它。

核心机制

  1. 解析用户问题 → 让 LLM 提取关键语义
  2. 匹配工具描述 → 让 LLM 判断哪个工具最适合
  3. 生成调用指令 → LLM 生成工具的调用格式并执行
  4. 工具返回结果 → LLM 解析工具返回的数据并回复用户

这套逻辑基于 ReAct(Reasoning + Acting) 框架,在 LangChain 里 Agent 主要是用这个方法来动态决策。

1. 解析用户问题

假设你输入:

1
agent.run("计算 25 * 4 + 10")

LangChain 会把这个问题交给 LLM(如 GPT-4),让它理解用户的意图。

LLM 可能会把你的问题理解成:

  • 这是一个数学计算问题
  • 需要找到一个能进行数学计算的工具
  • 计算表达式 25 * 4 + 10

2. 匹配工具描述

假设你有两个工具:

1
2
3
4
5
6
7
8
9
10
11
Tool(
name="Calculator",
func=calculator_tool,
description="用于数学计算。输入一个数学表达式(如 3 + 5 * 2),输出结果。",
)

Tool(
name="Wikipedia",
func=wiki.run,
description="查询 Wikipedia 词条,输入一个关键词(如 'Python programming'),获取相关信息。",
)

LLM 会对比问题和 description,发现 Calculator 的描述里提到了“数学计算”,所以它会选择 Calculator 这个工具。

关键点:LangChain 让 LLM 直接读 description,所以工具的名字 name 只是一个标识,核心还是 description 的语义匹配。

3. 生成调用指令

LangChain 让 LLM 生成一个类似 JSON 的格式,表示它要调用哪个工具:

1
2
3
4
{
"action": "Calculator",
"action_input": "25 * 4 + 10"
}

然后 LangChain 会解析这个指令,找到 Calculator 工具,并把 25 * 4 + 10 传给 func 去执行。

4. 工具返回结果

计算工具执行:

1
eval("25 * 4 + 10")  # 计算得到 110

LangChain 把 110 返回给 LLM,LLM 可能会回复:

1
25 * 4 + 10 = 110

最终 agent.run() 会输出这个结果。

总结

LangChain 让 LLM 负责:

  1. 分析用户语义
  2. 匹配工具(通过 description)
  3. 生成调用工具的指令
  4. 解释工具返回的结果

它的核心是利用 LLM 的推理能力,结合 ReAct 让它“思考后再行动”。所以只要 description 够清晰,即使 name 乱写,它也能找到正确的工具!


Reference

  • 《LangChain入门指南构建高可复用、可扩展的LLM应用程序》
  • 《基于大模型的RAG应用开发与优化——构建企业级LLM应用》

深度学习基础入门备忘

发表于 2025-02-17

简单粗略通读了解,先记录备忘
后续考虑结合相关视频深入理解

  • 《深度学习人门:基于Python的理论与实现》:https://github.com/Kingson4Wu/Deep-Learning-from-Scratch

    1. 感知机是一种接收多个输入信号并输出一个信号的算法。它的工作原理基于权重和偏置这两个关键参数。
    2. 机器学习的任务是让计算机自动确定合适的权重和偏置参数值。
    3. 求解机器学习问题的步骤
      1. 训练(学习)
      2. 推理(神经网络的前向传播)
    4. 激活函数(activation function):决定如何来激活输入信号的总和;激活函数是连接感知机和神经网络的桥梁。
    5. 神经网络的学习过程:通过损失函数 (loss function)和梯度法 (gradient method)来优化网络参数
      1. 学习的目标是通过梯度下降法(gradient descent method)找到使损失函数值最小的权重参数
      2. 学习率(learning rate):决定参数更新的步长(超参数、人工设定)
    6. 随机梯度下降(stochastic gradient descent)(SGD)能在一定程度上帮助避免局部最优,通常将SGD与其他技术结合使用,以获得更好的优化效果
    7. 深度学习:加深了层的深度神经网络;通过叠加层,可以创建更深的网络结构
  • 《深度学习进阶:自然语言处理》:https://github.com/Kingson4Wu/Natural-Language-Processing

    1. 自然语言处理的目标就是让计算机理解人说的话,进而完成 对我们有帮助的事情
    2. 单词的分布式表示(分布式假设)(单词向量化):“某个单词的含义由它周围的单词形成”;单词本身没有含义,单词含义由它 所在的上下文(语境)形成。
    3. 向量间的相似度:余弦相似度(cosine similarity);直观地表示了“两个向量在多大程度上指向同一方向”
    4. 让计算机理解单词含义:基于推理的方法(word2vec)(基于神经网络)。
    5. 语言模型(language model)给出了单词序列发生的概率;使用概率来评估一个单词序列发生的可能性,即在多大程度上是自然的 单词序列。
      • 生成的新文本是训练数据中没有的新生成的文本。因为语言模型并不是背诵了训练数据,而是学习了训练数据中单词的排列模式
      • 语言模型的评价:困惑度(perplexity)、分叉度
    6. “马尔可夫性”或者“马尔 可夫模型”“马尔可夫链”:指未来的状态仅 依存于当前状态。
    7. RNN(循环神经网络):被引入来解决前馈网络在处理时序数据上的局限性。
      • 传统RNN中存在的梯度消失和梯度爆炸问题
      • LSTM的结构与传统RNN的不同之处在于,它引入了记忆单元(c)。记忆单元在LSTM层之间传递,但不直接用作输出。LSTM的对外输出是隐藏状态向量(h)。
    8. seq2seq模型(也称为Encoder-Decoder模型)用于将一个时序数据转换为另一个时序数据
      • 传统 seq2seq 模型 将编码器输出压缩为固定长度向量,导致长序列信息丢失
      • Attention 机制 允许模型在解码时关注输入序列的不同部分,类似人类注意力
    9. Transformer:基于 Attention 构成;基于 Attention 构成
  • 《深度学习入门:强化学习》:https://github.com/Kingson4Wu/Reinforcement-Learning

    1. 机器学习(按学习方法划分):监督学习(supervised learning)、无监督学习(unsupervised learning)、强化学习(reinforcement learning)
      1. 监督学习:给正确答案打标签;输入的数据由“老师”打标签
      2. 无监督学习:无“正确答案标签”;没有 “老师”的存在;主要目标是找到隐藏在数据中的结构和模式;分组(聚类)、特征提取、降维
      3. 强化学习:智能代理和环境相互作用;智能代理是行动的主体;强化学习接受”奖励”作为来自环境的反馈
    2. 强化学习行动的策略
      1. “贪婪行动”(greedy ),也叫利用(exploitation):根据以前的经验选择最佳行动(可能错过更好的选择)
      2. “非贪婪行动”,也叫作探索(exploration):对价值做出更准确的估计。
    3. 强化学习算法最终归结为如何在“利用”和 “探索”之间取得平衡
    4. ε-greedy 算法、马尔可夫决策过程(MDP)
    5. 在强化学习中,我们的目标是获得最优策略
    6. 深度强化学习(deep reinforcement learning):强化学习和深度学习的结合
    7. 通用人工智能(artificial general intelligence, AGI)

其他

参数、输入向量和嵌入模型的真正关系

  • 在神经网络中,“参数”特指模型在训练过程中学习得到的变量,主要包括权重(weights)和偏置(biases),它们决定了模型如何处理输入并生成输出,是模型内部真正“学到的知识”。输入特征的数量(即输入维度)常被初学者误认为是“参数”,但实际上,它属于输入数据的结构,而非模型的可训练部分。每个神经元在接受输入时,会对输入向量进行加权求和并加上偏置,将这个结果作为激活函数的输入,激活函数再施加非线性变换,产生神经元的输出。虽然权重确实与输入一一对应,但激活函数并不直接作用于原始输入,而是作用于这个线性组合的结果。

  • 在现代深度学习模型中,尤其是语言模型(如 GPT),输入向量的维度是固定的,这一维度通常由嵌入模型(embedding layer)或输入预处理过程所决定。例如,文本经过分词和嵌入后,每个 token 被映射为一个固定长度的向量(如 768 维),整个输入变为一个定长矩阵。为了确保矩阵运算的可行性与模型结构的稳定性,输入长度往往被限制在最大长度内,不足时通过填充处理,超长则截断。因此,嵌入层不仅是将离散信息转为向量表示的桥梁,也是模型输入维度的决定因素之一。

感知机、激活函数和神经网络三者关系

  • 感知机是神经网络的基本构建单元,它通过对输入加权求和后传入激活函数来决定输出。激活函数引入非线性,使神经网络能拟合复杂关系。神经网络由多个感知机层叠构成,层与层之间通过激活函数连接,从而具备强大的表达和学习能力。三者关系为:激活函数是感知机的一部分,感知机是神经网络的基础单元。

三者之间的关系总结:

组成层级 关系说明
感知机 最基础的神经元模型,是神经网络的最小单元
激活函数 是感知机或神经元的核心部分,引入非线性
神经网络 是多个感知机/神经元的组合,通过激活函数形成强大的拟合能力

可以这样理解它们的层级结构:

1
2
3
神经网络 = 多个感知机(神经元)组成
感知机 = 线性加权求和 + 激活函数
激活函数 = 赋予神经网络非线性表达能力的关键

关于AI大语言模型替代人类工作的问题

发表于 2025-02-13

AI的局限性或缺点

  • 难以预测与控制:AI的运行机制像黑箱,难以准确预知其行为,尤其在关键场景下可能会犯致命错误。
  • 无法背锅:AI犯错时,责任归属难以明确,导致无法追究错误的责任,缺乏人类信誉体系的约束。
  • 逻辑推理不严谨:AI的推理基于概率预测,不是绝对严谨的逻辑推理。训练数据如果有误,AI可能无法辨别。
  • 无法创新:AI不具备创造全新概念的能力,更多的是基于历史数据进行知识复述与组合,无法像人类一样发明新技术或理念。
  • 对超出训练数据的场景应对差:AI在面对未曾训练过的数据时,表现较差,容易出错。

AI的好处

  • 提高效率:AI在许多领域极大提升了效率,尤其在数据处理、搜索和重复性任务上。对于程序员来说,它是一个强大的辅助工具,帮助快速解决技术问题。
  • 降低门槛:AI减少了对低级重复性任务的需求,拉近了人们在某些知识领域的差距。
  • 支持决策和监督:AI辅助决策,尤其是在复杂任务中,能提供数据支持,减少人为错误。

AI工具下需要的人才

  • 清晰表述与提问能力:能够清晰提出问题和有效沟通是与AI协同工作的关键,好的表述能力有助于提高工作效率。
  • 整理与分析能力:能够有效梳理信息、分解任务,并向AI提出清晰问题的人,会更善于利用AI工具。
  • 与产品交互能力:AI可以编写代码,但仍需要人类与产品经理沟通,理解需求并做出相应调整。

程序员的利好与不可替代的能力

  • AI对程序员的利好:
    • AI大幅提升了开发效率,尤其在编程辅助、技术搜索、业务方案思考等方面。
    • 某些低级任务减少了人力需求,使得程序员能更多专注于创造性和复杂问题的解决。
  • 程序员不可替代的地方:
    • 清晰的提问和判断能力:程序员的核心能力在于能理解问题,并准确表达需求,AI只能作为工具辅助工作。
    • 与产品沟通:AI生成的代码和解决方案需要程序员与产品团队对接,确保最终结果符合需求。
    • 决策和经验判断:AI的能力有限,尤其在面对复杂决策时,仍需依赖经验丰富的程序员来进行判断和修正。

个人观点

  • AI目前主要是利用历史数据和记忆进行信息处理,不能进行创新(如无法创造出类似K8S的技术)。
  • 尽管AI能提高程序员的工作效率,但目前它更多是辅助工具,而不是替代品。
  • 对普通程序员来说,理解大模型技术的基本原理和概念非常重要,未来将需要在“AI操作系统”上来构建应用。

扩展

来自claude.ai的评价
2025-02-13

我来分析一下这些观点,指出其中可能存在的错误或需要讨论的地方:

  1. 关于”无法创新”的说法需要更谨慎:
  • 虽然AI确实主要基于已有数据进行组合和推理,但说它”不具备创造全新概念的能力”可能过于绝对
  • AI已经展示出一定的创新能力,比如在围棋、蛋白质折叠等领域提出了人类之前没有想到的解决方案
  • 更准确的说法是AI的创新能力与人类不同,它通过大规模数据分析和模式识别来实现创新
  1. “逻辑推理不严谨”的表述不够准确:
  • 现代AI系统(尤其是形式化验证系统)可以进行严格的逻辑推理
  • 大语言模型确实存在基于概率的推理特点,但这不等同于所有AI系统都如此
  • 人类的推理同样也常常基于经验和概率判断,而不总是严格的逻辑推导
  1. 关于”难以预测与控制”:
  • 这个观点部分正确,但需要注意现代AI系统已经有了很多可解释性的工具和方法
  • 某些领域的AI系统(如用于医疗诊断的AI)已经实现了相当程度的可解释性
  • “像黑箱”这种说法可能过于简化了问题
  1. “无法背锅”的说法不够准确:
  • 实际上已经有了相关的法律和责任框架在建立
  • AI系统的责任可以追溯到开发者、部署者和使用者
  • 这更多是一个治理和监管的问题,而不是技术本身的限制
  1. “个人观点”部分关于K8S的例子不够恰当:
  • K8S本质上是一个系统架构和设计方案,而不是完全创新的技术
  • AI实际上可以通过分析已有系统设计模式,提出类似的架构方案
  • 更准确的说法是AI在某些创新领域的能力仍有限制,而不是完全无法创新
  1. 好处部分基本准确,但可以补充:
  • AI不仅提高效率,还能发现人类容易忽视的模式和关联
  • 在某些领域(如图像识别、语音处理)已经超越了人类性能
  • AI能够24/7工作,这个优势没有被提到
  1. 关于程序员不可替代性的分析基本合理,但可以补充:
  • 程序员在系统架构设计、安全性考虑等方面的经验特别重要
  • 处理边界条件和异常情况的能力仍然需要人类经验
  • 对业务场景的深入理解和商业价值判断也是关键能力
  1. “AI操作系统”的说法需要澄清:
  • 这个比喻可能会造成误解,更准确的说法是”AI基础设施”或”AI平台”
  • 程序员需要理解的不仅是技术原理,还包括AI的应用场景和限制

总的来说,这些观点大体上是合理的,但部分表述过于绝对或简化。AI的能力和局限性是一个复杂的话题,需要更细致和平衡的讨论。理解AI的真实能力和限制,对于更好地利用AI工具至关重要。

12…16>

155 日志
166 标签
RSS
© 2025 Kingson Wu
由 Hexo 强力驱动
|
主题 — NexT.Pisces v5.1.4