笔试强训 Day 22：添加字符、数组转换、装箱问题

添加字符字符串思路借鉴滑动窗口思路把 A 看做是一个参照在 B 中枚举参照长度相同的窗口然后位置一一对应对不同的位置进行计数A abb B bba 可能会有对齐匹配的想法但是 B 的长度是不能变的因此无需对齐只看对应位置字符是否相等即可 本次 cnt 2而不是 1找到 cnt 最小的窗口代码实现importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);char[]strAin.next().toCharArray();char[]strBin.next().toCharArray();intmstrA.length,nstrB.length;intretm;for(inti0;in-m;i){intcntm;for(intj0;jm;j){if(strA[j]strB[ij]){cnt--;}}retMath.min(cnt,ret);}System.out.println(ret);}}数组变换思路贪心当数组中所有的数乘以 2最终所有元素相同那么可以发过来将所有的数都除以 2直到所有的数为奇数如果符合条件此时数组中所有的奇数一定相同代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt();Long[]numsnewLong[n];for(inti0;in;i){nums[i]in.nextLong();while(nums[i]%20){nums[i]/2;}}longprenums[0];for(inti1;in;i){if(pre!nums[i]){System.out.print(NO);return;}}System.out.println(YES);}}装箱问题思路01 背包问题错误代码importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intvin.nextInt();intnin.nextInt();int[]numsnewint[n1];for(inti1;in;i)nums[i]in.nextInt();int[]dpnewint[20001];dp[0]v;intret0;for(inti1;in;i){for(intj1;ji;j){if(dp[j]nums[i]v)dp[i]Math.max(dp[j]nums[i],dp[i]);retMath.max(ret,dp[i]);}}System.out.println(v-ret);}}出发点选 i 物品时达到的体积最大值思路方向是对的但代码中dp的定义和状态转移存在几个关键问题导致无法得到正确结果。错误代码主要问题1.dp数组的定义和索引混乱定义了dp[0] v但dp[i]到底表示什么看起来你想让dp[i]表示「选择第 i 个物品时能获得的最大体积」但dp[0] v这个初始化不合理dp[0]应该表示不选任何物品时的体积为 0状态转移时用dp[j]作为容量来比较但dp[j]是体积值而不是容量值2. 双重循环的逻辑错误for(inti1;in;i){for(intj1;ji;j){if(dp[j]nums[i]v)dp[i]Math.max(dp[j]nums[i],dp[i]);retMath.max(ret,dp[i]);}}内层循环只遍历j i相当于只考虑了物品编号小于 i 的组合但物品的最优组合并不一定按编号顺序出现dp[j]已经被赋予了不同的含义最大体积但又用它来判断dp[j] nums[i] v逻辑混乱3. 没有处理「不选任何物品」的情况如果所有物品体积都大于箱子容量正确答案应该是v剩余空间不变但你的代码ret初始为 0最终会输出v这里碰巧是对的。但如果存在可选物品你的逻辑就可能出错。正确解法01背包这道题是经典的01背包问题——每个物品只能选一次目标是让装入的物品总体积尽可能大但不能超过箱子容量 V最后用V - 最大体积即为最小剩余空间。核心思路dp[j]表示容量为j的箱子能装下的最大物品体积。对每个物品从大到小遍历容量状态转移方程为dp[j] max(dp[j], dp[j - nums[i]] nums[i])正确代码importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intvin.nextInt();// 箱子容量intnin.nextInt();// 物品数量int[]numsnewint[n];for(inti0;in;i){nums[i]in.nextInt();}// dp[j] 表示容量为 j 的箱子能装下的最大体积int[]dpnewint[v1];for(inti0;in;i){// 从大到小遍历保证每个物品只用一次for(intjv;jnums[i];j--){dp[j]Math.max(dp[j],dp[j-nums[i]]nums[i]);}}// 最大能装下的体积是 dp[v]剩余空间 V - dp[v]System.out.println(v-dp[v]);}}以示例为例V24物品为 8、3、12、7、9、7最终dp[24] 24输出0。为什么你的代码只通过 40%你的算法本质上是一个错误的子集和求解它只考虑了物品按编号顺序的局部组合而不是全局最优。当测试用例中物品顺序打乱时比如最优解需要跳着选物品你的代码就会漏掉正确组合导致答案偏大剩余空间偏大。总结对比项你的代码正确01背包dp含义混乱dp[i]含义不清晰dp[j]容量 j 能装的最大体积遍历顺序正序物品可能被重复使用倒序保证每个物品只用一次状态转移只考虑编号小于 i 的物品考虑所有物品的组合结果只取局部最优全局最优把代码改成标准的01背包模板即可通过所有测试用例。