Day 35奇数位丢弃解题思路模拟可以先追踪“原序列中的位置”规律会很明显。位置从1开始而位置i对应的数字是i - 1。以n 5为例序列长度为n 1 6原位置1 2 3 4 5 6 数字 0 1 2 3 4 5 第 1 轮保留偶数位置 原位置2 4 6 数字 1 3 5 第 2 轮保留当前序列的偶数位置 原位置4 数字 3每轮结束后保留下来的原位置分别是第 1 轮2 的倍数 第 2 轮4 的倍数 第 3 轮8 的倍数 …… 第 k 轮2^k 的倍数因此最终保留的原位置就是不超过序列长度n 1的最大2的幂最终位置 2^⌊log₂(n1)⌋ 最终数字 最终位置 - 1例如n 5 n 1 6 不超过 6 的最大 2 的幂是 4 答案 4 - 1 3n 500时n 1 501不超过501的最大 2 的幂是256所以答案是255。// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15// 1 3 5 7 9 11 13 15// 3 7 11 15// 7 15// 15代码实现// 0..n// 丢弃第奇数位个的数importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);while(in.hasNextInt()){intnin.nextInt();intpower1;while(power*2n1){power*2;}System.out.println(power-1);}}}// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15// 1 3 5 7 9 11 13 15// 3 7 11 15// 7 15// 15求和解题思路递归型枚举注意可以递归的起始点来处理去重问题因为是递增数列的枚举没有相同数字代码实现importjava.util.*;publicclassMain{privatestaticintn,target;privatestaticListIntegerpath;privatestaticvoiddfs(intsum,intstart){if(sumtarget){for(intnum:path){System.out.print(num );}System.out.println();return;}for(intistart;in;i){if(sumitarget)break;path.add(i);// 选择了 i 后为了避免重复并保持递增下一层应该从 i 1 开始dfs(sumi,i1);path.remove(path.size()-1);}}publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);nin.nextInt();targetin.nextInt();pathnewArrayList();dfs(0,1);}}计算字符串的编辑距离解题思路设dp[i][j]表示将s的前i个字符变成t的前j个字符的最少操作数。计算dp[i][j]时考虑最后一步操作dp[i][j - 1] 1插入t[j - 1]dp[i - 1][j] 1删除s[i - 1]dp[i - 1][j - 1] 1将s[i - 1]替换为t[j - 1]所以字符不同时dp[i][j] Math.min( Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1] ) 1;字符相同时dp[i][j] dp[i - 1][j - 1];核心套路就是当前状态 更小的前驱状态 最后一次操作边界dp[i][0] i; dp[0][j] j;代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);char[]c1in.next().toCharArray();char[]c2in.next().toCharArray();intmc1.length,nc2.length;int[][]dpnewint[m1][n1];// 重要: 初始化for(inti0;im;i)dp[i][0]i;for(intj0;jn;j)dp[0][j]j;for(inti1;im;i){for(intj1;jn;j){if(c1[i-1]c2[j-1]){dp[i][j]dp[i-1][j-1];}else{// 重要: 不同的操作可以抽象成 dp 之间的转换, 找到操作次数最少的情况dp[i][j]Math.min(Math.min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])1;}}}System.out.println(dp[m][n]);}}
)
