这是 LeetCode 2911「得到 K 个半回文串的最少修改次数」的 Java 实现。核心思路这道题分为两个部分预处理cost[i][j]计算将子串s[i..j]变成半回文串的最小修改次数动态规划将字符串分成 k 段使总修改次数最少半回文串的定义一个长度为len的字符串是半回文串当且仅当存在1 d len且len % d 0使得将字符串按模d分成d个组后每个组都是回文串。例如adbgadd2时分成两组abg下标 0,2,4和dad下标 1,3,5两组都是回文串。优化点预处理每个长度的所有因子避免重复计算getCostD方法按偏移量offset0 到 d-1分别检查每组回文需要的修改次数Java 代码classSolution{publicintminimumChanges(Strings,intk){finalintns.length();// factors[i] : i 的所有真因子 (1 d i 且 i % d 0)ListInteger[]factorsgetFactors(n);// cost[i][j] : 将 s[i..j] 变成半回文串的最小修改次数int[][]costgetCost(s,n,factors);// dp[i][j] : 将 s[i:] 分成 j 个半回文子串的最小修改次数// 这里采用从右往左的 DP也可以改成从左往右int[][]dpnewint[n1][k1];for(int[]row:dp){Arrays.fill(row,n);// 用 n 作为无穷大最大修改次数不会超过 n}dp[n][0]0;// 空串分成 0 段修改次数为 0for(intin-1;i0;--i){for(intj1;jk;j){// 枚举下一段的结束位置 lfor(intli1;ln;l){dp[i][j]Math.min(dp[i][j],dp[l1][j-1]cost[i][l]);}}}returndp[0][k];}// 预处理 1~n 每个数的真因子privateListInteger[]getFactors(intn){ListInteger[]factorsnewList[n1];for(inti1;in;i){factors[i]newArrayList();factors[i].add(1);// 1 是所有数的因子}for(intd2;dn;d){for(intid*2;in;id){factors[i].add(d);}}returnfactors;}// 计算所有子串变成半回文串的最小代价privateint[][]getCost(finalStrings,intn,ListInteger[]factors){int[][]costnewint[n][n];for(inti0;in;i){for(intji1;jn;j){// 长度至少为 2 才能是半回文finalintlengthj-i1;intminCostlength;// 最大不会超过长度for(finalintd:factors[length]){minCostMath.min(minCost,getCostD(s,i,j,d));}cost[i][j]minCost;}}returncost;}// 计算将 s[i..j] 按周期 d 变成半回文串的修改次数// 按模 d 的余数分成 d 个组每组需要是回文串privateintgetCostD(finalStrings,inti,intj,intd){intcost0;// 对每个偏移量 offset (0 到 d-1)检查对应的组for(intoffset0;offsetd;offset){intlioffset;// 组的左端点intrj-d1offset;// 组的右端点// 在该组内以 d 为步长向中间靠拢检查回文while(lr){if(s.charAt(l)!s.charAt(r)){cost;}ld;r-d;}}returncost;}}复杂度分析项目 复杂度时间O(n³)— 预处理O(n³)枚举子串O(n²)× 枚举因子和检查O(n)DP 部分O(n²k)空间O(n²)—cost数组O(n²)dp数组O(nk)因子数组O(n log n)由于题目限制n 200O(n³)的算法完全可以通过。
Kimi LeetCode 2911. 得到 K 个半回文串的最少修改次数 Java实现
这是 LeetCode 2911「得到 K 个半回文串的最少修改次数」的 Java 实现。核心思路这道题分为两个部分预处理cost[i][j]计算将子串s[i..j]变成半回文串的最小修改次数动态规划将字符串分成 k 段使总修改次数最少半回文串的定义一个长度为len的字符串是半回文串当且仅当存在1 d len且len % d 0使得将字符串按模d分成d个组后每个组都是回文串。例如adbgadd2时分成两组abg下标 0,2,4和dad下标 1,3,5两组都是回文串。优化点预处理每个长度的所有因子避免重复计算getCostD方法按偏移量offset0 到 d-1分别检查每组回文需要的修改次数Java 代码classSolution{publicintminimumChanges(Strings,intk){finalintns.length();// factors[i] : i 的所有真因子 (1 d i 且 i % d 0)ListInteger[]factorsgetFactors(n);// cost[i][j] : 将 s[i..j] 变成半回文串的最小修改次数int[][]costgetCost(s,n,factors);// dp[i][j] : 将 s[i:] 分成 j 个半回文子串的最小修改次数// 这里采用从右往左的 DP也可以改成从左往右int[][]dpnewint[n1][k1];for(int[]row:dp){Arrays.fill(row,n);// 用 n 作为无穷大最大修改次数不会超过 n}dp[n][0]0;// 空串分成 0 段修改次数为 0for(intin-1;i0;--i){for(intj1;jk;j){// 枚举下一段的结束位置 lfor(intli1;ln;l){dp[i][j]Math.min(dp[i][j],dp[l1][j-1]cost[i][l]);}}}returndp[0][k];}// 预处理 1~n 每个数的真因子privateListInteger[]getFactors(intn){ListInteger[]factorsnewList[n1];for(inti1;in;i){factors[i]newArrayList();factors[i].add(1);// 1 是所有数的因子}for(intd2;dn;d){for(intid*2;in;id){factors[i].add(d);}}returnfactors;}// 计算所有子串变成半回文串的最小代价privateint[][]getCost(finalStrings,intn,ListInteger[]factors){int[][]costnewint[n][n];for(inti0;in;i){for(intji1;jn;j){// 长度至少为 2 才能是半回文finalintlengthj-i1;intminCostlength;// 最大不会超过长度for(finalintd:factors[length]){minCostMath.min(minCost,getCostD(s,i,j,d));}cost[i][j]minCost;}}returncost;}// 计算将 s[i..j] 按周期 d 变成半回文串的修改次数// 按模 d 的余数分成 d 个组每组需要是回文串privateintgetCostD(finalStrings,inti,intj,intd){intcost0;// 对每个偏移量 offset (0 到 d-1)检查对应的组for(intoffset0;offsetd;offset){intlioffset;// 组的左端点intrj-d1offset;// 组的右端点// 在该组内以 d 为步长向中间靠拢检查回文while(lr){if(s.charAt(l)!s.charAt(r)){cost;}ld;r-d;}}returncost;}}复杂度分析项目 复杂度时间O(n³)— 预处理O(n³)枚举子串O(n²)× 枚举因子和检查O(n)DP 部分O(n²k)空间O(n²)—cost数组O(n²)dp数组O(nk)因子数组O(n log n)由于题目限制n 200O(n³)的算法完全可以通过。
