当要你实现的时候,你会怎么下手呢?一般来讲的话,我们就是利用数组及最常用的遍历。这些是最常用的解题思路。可是在面试的时候,面试官更希望看到的是亮点!你的解题过程不能太繁琐,最重要的是保证效率及复杂度。对于算法,如果我们学的不是web前端的话,STL是你需要会的。因为算法与STL关系很密切,不仅是算法,还有数据结构!而这个题目,我们也能够从STL入手来解决问题。
在STL中,有一个关联容器map,这个容器提供了一种算法find,及其本身的特性——pair。pair数据结构能够帮我们在存储数据的同时统计数量。而且,由于map容器是由红黑二叉树实作而成的,它具有自动排序的功能!这个要记住哦!
好了,下面我们来看看实现:
//输出字符串各个字符的个数
#include "iostream"
#include "windows.h"
#include "string"
#include "map"
using namespace std;
int main()
{
string str;
int len;
char word;
cin>>str;
int index;
map<char,int> counts;
len=str.length();
int i;
for(i=0; i<len; i++)
{
word=str.at(i);
++counts[word];//将输入的字符串中的字符挨个输入到map容器
}
for(i=0; i<len; i++)
{
char cha=str.at(i);
map<char,int>::iterator num(counts.find(cha));//开始统计技术
if(num==counts.end())
{
cout<<"查找出错!!!"<<endl;
}
if(num->second>1)//判断是否重复
{
index=str.find(cha,i+1);
if(index!=str.npos&&i+1<len)
{
cout<<num->first<<" ";
cout<<num->second<<endl;
}
}
}
system("pause");
return 0;
}
在构造map时,传入char为数据,int为数量。这就为我们统计字符提供了方便。不过上面的代码只适合字符串中有两个重复字符的情况,若是大于两个,那么在输出的时候,就会重复了。后续改进算法......