資料結構
網路
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 次瀏覽
廣告