1. 算法练习的价值与我的日常实践作为一名长期与代码和逻辑打交道的开发者我始终认为算法能力是程序员的内功它决定了你解决问题的深度和效率上限。很多人把算法练习等同于“刷题”为了面试而突击这其实是一种误解。真正的算法练习是一种思维体操是持续保持对问题抽象、逻辑拆解和方案优化敏感度的日常习惯。我给自己定了个规矩无论多忙每周都要抽出固定时间针对性地练习几个算法问题9月13日这天也不例外。这不仅仅是完成几道题目而是通过这个过程复盘自己近期的知识盲区探索一些新出现的算法思想或者将经典算法应用到新的场景中去琢磨。今天想和大家分享的就是我在一次日常练习中围绕几个关键词展开的深度思考与实践涉及排序、图论、搜索优化等多个方面希望能给你带来一些不一样的启发。2. 从经典排序出发堆排序的现代理解与性能深潜当天的练习我决定从最基础的排序算法重新审视。排序是算法的基石而堆排序在其中以其稳定的O(n log n)时间复杂度和O(1)的空间复杂度如果不算递归栈著称。但教科书上的讲解往往止步于原理在实际应用中我们更需要理解它的微观性能和行为。2.1 堆排序的核心不仅是“排序”更是“选择”堆排序的本质可以看作是一种高效的“选择排序”。普通选择排序每次从未排序部分选出最小或最大值需要O(n)时间而堆特别是二叉堆这种数据结构能在O(log n)的时间内完成元素的插入和删除最值操作。堆排序就是利用最大堆或最小堆反复取出堆顶元素当前最值的过程。我写了一个简单的最大堆排序的C核心代码片段来重温这个过程void heapify(vectorint arr, int n, int i) { int largest i; // 初始化最大值为根节点 int left 2 * i 1; int right 2 * i 2; // 如果左子节点存在且大于根 if (left n arr[left] arr[largest]) largest left; // 如果右子节点存在且大于当前最大值 if (right n arr[right] arr[largest]) largest right; // 如果最大值不是根节点 if (largest ! i) { swap(arr[i], arr[largest]); // 递归地堆化受影响的子堆 heapify(arr, n, largest); } } void heapSort(vectorint arr) { int n arr.size(); // 构建最大堆从最后一个非叶子节点开始 for (int i n / 2 - 1; i 0; i--) heapify(arr, n, i); // 一个个从堆顶取出元素 for (int i n - 1; i 0; i--) { swap(arr[0], arr[i]); // 将当前堆顶最大值移到数组末尾 heapify(arr, i, 0); // 对剩余元素重新堆化 } }注意heapify函数的时间复杂度是O(log n)因为它只需要沿着树的一条路径向下比较。整个堆排序的时间复杂度为O(n log n)其中建堆过程是O(n)这是一个常常被忽略但非常重要的结论可以通过数学推导证明。2.2 实践中的性能考量与“八大排序”的选型思考提到C八大排序算法通常指冒泡、选择、插入、希尔、归并、快速、堆排序和基数排序。在练习中我习惯性地对比它们。对于几乎有序的数据插入排序效率惊人当数据量巨大且对最坏情况有要求时堆排序的稳定性这里指时间复杂度稳定非排序稳定性是优势而快速排序在平均情况下的常数因子最小是实践中的通用王者。但现代开发中我们很少自己实现排序。C的std::sort通常基于内省排序IntroSort它是快速排序、堆排序和插入排序的混合体会根据递归深度和数据规模智能切换算法以规避快排的最坏情况。理解这些底层算法正是为了在需要定制排序规则如复杂对象的多关键字排序、优化特定场景如链表排序用归并更优或在资源极端受限的环境如嵌入式系统堆排序的原地特性宝贵下能做出最合适的选择。3. 图论算法的实战演绎Dijkstra与A*的路径寻找哲学练习的第二个主题是图论算法。我选取了Dijkstra算法和A*算法进行对比实现这是解决最短路径问题的两大利器尤其在AGV自动导引运输车调度、游戏AI、地图导航中应用广泛。3.1 Dijkstra算法稳健的全局探索者Dijkstra算法的核心思想是贪心策略它从源点出发逐步扩展到距离最短的未访问节点直到覆盖目标点或所有点。它保证找到的是单源最短路径适用于边权非负的图。我实现了一个基于优先队列最小堆的Dijkstra这是效率最高的通用实现方式vectorint dijkstra(vectorvectorpairint, int graph, int start) { int n graph.size(); vectorint dist(n, INT_MAX); dist[start] 0; priority_queuepairint, int, vectorpairint, int, greater pq; // 最小堆 pq.emplace(0, start); while (!pq.empty()) { auto [currentDist, u] pq.top(); pq.pop(); if (currentDist dist[u]) continue; // 跳过已过时的信息 for (auto [v, weight] : graph[u]) { int newDist currentDist weight; if (newDist dist[v]) { dist[v] newDist; pq.emplace(newDist, v); } } } return dist; }这个实现的时间复杂度是O((VE) log V)其中V是顶点数E是边数。贪心算法在这里的体现是每次从优先队列中取出当前已知距离最短的节点并认为这个距离就是最终最短距离。这是一种“目光短浅”却最终正确的策略。3.2 A*算法启发式引导的智能搜索A*算法可以看作是Dijkstra算法的增强版为Dijkstra加入了启发式函数h(n)用于估算从当前节点n到目标点的代价。其优先级队列的排序依据从f(n) g(n)Dijkstrag(n)是实际代价变成了f(n) g(n) h(n)。一个经典的比喻是Dijkstra像是一个在黑暗中摸索、均匀向四周扩散的人而A*则像是一个拿着模糊地图启发函数的人虽然也摸索但会优先朝目标的大致方向前进。在三条AGV基本A*算法这个场景下A的优势非常明显。仓库地图可以建模为网格启发函数常使用曼哈顿距离或欧几里得距离。这能极大地减少需要探索的网格数量加快为每台AGV规划路径的速度。但这里有个关键点启发函数h(n)必须满足可采纳性admissible即永不高于实际代价和一致性consistent否则A无法保证找到最优路径。提示在实现A*时除了维护g值和f值通常还需要一个came_from字典来记录路径以便最后回溯。对于网格地图启发函数的选择直接影响效率曼哈顿距离适用于只能四方向移动的场景欧几里得距离适用于可八方向移动的场景。3.3 对比与选型何时用谁Dijkstra当你需要知道从起点到所有其他点的最短路径时或者图中存在负权边时需使用Bellman-FordDijkstra或其变体是首选。它稳健不依赖任何对目标的先验知识。A*当你只需要知道从起点到单一目标点的最短路径并且有一个良好的启发式函数时A*通常远快于Dijkstra。在游戏、机器人路径规划如AGV、地图导航中几乎是标准选择。这次练习让我再次体会到没有绝对最好的算法只有在特定约束和场景下最合适的算法。例如在动态变化的场景中可能需要结合D* Lite等增量搜索算法。4. 字符串匹配的艺术KMP算法原理与实现陷阱字符串匹配是另一个基础且重要的领域。我选择重温KMP算法Knuth-Morris-Pratt。相比于暴力匹配的O(m*n)复杂度KMP能在O(mn)的时间内完成匹配其核心在于当匹配失败时模式串能利用已匹配的信息“智能”地滑动而不是傻傻地只移动一位。4.1 理解Next数组KMP的灵魂KMP最难理解的部分就是next数组或称部分匹配表。next[j]表示模式串P中从开头到位置j的子串中其最长相等前后缀的长度。这个数组告诉我们当在j位置匹配失败时模式串应该回退到哪个位置继续与主串当前字符比较。构建next数组的过程本身就是一个“自我匹配”vectorint buildNext(const string pattern) { int m pattern.length(); vectorint next(m, 0); int j 0; // 指向前缀末尾 for (int i 1; i m; i) { // i指向后缀末尾 while (j 0 pattern[i] ! pattern[j]) { j next[j - 1]; // 不匹配回退j } if (pattern[i] pattern[j]) { j; } next[i] j; } return next; }4.2 常见实现陷阱与调试心得在实现KMP时最容易出错的地方有两个next数组的定义和初始化有的定义中next[0] -1这会导致后续循环判断条件略有不同。我更喜欢上述next[0]0的定义逻辑更统一。关键是理解其含义并能正确推导出简单模式串如“ababc”的next数组。匹配过程中的回退逻辑在while循环中回退j时必须确保j 0否则会死循环或越界。一个实用的调试方法是用小的测试用例主串“aabaabaaf”模式串“aabaaf”手工模拟算法过程并打印出每一步的i、j和next[j]值。理解KMP不仅能解决字符串匹配问题其“利用已有信息避免重复比较”的思想在解决其他子串、子序列问题时也很有启发。例如循环节判断、最短回文串添加等问题都可以通过计算next数组的变体来解决。5. 面对迷宫问题回溯与搜索算法的策略抉择P1238走迷宫这类题目是练习搜索算法的经典场景。它通常要求输出所有可能的路径并且可能要求按特定顺序比如字典序。这立刻让我想到了深度优先搜索DFS和回溯法。5.1 DFS回溯枚举所有可能路径走迷宫问题的标准解法是DFS因为需要探索到终点才能形成一条完整路径。回溯则是DFS中“恢复现场”的关键步骤。vectorvectorint directions {{0,1},{1,0},{0,-1},{-1,0}}; // 方向数组方便控制搜索顺序 vectorstring path; // 记录当前路径 vectorvectorstring allPaths; // 记录所有路径 void dfs(vectorvectorint maze, int x, int y, vectorvectorbool visited) { int m maze.size(), n maze[0].size(); // 到达终点 if (x m-1 y n-1) { allPaths.push_back(path); return; } // 遍历四个方向 for (auto dir : directions) { int nx x dir[0], ny y dir[1]; // 检查边界、可通行性、是否访问过 if (nx 0 nx m ny 0 ny n maze[nx][ny] 0 !visited[nx][ny]) { visited[nx][ny] true; path.push_back(( to_string(nx) , to_string(ny) )); dfs(maze, nx, ny, visited); // 回溯恢复现场 path.pop_back(); visited[nx][ny] false; } } }5.2 关于“P1238是什么算法”的思考网络上有人问“P1238走迷宫是什么算法”这其实反映了初学者的一种困惑面对问题如何选择算法对于走迷宫并输出所有路径如果只问能否到达或最短步数BFS通常是更好的选择因为它能天然地按层搜索最先找到的就是最短路径。如果要求输出所有路径或路径本身DFS回溯是更直接的选择因为它能自然地记录和回溯整条路径。如果迷宫非常大或者有特殊性质如只有少数障碍A*等启发式搜索也可以考虑但实现起来比DFS复杂。所以P1238代表的不是某个特定算法而是一类搜索问题。解题的关键在于根据题目具体要求是否需要路径、是否要求最优、数据规模选择合适的搜索策略并熟练地实现它。这比死记硬背算法模板重要得多。6. 算法思想的延伸从贪心到动态规划的思维跨越在练习中我还刻意对比了贪心算法和动态规划DP。贪心算法在每一步都做出局部最优选择希望导致全局最优。Dijkstra算法中选取当前距离最短的节点就是一种贪心策略。但贪心不是万能的它需要问题具有“贪心选择性质”和“最优子结构”。例如经典的“找零钱”问题用最少的硬币凑出某个金额如果硬币面额是常规的1、5、10、25贪心每次选最大面额是有效的。但如果面额是1、3、4要凑出6贪心会选411三枚而最优解是33两枚。这时就需要用动态规划来求解。动态规划通过保存子问题的解来避免重复计算核心是定义状态和状态转移方程。我从贪心练习跳到DP练习比如经典的“0-1背包问题”这种思维切换的练习能有效提升对问题本质的洞察力。贪心是“一条路走到黑”DP是“记住走过的路步步为营”。理解它们的区别和联系才能在面对新问题时快速判断可能的解法方向。7. 算法工具箱的持续更新关注前沿与工业实践日常算法练习不能只停留在经典问题上。根据热搜词我也花时间了解了一些更前沿或工业界热门的算法概念这能拓宽视野知道经典算法是如何被应用和扩展的。增量式PID算法这是工业控制领域的核心。经典PID算法输出控制量u(t) Kpe(t) Ki∫e(t)dt Kd*de(t)/dt。而增量式PID计算的是控制量的增量Δu(t)它只与最近几次的偏差有关输出更平滑对执行机构更友好且不易产生积分饱和在单片机等嵌入式系统中实现更方便。理解它需要扎实的数学和控制理论背景。LSTM算法训练和推理作为循环神经网络RNN的变体LSTM通过门控机制解决了长序列依赖问题。在练习中我虽然不会去手写LSTM的反向传播但会通过框架如PyTorch实践一个简单的时序预测任务理解其input gate,forget gate,output gate的作用并关注其训练时间长、需GPU和推理相对快阶段的不同特点。联邦平均算法这是联邦学习中的核心协同训练算法。在数据隐私要求高的场景下多个客户端在本地训练模型只将模型参数更新而非数据上传到服务器进行聚合平均得到全局模型。我关注的是其通信效率、异构数据下的收敛性以及隐私保护机制如差分隐私的结合。这代表了算法从集中式向分布式、隐私保护方向的发展。工业异常检测算法这通常结合了传统图像处理如Sobel算法做边缘检测和现代深度学习算法如自编码器、GAN。我的练习重点是理解流程如何利用正常样本训练模型使得模型对异常样本产生较高的重构误差或较低的生成概率从而触发报警。这需要计算机视觉和机器学习的交叉知识。这些领域可能很深我不求立即精通但保持关注和初步实践能让我在需要时快速切入。例如理解了Sobel算法的边缘检测原理当需要在资源受限设备上做初步图像处理时我就知道这是一个轻量且有效的选择。8. 我的练习方法论与资源分享最后分享一下我个人坚持算法练习的方法。我不追求刷题数量而是注重深度和联系。主题式练习像今天这样围绕一个或几个相关主题如排序、图搜索、字符串展开对比不同算法实现它们并分析时间/空间复杂度。一题多解对于一个具体问题如迷宫问题尝试用DFS、BFS甚至A*如果适用都实现一遍比较代码复杂度和运行效率。联系实际看到MPPT算法光伏最大功率点跟踪就去了解它如何用扰动观察法或电导增量法本质也是优化算法看到Checksum算法就去写一个简单的代码验证其检错能力。思考算法在真实世界中的应用能让学习更有动力。善用工具与社区本地用VS Code或CLion写好代码用LeetCode、AcWing等平台测试。遇到卡壳去讨论区看高票答案但一定要理解透彻而不是复制粘贴。定期复盘准备一个笔记我用的是Markdown文档记录每个经典算法的核心思想、代码模板、易错点以及相关联的其他算法或问题。定期回顾形成自己的知识网络。算法之路道阻且长。它没有捷径唯有持续、刻意且带有思考的练习。每一次练习都是对思维的一次打磨。希望我9月13日这天的练习心得能为你提供一些参考。不要把它当成任务而是当作一种探索逻辑与智慧之美的日常。当你为一个精妙的解法而拍案叫绝时那种快乐就是坚持下去的最好理由。
算法实践：从堆排序、Dijkstra到KMP，探索经典算法的现代应用
1. 算法练习的价值与我的日常实践作为一名长期与代码和逻辑打交道的开发者我始终认为算法能力是程序员的内功它决定了你解决问题的深度和效率上限。很多人把算法练习等同于“刷题”为了面试而突击这其实是一种误解。真正的算法练习是一种思维体操是持续保持对问题抽象、逻辑拆解和方案优化敏感度的日常习惯。我给自己定了个规矩无论多忙每周都要抽出固定时间针对性地练习几个算法问题9月13日这天也不例外。这不仅仅是完成几道题目而是通过这个过程复盘自己近期的知识盲区探索一些新出现的算法思想或者将经典算法应用到新的场景中去琢磨。今天想和大家分享的就是我在一次日常练习中围绕几个关键词展开的深度思考与实践涉及排序、图论、搜索优化等多个方面希望能给你带来一些不一样的启发。2. 从经典排序出发堆排序的现代理解与性能深潜当天的练习我决定从最基础的排序算法重新审视。排序是算法的基石而堆排序在其中以其稳定的O(n log n)时间复杂度和O(1)的空间复杂度如果不算递归栈著称。但教科书上的讲解往往止步于原理在实际应用中我们更需要理解它的微观性能和行为。2.1 堆排序的核心不仅是“排序”更是“选择”堆排序的本质可以看作是一种高效的“选择排序”。普通选择排序每次从未排序部分选出最小或最大值需要O(n)时间而堆特别是二叉堆这种数据结构能在O(log n)的时间内完成元素的插入和删除最值操作。堆排序就是利用最大堆或最小堆反复取出堆顶元素当前最值的过程。我写了一个简单的最大堆排序的C核心代码片段来重温这个过程void heapify(vectorint arr, int n, int i) { int largest i; // 初始化最大值为根节点 int left 2 * i 1; int right 2 * i 2; // 如果左子节点存在且大于根 if (left n arr[left] arr[largest]) largest left; // 如果右子节点存在且大于当前最大值 if (right n arr[right] arr[largest]) largest right; // 如果最大值不是根节点 if (largest ! i) { swap(arr[i], arr[largest]); // 递归地堆化受影响的子堆 heapify(arr, n, largest); } } void heapSort(vectorint arr) { int n arr.size(); // 构建最大堆从最后一个非叶子节点开始 for (int i n / 2 - 1; i 0; i--) heapify(arr, n, i); // 一个个从堆顶取出元素 for (int i n - 1; i 0; i--) { swap(arr[0], arr[i]); // 将当前堆顶最大值移到数组末尾 heapify(arr, i, 0); // 对剩余元素重新堆化 } }注意heapify函数的时间复杂度是O(log n)因为它只需要沿着树的一条路径向下比较。整个堆排序的时间复杂度为O(n log n)其中建堆过程是O(n)这是一个常常被忽略但非常重要的结论可以通过数学推导证明。2.2 实践中的性能考量与“八大排序”的选型思考提到C八大排序算法通常指冒泡、选择、插入、希尔、归并、快速、堆排序和基数排序。在练习中我习惯性地对比它们。对于几乎有序的数据插入排序效率惊人当数据量巨大且对最坏情况有要求时堆排序的稳定性这里指时间复杂度稳定非排序稳定性是优势而快速排序在平均情况下的常数因子最小是实践中的通用王者。但现代开发中我们很少自己实现排序。C的std::sort通常基于内省排序IntroSort它是快速排序、堆排序和插入排序的混合体会根据递归深度和数据规模智能切换算法以规避快排的最坏情况。理解这些底层算法正是为了在需要定制排序规则如复杂对象的多关键字排序、优化特定场景如链表排序用归并更优或在资源极端受限的环境如嵌入式系统堆排序的原地特性宝贵下能做出最合适的选择。3. 图论算法的实战演绎Dijkstra与A*的路径寻找哲学练习的第二个主题是图论算法。我选取了Dijkstra算法和A*算法进行对比实现这是解决最短路径问题的两大利器尤其在AGV自动导引运输车调度、游戏AI、地图导航中应用广泛。3.1 Dijkstra算法稳健的全局探索者Dijkstra算法的核心思想是贪心策略它从源点出发逐步扩展到距离最短的未访问节点直到覆盖目标点或所有点。它保证找到的是单源最短路径适用于边权非负的图。我实现了一个基于优先队列最小堆的Dijkstra这是效率最高的通用实现方式vectorint dijkstra(vectorvectorpairint, int graph, int start) { int n graph.size(); vectorint dist(n, INT_MAX); dist[start] 0; priority_queuepairint, int, vectorpairint, int, greater pq; // 最小堆 pq.emplace(0, start); while (!pq.empty()) { auto [currentDist, u] pq.top(); pq.pop(); if (currentDist dist[u]) continue; // 跳过已过时的信息 for (auto [v, weight] : graph[u]) { int newDist currentDist weight; if (newDist dist[v]) { dist[v] newDist; pq.emplace(newDist, v); } } } return dist; }这个实现的时间复杂度是O((VE) log V)其中V是顶点数E是边数。贪心算法在这里的体现是每次从优先队列中取出当前已知距离最短的节点并认为这个距离就是最终最短距离。这是一种“目光短浅”却最终正确的策略。3.2 A*算法启发式引导的智能搜索A*算法可以看作是Dijkstra算法的增强版为Dijkstra加入了启发式函数h(n)用于估算从当前节点n到目标点的代价。其优先级队列的排序依据从f(n) g(n)Dijkstrag(n)是实际代价变成了f(n) g(n) h(n)。一个经典的比喻是Dijkstra像是一个在黑暗中摸索、均匀向四周扩散的人而A*则像是一个拿着模糊地图启发函数的人虽然也摸索但会优先朝目标的大致方向前进。在三条AGV基本A*算法这个场景下A的优势非常明显。仓库地图可以建模为网格启发函数常使用曼哈顿距离或欧几里得距离。这能极大地减少需要探索的网格数量加快为每台AGV规划路径的速度。但这里有个关键点启发函数h(n)必须满足可采纳性admissible即永不高于实际代价和一致性consistent否则A无法保证找到最优路径。提示在实现A*时除了维护g值和f值通常还需要一个came_from字典来记录路径以便最后回溯。对于网格地图启发函数的选择直接影响效率曼哈顿距离适用于只能四方向移动的场景欧几里得距离适用于可八方向移动的场景。3.3 对比与选型何时用谁Dijkstra当你需要知道从起点到所有其他点的最短路径时或者图中存在负权边时需使用Bellman-FordDijkstra或其变体是首选。它稳健不依赖任何对目标的先验知识。A*当你只需要知道从起点到单一目标点的最短路径并且有一个良好的启发式函数时A*通常远快于Dijkstra。在游戏、机器人路径规划如AGV、地图导航中几乎是标准选择。这次练习让我再次体会到没有绝对最好的算法只有在特定约束和场景下最合适的算法。例如在动态变化的场景中可能需要结合D* Lite等增量搜索算法。4. 字符串匹配的艺术KMP算法原理与实现陷阱字符串匹配是另一个基础且重要的领域。我选择重温KMP算法Knuth-Morris-Pratt。相比于暴力匹配的O(m*n)复杂度KMP能在O(mn)的时间内完成匹配其核心在于当匹配失败时模式串能利用已匹配的信息“智能”地滑动而不是傻傻地只移动一位。4.1 理解Next数组KMP的灵魂KMP最难理解的部分就是next数组或称部分匹配表。next[j]表示模式串P中从开头到位置j的子串中其最长相等前后缀的长度。这个数组告诉我们当在j位置匹配失败时模式串应该回退到哪个位置继续与主串当前字符比较。构建next数组的过程本身就是一个“自我匹配”vectorint buildNext(const string pattern) { int m pattern.length(); vectorint next(m, 0); int j 0; // 指向前缀末尾 for (int i 1; i m; i) { // i指向后缀末尾 while (j 0 pattern[i] ! pattern[j]) { j next[j - 1]; // 不匹配回退j } if (pattern[i] pattern[j]) { j; } next[i] j; } return next; }4.2 常见实现陷阱与调试心得在实现KMP时最容易出错的地方有两个next数组的定义和初始化有的定义中next[0] -1这会导致后续循环判断条件略有不同。我更喜欢上述next[0]0的定义逻辑更统一。关键是理解其含义并能正确推导出简单模式串如“ababc”的next数组。匹配过程中的回退逻辑在while循环中回退j时必须确保j 0否则会死循环或越界。一个实用的调试方法是用小的测试用例主串“aabaabaaf”模式串“aabaaf”手工模拟算法过程并打印出每一步的i、j和next[j]值。理解KMP不仅能解决字符串匹配问题其“利用已有信息避免重复比较”的思想在解决其他子串、子序列问题时也很有启发。例如循环节判断、最短回文串添加等问题都可以通过计算next数组的变体来解决。5. 面对迷宫问题回溯与搜索算法的策略抉择P1238走迷宫这类题目是练习搜索算法的经典场景。它通常要求输出所有可能的路径并且可能要求按特定顺序比如字典序。这立刻让我想到了深度优先搜索DFS和回溯法。5.1 DFS回溯枚举所有可能路径走迷宫问题的标准解法是DFS因为需要探索到终点才能形成一条完整路径。回溯则是DFS中“恢复现场”的关键步骤。vectorvectorint directions {{0,1},{1,0},{0,-1},{-1,0}}; // 方向数组方便控制搜索顺序 vectorstring path; // 记录当前路径 vectorvectorstring allPaths; // 记录所有路径 void dfs(vectorvectorint maze, int x, int y, vectorvectorbool visited) { int m maze.size(), n maze[0].size(); // 到达终点 if (x m-1 y n-1) { allPaths.push_back(path); return; } // 遍历四个方向 for (auto dir : directions) { int nx x dir[0], ny y dir[1]; // 检查边界、可通行性、是否访问过 if (nx 0 nx m ny 0 ny n maze[nx][ny] 0 !visited[nx][ny]) { visited[nx][ny] true; path.push_back(( to_string(nx) , to_string(ny) )); dfs(maze, nx, ny, visited); // 回溯恢复现场 path.pop_back(); visited[nx][ny] false; } } }5.2 关于“P1238是什么算法”的思考网络上有人问“P1238走迷宫是什么算法”这其实反映了初学者的一种困惑面对问题如何选择算法对于走迷宫并输出所有路径如果只问能否到达或最短步数BFS通常是更好的选择因为它能天然地按层搜索最先找到的就是最短路径。如果要求输出所有路径或路径本身DFS回溯是更直接的选择因为它能自然地记录和回溯整条路径。如果迷宫非常大或者有特殊性质如只有少数障碍A*等启发式搜索也可以考虑但实现起来比DFS复杂。所以P1238代表的不是某个特定算法而是一类搜索问题。解题的关键在于根据题目具体要求是否需要路径、是否要求最优、数据规模选择合适的搜索策略并熟练地实现它。这比死记硬背算法模板重要得多。6. 算法思想的延伸从贪心到动态规划的思维跨越在练习中我还刻意对比了贪心算法和动态规划DP。贪心算法在每一步都做出局部最优选择希望导致全局最优。Dijkstra算法中选取当前距离最短的节点就是一种贪心策略。但贪心不是万能的它需要问题具有“贪心选择性质”和“最优子结构”。例如经典的“找零钱”问题用最少的硬币凑出某个金额如果硬币面额是常规的1、5、10、25贪心每次选最大面额是有效的。但如果面额是1、3、4要凑出6贪心会选411三枚而最优解是33两枚。这时就需要用动态规划来求解。动态规划通过保存子问题的解来避免重复计算核心是定义状态和状态转移方程。我从贪心练习跳到DP练习比如经典的“0-1背包问题”这种思维切换的练习能有效提升对问题本质的洞察力。贪心是“一条路走到黑”DP是“记住走过的路步步为营”。理解它们的区别和联系才能在面对新问题时快速判断可能的解法方向。7. 算法工具箱的持续更新关注前沿与工业实践日常算法练习不能只停留在经典问题上。根据热搜词我也花时间了解了一些更前沿或工业界热门的算法概念这能拓宽视野知道经典算法是如何被应用和扩展的。增量式PID算法这是工业控制领域的核心。经典PID算法输出控制量u(t) Kpe(t) Ki∫e(t)dt Kd*de(t)/dt。而增量式PID计算的是控制量的增量Δu(t)它只与最近几次的偏差有关输出更平滑对执行机构更友好且不易产生积分饱和在单片机等嵌入式系统中实现更方便。理解它需要扎实的数学和控制理论背景。LSTM算法训练和推理作为循环神经网络RNN的变体LSTM通过门控机制解决了长序列依赖问题。在练习中我虽然不会去手写LSTM的反向传播但会通过框架如PyTorch实践一个简单的时序预测任务理解其input gate,forget gate,output gate的作用并关注其训练时间长、需GPU和推理相对快阶段的不同特点。联邦平均算法这是联邦学习中的核心协同训练算法。在数据隐私要求高的场景下多个客户端在本地训练模型只将模型参数更新而非数据上传到服务器进行聚合平均得到全局模型。我关注的是其通信效率、异构数据下的收敛性以及隐私保护机制如差分隐私的结合。这代表了算法从集中式向分布式、隐私保护方向的发展。工业异常检测算法这通常结合了传统图像处理如Sobel算法做边缘检测和现代深度学习算法如自编码器、GAN。我的练习重点是理解流程如何利用正常样本训练模型使得模型对异常样本产生较高的重构误差或较低的生成概率从而触发报警。这需要计算机视觉和机器学习的交叉知识。这些领域可能很深我不求立即精通但保持关注和初步实践能让我在需要时快速切入。例如理解了Sobel算法的边缘检测原理当需要在资源受限设备上做初步图像处理时我就知道这是一个轻量且有效的选择。8. 我的练习方法论与资源分享最后分享一下我个人坚持算法练习的方法。我不追求刷题数量而是注重深度和联系。主题式练习像今天这样围绕一个或几个相关主题如排序、图搜索、字符串展开对比不同算法实现它们并分析时间/空间复杂度。一题多解对于一个具体问题如迷宫问题尝试用DFS、BFS甚至A*如果适用都实现一遍比较代码复杂度和运行效率。联系实际看到MPPT算法光伏最大功率点跟踪就去了解它如何用扰动观察法或电导增量法本质也是优化算法看到Checksum算法就去写一个简单的代码验证其检错能力。思考算法在真实世界中的应用能让学习更有动力。善用工具与社区本地用VS Code或CLion写好代码用LeetCode、AcWing等平台测试。遇到卡壳去讨论区看高票答案但一定要理解透彻而不是复制粘贴。定期复盘准备一个笔记我用的是Markdown文档记录每个经典算法的核心思想、代码模板、易错点以及相关联的其他算法或问题。定期回顾形成自己的知识网络。算法之路道阻且长。它没有捷径唯有持续、刻意且带有思考的练习。每一次练习都是对思维的一次打磨。希望我9月13日这天的练习心得能为你提供一些参考。不要把它当成任务而是当作一种探索逻辑与智慧之美的日常。当你为一个精妙的解法而拍案叫绝时那种快乐就是坚持下去的最好理由。