笔试强训 Day 35：奇数位丢弃、求和、计算字符串的编辑距离
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₂(n+1)⌋ 最终数字 = 最终位置 - 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){Scannerin=newScanner(System.in);while(in.hasNextInt()){intn=in.nextInt();intpower=1;while(power*2<=n+1){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;privatestaticList<Integer>path;privatestaticvoiddfs(intsum,intstart){if(sum==target){for(intnum:path){System.out.print(num+" ");}System.out.println();return;}for(inti=start;i<=n;i++){if(sum+i>target)break;path.add(i);// 选择了 i 后，为了避免重复并保持递增，下一层应该从 i + 1 开始dfs(sum+i,i+1);path.remove(path.size()-1);}}publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);n=in.nextInt();target=in.nextInt();path=newArrayList<>();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){Scannerin=newScanner(System.in);char[]c1=in.next().toCharArray();char[]c2=in.next().toCharArray();intm=c1.length,n=c2.length;int[][]dp=newint[m+1][n+1];// 重要: 初始化for(inti=0;i<=m;i++)dp[i][0]=i;for(intj=0;j<=n;j++)dp[0][j]=j;for(inti=1;i<=m;i++){for(intj=1;j<=n;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]);}}