老程序员回炉补基础五经典算法——背包、LCS、N皇后、汉诺塔与更多这一章是我的算法练兵场。从递归入门的汉诺塔和阶乘到动态规划的背包和LCS再到回溯的N皇后每一种算法思想都让我对如何把现实问题抽象为数学模型有了更深的理解。一、递归入门阶乘与汉诺塔阶乘学习时间2023年9月27日publicclassfactorial{publiclongcfactorial(longn){if(n0){return1;}returnn*cfactorial(n-1);}}最简单的递归。n! n × (n-1)!边界条件是 0! 1。递归三要素递归体n * cfactorial(n - 1)终止条件n 0返回值每次递归向终止条件逼近n 不断减小汉诺塔学习时间2023年9月26日publicclasshtower{publicvoidf(intn,Stringfrom,Stringmid,Stringto){if(n1){System.out.println(n:from-to);}else{f(n-1,from,to,mid);// 上面n-1个盘子从A移到BSystem.out.println(n:from-to);// 最大的盘子从A移到Cf(n-1,mid,from,to);// n-1个盘子从B移到C}}}汉诺塔是理解递归最好的例子。3个盘子f(3, A, B, C): f(2, A, C, B) → 把上面2个从A移到B借C 移动盘子3: A→C → 把最大的从A移到C f(2, B, A, C) → 把2个从B移到C借A关键洞察不管有多少个盘子问题都可以分解为三步——把上面的移走、移最底下的、把上面的移回来。这就是分治的思想。二、动态规划0-1背包问题学习时间2023年10月7日物品定义publicclassStuff{privatedoubleweigth;// 重量privatedoublevalue;// 价值privateintnumber;// 编号publicStuff(intnumber,doubleweigth,doublevalue){this.numbernumber;this.valuevalue;this.weigthweigth;}}核心算法publicclassKnapsack{/** * 0-1 背包问题 * param list 物品列表 * param weigth 背包容量 * return 动态规划表 c[i][w] 表示前i个物品、容量为w时的最大价值 */publicint[][]f(ListStufflist,intweigth){intc[][]newint[list.size()1][weigth1];for(inti1;ilist.size();i){c[i][0]0;for(intw1;wweigth;w){Stuffobjlist.get(i-1);if(obj.getWeigth()w){if(obj.getValue()c[i-1][(int)(w-obj.getWeigth())]c[i-1][w]){c[i][w](int)(obj.getValue()c[i-1][(int)(w-obj.getWeigth())]);}else{c[i][w]c[i-1][w];}}else{c[i][w]c[i-1][w];}}}returnc;}}状态转移方程c[i][w] max( c[i-1][w], // 不选第i个物品 value[i] c[i-1][w - weight[i]] // 选第i个物品 )测试用例物品[{编号:1, 重量:3, 价值:4}, {编号:5, 重量:9, 价值:13}, {编号:2, 重量:4, 价值:5}, {编号:3, 重量:7, 价值:10}, {编号:4, 重量:8, 价值:11}] 背包容量17我的理解动态规划的核心是找到状态转移方程。背包问题的状态是考虑前i个物品、容量为w时的最大价值每个状态只依赖上一行的状态。动态规划表DP Table是理解算法的关键w0 w1 w2 w3 w4 ... w17 i0 0 0 0 0 0 ... 0 i1 0 0 0 4 4 ... 4 i2 0 0 0 4 4 ... 13 ...从最后一行最后一列就能读出最优解。架构师视角背包问题的思想在工程中广泛应用服务器资源分配有限的CPU/内存如何分配给多个服务使总收益最大任务调度有限时间内选择哪些任务执行使产出最大缓存策略有限的缓存空间缓存哪些数据使命中率最高三、动态规划最长公共子序列LCS学习时间2023年9月27日publicclassLCS{publicvoidf(char[]X,char[]Y,intl[][]){for(inti1;iX.length;i){for(intj1;jY.length;j){if(X[i-1]Y[j-1]){l[i][j]l[i-1][j-1]1;}else{intm0,n0;ml[i-1][j];nl[i][j-1];if(mn){l[i][j]m;// BUG应该是 n}else{l[i][j]n;// BUG应该是 m}}}}}}状态转移方程if X[i] Y[j]: l[i][j] l[i-1][j-1] 1 else: l[i][j] max(l[i-1][j], l[i][j-1])一个真实的 Bug我在这段代码中犯了一个错误当m n时应该取较大值n但我写成了l[i][j] m。这意味着当两个字符不匹配时我取的是较小值而不是较大值。这个 Bug 不是抄代码会犯的错误——抄代码至少会抄对逻辑。它是理解不够深入时手写代码的典型问题我记住了要比较但搞反了取值的方向。修正后的代码if(mn){l[i][j]n;// 取较大值}else{l[i][j]m;// 取较大值}测试X {A,B,C,B,D,A,B} Y {B,D,C,A,B,A} LCS 长度 4BCBA 或 BDAB架构师视角LCS 的应用场景Git diff比较两个版本的代码差异本质是 LCS 问题DNA 序列比对生物信息学中比对基因序列的相似性拼写检查找到最相似的单词四、回溯N皇后问题学习时间2023年10月13日N皇后问题在 N×N 的棋盘上放置 N 个皇后使它们互不攻击不在同一行、同一列、同一对角线上。递归解法privateintn8;privateintp[];publicvoidNqueue(intk){if(kn){// 所有皇后都放好了输出一种解法System.out.println(Arrays.toString(p));return;}for(inti0;in;i){intj0;for(;jk;j){// 检查是否和已放置的皇后冲突if(p[j]i||Math.abs(p[j]-i)Math.abs(k-j)){break;}}if(jk){// 没有冲突p[k]i;Nqueue(k1);// 放下一行的皇后}}}我的理解这是一个经典的回溯算法。p[k] i表示第 k 行的皇后放在第 i 列。冲突检测只需两个条件p[j] i同一列Math.abs(p[j] - i) Math.abs(k - j)同一对角线行差等于列差回溯的思想是走一步看一步走不通就退回来换一条路。for循环尝试当前行的每一列如果某一列不冲突就放下去递归处理下一行如果所有列都冲突递归自然返回上一行就会尝试下一个位置。迭代解法我还写了一个非递归版本wNqueue()用while循环手动模拟递归的回溯过程publicvoidwNqueue(){inti,j,count1;intpos1[]newint[n1];for(i1;in;i)pos1[i]0;j1;while(j1){pos1[j]pos1[j]1;while(pos1[j]n!isplace(pos1,j)){pos1[j]pos1[j]1;}if(pos1[j]njn){// 找到一组解System.out.print(第 (count):);for(i1;in;i)System.out.print(pos1[i]);System.out.println();}if(pos1[j]njn){jj1;// 放下一行}else{pos1[j]0;jj-1;// 回溯到上一行}}}非递归版本的核心j是当前行号pos1[j]是当前尝试的列号。当本行所有列都试过了还不行pos1[j] n就重置当前行并回退到上一行。8皇后的解8皇后共有92种不同的放置方案。五、更多算法练习最大子段和Sum.java中包含了最大子段和问题的两种解法分治法O(n log n)intmaxSum(intarray[],intleft,intright){if(leftright){returnarray[left]0?array[left]:0;}intmid(leftright)/2;intleftMaxmaxSum(array,left,mid);intrightMaxmaxSum(array,mid1,right);// 跨中点的最大子段和ints00,s10,lefts0,rights0;for(intimid;ileft;i--){leftsarray[i];if(leftss0)s0lefts;}for(intimid1;iright;i){rightsarray[i];if(rightss1)s1rights;}returnmax(leftMax,rightMax,s0s1);}Kadane 算法O(n)最优解intmaxSum(int[]array){intmax0,temp0;for(inti0;iarray.length;i){temparray[i];if(tempmax)maxtemp;if(temp0)temp0;// 前缀和为负就丢弃}returnmax;}Kadane 算法是一个经典的贪心/DP混合思路如果一段子数组的和已经是负数了那它不可能成为最大子段和的一部分直接丢弃从头开始。最大公约数欧几里得算法intgcd(inta,intb){intrem0;while(b0){rema%b;ab;brem;}returna;}辗转相除法公元前 300 年欧几里得发明的算法至今仍在使用。快速幂publicdoublepower(doublei,longn){if(n3)returni*i*i;elseif(n2)returni*i;elseif(n1)returni;if(n%20){returnpower(i*i,n/2);}else{returnpower(i*i,n/2)*i;}}快速幂将 O(n) 的乘法降到 O(log n)x^n (x²)^(n/2)。页码统计voidpageNumber(){intpages99;intnumber[]newint[10];for(inti1;ipages;i){intnumi;do{intremnum%10;number[rem];numnum/10;}while(num0);}}统计一本书从第1页到第99页每个数字0-9出现了多少次。这是一个简单的数学问题但对理解数位操作有帮助。五种算法思想总结算法思想代表问题核心思路递归汉诺塔、阶乘大问题拆成同类小问题分治最大子段和、归并排序分成子问题分别求解再合并动态规划0-1背包、LCS记录子问题的解避免重复计算回溯N皇后试探撤销走不通就回头贪心Kadane算法、快速幂每一步选局部最优写在最后五个月的学习总结从2023年8月到2024年1月我用5个月时间补完了这些基础月份学习内容2023.8链表、栈、队列2023.9排序算法、递归2023.10图、树、经典算法2023.11堆排序、Java基础2023.12JVM类加载、内存2024.1快速排序收官代码中有 BugLCS有未完成的功能Prim有拼写错误BSF/DSF。但这些不完美恰恰证明了这是真实的学习过程而不是复制粘贴的成果展示。作为一个43岁的架构师我想说的是永远不要觉得补基础是浪费时间。你写的每一行底层代码都会在未来的某一天帮你做出更好的架构决策。系列完