丑陋的字符串--七月牛客模拟笔试题解（一）

丑陋的字符串

| 时间限制：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;
}