最近在重新学习 Linux C++ 的过程中，发现了一种优雅的方式：借助 Docker + VS Code Dev Container 在任何系统上轻松获得一致的 Linux 开发调试环境。作为长期在 macOS 和 Windows 上开发的人，这种体验让我感受到前所未有的丝滑，真有点“相逢恨晚”。

从此，无论是 C++、Python、Go，还是其他需要 Linux 环境的项目，都可以通过 Dev Container 轻松构建一致的开发调试环境。以下是相关的整理和总结。

1. Dev Container 的核心优势

• 统一环境：项目环境配置集中管理，避免“环境配置地狱”。
• 真实 Linux 环境：Mac/Windows 上可获得接近原生 Linux 的开发体验。
• 环境隔离：每个项目独立运行，避免宿主机污染。
• 一键上手：新人无需安装复杂依赖，直接启动容器即用。
• 跨平台一致性：团队成员无论使用何种操作系统，都能保持开发环境完全一致。

2. 调试工作原理

• VS Code 前端：仅负责界面展示和用户交互。
• 容器内调试器后端：断点、变量跟踪等逻辑均在容器中执行。
• Docker 通信：通过端口映射或内置通道实现容器与宿主机的连接。
• DAP 协议：调试适配器协议（Debug Adapter Protocol）统一了调试接口，支持多语言插件。
• 无缝体验：Dev Container 自动部署 VS Code Server，调试如同本地运行。

3. 跨架构开发（Mac ARM 跑 x86 容器）

• QEMU 仿真：通过指令翻译运行 x86 ELF 程序。
• binfmt_misc：自动识别并调度不同架构的可执行文件。
• 优势：可兼容仅支持 x86 的旧软件或镜像。
• 不足：性能有损耗，不适合重度计算任务或长期运行。

4. 微服务项目的容器化策略

1. 共享开发环境容器
   单一容器作为开发机，挂载多个项目，减少容器启动和切换成本。

2. 多服务合一容器
   借助 supervisord 管理多个进程，将多个微服务打包到同一个容器中运行。

3. docker-compose 管理公共依赖
   数据库、缓存等共享服务通过 docker-compose 集中管理，避免重复维护。

4. 多项目 Dev Container 配置

   • 利用 workspaceMount 挂载多个项目目录；
   • .devcontainer/ 建议放在仓库或 monorepo 顶层，便于团队协作。

方法1 vs 方法4 对比表

对于大型项目或多团队协作，可以考虑 Kubernetes 或云端 Codespaces 来简化开发环境管理。

5. 总结与趋势

• 容器化开发环境已成趋势：开发环境可以像代码一样被版本化、迁移、复刻。
• 适用场景广泛：不仅适合现代项目，对老旧技术栈（如 PHP 项目）同样友好。
• 开发体验升级：只需一次配置，团队成员无需手动搭建环境，即可专注业务开发。

这样一套方案，让跨平台、跨语言、跨架构的开发调试都像在本地一样丝滑高效。

参考例子

• https://github.com/Kingson4Wu/cpp-linux-playground

以下内容由AI生成

在日常使用家庭宽带时，很多人会遇到“到底我家有没有独立公网 IP”的问题。这不仅关系到能否顺利访问外网，更影响到是否可以在家中搭建服务器、使用 P2P 应用等。本文将系统梳理家庭宽带 IP 的分配方式、运营商 NAT 的机制以及其对用户的实际影响。

1. 家庭宽带的几种典型 IP 分配方式

（1）独立公网 IP

• 家庭路由器的 WAN 口直接获取公网 IPv4 地址（或独立 IPv6 前缀）。
• 此时家庭就是一个独立的外网节点，可直接与互联网通信（除非被防火墙限制）。
• 典型场景：早期 ADSL 宽带、当前部分电信/联通/移动的 IPv6 分配。

优势：可开放端口、搭建服务器，外网可直接访问家庭设备。

（2）共享公网 IP（运营商 NAT / CGNAT）

• 由于 IPv4 地址紧张，很多家庭宽带 WAN 口拿到的并不是公网地址，而是内网地址：

  • 100.64.x.x（CGNAT 专用）、10.x.x.x、172.16–31.x.x、192.168.x.x 等。

