笔试强训 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背包模板即可通过所有测试用例。

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

相关推荐

STM32串口高效接收不定长数据：空闲中断与DMA循环模式实战详解

AI睡眠语音分析：解码梦话预测神经系统疾病

百考通得力助手：助力每一份研究从良好开端走向卓越成果

更多资讯

社会参考的低压电工证上岗必备怎么考才不白交钱

通州区低压电工证在哪怎么报名，工地太忙根本没时间复习考试

郑州报考避坑指南：实操考试心里没底怕挂科？天网监控系统查电工证全攻略

濮阳电工证在哪里办理电子证书能异地转吗

物业电工证外皮怎么看 2026河南最新政策告诉你怎么报

3个真实经历告诉你，玉林电工证查询别再走弯路，工地太忙根本没时间复习考试

今日更新

单位电工证怎么保管？2026河南最新政策你必须知道

电工证上哪个网校内部消息教你避开报名陷阱

荆州电工证补贴怎么领？官方报名入口全解析，别再走弯路

本周精选

普宁电工证在哪报名官方回应怕考不过白交培训费？这些避坑干货你必须知道

高压电工证登高练习题在哪考合格率高？怕考不过白交培训费

电工作业登记表通过率揭秘：怕考不过白交培训费？洛阳学员亲测经验全公开

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？