醜陋的字元串--七月牛客模拟筆試題解（一）

醜陋的字元串

| 時間限制：1秒 | 記憶體限制：32768K | 語言限制： 不限

【醜陋的字元串】牛牛喜歡字元串,但是他讨厭醜陋的字元串。對于牛牛來說,一個字元串的醜陋值是字元串中相同連續字元對的個數。比如字元串“ABABAABBB”的醜陋值是3,因為有一對"AA"和兩對重疊的"BB"。現在給出一個字元串,字元串中包含字元’A’、‘B’和’?’。牛牛現在可以把字元串中的問号改為’A’或者’B’。牛牛現在想讓字元串的醜陋值最小,希望你能幫幫他。

輸入描述：輸入包括一個字元串s,字元串長度length(1 ≤ length ≤ 50),字元串隻包含’A’,‘B’,’?'三種字元。

輸出描述：輸出一個整數,表示最小的醜陋值

示例1

輸入：A?A

輸出：0

解題思路

若字元串以’？‘開頭，前任意個’？‘字元都可以不用管，因為都可以跟第一個非’？‘字元形成AB交錯的字元串，

是以要從第一個非’?‘字元開始周遊。

若下一個字元為‘？’，則把？變為與目前字元相反的字元，若目前字元為A，則問号變為B。

若下一個字元不為’？’，判斷下一個字元是否與目前字元相同，若相同，則醜陋值加以

#include <iostream>
#include <string>
using namespace std;
int uglyStringNum(string str);
int main()
{
	string str;
	cin >> str;
	cout << uglyStringNum(str)<< endl;
}
int uglyStringNum(string str)
{
	if (str == "") return 0;
	int res = 0;
	for (int i = 0; i < str.size()-1; i++)
	{
		if(str[i] == '?') continue;
		if (str[i + 1] == '?')
		{
			str[i + 1] = str[i] == 'A' ? 'B' : 'A';
		}
		else if (str[i + 1] == str[i]) res++;
	}
	return res;
}