字符串问题(哈希表解决)
码蹄集OJ-连续的串
给你一个字符串,找出现次数最多的长度为2的子串。
暴力解决:定义一个二维数组,横坐标代表长度为二的字符串的第一个字母,纵坐标指的是第二个字母。遍历所给字符串,每两个两个遍历,最后取得二维数组的最大值。最后从数组中将这个最大值所对应的字符串找出来。
#include<bits/stdc++.h> using namespace std;int main( )
{int n,b=0;char s[101];cin>>n>>s;int arr[26][26]={0};for(int i=0;i<n-1;i++){int x=s[i]-'A';int y=s[i+1]-'A';arr[x][y]++;b=max(b,arr[x][y]);}for(int i=0;i<26;i++){for(int j=0;j<26;j++){if(arr[i][j]==b){cout<<char('A'+i)<<char('A'+j);return 0;}}}
}
利用map数据结构解决:
map<string, int> freq;
定义一个map集合,表示每一种字符串出现的次数。利用substr()函数从i开始向后取2个元素,再将这个字符串出现的次数加一。遍历哈希表找到出现次数的最大值,也就是值(p.second())的最大值,和这个键值所对应的字符串。
#include<bits/stdc++.h> using namespace std;int main( )
{int n;string s;cin >> n >> s;map<string, int> freq;for(int i=0;i<n-1;i++){string sub=s.substr(i,2);freq[sub]++;}int maxnum=0;string ss;for(const auto&p:freq){if(p.second>maxnum||p.second==maxnum&&(ss.empty()||p.first<ss)){maxnum=p.second;ss=p.first;}}cout<<ss<<endl;return 0;
}