Leetcode 451 根据字符出现频率排序
@(C++)[leetcode]
1.思路
- 初始化一个长度为48的数组，记录各个字母的个数
- 扫描一遍输入字符串，更新数组的值
- 对数组进行排序
2尝试过程中第一版本代码
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string frequencySort(string s) {
vector<int> alphabet_count;
// 24 for small 24 for big
for(int i=0;i<24;i++) {
alphabet_count.push_back(0);
alphabet_count.push_back(0);
}
for(char c : s){
if( c >= 'a' && c <= 'z'){
alphabet_count[c-'a']++;
}else if(c >= 'A' && c <= 'Z'){
alphabet_count[c-'A'+24]++;
}
}
for(int i=0;i<24;i++){
cout<<char(i+'a')<<",";
}
for(int i=0;i<24;i++){
cout<<char(i+'A')<<",";
}
cout<<endl;
for(int i : alphabet_count){
cout<<i<<",";
}
cout<<endl;
return s;
}
int main(){
string s = "abcdefgABCDEFG";
frequencySort(s);
return 0;
}
输出结果，可以正确统计各个字母的数量
a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X
1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
2.1遇到的问题
但是对数组排序之后，信息丢失，不知道哪个数字对应哪一个字母。
2.2 想想解决办法
可以定义一个结构体，结构体每部包含两个属性:
- 字母
- 字母出现的个数
3 新的方案
3.1 定义结构体，写构造函数
struct alphabet
{
char c;
int count;
alphabet(char c, int n):c(c),count(n){}
};
3.2 改写函数
实现了对结构体的排序，这边直接调用了 #include <algorithm>中的sort()
string frequencySort(string s) {
vector<alphabet> alphabets;
for(int i=0;i<24;i++) {
alphabets.push_back(alphabet('a'+i,0));
}
for(int i=0;i<24;i++) {
alphabets.push_back(alphabet('A'+i,0));
}
for(char c:s){
if( c >= 'a' && c <= 'z'){
alphabets[c-'a'].count++;
}else if(c >= 'A' && c <= 'Z'){
alphabets[c-'A'+24].count++;
}
}
sort(alphabets.begin(),alphabets.end(),[](const alphabet &a, const alphabet &b) {
return a.count > b.count;
});
string result;
for(alphabet a:alphabets){
for(int i = 0;i<a.count;i++){
result.push_back(a.c);
}
}
return result;
}
3.3 提交！
发现没考虑数字的情况！！！！！！！
部分没过
加上数字的情况再试一下，改的过程中发现了问题！是26个字母不是24个字母啊！！！！！
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
// @lc code=start
class Solution {
public:
struct alphabet
{
char c;
int count;
alphabet(char c, int n):c(c),count(n){}
};
string frequencySort(string s) {
vector<alphabet> alphabets;
for(int i=0;i<26;i++) {
alphabets.push_back(alphabet('a'+i,0));
}
for(int i=0;i<26;i++) {
alphabets.push_back(alphabet('A'+i,0));
}
for(int i=0;i<10;i++) {
alphabets.push_back(alphabet('0'+i,0));
}
for(char c:s){
if( c >= 'a' && c <= 'z'){
alphabets[c-'a'].count++;
}else if(c >= 'A' && c <= 'Z'){
alphabets[c-'A'+26].count++;
}else if(c >= '0' && c <= '9'){
alphabets[c-'0'+52].count++;
}
}
sort(alphabets.begin(),alphabets.end(),[](const alphabet &a, const alphabet &b) {
return a.count > b.count;
});
string result;
for(alphabet a:alphabets){
for(int i = 0;i<a.count;i++){
result.push_back(a.c);
}
}
return result;
}
};
过了！
AC
