題意：小扣出去秋游魏割，途中收集了一些紅葉和黃葉譬嚣，他利用這些葉子初步整理了一份秋葉收藏集 leaves， 字符串 leaves 僅包含小寫(xiě)字符 r 和 y钞它， 其中字符 r 表示一片紅葉拜银，字符 y 表示一片黃葉。
出于美觀整齊的考慮遭垛，小扣想要將收藏集中樹(shù)葉的排列調(diào)整成「紅尼桶、黃、紅」三部分锯仪。每部分樹(shù)葉數(shù)量可以不相等泵督，但均需大于等于 1。每次調(diào)整操作庶喜，小扣可以將一片紅葉替換成黃葉或者將一片黃葉替換成紅葉小腊。請(qǐng)問(wèn)小扣最少需要多少次調(diào)整操作才能將秋葉收藏集調(diào)整完畢。
思路：這題咋一看是個(gè)O(N^2)的復(fù)雜度溃卡，但是用前綴和可以做到O(N)溢豆。用sum[i]表示i及i之前的red樹(shù)葉的總個(gè)數(shù)，假設(shè)最終的結(jié)果是[0,i]是red瘸羡，[i+1, j]是yellow，[j+1, n]是red. 那么總共翻轉(zhuǎn)的次數(shù)可以表示為：
化簡(jiǎn)得到?
其中前半部分只跟
這樣在O(N)的復(fù)雜度內(nèi)可以得到答案卷仑。
C++代碼：
class?Solution?{
public:
????static?const?int?maxn?=?100010;
????int?sum[maxn];
????int?minx[maxn];
????int?minimumOperations(string?leaves)?{
????????memset(sum,?0,?sizeof(sum));
????????memset(minx,?0,?sizeof(minx));
????????for(int?i?=?0;?i?<?leaves.size();?i++){
????????????if(leaves[i]?==?'r'){
????????????????if(i?==?0)?sum[i]?=?1;
????????????????else?sum[i]?=?sum[i?-?1]?+?1;
????????????}else?if(i?!=?0)?sum[i]?=?sum[i?-?1];
????????}
????????for(int?i?=?leaves.size()?-?2;?i?>=?0;?i--){
????????????if(i?==?leaves.size()?-?2){
????????????????minx[i]?=?2?*?sum[i]?-?i;
????????????}
????????????else?minx[i]?=?min(minx[i?+?1],?2?*?sum[i]?-?i);
????????}
????????int?res?=?-1;
????????int?n?=?leaves.size()?-?1;
????????for(int?i?=?0;?i?<?leaves.size()?-?2;?i++){
????????????int?tmp?=?i?+?n?+?1?-?2?*?sum[i]?-?sum[n]?+?minx[i?+?1];
????????????if(res?==?-1)?res?=?tmp;
????????????else?res?=?min(res,?tmp);
????????}
????????return?res;
????}
};
//"yyrryrryryyyyyyryy"
//"yyrryryy"
//"yyyrryryy"
