题意

统计一行字符串中大写字母出现的次数

限制：字符串长度不大于250

方法

实现

直接按照题意，遍历字符串，如果是大写字母，则统计+1，最后输出统计值即可

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    while(getline(cin,s)){
        int n = s.length();
        int ans = 0; // 次数
        for(int i = 0;i<n;i++) {
            ans+= isalpha(s[i]) && isupper(s[i]); // 大写字母
        }
        printf("%d\n",ans);
    }
    return 0;
}

复杂度分析

时间复杂度: 遍历中每位操作代价为常数，所以总时间复杂度为$O(n)O(n)$

空间复杂度: 主要消耗在字符串储存，所以空间复杂度为$O(n)O(n)$

排序+二分

以题目样例为例，对于输入add123#$%#%#O按其字符排序后为

注意到大写字母是属于一个连续区间的，而排序好的数组可以使用二分法。

所以直接找到大写字母开头和结尾的区间，计算区间长度即可

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    while(getline(cin,s)){
        int n = s.length();
        sort(s.begin(),s.end()); // 排序
        printf("%d\n",upper_bound(s.begin(),s.end(),'Z')-lower_bound(s.begin(),s.end(),'A')); // 二分查找
    }
    return 0;
}

复杂度分析

时间复杂度: 处理过程中，排序复杂度最大$O(n\cdot log(n))O(n\backslash cdot\; log(n))$

空间复杂度: 主要消耗在字符串存储，所以是$O(n)O(n)$