笔试强训 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睡眠语音分析：解码梦话预测神经系统疾病

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

更多资讯

STC15单片机超声波测距OLED显示实战：从原理到原理图设计

C#对象映射实战：反射、特性与表达式树应用

半导体设备技术突破与智能化发展趋势

LTspice元器件库本质：路径、符号与模型三要素协同机制

EITtext_EIT：Python实现行内实体标签解析与转换实战

Qt+OpenCV+C++实战：从零构建行车辅助系统核心功能

今日更新

基于MATLAB的CRI显色指数计算：从SPD光谱到Ra的完整流程

JSP+Servlet+MySQL博客系统源码部署与优化全攻略

蜂窝调度算法 MATLAB 实现：比例公平、轮询与最大 C/I 对比

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

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