华为od机试真题- 最小的调整次数

题目描述：

给定一个仅由'A'、'B'、'C'三种字符组成的字符串S，请你计算最少需要修改多少个字符，才能使S满足其中任意相邻的两个字符都不同。

例如，如果 S = "ABABA"，其中最少修改次数为1，即将最后一个'A'改为'C'，使得该串符合所要求的条件。

输入描述：

第一行输入一个整数T，表示有T组数据。接下来有T组数据，每组数据有一行字符串S，其中1 ≤ T ≤ 100，1 ≤ |S| ≤ 100。

输出描述：

每组数据输出一行，即修改次数的最小值。

思路分析：

这是一道非常经典的题目。它的核心就是贪心算法。

由于只有三个字符，那么如果当前位置和前一个位置相同，那么将当前位置修改为与前一个位置不同的字符就可以了。记得改完之后，还需要更新当前位置，以便扫描下一个字符。

如果遇到了情况，需要将前一个字符和当前字符都修改，这是因为要满足任意两个相邻字符都不同的要求。

代码实现：

首先读入T组数据：

int T;
cin >> T;

接下来处理T组数据：

while (T--)
{
string s;
cin >> s;
int cnt = 0;
for (int i = 1; i < s.length(); ++i)
{
if (s[i] == s[i - 1])
{
s[i] = s[i - 1] == 'A' ? 'B' : (s[i - 1] == 'B' ? 'C' : 'A');
++cnt;
}
if (i > 1 && s[i] == s[i - 2])
{
s[i] = s[i - 2] == 'A' ? 'B' : (s[i - 2] == 'B' ? 'C' : 'A');
++cnt;
}
}
cout << cnt << endl;
}

完整代码：