面试算法92:翻转字符
2024-01-07 22:32:47
题目
输入一个只包含’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’时,这一步不需要翻转,f(i)=f(i-1);当输入字符串中下标为i的字符是’1’时,f(i)=f(i-1)+1,因为要把下标为i的字符翻转成’0’。
- 如果翻转之后下标为i的字符是’1’,那么无论下标为i-1的字符是’0’还是’1’都满足题目的要求。当输入字符串S[i]是’0’时,g(i)=min[f(i-1),g(i-1)]+1,因为要把第i个字符翻转成’1’;当S[i]是’1’时,此时不需要翻转字符,因此g(i)=min[f(i-1),g(i-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;
}
// 第一个2:f(i)对应二维数组dp的第1行,g(i)对应dp的第2行
// 第二个2: 由于计算f(i)和g(i)只需要用到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]);
}
}
文章来源:https://blog.csdn.net/GoGleTech/article/details/135392530
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!