题解 | #名字的漂亮度#

名字的漂亮度

http://www.nowcoder.com/practice/02cb8d3597cf416d9f6ae1b9ddc4fde3

题意：

每个字母都有一个“漂亮度”，范围在1到26之间。

没有任何两个不同字母拥有相同的“漂亮度”。字母忽略大小写。

给出一个字符串，计算最大可能的“漂亮度”。

方法一：

贪心

思路：

      对字符串的每种字母计数，字母忽略大小写。

      然后根据贪心，排序。

      （让数值最大的字母*26+数值次大的字母*25+......）以此类推。

#include <bits/stdc++.h>

using namespace std;
int cnt[26];//计数数组

int main(){
    int n;
    string s;
    cin >> n;
    while(n--){
        memset(cnt,0,sizeof(cnt));
        cin >> s;
        int len=s.size();
        for(int i=0;i<len;i++){
            if(s[i]>='a')
                s[i]-=32;
            cnt[s[i]-'A']++;//对字母计数
        }
        sort(cnt,cnt+26);//排序
        int sum=0;
        int num=26;
        for(int i=25;i>=0;i--){//贪心
            if(cnt[i]==0)
                break;
            sum+=cnt[i]*(num--);//求和
        }
        cout << sum << endl;
    }
    return 0;
}

时间复杂度： $O(n),n是字符串长度，排序的数组最大是26，因此排序时间是常数时间。$

空间复杂度： $O(1),cnt[\ ]计数数组长度为26，常数级别存储空间。$

方法二：

优先队列

思路：

思路同方法一相同，但利用优先队列来排序，每次弹出最大值。

#include <bits/stdc++.h>

using namespace std;
int cnt[26];//计数数组

int main(){
    int n;
    string s;
    cin >> n;
    while(n--){
        memset(cnt,0,sizeof(cnt));
        cin >> s;
        int len=s.size();
        for(int i=0;i<len;i++){
            if(s[i]>='a')
                s[i]-=32;
            cnt[s[i]-'A']++;//对字母计数
        }
        priority_queue<int> q;//优先队列
        for(int i=0;i<26;i++)
            q.push(cnt[i]);
        int sum=0;
        int num=26;
        while(!q.empty()){//贪心
            sum+=q.top()*(num--);//求和
            q.pop();
        }
        cout << sum << endl;
    }
    return 0;
}