150
龐果網之字符串消除
題目詳情
給定一個字符串，僅由a,b,c 3種小寫字母組成。當出現連續兩個不同的字母時，你可以用另外一個字母替換它，如
- 有ab或ba連續出現，你把它們替換為字母c；
- 有ac或ca連續出現時，你可以把它們替換為字母b；
- 有bc或cb 連續出現時，你可以把它們替換為字母a。
你可以不斷反複按照這個規則進行替換，你的目標是使得最終結果所得到的字符串盡可能短，求最終結果的最短長度。
輸入：字符串。長度不超過200，僅由abc三種小寫字母組成。
輸出： 按照上述規則不斷消除替換，所得到的字符串最短的長度。
例如：輸入cab，輸出2。因為我們可以把它變為bb或者變為cc。
輸入bcab，輸出1。盡管我們可以把它變為aab -> ac -> b，也可以把它變為bbb，但因為前者長度更短，所以輸出1。
/*********************************
* 日期：2013-11-03
* 作者：SJF0115
* 題號: 題目 字符串消除
* 來源：https://hero.pongo.cn/Question/Details?ID=85&ExamID=83
* 結果：AC
* 來源：龐果網
* 總結：
**********************************/
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
int minLength(const char *s){
int i,len,a = 0,b = 0,c = 0;
len = strlen(s);
//統計字符a,b,c個數
for(i = 0;i < len;i++){
if(s[i] == 'a'){
a++;
}
else if(s[i] == 'b'){
b++;
}
else if(s[i] == 'c'){
c++;
}
}
if(a == len || b == len || c == len){
return len;
}
else{
//判斷奇偶性
a %= 2;
b %= 2;
c %= 2;
if(a + b + c == 0 || a + b + c == 3)
{
return 2;
}
else
{
return 1;
}
}
}
int main()
{
char str[201];
while(scanf("%s",str) != EOF){
printf("%d\n",minLength(str));
}
return 0;
}
【解析】：
最後更新：2017-04-03 14:54:03