• 运营商在核心网部署 NAT，把成百上千家庭流量映射到同一个公网 IP 上。

特点与问题：

• 家庭没有独立公网出口，而是和他人“拼”一个公网 IP。
• 限制：端口映射困难甚至不可能 → 无法轻易搭建对外服务。

（3）混合模式（IPv6 公网 + IPv4 NAT）

• 家庭可获得独立的 IPv6 前缀（相当于独立公网地址）。
• IPv4 依旧通过 NAT，共享公网 IP。
• 这种情况在目前逐渐普及，算是“半独立外网”。

2. 内网与外网的关系

• LAN 内网 IP：路由器分配给家庭设备的地址（如 192.168.x.x），可支持上百台设备。
• WAN IP：路由器外网口的地址，可能是真公网，也可能是运营商 NAT 内网（如 100.64.x.x）。

关键点：

• 家庭可分配的内网 IP 数量不受共享公网限制，理论上仍可支持数百设备。

• 共享公网真正的限制在于：

  • 端口映射受阻
  • P2P 软件连接困难
  • 搭建家庭服务器几乎不可能

3. CGNAT 的工作机制

CGNAT 的核心是 端口映射表。

1. 家庭路由器将内网设备请求 NAT 成 WAN IP + 端口。
2. 运营商 CGNAT 再将 WAN IP + 端口转换为 公网 IP + 唯一端口。
3. 返回数据时，CGNAT 通过映射表查找，精准把数据包发回正确的家庭。

要点：

• 即使不同家庭设备端口相同，CGNAT 会分配不同的公网端口 → 不会冲突。
• 每个家庭必须有唯一的 WAN IP（即便是私有地址），否则映射表无法区分连接。

4. 特殊地址段：100.64.x.x

• 定义：RFC 6598 规定 100.64.0.0/10 专用于 运营商级 NAT。

• 特性：

  • 不是公网 IP（外网无法直达）。
  • 不是家庭 LAN 内网（192.168/10.x/172.16–31），而是运营商内部“二级内网”。

• 工作方式：

  1 2 3 4 5 6

  家庭设备 192.168.1.2 ↓ 家庭路由器 NAT WAN: 100.64.1.2 ← 运营商私有地址 ↓ 运营商 CGNAT 公网 IP: 1.2.3.4 ↓ Internet

注意：家庭网络不应使用 100.64.x.x 作为 LAN 地址，否则会和运营商 CGNAT 冲突，导致公网无法访问。

5. 总结

1. 独立公网 IP：可直接对外通信，最自由。
2. 共享公网 IP（CGNAT）：常见于 IPv4，无法轻易开放端口，但家庭内网不受影响。
3. IPv6 普及下的混合模式：IPv6 独立公网，IPv4 仍共享。
4. 100.64.x.x 是运营商内网地址，不是公网 IP。
5. 核心差异：家庭内网数量不受限制，但共享公网时外网访问受阻。

📌 一句话总结：
大多数家庭宽带并没有独立公网 IPv4，而是通过 CGNAT 与他人共享出口。要想获得真正独立的公网地址，需要向运营商申请“公网 IP 服务”或使用企业宽带。

以下内容由AI生成，本人审阅

一、VPN 的基本原理

**VPN（Virtual Private Network，虚拟专用网络）**的核心思想是在 公网上（Internet） 建立一条 加密隧道，使用户的数据能够像在同一局域网中一样安全传输。其关键机制包括：

1. 隧道封装（Tunneling）

   • 将原始 IP 包或 TCP/UDP 流量再次封装后发送至 VPN 服务器。
   • VPN 服务器解封装后再转发至目标网站或服务。
   • 常见协议包括 PPTP、L2TP、IPSec、OpenVPN（基于 TLS/SSL）、WireGuard 等。

2. 数据加密（Encryption）

   • VPN 的核心能力之一就是加密，例如 AES、ChaCha20。
   • 运营商或中间路由器看到的只是加密数据流，而无法识别内容。

3. 虚拟网卡（Virtual NIC）

   • 客户端安装 VPN 时会创建虚拟网卡。
   • 系统将原始流量交给虚拟网卡，由 VPN 客户端进行加密与封装，再传输至服务器。

