調(diào)整隊(duì)形

問(wèn)題描述

在幼兒園有n個(gè)小朋友排列為一個(gè)隊(duì)伍仰冠,從左到右一個(gè)挨著一個(gè)編號(hào)為(0~n-1)。其中有一些是男生蝶糯,有一些是女生洋只,男生用'B'表示,女生用'G'表示昼捍。小朋友們都很頑皮识虚,當(dāng)一個(gè)男生挨著的是女生的時(shí)候就會(huì)發(fā)生矛盾。作為幼兒園的老師妒茬,你需要讓男生挨著女生或者女生挨著男生的情況最少担锤。你只能在原隊(duì)形上進(jìn)行調(diào)整,每次調(diào)整只能讓相鄰的兩個(gè)小朋友交換位置乍钻,現(xiàn)在需要盡快完成隊(duì)伍調(diào)整肛循,你需要計(jì)算出最少需要調(diào)整多少次可以讓上述情況最少。例如:
GGBBG -> GGBGB -> GGGBB
這樣就使之前的兩處男女相鄰變?yōu)橐惶幭噜徱瘢枰{(diào)整隊(duì)形2次

輸入描述

輸入數(shù)據(jù)包括一個(gè)長(zhǎng)度為n且只包含G和B的字符串.n不超過(guò)50.

輸出描述

輸出一個(gè)整數(shù)多糠,表示最少需要的調(diào)整隊(duì)伍的次數(shù)

輸入例子

GGBBG

輸出例子

2

分析

初看起來(lái)和逆序?qū)Φ膯?wèn)題很像,逆序?qū)梢栽诟鞣N排序算法中進(jìn)行統(tǒng)計(jì)欢摄。但是題目要求男生和女生只能和相鄰的小朋友交換位置熬丧,不能和隊(duì)伍中的任何一個(gè)人交換位置笋粟。于是想到two-pointers的方法怀挠,首尾指針遍歷析蝴,遇到順序不對(duì)的就進(jìn)行交換,累加計(jì)數(shù)器绿淋。注意最終的結(jié)果可能是GGG...BBB...闷畸,也可能是BBB...GGG...,兩種情況都需要考慮吞滞,最后取交換次數(shù)較小的那個(gè)佑菩。

note

不需要真正交換元素,遍歷到順序不對(duì)的元素只累加計(jì)數(shù)器就好了

代碼

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

// 計(jì)算交換次數(shù)裁赠,bc(begin character)為隊(duì)首性別殿漠,ec(end character)為隊(duì)尾性別
int calcSwapCount(char bc, char ec, char *str, int n)
{
    int count = 0;
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        if (str[begin] == bc)
            begin++;
        else if (str[end] == ec)
            end--;
        else if (str[begin] == ec && str[end] == bc)
        {
            count += end - begin; // 將順序出錯(cuò)的begin和end交換需要的步數(shù)
            begin++;
            end--;
        }
    }
    return count;
}

int main()
{
    char str[51];
    scanf("%s", &str);
    int n = strlen(str);

    printf("%d\n", min(calcSwapCount('G', 'B', str, n), 
        calcSwapCount('B', 'G', str, n)));

    return 0;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市佩捞,隨后出現(xiàn)的幾起案子绞幌,更是在濱河造成了極大的恐慌,老刑警劉巖一忱,帶你破解...
    沈念sama閱讀 223,002評(píng)論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件莲蜘,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡帘营,警方通過(guò)查閱死者的電腦和手機(jī)票渠,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評(píng)論 3 400
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)芬迄,“玉大人问顷,你說(shuō)我怎么就攤上這事≠魇幔” “怎么了择诈?”我有些...
    開封第一講書人閱讀 169,787評(píng)論 0 365
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)出皇。 經(jīng)常有香客問(wèn)我羞芍,道長(zhǎng),這世上最難降的妖魔是什么郊艘? 我笑而不...
    開封第一講書人閱讀 60,237評(píng)論 1 300
  • 正文 為了忘掉前任荷科,我火速辦了婚禮,結(jié)果婚禮上纱注,老公的妹妹穿的比我還像新娘畏浆。我一直安慰自己,他們只是感情好狞贱,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評(píng)論 6 398
  • 文/花漫 我一把揭開白布刻获。 她就那樣靜靜地躺著,像睡著了一般瞎嬉。 火紅的嫁衣襯著肌膚如雪蝎毡。 梳的紋絲不亂的頭發(fā)上厚柳,一...
    開封第一講書人閱讀 52,821評(píng)論 1 314
  • 那天,我揣著相機(jī)與錄音沐兵,去河邊找鬼别垮。 笑死,一個(gè)胖子當(dāng)著我的面吹牛扎谎,可吹牛的內(nèi)容都是我干的碳想。 我是一名探鬼主播,決...
    沈念sama閱讀 41,236評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼毁靶,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼胧奔!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起预吆,我...
    開封第一講書人閱讀 40,196評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤葡盗,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后啡浊,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體觅够,經(jīng)...
    沈念sama閱讀 46,716評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評(píng)論 3 343
  • 正文 我和宋清朗相戀三年巷嚣,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了喘先。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,928評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡廷粒,死狀恐怖窘拯,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情坝茎,我是刑警寧澤涤姊,帶...
    沈念sama閱讀 36,583評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站嗤放,受9級(jí)特大地震影響思喊,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜次酌,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評(píng)論 3 336
  • 文/蒙蒙 一恨课、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧岳服,春花似錦剂公、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至,卻和暖如春拖吼,著一層夾襖步出監(jiān)牢的瞬間鳞上,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工绿贞, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留因块,地道東北人橘原。 一個(gè)月前我還...
    沈念sama閱讀 49,378評(píng)論 3 379
  • 正文 我出身青樓籍铁,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親趾断。 傳聞我的和親對(duì)象是個(gè)殘疾皇子拒名,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容