数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C++ 中将字符串翻转为单调递增
假设给定一个由 '0' 和 '1' 组成的字符串。如果该字符串由一些 '0'（可能为 0）后跟一些 '1'（也可能为 0）组成，则该字符串将是单调递增的。我们有一个由 '0' 和 '1' 组成的字符串 S，我们可能会将任何 '0' 翻转为 '1'，或将 '1' 翻转为 '0'。求出使 S 单调递增所需的最小翻转次数。因此，如果输入为 "010110"，那么输出将为 2。通过翻转，我们可以得到 "011111" 或 "000111"。
要解决这个问题，我们将遵循以下步骤 -
n := S 的大小，设置 flipCount := 0，oneCount := 0
对于 i 在 0 到 n – 1 的范围内
如果 S[i] 为 0，则
如果 oneCount = 0，则跳到下一个迭代
将 flipCount 增加 1
否则将 oneCount 增加 1
如果 oneCount < flipCount，则设置 flipCount := oneCount
返回 flipCount
让我们看看以下实现以获得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minFlipsMonoIncr(string S) {
int n = S.size();
int flipCount = 0;
int oneCount = 0;
for(int i = 0; i < n; i++){
if(S[i] == '0'){
if(oneCount == 0) continue;
flipCount++;
} else oneCount++;
if(oneCount < flipCount) flipCount = oneCount;
}
return flipCount;
}
};
main(){
Solution ob;
cout << (ob.minFlipsMonoIncr("010110"));
}输入
"010110"
输出
2
更新于： 30-4-2020
314 次浏览
广告