二、正向代理的基本原理

正向代理（Forward Proxy） 是一种由客户端主动指定的代理模式：

• 客户端 → 代理服务器 → 目标网站
• 代理服务器替代客户端访问网站。

常见类型包括：

• HTTP Proxy：仅代理网页流量。
• SOCKS5 Proxy：支持 TCP/UDP，更通用。

👉 如果在正向代理的基础上增加加密，就得到 加密正向代理，例如：

• Shadowsocks（基于 SOCKS5 + 加密）
• V2Ray、Trojan（自定义协议 + 加密）

三、VPN 与正向代理的关系

1. 共性

   • 都是正向代理的广义形式，用户请求最终都由中间服务器转发。
   • 都可以实现数据加密、突破访问限制、保护隐私。

2. 差异

   • VPN：工作在 网络层，接管整个系统的所有流量，不需要应用单独配置。
   • 加密代理（Shadowsocks/V2Ray/Trojan 等）：工作在 传输层/应用层，更灵活，可以选择性分流。

✅ 准确的表述是：

VPN 是一种在网络层实现的“全流量加密隧道代理”；而机场协议（如 Shadowsocks/V2Ray/Trojan）是工作在传输层或应用层的“加密正向代理”。

四、为什么“机场代理”常被叫做 VPN

• 手机或电脑端的 Shadowsocks/V2Ray 客户端通常会申请系统的 VPN 权限（VPNService），创建虚拟网卡，将流量导入代理。
• 在用户体验上，表现为“一键开启，所有流量都出国”，与 VPN 相似。
• 但协议层面，它们并非传统 VPN，而是 加密正向代理 + VPN 伪装 的结合体。

五、效果、效率与使用体验差异

1. 效果层面

• VPN：全流量隧道，统一加密转发。
• 机场代理：通过加密代理转发流量，用户体验上几乎无差别。

2. 效率与性能

• VPN：底层封装，效率较高（WireGuard 延迟小、速度快）。
• 代理：协议转换可能增加开销，但现代实现已高度优化。

3. 使用体验

• VPN：系统级全局接管，适合企业远程办公、统一管控。
• 机场代理：支持灵活分流（国际流量走代理、国内直连），更适合个人日常使用。

六、典型场景对比

1. 公司 VPN

   • 常见模式是 全隧道（Full Tunnel），所有流量经由公司出口，安全统一但效率偏低。
   • 有些公司支持 分隧道（Split Tunnel），仅内网走 VPN，外网直连，但安全性存在隐患。

2. 机场代理

   • 可选择 全局代理，模拟 VPN 效果。
   • 或使用 规则分流（PAC 模式），国际流量走代理，国内直连，更高效。

七、总结

• VPN：本质是 网络层的加密隧道代理，接管系统所有流量。
• 机场协议（Shadowsocks、V2Ray、Trojan）：本质是 传输层/应用层的加密正向代理，通过虚拟网卡实现“伪装成 VPN”的体验。
• 共同点：都加密、都代理、都能突破限制。
• 差异点：VPN 更底层、统一接管；机场代理更灵活、支持分流。

👉 一句话概括：
VPN 与机场协议都是“加密正向代理”，区别只在于工作层级和使用方式。

以下内容由AI生成，本人审阅

在网络代理领域，SOCKS5 是一种常用的正向代理协议。它不同于传统的 HTTP 代理，能够为各种应用层协议提供通用的转发支持。本文将从概念、协议机制、工作流程和应用场景几个层次，系统梳理 SOCKS5 的技术原理。

1. 正向代理的基本概念

正向代理是指客户端主动使用代理服务器，把请求先发给代理，再由代理去访问目标服务器，并把结果返回客户端。

主要作用：

• 隐藏客户端真实 IP
• 绕过访问限制（如内网封锁、跨境访问）
• 统一出口流量，便于管理和审计

2. SOCKS 协议简介

SOCKS (Socket Secure) 是一种通用的代理协议，不依赖特定的应用层协议。

• SOCKS5 是该协议的第 5 版，支持更多功能：

  • TCP 与 UDP 转发
  • 用户认证（无认证、用户名/密码等）
  • IPv4 / IPv6 / 域名解析

