首页 > 其他 > 详细

字符串完美度

时间:2014-05-03 16:56:39      阅读:415      评论:0      收藏:0      [点我收藏+]
题目详情

我们要给每个字母配一个1-26之间的整数,具体怎么分配由你决定,但不同字母的完美度不同,

而一个字符串的完美度等于它里面所有字母的完美度之和,且不在乎字母大小写,也就是说字母F和f的完美度是一样的。


现在给定一个字符串,输出它的最大可能的完美度。

例如:dad,你可以将26分配给d,25分配给a,这样整个字符串最大可能的完美度为77。


函数头部

C

int perfect(const char *s);

C++

int perfect(const string &s);

java

public static int perfect(String s);



算法描述


题目比较简单,先把字符串都变成大写或者小写,然后依次找出出现次数最多的字母,然后最多的分26,次多的分25,依次类推,最后求和。

直接上代码了。

         
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
void QuickSort(int next[26],int low,int high,int size){
    int i = low;
    int j = high;
    int temp;
    if(i < j){
        temp = next[low];
        while(i < j){
            while(j > i && next[j] <= temp)
                j--;
            next[i] = next[j];
            while(i < j && next[i] >= temp)
                i++;
            next[j] = next[i];
        }
        next[i] = temp;
        QuickSort(next,low,i-1,size);
        QuickSort(next,i+1,high,size);
    }
}
void QuickSortDC(int next[26],int low,int high,int size){
    QuickSort(next,low,high,size);
}
void transform(string &str)
{
    for(int i=0;i<str.length();i++){
        if(islower(str[i]))
            str[i] = str[i]-32;
    }
}
int perfect(const string &s) {
    string str = s;
    int count[26];
    for(int i=0;i<26;i++)
        count[i] = 0;
    transform(str);
    for(int k=0;k<str.length();k++){
        count[str[k]-65]++;
    }
    QuickSortDC(count,0,25,26);
                                            
    int j=26;
    int sum=0;
    for(int x=0;x<26;x++){
        if(count[x] != 0){
            sum+=count[x]*j;
            j--;
        }
    }
    return sum;
}
//start 提示:自动阅卷起始唯一标识,请勿删除或增加。
int main()
{  
                                            
}
//end //提示:自动阅卷结束唯一标识,请勿删除或增加。

代码有点粗糙,但能理解这道题的做法就行了。


字符串完美度,布布扣,bubuko.com

字符串完美度

原文:http://blog.csdn.net/idiotxl_1020/article/details/24904903

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!