题解 | #名字的漂亮度#

名字的漂亮度

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

题目的主要信息：

字符串的“漂亮度”是其所有字母“漂亮度”的总和。
每个字母都有一个“漂亮度”，范围在1到26之间。没有任何两个不同字母拥有相同的“漂亮度”。字母忽略大小写。

给出多个名字，计算每个名字最大可能的“漂亮度”。

方法一：

首先统计字符串中，每个字符出现的次数，用num储存。要想最大化字符串的漂亮度，只需要让出现次数最多的字母的漂亮度最大即可，因此对num从大到小排序，然后计算字符串的漂亮度，出现次数最多的字符的漂亮度为26，然后递减为25、24……。最后得到的漂亮度即为最大的漂亮度。 alt 具体做法：

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

static bool cmp( int a, int b){//用于改变sort的排序方式
    return a>b?true:false;
}

int main(){
    int n;
    while(cin>>n){
        string str;
        for(int i=0;i<n;i++){
            cin>>str;
            vector<int> num(26,0);
            for(int j=0;j<str.size();j++){
                num[str[j]-'a']++;//统计每个字符出现的次数
            }
            sort(num.begin(),num.end(),cmp);//从大到小排序
            int result=0;
            int value=26;//单个字符的漂亮度
            for(int j=0;j<num.size();j++){//遍历一遍所有字符，出现次数最多的漂亮度越大
                if(num[j]!=0){
                    result+=value*num[j];//加上当前字符的漂亮度
                    value--;
                }
            }
            cout<<result<<endl;
        }
    }
}

复杂度分析：

时间复杂度： $O (n l o g_{2} n)$ ，sort函数是快速排序，时间复杂度为 $O (n l o g_{2} n)$ 。
空间复杂度： $O (1)$ ，num的大小为常数，

方法二：

方法二和方法一整体思路相同。首先统计字符串中，每个字符出现的次数，用num储存。要想最大化字符串的漂亮度，只需要让出现次数最多的字母的漂亮度最大即可，在方法二中引入降序的优先队列，能保证加入到优先队列中的元素按照降序排列，计算的时候从优先队列中pop出的元素是按照出现次数降序出现的，最先计算的漂亮度最大，而后递减。优先队列的引进减少了时间复杂度。

具体做法：

#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        while(n--){
            string str;
            cin >> str;
            vector<int> num(26,0);//保存每个字符的出现次数
            for(int i = 0; i < str.size(); i++){
                num[str[i]-'a']++; //统计每个字母出现次数
            }
            priority_queue <int,vector<int>,less<int> > q;//降序的优先队列
            for(auto iter:num){
                if(iter!=0){//将出现次数不为0的加入到优先队列中
                    q.push(iter);
                }
            }
            int res = 0;
            int value = 26; 
            while(!q.empty()){ //遍历优先队列计算字符串的漂亮度
                res += q.top() * value; //出现次数越多的字符漂亮度越大
                q.pop();
                value--;//漂亮度递减
            }
            cout << res << endl;
        }
    }
    return 0;
}

复杂度分析：