👉 与 HTTP 代理相比，SOCKS5 并不解析上层应用协议，只做数据字节的透明转发，因此适用范围更广。

3. SOCKS5 的工作流程

假设客户端配置了一个 SOCKS5 代理，整个交互过程如下：

1）客户端与代理握手

• 客户端告知代理：“我支持哪些认证方式（无认证 / 用户名密码 / …）”
• 代理回应：“我要求用某种认证方式”
• 若需认证，客户端提交凭证，通过后进入下一阶段

2）客户端请求目标地址

• 客户端通过代理的 TCP 连接，发送目标地址和端口，例如：example.com:80
• 代理尝试与目标服务器建立连接

3）代理回应结果

• 连接成功：返回成功报文，允许数据传输
• 连接失败：返回错误码（如目标不可达、连接被拒绝等）

4）数据转发

• 客户端与目标服务器的所有数据均通过代理中转
• 代理只做字节转发，不理解应用层协议内容
• 这使得 SOCKS5 成为一种非常通用的代理机制

4. TCP 与 UDP 的支持

SOCKS5 协议既能代理 TCP，也能代理 UDP：

• TCP CONNECT

  • 客户端请求代理建立到目标服务器的 TCP 连接
  • 数据传输过程中，代理双向转发 TCP 流量
  • 应用场景：网页浏览、SSH、邮件收发等

• UDP ASSOCIATE

  • 客户端先通过 TCP 控制通道告诉代理要进行 UDP 转发
  • 代理返回一个专用的 UDP 端口
  • 客户端将 UDP 数据包（带 SOCKS5 UDP 头）发送到该端口，代理再转发到目标服务器
  • 应用场景：DNS 查询、在线游戏、视频流

5. TCP 与 UDP 的关系

需要特别注意：

1. 控制信道：必然是 TCP

   • 无论最终转发 TCP 还是 UDP，客户端和代理之间都要先建立一条 TCP 连接
   • 握手、认证、UDP 转发上下文都依赖该 TCP 控制信道

2. 数据通道：因请求而异

   • CONNECT 命令 → 代理 TCP 流量
   • UDP ASSOCIATE 命令 → 代理 UDP 数据包

👉 简单比喻：

• TCP 就像一条“电话线”，你先打电话告诉代理你要去哪
• 如果是 TCP 业务，代理帮你中继对话
• 如果是 UDP 业务，代理给你一个“邮局地址”，你把信件（UDP 包）寄过去，它帮你转发

6. 为什么 SOCKS5 常用

SOCKS5 在现代网络应用中被广泛使用，原因在于：

• 协议层次低：位于 TCP/UDP 之上，应用层之下，对上层协议透明
• 适用性广：能代理任意应用层协议，不仅限于 HTTP
• 支持 UDP 转发：满足实时性要求高的业务场景
• 支持身份认证与 IPv6：更安全，适应新网络环境
• 比 HTTP 代理更灵活：不做解析，只做转发

7. 总结

一句话概括：
SOCKS5 正向代理的原理是——客户端和代理建立 TCP 会话，告诉代理要访问的目标地址，代理再代表客户端发起连接，并负责转发所有 TCP/UDP 数据。代理本身不理解应用层协议，只是透明转发。

⚡关键点回顾：

• SOCKS5 协议本身基于 TCP
• 可代理 TCP 与 UDP 流量
• UDP 转发依赖 TCP 控制信道维持会话
• 对应用层协议透明，通用性极强

发现之前的理解有一点小偏差，重新整理一下
以下内容由AI生成，本人审阅

在日常开发和运维中，“正向代理（Forward Proxy）”和“反向代理（Reverse Proxy）”是两个高频概念。但很多人容易混淆两者的请求格式和工作机制。本文将从 HTTP 报文格式、TCP 连接目标、历史规范 等角度，系统梳理这两种代理的差别与本质。

1. 正向代理（Forward Proxy）

使用场景

客户端无法直接访问目标网站（如跨境访问、内网限制），于是先把请求交给代理服务器，由代理转发给目标站点。

请求示例

