乐清 网站建设,外贸网站外链平台,网络舆情软件免费入口官网,湖北网站开发培训题目
输入一个只包含’0’和’1’的字符串#xff0c;其中#xff0c;‘0’可以翻转成’1’#xff0c;‘1’可以翻转成’0’。请问至少需要翻转几个字符#xff0c;才可以使翻转之后的字符串中所有的’0’位于’1’的前面#xff1f;翻转之后的字符串可能只包含字符’0’…题目
输入一个只包含’0’和’1’的字符串其中‘0’可以翻转成’1’‘1’可以翻转成’0’。请问至少需要翻转几个字符才可以使翻转之后的字符串中所有的’0’位于’1’的前面翻转之后的字符串可能只包含字符’0’或’1’。例如输入字符串00110至少需要翻转一个字符才能使所有的’0’位于’1’的前面。可以将最后一个字符’0’翻转成’1’得到字符串00111。
分析
f(i): 表示把字符串中S[0…i]变成符合要求的字符串并且最后一个字符是’0’所需要的最少翻转次数g(i): 表示把字符串中S[0…i]变成符合要求的字符串并且最后一个字符是’1’所需要的最少翻转次数如果翻转之后下标为i的字符是’0’那么下标为i-1的字符一定是’0’否则就不满足所有的字符’0’位于’1’的前面的这个要求。当输入字符串中下标为i的字符即S[i]是’0’时这一步不需要翻转fifi-1当输入字符串中下标为i的字符是’1’时fifi-11因为要把下标为i的字符翻转成’0’。如果翻转之后下标为i的字符是’1’那么无论下标为i-1的字符是’0’还是’1’都满足题目的要求。当输入字符串S[i]是’0’时gimin[fi-1gi-1]1因为要把第i个字符翻转成’1’当S[i]是’1’时此时不需要翻转字符因此gimin[fi-1gi-1]。
解
public class Test {public static void main(String[] args) {int result minFlipsMonoIncr(00110);System.out.println(result);}// f(i): 表示把字符串中S[0..i]变成符合要求的字符串并且最后一个字符是0所需要的最少翻转次数// g(i): 表示把字符串中S[0..i]变成符合要求的字符串并且最后一个字符是1所需要的最少翻转次数// f(i) f(i-1) ch 0?0:1// g(i) g(i-1) Math.min(f(i-1),g(i-1)) (ch 1?0:1);public static int minFlipsMonoIncr(String S) {int len S.length();if (len 0) {return 0;}// 第一个2f(i)对应二维数组dp的第1行g(i)对应dp的第2行// 第二个2: 由于计算f(i)和gi只需要用到f(i-1)和g(i-1)的值int[][] dp new int[2][2];char ch S.charAt(0);dp[0][0] ch 0 ? 0 : 1;dp[1][0] ch 1 ? 0 : 1;for (int i 1; i len; i) {ch S.charAt(i);int prev0 dp[0][(i - 1) % 2];int prev1 dp[1][(i - 1) % 2];dp[0][i % 2] prev0 (ch 0 ? 0 : 1);dp[1][i % 2] Math.min(prev0, prev1) (ch 1 ? 0 : 1);}return Math.min(dp[0][(len - 1) % 2], dp[1][(len - 1) % 2]);}}
