题解 | #统计大写字母个数#

统计大写字母个数

http://www.nowcoder.com/practice/434414efe5ea48e5b06ebf2b35434a9c

题意

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

限制:字符串长度不大于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按其字符排序后为

0 1 2 3 4 5 6 7 8 9 10 11 12
# # # $ % % 1 2 3 O a d d
- - - - - - - - - 大写字母 - - -

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

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

代码

#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(nlog(n))O(n\cdot log(n))

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

全部评论

相关推荐

佛系的本杰明反对画饼:个人看法,实习经历那段是败笔,可以删掉,它和你目标岗位没什么关系,没有用到什么专业技能,甚至会降低你项目经历内容的可信度。个人技能那里可以再多写一点,去boss直聘上看别人写的岗位要求,可以把你会的整合一下,比如熟悉常规的开关电源拓扑结构(BUCK、正激、反激、LLC等),熟悉常用的通信总线协议和通信接口,如UART,IIC,SPI等。简历首先是HR看的,HR大多不懂技术,会从简历里去找关键字,你没有那些关键字他可能就把你筛掉了,所以个人技能尽量针对着岗位描述写一下。还有电赛获佳绩,获奖了就写什么奖,没获奖就把获佳绩删了吧,要不会让人感觉夸大。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务