笔试强训 Day 26：小红的 ABC、不相邻取数、空调遥控
Day 26小红的 ABC解题思路注意本题不是找最长回文子串而是最短回文子串最短小于 2返回 -1找最短回文子串可以先枚举 2 个字符子串3 个字符子串后面的 4 个字符子串、5 个字符子串其实最短的都是 3所以只枚举 2,3 两种长度的子串代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);Stringsin.next();intns.length();intret1;for(inti0;in-1;i){if(s.charAt(i)s.charAt(i1))ret2;}for(inti0;in-2;i){if(s.charAt(i)s.charAt(i2)ret!2)ret3;}if(ret1)ret-1;System.out.println(ret);}}拓展最长回文子串好的我用一个具体例子来演示这个循环条件是如何导致问题的。以s abcca为例你的原始循环for(intin;i1;i--){for(intj1;jnji;j){// DP处理}}逐轮执行过程第1轮i 5内层循环j从 1 开始检查j n j i→1 5 1 5→true false→false循环直接终止不执行任何代码结果i5 时什么都没做第2轮i 4内层循环j从 1 开始检查1 5 1 4→true false→false循环直接终止结果i4 时什么都没做第3轮i 3内层循环j从 1 开始检查1 5 1 3→true false→false循环直接终止结果i3 时什么都没做第4轮i 2内层循环j从 1 开始检查1 5 1 2→true false→false循环直接终止结果i2 时什么都没做第5轮i 1内层循环j从 1 开始j1检查1 5 1 1→true true→true执行代码j2检查2 5 2 1→true true→true执行代码j3检查3 5 3 1→true true→true执行代码j4检查4 5 4 1→true true→true执行代码j5检查5 5 5 1→true true→true执行代码问题总结只计算了以位置1开头的子串计算了[1,1],[1,2],[1,3],[1,4],[1,5]即a,ab,abc,abcc,abcca完全没有计算的子串以位置2开头的[2,2],[2,3],[2,4],[2,5]→b,bc,bcc,bcca以位置3开头的[3,3],[3,4],[3,5]→c,cc,cca以位置4开头的[4,4],[4,5]→c,ca以位置5开头的[5,5]→a结果是虽然cc是回文子串位置3到4但因为 i3 时的内层循环根本没执行所以dp[3][4]永远保持默认值false最终 ret 保持为 1输出 -1。正确的循环应该是for(intin;i1;i--){for(intji;jn;j){// j从i开始而不是从1开始// DP处理}}这样就能计算所有子串[i,j]了。importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);Stringsin.next();intns.length();boolean[][]dpnewboolean[n2][n2];intret1;// dp[i1][j-1]for(intin;i1;i--){for(intj1;jn;j){if(s.charAt(i-1)s.charAt(j-1)){if(ij||i1j){dp[i][j]true;}else{dp[i][j]dp[i1][j-1];}}if(dp[i][j])retMath.max(j-i1,ret);}}if(ret1)ret-1;System.out.println(ret);}}不相邻取数解题思路动态规划重点在想出状态表示代码实现importjava.util.*;importjava.io.*;publicclassMain{privatestaticPrintWriteroutnewPrintWriter(newBufferedWriter(newOutputStreamWriter(System.out)));privatestaticReadinnewRead();publicstaticvoidmain(String[]args)throwsIOException{intnin.nextInt();int[]numsnewint[n];for(inti0;in;i){nums[i]in.nextInt();}int[]dpnewint[n2];for(inti2;i1n;i){dp[i]Math.max(dp[i-2]nums[i-2],dp[i-1]);}out.println(dp[n1]);out.close();}}classRead{StringTokenizerstnewStringTokenizer();BufferedReaderbfnewBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{if(!st.hasMoreTokens()){Stringlinebf.readLine();if(linenull)returnnull;stnewStringTokenizer(line);}returnst.nextToken();}intnextInt()throwsIOException{returnInteger.parseInt(next());}}空调遥控解题思路注意这题不适合二分温度因为“某个温度能满足的人数”并不具有单调性。正确解法是使用滑动窗口思想在排序后满足诉求的温度范围 [K - p, K p]K 无限制所以应该找到数组中前后差不超过 2p 的最大窗口代码实现importjava.util.*;importjava.io.*;publicclassMain{privatestaticPrintWriteroutnewPrintWriter(newBufferedWriter(newOutputStreamWriter(System.out)));privatestaticReadinnewRead();publicstaticvoidmain(String[]args)throwsIOException{intnin.nextInt(),pin.nextInt();int[]numsnewint[n];for(inti0;in;i){nums[i]in.nextInt();}Arrays.sort(nums);intret0;for(intl0,r0;rn;r){// 滑动窗口, 找到一块温度差在 2p 的窗口while((long)nums[r]-nums[l]2L*p)l;retMath.max(ret,r-l1);}out.println(ret);out.close();}}classRead{StringTokenizerstnewStringTokenizer();BufferedReaderbfnewBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{if(!st.hasMoreTokens()){Stringlinebf.readLine();if(linenull)returnnull;stnewStringTokenizer(line);}returnst.nextToken();}intnextInt()throwsIOException{returnInteger.parseInt(next());}}
)