客户端请求发送给代理时，请求行必须带完整 URL：

1
2

GET http://www.example.com/index.html HTTP/1.1
Host: www.example.com

• TCP 连接目标：代理服务器（如 proxy.mycorp.com:8080）
• 请求行：完整 URL（http://host/path）
• Host：目标站点域名（www.example.com）

👉 代理根据 URL 或 Host，建立新连接去访问目标网站，再返回结果。

2. 反向代理（Reverse Proxy）

使用场景

客户端以为自己访问的是目标站点，其实连到的是反向代理（常见如 Nginx、Apache）。代理再根据配置，把请求分发给后端不同的服务。

请求示例

客户端对代理并不知情，请求格式与直连一致：

1
2

GET /index.html HTTP/1.1
Host: www.example.com

• TCP 连接目标：反向代理（如 nginx）
• 请求行：相对路径 /path
• Host：目标站点域名（用于路由转发）

👉 对客户端而言，看起来就是访问了目标站点。

3. 请求报文差异总结

4. 为什么正向代理要写完整 URL？

这源于 HTTP/1.0 的历史限制：

• 早期（HTTP/1.0）：请求行只有路径，如 GET /index.html HTTP/1.0。
  当时一个 IP 对应一个网站，直连场景没问题；但如果连的是代理，代理无法得知目标域名。
  👉 解决方案：在代理模式下，强制请求行写完整 URL。

• HTTP/1.1：引入 Host 头，直连时可区分虚拟主机。
  但 代理模式依旧保留完整 URL 规则，原因有两点：

  1. 向后兼容旧代理。
  2. 代理可直接用 URL 做缓存键、写日志，逻辑更清晰。

因此，虽然代理理论上可以只靠 Host 判断目标，但规范要求写完整 URL。

5. TCP 连接层与应用层的分工

这里的核心区别在于 TCP 与 HTTP 的分工：

• TCP 层：只管“连哪个 IP:Port”。

  • 直连：连 www.example.com:80
  • 正向代理：连 proxy.mycorp.com:8080

• HTTP 层：报文里体现目标站点信息。

  • 直连/反向代理：请求行 /path + Host
  • 正向代理：请求行 http://host/path + Host

👉 换句话说，TCP 根本不知道什么是代理，它只负责传字节流；代理语义完全由 HTTP 层和客户端实现决定。

6. 为什么客户端在代理模式下，TCP 连接建到代理服务器？

👉 因为这是 客户端实现决定的，不是 HTTP 协议强制的。

1. 普通直连模式

浏览器要访问 http://www.example.com/index.html：

• DNS 解析 www.example.com → 得到 IP

• 建立 TCP 连接 www.example.com:80

• 发请求：

  1 2	GET /index.html HTTP/1.1 Host: www.example.com

2. 配置了正向代理模式

当浏览器或系统配置了代理地址，例如：

• 代理地址：proxy.mycorp.com
• 端口：8080

此时客户端行为改变：

• DNS 不再解析 www.example.com

• TCP 连接目标改为 proxy.mycorp.com:8080

• 发请求：

  1 2	GET http://www.example.com/index.html HTTP/1.1 Host: www.example.com

👉 代理收到报文后，根据 Host 或 URL 确定目标网站，再去转发。

3. 为什么这是客户端逻辑？

• HTTP 协议只规定“请求报文格式”

• TCP 连接目标是由客户端实现决定的

• 浏览器配置代理的含义就是：

  “以后别直连目标网站，把请求先交给代理。”

因此：
✔ 直连模式 → TCP 连目标站点
✔ 代理模式 → TCP 连代理服务器
✔ 完全是客户端的选择和实现逻辑

4. 特别注意：HTTPS + 代理

当访问 HTTPS 时，客户端会先向代理发送 CONNECT 方法：

1
2

CONNECT www.example.com:443 HTTP/1.1
Host: www.example.com:443

代理收到后，建立一条 TCP 隧道；TLS 握手和加密流量在隧道中传输，代理无法解密。
👉 这同样完全是客户端的实现逻辑。

✅ 结论
正向代理模式下，客户端确实是 主动选择连代理服务器，而不是目标站点。
这是因为客户端知道自己在用代理，所以构造了“特殊的请求行 + 代理 TCP 目标”。

