C 小苯的字符串变化

题意:

给定字母组成的字符串, 将其变为前段大写, 后段小写的形式.
每次操作可改变一个字母的大小写, 求最小操作数

思路:

  • 求最小操作数, 即为选定一个最合适的位置, 在此之前的大写字母变小写, 之后的小写字母变大写, 该位置本身的字母是大写还是小写无关紧要(除了首尾两位). 而这些要更改字母的总数就是该位置的操作数了.

  • 使用前缀和求得每个位置前大写个数, 后缀和求得每个位置后小写个数,计算的复杂度为O(n)

  • 再遍历一下, 求得最小值, 输出

注意点:

题目要求全大写或全小写不符合要求.
所以最佳位置不能选在第一个和最后一个(这些位置上字母的大小写不可忽略, 头必须大写, 尾必须小写. 不符合的话需要被改掉, 而最佳位置的字母不会被更改)

错误原因:

根本没想到用前缀和...
一直在想能不能用递归求解, 把题目想复杂了, 看了题解直呼原来如此!

输入:

一个字符串

输出:

一个整数，表示最少的操作次数。

AC代码:

#include <string>
using namespace std;

int fron[100005] = {0, 0}, back[100005] = {0, 0};
string str;

bool islower(char s)
{
	return s <= 'z' && s >= 'a';
}
bool isupper(char s)
{
	return s <= 'Z' && s >= 'A';
}

int main()
{
	cin >> str;//输入
    
	int length = str.size();
	fron[0] = 0;
	back[length - 1] = 0;
	for (int i = 1, j = length - 2; i < length - 1, j > 0; i++, j--)
	{//双指针分别从后面和前面开始计算字母总数, 并存到数组中
		if (islower(str[i - 1]))
			fron[i] = fron[i - 1] + 1;
		else
			fron[i] = fron[i - 1];

		if (isupper(str[j + 1]))
			back[j] = back[j + 1] + 1;
		else
			back[j] = back[j + 1];
	}
    
	int mins = 100005;//找最小值
	for (int i = 1; i < length - 1; i++)
	{
		mins = min(mins, fron[i] + back[i]);
	}
	cout << mins;
	return 0;
}