问题描述:
我们要给每个字母配一个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,以此类推。
public static int perfect(String s){ s = s.replaceAll("![a-zA-Z]", "").toLowerCase(); char[] chars = new char[26]; int[] frequencies = new int[26]; int cursor = 0; outer: for(int i = 0; i < s.length(); i++) { char c = s.charAt(i); for(int j = 0; j < 26; j++) { if (chars[j] == c) { frequencies[j] += 1; continue outer; } } chars[cursor] = c; frequencies[cursor++] = 1; } int temp = 0; for (int i = frequencies.length - 1; i > 0; i--) { boolean isSort = false; for (int j = 0; j < i; j++) { if(frequencies[j+1] < frequencies[j]) { temp = frequencies[j]; frequencies[j] = frequencies[j+1]; frequencies[j+1] = temp; isSort = true; } if(!isSort) break; } } int sum = 0; cursor = 0; for (int i = frequencies.length-1; i > 0; i--) { sum += frequencies[i] * (26 - cursor++); } return sum; }