其实从客户端角度看，即使请求行写得像直连模式，效果也常常一样，因为多数代理会兼容：

• 如果请求行缺少完整 URL
• 代理也能 fallback 到用 Host 提取目标域名

因此对用户体验影响不大，差别更多是 规范要求 vs 代理实现的便利性。

7. 正向代理的本质

从不同角度来看，正向代理的核心本质可以归纳为三层：

• 从 TCP 角度
  客户端只是在“建 TCP 连接”这一步，选择连代理服务器的 IP:Port，而不是目标服务器的 IP:Port。
  👉 对 TCP 来说，这没有什么“特殊”，就是连了另一台机器而已。

• 从 HTTP 角度
  客户端在请求报文里写的是绝对 URI（http://host/path），这样代理才能知道目标是谁。
  👉 这就是“请求行会有完整路径”的原因。

• 从代理实现角度
  代理要支持解析这种“带绝对 URI 的请求行”，并根据 Host/URI 再去发起一个新的 TCP 连接转发给目标。
  👉 这就是“代理服务器要有支持转发的逻辑”。

8. 实际实现 vs 规范要求

9. HTTPS 与正向代理的特殊性

当通过正向代理访问 HTTPS 站点时，客户端先发起 CONNECT 隧道请求：

1
2

CONNECT www.example.com:443 HTTP/1.1
Host: www.example.com:443

代理建立 TCP 隧道后，客户端在隧道内直接跑 TLS 握手，代理无法看到明文。
👉 这同样由客户端的代理配置决定，TCP 本身并不区分。

10. 结论

1. 正向代理：

   • TCP 连代理服务器
   • HTTP 请求行写完整 URL
   • 客户端知道自己在用代理

2. 反向代理：

   • TCP 连反向代理（表面看似目标站点）
   • HTTP 请求行写路径，Host 提供目标域名
   • 客户端无感知

3. 核心差别：

   • 正向代理：服务于客户端，帮助突破访问限制
   • 反向代理：服务于服务器，做负载均衡、缓存、安全隔离

📌 总结一句话：
正向代理是客户端主动配置的中转站，反向代理是服务端架构中的门面。区别的本质在于 TCP 建链目标和 HTTP 请求行格式。

以下文章有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

====

20251201 - claude.ai

我来分析一下这篇文章中是否有已经过时的观点。

整体来看，文章的核心论述仍然基本正确，但有几个地方需要更新：

✅ 仍然正确的部分

1. 不翻译成英语再推理 - 这个结论依然成立，主流模型确实直接在原语言上处理
2. 跨语言共享语义空间 - 这是多语言模型的核心机制，没有改变
3. 英语数据占比高 - 训练数据中英语仍占主导地位

⚠️ 需要更新的观点

1. “英语效果更好”的差距正在缩小

文章强调英语输入效果明显更好，但在 2025 年：

• Claude 3.5 Sonnet/Opus 和 GPT-4 等新模型在中文等非英语语言上的表现已大幅提升
• 中文、日语等语言的推理质量、知识准确性已接近英语水平
• 很多场景下直接用中文提问的效果已经足够好

2. “英文 Prompt + 中文输出”策略的必要性下降

文章推荐使用英文 Prompt 再要求中文输出，但现在：

• 直接用中文 Prompt 的效果已经很好
• 这种”绕路”策略的性价比降低
• 除非是极度复杂的推理任务,否则不必刻意用英文

3. 模型列表已过时

文章提到的模型（GPT、Claude、Gemini 等）都有了更新版本，2025 年应该提及：

• Claude 3.5 Sonnet, Claude Opus 4
• GPT-4o, o1 系列
• Gemini 2.0
• 新的开源模型如 Llama 3.3, Qwen 2.5 等

📊 当前实际情况（2025年）

对于像 Claude 3.5 Sonnet 这样的模型：

• 中文直接推理效果已经非常好
• 知识完整性在中英文之间差距很小
• 复杂推理用中文也能得到高质量结果

结论

这篇文章的基本原理没有过时，但程度性结论需要更新——英语的优势仍存在，但已不像文章描述的那么明显。现在更建议：直接用你最习惯的语言提问即可。

