力扣926. 將字符串翻轉(zhuǎn)到單調(diào)遞增
如果一個(gè)由 '0' 和 '1' 組成的字符串，是以一些 '0'（可能沒有 '0'）后面跟著一些 '1'（也可能沒有 '1'）的形式組成的，那么該字符串是單調(diào)遞增的。
我們給出一個(gè)由字符 '0' 和 '1' 組成的字符串 S，我們可以將任何 '0' 翻轉(zhuǎn)為 '1' 或者將 '1' 翻轉(zhuǎn)為 '0'。
返回使 S 單調(diào)遞增的最小翻轉(zhuǎn)次數(shù)。

示例 1：
輸入："00110"
輸出：1
解釋：我們翻轉(zhuǎn)最后一位得到 00111.

示例 2：
輸入："010110"
輸出：2
解釋：我們翻轉(zhuǎn)得到 011111，或者是 000111。

示例 3：
輸入："00011000"
輸出：2
解釋：我們翻轉(zhuǎn)得到 00000000。

提示：
1 <= S.length <= 20000
S 中只包含字符 '0' 和 '1'

來源：力扣（LeetCode）
鏈接
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

心路歷程：

在最初拿到這道題以及看到它給的例子時(shí)，很容易會(huì)想到說要翻轉(zhuǎn)的數(shù)字會(huì)不會(huì)和左右兩邊的數(shù)字是有聯(lián)系的。

就好像實(shí)例2：把010110翻轉(zhuǎn)成第一種011111或第二種000111，在第一種結(jié)果會(huì)想到第二個(gè)0翻轉(zhuǎn)過來是因?yàn)樽筮吺?，在第二種結(jié)果把1翻轉(zhuǎn)是因?yàn)橛疫吺?，但是這種只從左右兩邊的數(shù)字判斷當(dāng)前的數(shù)字是否需要翻轉(zhuǎn)顯然過于片面，并且結(jié)果是不準(zhǔn)確的。

因此會(huì)想到，想要翻轉(zhuǎn)的次數(shù)最小，就要尋找出，在一串?dāng)?shù)字中的某一段數(shù)字里面0的個(gè)數(shù)比1少（或者1的個(gè)數(shù)比0少），從而實(shí)現(xiàn)單調(diào)遞增。

例如000001101000011100111001111

什么時(shí)候要開始計(jì)數(shù)呢？難道從第一個(gè)數(shù)開始計(jì)數(shù)嗎？不是的，從例子可以看出，無論前面有多少個(gè)0都沒有關(guān)系，不可能因?yàn)榭倲?shù)的0比總數(shù)1多就要把全部的1翻轉(zhuǎn)過來。

所以是從出現(xiàn)第一個(gè)1開始計(jì)數(shù)，每當(dāng)出現(xiàn)0的個(gè)數(shù)大于1的個(gè)數(shù)就把前面數(shù)到的1翻轉(zhuǎn)（因?yàn)楹竺孢€有0，把0翻轉(zhuǎn)的代價(jià)比1大），然后重新計(jì)數(shù)，直到數(shù)完這一串?dāng)?shù)，然后把計(jì)數(shù)的0翻過來。

代碼如下：

#include "iostream";
using namespace std;
int main(){
    string s;
    int count0=0,count1=0,i=0,numcount=0;
    cin>>s;
    int len=s.length();
    while(i<len){
        if(s[i++]=='1')
           count1++;
        else 
        {
           if(count1>0)  count0++;
        }
        if(count0>count1)
           {
             numcount+=count1;
             count0=0;
             count1=0;
           }
    }
    cout<<numcount+count0<<endl;
}