本帖主要表达了作者心中的喜悦之情，毕竟这是人生第一道题被系统肯定。
做这道题所用的时间与效率是成反比的。
在51nod网站中做的一道有助于理解贪心算法的题目：
输入
输入一个字符串S(S的长度 <= 10000)，S中没有除字母外的其他字符。
输出
由你将1-26分配给不同的字母，使得字符串S的完美度最大，输出这个完美度。
输入示例
dad
输出示例
77
【我的解题思路】
- 先计算英文字符串中每个单词所出现的次数，傻傻的我只想到了数组去保存az(AZ)每个单词出现过的次数；
- 得到统计好次数的数组后，将数组以降序形式排序，得到新的数组；
- 将排序完成后的数组与最适合的完美度（出现次数最高的单词给予26的完美度，次之则给予25的完美度，依此类推……）相配合并累加。
- 最后输出整个字符串的完美度。
【我的解题结论】
我现在解题的思路还是有太多的局限性了，需要突破。（比如，要计算英文字符串中每个单词各出现几次，我居然用了数组，并且是一个长度为26，感觉这个用法不是最恰当的）
程序代码：
import java.util.Scanner;
public class greedyTest {
public int[] greedyCountWords(String word) {
/* 从0到字符串的长度减1 */
int i = 0; // 便字符数组索引
int count[] = new int[26]; //出现次数记录, 其中每个元素代表a~z出现的次数
while (i < word.length()) {
//System.out.println(word + "--->>" + i);
switch(word.charAt(i)) {
case 'A' :
count[0]++;
break;
case 'a' :
count[0]++;
break;
case 'B' :
count[1]++;
break;
case 'b' :
count[1]++;
break;
case 'C' :
count[2]++;
break;
case 'c' :
count[2]++;
break;
case 'D' :
count[3]++;
break;
case 'd' :
count[3]++;
break;
case 'E' :
count[4]++;
break;
case 'e' :
count[4]++;
break;
case 'F' :
count[5]++;
break;
case 'f' :
count[5]++;
break;
case 'G' :
count[6]++;
break;
case 'g' :
count[6]++;
break;
case 'H' :
count[7]++;
break;
case 'h' :
count[7]++;
break;
case 'I' :
count[8]++;
break;
case 'i' :
count[8]++;
break;
case 'J' :
count[9]++;
break;
case 'j' :
count[9]++;
break;
case 'K' :
count[10]++;
break;
case 'k' :
count[10]++;
break;
case 'L' :
count[11]++;
break;
case 'l' :
count[11]++;
break;
case 'M' :
count[12]++;
break;
case 'm' :
count[12]++;
break;
case 'N' :
count[13]++;
break;
case 'n' :
count[13]++;
break;
case 'O' :
count[14]++;
break;
case 'o' :
count[14]++;
break;
case 'P' :
count[15]++;
break;
case 'p' :
count[15]++;
break;
case 'Q' :
count[16]++;
break;
case 'q' :
count[16]++;
break;
case 'R' :
count[17]++;
break;
case 'r' :
count[17]++;
break;
case 'S' :
count[18]++;
break;
case 's' :
count[18]++;
break;
case 'T' :
count[19]++;
break;
case 't' :
count[19]++;
break;
case 'U' :
count[20]++;
break;
case 'u' :
count[20]++;
break;
case 'V' :
count[21]++;
break;
case 'v' :
count[21]++;
break;
case 'W' :
count[22]++;
break;
case 'w' :
count[22]++;
break;
case 'X' :
count[23]++;
break;
case 'x' :
count[23]++;
break;
case 'Y' :
count[24]++;
break;
case 'y' :
count[24]++;
break;
case 'Z' :
count[25]++;
break;
case 'z' :
count[25]++;
break;
default : System.out.println("请给出正确的字符串：_ /");
break;
}
i++;
}
/* 遍历数组 */
/* for (int i1 = 0; i1 < count.length; i1++) {
System.out.println("迭代" + count[i1]);
}
*/
return count;
}
// 计算完美度
public int perfectDegree(int[] count) {
/*
将数组排序，从大到小
*/
for (int i = 0; i < count.length - 1; i++) {
for (int j = 0; j < count.length - 1; j++) {
// 数组元素比较，前面的元素小于后面的元素，则互相交换位置
if (count[j] < count[j + 1]) {
int temp = count[j];
count[j] = count[j + 1];
count[j + 1] = temp;
}
}
}
/*
for (int i = 0; i < count.length; i++) {
System.out.println(count[i]);
}
*/
/* 循环将完美度依次赋值并累加 */
int degree = 26;
int plus = 0;
for (int i = 0; i < 26; i++) {
plus += count[i] * degree;
degree--;
}
return plus;
}
public static void main(String[] args) {
greedyTest gdt = new greedyTest();
System.out.println("请输入你要测试的字符串:");
Scanner input = new Scanner(System.in);
// 调用单词计数方法
int[] count = gdt.greedyCountWords(input.next());
int thePerfectDegree = gdt.perfectDegree(count);
System.out.println(thePerfectDegree);
}
}
网友评论