====

多语言大模型工作原理总结

2025-12-01

核心问题与答案

Q1: 大模型是否将非英语翻译成英语再推理？

❌ 否。 模型直接在原语言上理解和推理，不存在”翻译成英语→推理→翻译回来”的过程。

实际工作机制

1. 跨语言语义空间

1
2
3
4
5
6

不同语言 → 统一的语义向量空间

"我爱你"     → [0.8, 0.6, -0.2, 0.9, ...]
"I love you" → [0.79, 0.61, -0.19, 0.88, ...]
"Te amo"     → [0.81, 0.59, -0.21, 0.91, ...]
              ↑ 这些向量在高维空间中极度接近

关键原理： 相同意思的不同语言表达，在模型内部指向同一个语义区域。

2. 处理流程

1
2
3
4
5
6
7
8
9

输入："量子计算的最新进展是什么？"
  ↓
Token化 + 嵌入层
  ↓
转换为语义向量（语言中立的数学表示）
  ↓
在向量空间中推理
  ↓
直接生成中文输出

没有中间的”英文文本”存在！

为什么会看到”英文思考”？

现象

用中文提问时，扩展思考过程显示英文。

原因

1. 推理训练主要在英文上进行 → 内部推理倾向用英文结构化
2. 搜索策略选择 → 英文资料更丰富，搜索时优先用英文关键词
3. 但这不是翻译！ → 是把抽象的语义概念用文字展示时选择了英文

类比

就像双语者思考时可能用某种语言，但这不代表他们翻译了你的问题——他们已经直接理解了概念本身。

跨语言对齐如何实现？

主要机制（~95%）：单语数据 + 共享参数

原理1：分布假说

1
2
3
4
5

"cat" 和 "猫" 出现的上下文高度相似
  ↓
模型推断它们应该表示相同概念
  ↓
在语义空间中映射到相近位置

原理2：共享参数强制对齐

1
2
3
4
5
6
7

同一个神经网络处理所有语言
  ↓
如果"France"和"法国"表示差异太大
  ↓
模型需要两套逻辑（但参数是共享的，做不到）
  ↓
最优策略：让它们的向量表示尽可能接近

原理3：跨语言上下文相似性

1
2
3
4
5
6

英文维基："Paris is the capital of France..."
中文维基："巴黎是法国的首都..."
  ↓
"Paris"和"巴黎"的"语义邻居"高度重叠
  ↓
模型推断它们指向同一事物

辅助机制（<5%）：平行对照数据

作用

1. 提供锚点 → 消除系统性偏移
2. 消除歧义 → 区分”bank”是”银行”还是”河岸”
3. 加速对齐 → 直接告诉模型对应关系

数据量

• 高质量翻译对：估计100万-1000万对
• 维基百科跨语言链接：百万级
• 总占比 < 5%，但作用关键

关键发现

1. 桥接语言现象

即使没有”中文↔法语”直接对照，只要有：

• 中文↔英语
• 英语↔法语

就能实现中文↔法语翻译（英语作为桥梁）

2. 零样本跨语言迁移

1
2
3

训练：英文问答 + 少量中英翻译（无问答）
结果：能回答中文问题！
原因：问答能力通过语义对齐自动迁移

3. 对齐的”突现”

训练过程中，各语言语义空间会突然快速对齐（相变现象）

最终答案总结

形象比喻

盖房子：

• 单语数据 = 砖块（主体结构，95%）
• 对照数据 = 水平仪（保证对齐，5%）

GPS定位：

• 单语学习 = 惯性导航（主要机制）
• 对照数据 = GPS校准信号（消除累积误差）

学外语：

• 单语数据 = 沉浸式学习（建立语感）
• 对照数据 = 偶尔查字典（消除疑惑）

为什么这能工作？

1. 世界是共享的 → 所有语言描述同一个现实
2. 语言结构的普遍性 → 主谓宾、因果关系等普遍存在
3. 压缩即对齐 → 统一表示比分离表示更节省参数

这是从海量数据中涌现（emerge）出来的能力，而非人为编程！

🧠 一、费曼学习法（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