[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;
}