[Offer收割]程式設計練習賽79——字母去重

題目

時間限制:10000ms

單點時限:1000ms

記憶體限制:256MB

描述

給定一個字元串S，每次操作你可以将其中任意一個字元修改成其他任意字元。

請你計算最少需要多少次操作，才能使得S中不存在兩個相鄰的相同字元。

輸入

隻包含小寫字母的字元串S。

1 ≤ |S| ≤ 100000

輸出

一個整數代表答案

樣例輸入

aab
           

樣例輸出

1
           

思路

這道題是一道水題。思路是從字元串的第二個字元開始，看s[i]是否與s[i-1]相等，如果相等，就看s[i-1]的值是否進行了修改，如果s[i-1]進行了修改，那麼s[i]就不用再進行修改（因為s[i-1]可以修改為任意字元，是以無論如何都可以改成與其相鄰的字元不同）；如果s[i-1]沒有進行修改，那麼就要改s[i]。這裡主要的技巧在于如何記錄是否進行了修改。

代碼

#include <iostream>
#include <stdio.h>
#include <string>
#include<string.h>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;



int main() {
    char s[100005];
    int i, j, k, ans, tip;
    while(~scanf("%s", &s)) {
        ans = 0;
        tip = 0;
        for(i=1; i<strlen(s); i++) {
            if(s[i] == s[i-1]) {
                if(tip == 0) {
                    tip++;
                    ans++;
                }
                else {
                    tip = 0;
                }
            }
            else {
                tip = 0;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}