算法题将字符串翻转到单调递增-程序员充电站

926. 将字符串翻转到单调递增

问题描述

如果一个二进制字符串的每个字符都满足：'0'在'1'之前（即形如"000...111..."），则称该字符串为单调递增的。

给定一个二进制字符串s，你可以将其中的任意'0'翻转为'1'，或将'1'翻转为'0'。

返回使s单调递增所需的最少翻转次数。

示例：

输入: s = "00110" 输出: 1 解释: 翻转最后一位得到 "00111"。 输入: s = "010110" 输出: 2 解释: 翻转第二位和第五位得到 "000111"。 输入: s = "00011000" 输出: 2 解释: 翻转第五位和第六位得到 "00000000"。

算法思路

前缀和：对于每个可能的分割位置i（0 <= i <= n）：
- 左边[0, i-1]应该全是'0'，需要翻转的'1'数量 = 左边'1'的数量
- 右边[i, n-1]应该全是'1'，需要翻转的'0'数量 = 右边'0'的数量
- 总翻转次数 = 左边'1'的数量 + 右边'0'的数量
动态规划：维护两个状态：
- dp0：以当前位置结尾，且当前字符为'0'时的最少翻转次数
- dp1：以当前位置结尾，且当前字符为'1'时的最少翻转次数
- 状态转移：
  - 如果当前字符是'0'：dp0不变，dp1 = min(dp0, dp1) + 1
  - 如果当前字符是'1'：dp0++，dp1 = min(dp0, dp1)

代码实现

方法一：前缀和

classSolution{/** * 使用前缀和计算最少翻转次数 * * @param s 二进制字符串 * @return 使字符串单调递增的最少翻转次数 */publicintminFlipsMonoIncr(Strings){intn=s.length();// 计算前缀和：prefixOnes[i] 表示 s[0...i-1] 中 '1' 的数量int[]prefixOnes=newint[n+1];for(inti=0;i<n;i++){prefixOnes[i+1]=prefixOnes[i]+(s.charAt(i)=='1'?1:0);}intminFlips=Integer.MAX_VALUE;// 枚举所有可能的分割点 i（0 <= i <= n）// 分割点 i 表示 [0, i-1] 为 '0'，[i, n-1] 为 '1'for(inti=0;i<=n;i++){// 左边 [0, i-1] 中 '1' 的数量（需要翻转为 '0'）intonesToLeft=prefixOnes[i];// 右边 [i, n-1] 中 '0' 的数量（需要翻转为 '1'）intzerosToRight=(n-i)-(prefixOnes[n]-prefixOnes[i]);minFlips=Math.min(minFlips,onesToLeft+zerosToRight);}returnminFlips;}}

方法二：动态规划

classSolution{/** * 动态规划 * * @param s 二进制字符串 * @return 使字符串单调递增的最少翻转次数 */publicintminFlipsMonoIncr(Strings){// dp0: 当前位置为 '0' 时的最少翻转次数// dp1: 当前位置为 '1' 时的最少翻转次数intdp0=0,dp1=0;for(charc:s.toCharArray()){if(c=='0'){// 当前字符是 '0'// dp0 不变（保持为 '0'，不需要翻转）// dp1 = min(dp0, dp1) + 1（翻转为 '1'）dp1=Math.min(dp0,dp1)+1;}else{// 当前字符是 '1'// dp0++（翻转为 '0'）// dp1 = min(dp0, dp1)（保持为 '1'，不需要翻转）dp0++;dp1=Math.min(dp0,dp1);}}returnMath.min(dp0,dp1);}}

算法分析

方法	时间复杂度	空间复杂度
前缀和	O(n)	O(n)
动态规划	O(n)	O(1)

算法过程

输入：s = "010110"

方法一：

prefixOnes = [0,0,1,1,2,3,3]
枚举分割点：
- i=0: 左边’1’数=0，右边’0’数=3 → 翻转=3
- i=1: 左边’1’数=0，右边’0’数=2 → 翻转=2
- i=2: 左边’1’数=1，右边’0’数=2 → 翻转=3
- i=3: 左边’1’数=1，右边’0’数=1 → 翻转=2
- i=4: 左边’1’数=2，右边’0’数=1 → 翻转=3
- i=5: 左边’1’数=3，右边’0’数=1 → 翻转=4
- i=6: 左边’1’数=3，右边’0’数=0 → 翻转=3
最小值 = 2

方法二：

c='0':dp0=0（保持0），dp1=1（翻转为1）→(0,1)
c='1':dp0=1（翻转为0），dp1=min(0,1)=0（保持1）→(1,0)
c='0':dp0=1（保持0），dp1=min(1,0)+1=1（翻转为1）→(1,1)
c='1':dp0=2（翻转为0），dp1=min(1,1)=1（保持1）→(2,1)
c='1':dp0=3（翻转为0），dp1=min(2,1)=1（保持1）→(3,1)
c='0':dp0=3（保持0），dp1=min(3,1)+1=2（翻转为1）→(3,2)
结果：min(3,2) = 2

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例System.out.println("Test 1: "+solution.minFlipsMonoIncr("00110"));// 1// 测试用例2：另一个标准示例System.out.println("Test 2: "+solution.minFlipsMonoIncr("010110"));// 2// 测试用例3：复杂情况System.out.println("Test 3: "+solution.minFlipsMonoIncr("00011000"));// 2// 测试用例4：全0System.out.println("Test 4: "+solution.minFlipsMonoIncr("0000"));// 0// 测试用例5：全1System.out.println("Test 5: "+solution.minFlipsMonoIncr("1111"));// 0// 测试用例6：交替System.out.println("Test 6: "+solution.minFlipsMonoIncr("010101"));// 3// 测试用例7：单字符System.out.println("Test 7: "+solution.minFlipsMonoIncr("0"));// 0System.out.println("Test 8: "+solution.minFlipsMonoIncr("1"));// 0// 测试用例8：需要全翻转为0System.out.println("Test 9: "+solution.minFlipsMonoIncr("1111100000"));// 5// 测试用例9：需要全翻转为1System.out.println("Test 10: "+solution.minFlipsMonoIncr("0000011111"));// 0// 测试用例10：长字符串StringlongStr="00000000000000000000000000000000000000000000000000";System.out.println("Test 11: "+solution.minFlipsMonoIncr(longStr));// 0}