《算法图解》读书笔记实战解读二分查找、图算法与动态规划在 LeetCode-Go 中的 Go 代码验证【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术指南以仓库内 《算法图解》笔记 为骨架逐条拆解二分查找、大 O 表示法、递归、散列表、广度优先搜索、迪杰斯特拉算法、贪心算法、NP 完全问题、动态规划以及布隆过滤器、Simhash 等核心概念并结合 LeetCode-Go 仓库中对应题目的 Go 实现与测试用例进行实战验证。读完本文你不仅能理解这些算法的适用前提与边界条件还能在 leetcode 目录中定位到每一类算法的真实代码与可运行测试建立读书笔记 → 源码实现 → 测试验证的完整学习闭环。一、二分查找有序是唯一前提笔记开篇就强调了一条最容易被人忽略的前提仅当列表是有序的时候二分查找才管用。二分查找Binary Search每一轮把搜索区间对半收缩通过比较中间元素与目标值的大小关系将查找范围缩小一半因此时间复杂度为 O(log n)。但这一切的前提是列表必须有序——如果列表无序二分查找的减半策略会丢失信息结果毫无意义。仓库中 704. Binary Search 的实现 是二分查找最标准的迭代模板func search704(nums []int, target int) int { low, high : 0, len(nums)-1 for low high { mid : low (high-low)1 if nums[mid] target { return mid } else if nums[mid] target { high mid - 1 } else { low mid 1 } } return -1 }这段代码有 3 个值得学习的细节循环不变式low high保证区间非空时才继续搜索low、high初始化为0与len(nums)-1全程闭合区间。防溢出写法mid : low (high-low)1用位运算替代(lowhigh)/2避免大数相加溢出同时1等价于整除 2。这也是 note/time_complexity.md 中递归版二分查找注释防溢出的原因。收缩方向nums[mid] target时目标在左半区high mid - 1反之low mid 1。注意mid本身已经被比较过所以收缩时要跳过它。对应的 704 测试用例 覆盖了命中与未命中两种场景在[-1,0,3,5,9,12]中查找 9 返回下标 4查找 2 返回 -1验证了search704在升序数组上的正确性。二分查找的变体在仓库中大量出现例如 35. Search Insert Position 解决找不到时返回应插入位置的问题逻辑上等价于寻找第一个不小于target的下标func searchInsert(nums []int, target int) int { low, high : 0, len(nums)-1 for low high { mid : low (high-low)1 if nums[mid] target { high mid - 1 } else { if (mid len(nums)-1) || (nums[mid1] target) { return mid 1 } low mid 1 } } return 0 }从数据规模看见 note/time_complexity.md 中的复杂度对照表O(log n) 的算法可以处理 10^10 级别的数据规模这正是二分查找在海量有序数据中依然高效的原因。二、大 O 表示法度量的是增速笔记中的第二条核心观点大 O 表示法指出了算法运行时间的增速算法运行时间是从其增速的角度度量的。大 O 不关心具体的执行秒数而是描述当输入规模 n 增大时运行时间增长的速度。例如 O(n) 意味着时间与输入规模线性相关O(n²) 意味着规模翻倍时时间变为 4 倍O(log n) 意味着规模翻倍时只多一次比较。note/time_complexity.md 给出了更细致的工程参考1 秒内能解决问题的数据规模约为 10^6 ~ 10^7。以此推算O(n²) 算法可处理 10^4 级别数据O(n) 算法可处理 10^8 级别数据O(nlog n) 算法可处理 10^7 级别数据O(log n) 算法可处理 10^10 级别数据典型如二分搜索O(1) 算法理论上不受数据规模影响典型如数学公式类题目。同时该笔记还提醒了几个具有迷惑性的复杂度外层循环sz每轮翻倍sz sz内层是 O(n)整体是 O(nlog n) 而非 O(n²)——因为外层实际只执行 log n 轮素数判断for x : 2; x*x n; x是 O(√n) 而非 O(n)字符串数组排序的复杂度要区分字符串长度 s 与数组长度 n 两个独立变量先对 n 个字符串各自排序是 O(n·slog s)再对整个数组按字典序排序是 O(s·nlog n)因为每次比较字符串要付出 O(s) 成本整体为 O(n·s·(log s log n))简单套用 O(nlog n n²log n) 的答案是错误的。可见大 O 分析不仅是理论概念更是评估解法能否通过评测的数据规模预判工具在 LeetCode 刷题中常被用来先估算时间复杂度、再决定选用哪种算法。三、递归基线条件与递归条件笔记引用了 Leigh Caldwell 在 Stack Overflow 上的一段话点出循环与递归的取舍如果使用循环程序的性能可能更高如果使用递归程序可能更容易理解。如何选择要看什么对你来说更重要。关于递归笔记给出了最核心的两条规律1. 每个递归函数都由两部分组成递归条件recursive case函数调用自己基线条件base case函数不再调用自己从而避免无限循环。2. 优化递归调用栈的两种方法重新编写代码转而使用循环使用尾递归笔记同时注明这是高级主题且并非所有语言都支持尾递归。此外还有一条非常实用的经验编写涉及数组的递归函数时基线条件通常是数组为空或只包含一个元素。这与归并排序、快速排序等分治算法的终止条件完全一致。note/time_complexity.md 进一步给出了递归的复杂度分析框架单次递归调用若递归深度为 depth、单次递归体内复杂度为 T则总体复杂度为 O(T × depth)。递归版二分查找每次只调用一次自身深度为 log n单次体内是 O(1)故整体为 O(log n)多次递归调用需要画递归树统计调用次数。例如f(n) f(n-1) f(n-1)的调用次数为 2^0 2^1 ... 2^n O(2^n)空间代价递归需要保存调用栈信息空间复杂度往往高于等价循环。同一个求和函数迭代版时间 O(n)、空间 O(1)递归版时间 O(n)、空间 O(n)。该笔记还指出Haskell 等函数式编程语言没有循环只能靠递归因此深入理解递归是学习函数式语言的前置条件。仓库中leetcode目录有大量递归题解例如树的遍历、回溯搜索0078.Subsets、0090.Subsets-II等组合/子集问题都依赖基线条件 递归条件的结构可作为递归的进阶练习。四、散列表低装填因子 良好散列函数笔记对散列表Hash Table给出了简洁的工程结论散列表要避免冲突需要有较低的装填因子、良好的散列函数。装填因子load factor 散列表中的元素数 / 位置总数。装填因子越低冲突概率越低查找性能越好当装填因子过大时应扩容。散列函数应尽量将键均匀地映射到整个散列表地址空间避免大量键被映射到同一槽位形成聚集。Go 语言中 map 正是散列表的标准实现仓库中大量题目以 map 作为核心数据结构例如哈希计数、两数之和、滑动窗口去重等场景。structures目录中还包含自定义数据结构的实现可与 note/grokking_algorithms.md 中散列表的知识点互相印证。五、图与广度优先搜索检查过的节点不要重复检查笔记对图的基础概念做了两点定义有向图边为箭头箭头的方向指定了关系的方向无向图边不带箭头关系是双向的。针对最短路径问题笔记强调广度优先搜索BFS的黄金法则广度优先搜索求最短路径对于检查过的点务必不要再去检查否则会导致无限循环。BFS 按层级逐层向外扩散第一次到达某节点时走过的路径就是最短路径如果重复检查已访问节点既可能陷入环路的死循环也会破坏先到先得的最短路径性质。实现上通常用队列存储待访问节点、用 visited 集合记录已检查节点。仓库中0200.Number-of-Islands岛屿数量、0127.Word-Ladder单词接龙BFS 求最短变换次数等题目都是 BFS 的典型应用其中单词接龙一题与笔记中BFS 求最短路径的场景完全对应。六、迪杰斯特拉算法与贝尔曼-福德算法边权的前提约束笔记对最短路径算法给出了两个精确的适用条件在无向图中每条边都是一个环。迪杰斯特拉算法只能用于有向无环图DAG如果有负权边就不能使用迪杰斯特拉算法。在有负权边的图中要求最短路径需要用到贝尔曼-福德算法Bellman-Ford algorithm。迪杰斯特拉Dijkstra算法采用贪心策略每次从未确定最短路径的节点中选出当前距离最小的节点进行松弛。它无法处理负权边是因为一旦出现负权边之前贪心确定的最短路径可能被后续的负权边推翻。而贝尔曼-福德算法通过对所有边进行 V-1 轮松弛能正确处理负权边只要不存在负权环。笔记的这条边界条件在工程中非常重要——选错算法不只是性能问题而是结果正确性的问题。七、贪心算法与 NP 完全问题笔记对贪心算法给出了一句精炼概括贪心算法的理念每步都采取最优解。每步都选择局部最优解最终得到的就是全局最优解。贪心算法在每步局部最优 全局最优成立的问题上如部分背包问题、活动选择非常高效但在很多问题上局部最优并不等于全局最优此时强行贪心会得到次优解。关于NP 完全问题笔记给出了 6 条实用的判断线索元素较少时运行很快但随元素数量增加速度急剧变慢涉及所有组合的问题通常是 NP 完全问题不能将问题分成小问题必须考虑各种可能的情况问题涉及序列如旅行商问题中的城市序列且难以解决问题涉及集合如广播台集合且难以解决问题可转换为集合覆盖问题或旅行商问题。面对 NP 完全问题笔记给出了清醒的建议对于 NP 完全问题还没有找到快速解决方案面临 NP 完全问题最佳的做法是使用近似算法。近似算法放弃绝对最优换取足够接近最优 多项式时间这是工程中处理 NP 完全问题的现实策略。八、动态规划离散子问题 网格 一门艺术笔记对动态规划Dynamic Programming给出了三条核心论断仅当每个子问题都是离散的即不依赖于其他子问题时动态规划才管用每种动态规划解决方案都涉及网格没有放之四海皆准的计算动态规划的公式动态规划是一门艺术。离散子问题意味着每个子问题可以独立求解子问题之间不构成循环依赖否则是图搜索问题而非 DP 问题。网格指 DP 表——经典例题如背包问题、最长公共子串/子序列状态转移都是在一张表格上逐格推进的。笔记还提到一个有趣的工程事实git diff 命令指出两个文件的差异使用的就是动态规划实现的——它本质上是在求解两个文本序列的最长公共子序列LCS与 LeetCode 1143. Longest Common Subsequence 是同一类问题。仓库中有大量 DP 题解可以对照验证例如House Robber一维 DPdp[i]代表抢nums[0...i]的最大收益状态转移为dp[i] max(dp[i-1], nums[i]dp[i-2])并附有滚动变量优化空间到 O(1) 的第二版实现func rob198(nums []int) int { n : len(nums) if n 0 { return 0 } if n 1 { return nums[0] } dp : make([]int, n) dp[0], dp[1] nums[0], max(nums[1], nums[0]) for i : 2; i n; i { dp[i] max(dp[i-1], nums[i]dp[i-2]) } return dp[n-1] }Coin Change完全背包型 DPdp[i]表示凑出金额 i 的最少硬币数dp[i] min(dp[i], dp[i-coins[j]]1)无法凑出时返回 -1func coinChange(coins []int, amount int) int { dp : make([]int, amount1) dp[0] 0 for i : 1; i len(dp); i { dp[i] amount 1 } for i : 1; i amount; i { for j : 0; j len(coins); j { if coins[j] i { dp[i] min(dp[i], dp[i-coins[j]]1) } } } if dp[amount] amount { return -1 } return dp[amount] }网格型 DP 的代表作0062.Unique-Paths、0064.Minimum-Path-Sum网格上逐格递推、0120.Triangle三角形网格自底向上递推、0300.Longest-Increasing-Subsequence子序列型 DP、0213.House-Robber-II环形结构拆分为两个线性 DP、0337.House-Robber-III树形 DP。对比这些题目可以体会到笔记动态规划是一门艺术的含义虽然都叫 DP但状态定义、转移方程、遍历顺序因问题而异需要针对具体问题设计网格与转移规则。九、概率型数据结构与散列函数布隆过滤器、Simhash笔记最后一部分介绍了三类与近似答案相关的技术1. 布隆过滤器Bloom Filter布隆过滤器是一个概率型数据结构它提供的答案有可能不对但很可能是正确的。可能出现错报的情况但是不可能出现漏报的情况。布隆过滤器非常适合用于不要求答案绝对准确的情况。布隆过滤器用多个散列函数将元素映射到位数组的若干位上。查询时若任一对应位为 0则元素必然不在不会漏报若所有位为 1则元素可能在可能错报。因此它的误判方向是可能把不存在的元素误报为存在绝不会漏掉真实存在的元素。它常用于防止缓存穿透、URL 去重等海量场景。2. bcrypt 与 SHA当前最安全的密码散列函数是 bcrypt但没有任何东西是万无一失的。bcrypt 内置盐值与可调计算代价是目前密码存储的主流选择SHA 散列函数是局部不敏感的——输入哪怕只有一个字符变化散列值也会截然不同因此适合做完整性校验不适合做相似度度量。3. Simhash局部敏感散列Simhash 对字符串做细微的修改生成的散列值也只存在细微的差别。这让你能够通过比较散列值来判断两个字符串的相似程度。笔记给出了三个经典应用场景Google 使用 Simhash 判断网页是否已搜集爬虫去重老师可以用 Simhash 判断学生论文是否抄袭Scribd 用 Simhash 检测用户上传内容是否与出版小说相似相似则自动拒绝。Simhash 与 SHA 形成鲜明对比前者相似输入 → 相似散列值后者相似输入 → 完全不同散列值。需要判断两项内容是否相似时Simhash 类局部敏感散列LSH是首选。笔记还总结了一条通用策略面临海量数据且只要求答案八九不离十时可考虑使用概率型算法。这与布隆过滤器允许错报、拒绝漏报、Simhash允许少量差异、度量相似度的定位一脉相承当精确计算代价过高时用可控的误差换取数量级上的性能提升是工程上的重要权衡。十、总结一条可执行的算法学习路线将 《算法图解》笔记 的全部要点串起来可以整理出一条主线清晰的算法知识框架主题核心结论仓库实战对应二分查找仅有序列表可用O(log n)0704. Binary Search、0035. Search Insert Position大 O 表示法度量增速不度量绝对时间note/time_complexity.md 数据规模对照表递归基线条件 递归条件注意调用栈代价回溯类题目子集、组合、排列散列表低装填因子 良好散列函数Go map 及structures自定义结构BFS最短路径检查过的节点不重复检查岛屿数量、单词接龙等图遍历题Dijkstra / Bellman-Ford仅适用于有向无环图负权边用贝尔曼-福德带权最短路相关题目贪心与 NP 完全局部最优≠全局最优NP 完全用近似算法贪心类题目动态规划离散子问题、网格、无固定公式198. House Robber、322. Coin Change、62. Unique Paths 等概率型算法布隆过滤器不漏报、可错报Simhash 度量相似度海量去重/查重场景建议的学习路径是先精读 note/grokking_algorithms.md 建立概念框架再对照 note/time_complexity.md 补齐复杂度分析能力最后回到leetcode目录按图索骥找到每类算法的 Go 实现与测试用例亲自运行验证。这样概念 → 复杂度 → 实现 → 测试四步走恰好对应了算法学习从理解到掌握的全过程。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/13 12:23:41 · 阅读 1.2k 《算法图解》读书笔记实战解读：二分查找、图算法与动态规划在 LeetCode-Go 中的 Go 代码验证
《算法图解》读书笔记实战解读二分查找、图算法与动态规划在 LeetCode-Go 中的 Go 代码验证【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术指南以仓库内 《算法图解》笔记 为骨架逐条拆解二分查找、大 O 表示法、递归、散列表、广度优先搜索、迪杰斯特拉算法、贪心算法、NP 完全问题、动态规划以及布隆过滤器、Simhash 等核心概念并结合 LeetCode-Go 仓库中对应题目的 Go 实现与测试用例进行实战验证。读完本文你不仅能理解这些算法的适用前提与边界条件还能在 leetcode 目录中定位到每一类算法的真实代码与可运行测试建立读书笔记 → 源码实现 → 测试验证的完整学习闭环。一、二分查找有序是唯一前提笔记开篇就强调了一条最容易被人忽略的前提仅当列表是有序的时候二分查找才管用。二分查找Binary Search每一轮把搜索区间对半收缩通过比较中间元素与目标值的大小关系将查找范围缩小一半因此时间复杂度为 O(log n)。但这一切的前提是列表必须有序——如果列表无序二分查找的减半策略会丢失信息结果毫无意义。仓库中 704. Binary Search 的实现 是二分查找最标准的迭代模板func search704(nums []int, target int) int { low, high : 0, len(nums)-1 for low high { mid : low (high-low)1 if nums[mid] target { return mid } else if nums[mid] target { high mid - 1 } else { low mid 1 } } return -1 }这段代码有 3 个值得学习的细节循环不变式low high保证区间非空时才继续搜索low、high初始化为0与len(nums)-1全程闭合区间。防溢出写法mid : low (high-low)1用位运算替代(lowhigh)/2避免大数相加溢出同时1等价于整除 2。这也是 note/time_complexity.md 中递归版二分查找注释防溢出的原因。收缩方向nums[mid] target时目标在左半区high mid - 1反之low mid 1。注意mid本身已经被比较过所以收缩时要跳过它。对应的 704 测试用例 覆盖了命中与未命中两种场景在[-1,0,3,5,9,12]中查找 9 返回下标 4查找 2 返回 -1验证了search704在升序数组上的正确性。二分查找的变体在仓库中大量出现例如 35. Search Insert Position 解决找不到时返回应插入位置的问题逻辑上等价于寻找第一个不小于target的下标func searchInsert(nums []int, target int) int { low, high : 0, len(nums)-1 for low high { mid : low (high-low)1 if nums[mid] target { high mid - 1 } else { if (mid len(nums)-1) || (nums[mid1] target) { return mid 1 } low mid 1 } } return 0 }从数据规模看见 note/time_complexity.md 中的复杂度对照表O(log n) 的算法可以处理 10^10 级别的数据规模这正是二分查找在海量有序数据中依然高效的原因。二、大 O 表示法度量的是增速笔记中的第二条核心观点大 O 表示法指出了算法运行时间的增速算法运行时间是从其增速的角度度量的。大 O 不关心具体的执行秒数而是描述当输入规模 n 增大时运行时间增长的速度。例如 O(n) 意味着时间与输入规模线性相关O(n²) 意味着规模翻倍时时间变为 4 倍O(log n) 意味着规模翻倍时只多一次比较。note/time_complexity.md 给出了更细致的工程参考1 秒内能解决问题的数据规模约为 10^6 ~ 10^7。以此推算O(n²) 算法可处理 10^4 级别数据O(n) 算法可处理 10^8 级别数据O(nlog n) 算法可处理 10^7 级别数据O(log n) 算法可处理 10^10 级别数据典型如二分搜索O(1) 算法理论上不受数据规模影响典型如数学公式类题目。同时该笔记还提醒了几个具有迷惑性的复杂度外层循环sz每轮翻倍sz sz内层是 O(n)整体是 O(nlog n) 而非 O(n²)——因为外层实际只执行 log n 轮素数判断for x : 2; x*x n; x是 O(√n) 而非 O(n)字符串数组排序的复杂度要区分字符串长度 s 与数组长度 n 两个独立变量先对 n 个字符串各自排序是 O(n·slog s)再对整个数组按字典序排序是 O(s·nlog n)因为每次比较字符串要付出 O(s) 成本整体为 O(n·s·(log s log n))简单套用 O(nlog n n²log n) 的答案是错误的。可见大 O 分析不仅是理论概念更是评估解法能否通过评测的数据规模预判工具在 LeetCode 刷题中常被用来先估算时间复杂度、再决定选用哪种算法。三、递归基线条件与递归条件笔记引用了 Leigh Caldwell 在 Stack Overflow 上的一段话点出循环与递归的取舍如果使用循环程序的性能可能更高如果使用递归程序可能更容易理解。如何选择要看什么对你来说更重要。关于递归笔记给出了最核心的两条规律1. 每个递归函数都由两部分组成递归条件recursive case函数调用自己基线条件base case函数不再调用自己从而避免无限循环。2. 优化递归调用栈的两种方法重新编写代码转而使用循环使用尾递归笔记同时注明这是高级主题且并非所有语言都支持尾递归。此外还有一条非常实用的经验编写涉及数组的递归函数时基线条件通常是数组为空或只包含一个元素。这与归并排序、快速排序等分治算法的终止条件完全一致。note/time_complexity.md 进一步给出了递归的复杂度分析框架单次递归调用若递归深度为 depth、单次递归体内复杂度为 T则总体复杂度为 O(T × depth)。递归版二分查找每次只调用一次自身深度为 log n单次体内是 O(1)故整体为 O(log n)多次递归调用需要画递归树统计调用次数。例如f(n) f(n-1) f(n-1)的调用次数为 2^0 2^1 ... 2^n O(2^n)空间代价递归需要保存调用栈信息空间复杂度往往高于等价循环。同一个求和函数迭代版时间 O(n)、空间 O(1)递归版时间 O(n)、空间 O(n)。该笔记还指出Haskell 等函数式编程语言没有循环只能靠递归因此深入理解递归是学习函数式语言的前置条件。仓库中leetcode目录有大量递归题解例如树的遍历、回溯搜索0078.Subsets、0090.Subsets-II等组合/子集问题都依赖基线条件 递归条件的结构可作为递归的进阶练习。四、散列表低装填因子 良好散列函数笔记对散列表Hash Table给出了简洁的工程结论散列表要避免冲突需要有较低的装填因子、良好的散列函数。装填因子load factor 散列表中的元素数 / 位置总数。装填因子越低冲突概率越低查找性能越好当装填因子过大时应扩容。散列函数应尽量将键均匀地映射到整个散列表地址空间避免大量键被映射到同一槽位形成聚集。Go 语言中 map 正是散列表的标准实现仓库中大量题目以 map 作为核心数据结构例如哈希计数、两数之和、滑动窗口去重等场景。structures目录中还包含自定义数据结构的实现可与 note/grokking_algorithms.md 中散列表的知识点互相印证。五、图与广度优先搜索检查过的节点不要重复检查笔记对图的基础概念做了两点定义有向图边为箭头箭头的方向指定了关系的方向无向图边不带箭头关系是双向的。针对最短路径问题笔记强调广度优先搜索BFS的黄金法则广度优先搜索求最短路径对于检查过的点务必不要再去检查否则会导致无限循环。BFS 按层级逐层向外扩散第一次到达某节点时走过的路径就是最短路径如果重复检查已访问节点既可能陷入环路的死循环也会破坏先到先得的最短路径性质。实现上通常用队列存储待访问节点、用 visited 集合记录已检查节点。仓库中0200.Number-of-Islands岛屿数量、0127.Word-Ladder单词接龙BFS 求最短变换次数等题目都是 BFS 的典型应用其中单词接龙一题与笔记中BFS 求最短路径的场景完全对应。六、迪杰斯特拉算法与贝尔曼-福德算法边权的前提约束笔记对最短路径算法给出了两个精确的适用条件在无向图中每条边都是一个环。迪杰斯特拉算法只能用于有向无环图DAG如果有负权边就不能使用迪杰斯特拉算法。在有负权边的图中要求最短路径需要用到贝尔曼-福德算法Bellman-Ford algorithm。迪杰斯特拉Dijkstra算法采用贪心策略每次从未确定最短路径的节点中选出当前距离最小的节点进行松弛。它无法处理负权边是因为一旦出现负权边之前贪心确定的最短路径可能被后续的负权边推翻。而贝尔曼-福德算法通过对所有边进行 V-1 轮松弛能正确处理负权边只要不存在负权环。笔记的这条边界条件在工程中非常重要——选错算法不只是性能问题而是结果正确性的问题。七、贪心算法与 NP 完全问题笔记对贪心算法给出了一句精炼概括贪心算法的理念每步都采取最优解。每步都选择局部最优解最终得到的就是全局最优解。贪心算法在每步局部最优 全局最优成立的问题上如部分背包问题、活动选择非常高效但在很多问题上局部最优并不等于全局最优此时强行贪心会得到次优解。关于NP 完全问题笔记给出了 6 条实用的判断线索元素较少时运行很快但随元素数量增加速度急剧变慢涉及所有组合的问题通常是 NP 完全问题不能将问题分成小问题必须考虑各种可能的情况问题涉及序列如旅行商问题中的城市序列且难以解决问题涉及集合如广播台集合且难以解决问题可转换为集合覆盖问题或旅行商问题。面对 NP 完全问题笔记给出了清醒的建议对于 NP 完全问题还没有找到快速解决方案面临 NP 完全问题最佳的做法是使用近似算法。近似算法放弃绝对最优换取足够接近最优 多项式时间这是工程中处理 NP 完全问题的现实策略。八、动态规划离散子问题 网格 一门艺术笔记对动态规划Dynamic Programming给出了三条核心论断仅当每个子问题都是离散的即不依赖于其他子问题时动态规划才管用每种动态规划解决方案都涉及网格没有放之四海皆准的计算动态规划的公式动态规划是一门艺术。离散子问题意味着每个子问题可以独立求解子问题之间不构成循环依赖否则是图搜索问题而非 DP 问题。网格指 DP 表——经典例题如背包问题、最长公共子串/子序列状态转移都是在一张表格上逐格推进的。笔记还提到一个有趣的工程事实git diff 命令指出两个文件的差异使用的就是动态规划实现的——它本质上是在求解两个文本序列的最长公共子序列LCS与 LeetCode 1143. Longest Common Subsequence 是同一类问题。仓库中有大量 DP 题解可以对照验证例如House Robber一维 DPdp[i]代表抢nums[0...i]的最大收益状态转移为dp[i] max(dp[i-1], nums[i]dp[i-2])并附有滚动变量优化空间到 O(1) 的第二版实现func rob198(nums []int) int { n : len(nums) if n 0 { return 0 } if n 1 { return nums[0] } dp : make([]int, n) dp[0], dp[1] nums[0], max(nums[1], nums[0]) for i : 2; i n; i { dp[i] max(dp[i-1], nums[i]dp[i-2]) } return dp[n-1] }Coin Change完全背包型 DPdp[i]表示凑出金额 i 的最少硬币数dp[i] min(dp[i], dp[i-coins[j]]1)无法凑出时返回 -1func coinChange(coins []int, amount int) int { dp : make([]int, amount1) dp[0] 0 for i : 1; i len(dp); i { dp[i] amount 1 } for i : 1; i amount; i { for j : 0; j len(coins); j { if coins[j] i { dp[i] min(dp[i], dp[i-coins[j]]1) } } } if dp[amount] amount { return -1 } return dp[amount] }网格型 DP 的代表作0062.Unique-Paths、0064.Minimum-Path-Sum网格上逐格递推、0120.Triangle三角形网格自底向上递推、0300.Longest-Increasing-Subsequence子序列型 DP、0213.House-Robber-II环形结构拆分为两个线性 DP、0337.House-Robber-III树形 DP。对比这些题目可以体会到笔记动态规划是一门艺术的含义虽然都叫 DP但状态定义、转移方程、遍历顺序因问题而异需要针对具体问题设计网格与转移规则。九、概率型数据结构与散列函数布隆过滤器、Simhash笔记最后一部分介绍了三类与近似答案相关的技术1. 布隆过滤器Bloom Filter布隆过滤器是一个概率型数据结构它提供的答案有可能不对但很可能是正确的。可能出现错报的情况但是不可能出现漏报的情况。布隆过滤器非常适合用于不要求答案绝对准确的情况。布隆过滤器用多个散列函数将元素映射到位数组的若干位上。查询时若任一对应位为 0则元素必然不在不会漏报若所有位为 1则元素可能在可能错报。因此它的误判方向是可能把不存在的元素误报为存在绝不会漏掉真实存在的元素。它常用于防止缓存穿透、URL 去重等海量场景。2. bcrypt 与 SHA当前最安全的密码散列函数是 bcrypt但没有任何东西是万无一失的。bcrypt 内置盐值与可调计算代价是目前密码存储的主流选择SHA 散列函数是局部不敏感的——输入哪怕只有一个字符变化散列值也会截然不同因此适合做完整性校验不适合做相似度度量。3. Simhash局部敏感散列Simhash 对字符串做细微的修改生成的散列值也只存在细微的差别。这让你能够通过比较散列值来判断两个字符串的相似程度。笔记给出了三个经典应用场景Google 使用 Simhash 判断网页是否已搜集爬虫去重老师可以用 Simhash 判断学生论文是否抄袭Scribd 用 Simhash 检测用户上传内容是否与出版小说相似相似则自动拒绝。Simhash 与 SHA 形成鲜明对比前者相似输入 → 相似散列值后者相似输入 → 完全不同散列值。需要判断两项内容是否相似时Simhash 类局部敏感散列LSH是首选。笔记还总结了一条通用策略面临海量数据且只要求答案八九不离十时可考虑使用概率型算法。这与布隆过滤器允许错报、拒绝漏报、Simhash允许少量差异、度量相似度的定位一脉相承当精确计算代价过高时用可控的误差换取数量级上的性能提升是工程上的重要权衡。十、总结一条可执行的算法学习路线将 《算法图解》笔记 的全部要点串起来可以整理出一条主线清晰的算法知识框架主题核心结论仓库实战对应二分查找仅有序列表可用O(log n)0704. Binary Search、0035. Search Insert Position大 O 表示法度量增速不度量绝对时间note/time_complexity.md 数据规模对照表递归基线条件 递归条件注意调用栈代价回溯类题目子集、组合、排列散列表低装填因子 良好散列函数Go map 及structures自定义结构BFS最短路径检查过的节点不重复检查岛屿数量、单词接龙等图遍历题Dijkstra / Bellman-Ford仅适用于有向无环图负权边用贝尔曼-福德带权最短路相关题目贪心与 NP 完全局部最优≠全局最优NP 完全用近似算法贪心类题目动态规划离散子问题、网格、无固定公式198. House Robber、322. Coin Change、62. Unique Paths 等概率型算法布隆过滤器不漏报、可错报Simhash 度量相似度海量去重/查重场景建议的学习路径是先精读 note/grokking_algorithms.md 建立概念框架再对照 note/time_complexity.md 补齐复杂度分析能力最后回到leetcode目录按图索骥找到每类算法的 Go 实现与测试用例亲自运行验证。这样概念 → 复杂度 → 实现 → 测试四步走恰好对应了算法学习从理解到掌握的全过程。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考