题目跳转:http://acm.hdu.edu.cn/showproblem.php?pid=1058
这题考的是动态规划
共使用了两种方式,自测答案是对的,不过提交的时候都因Time Limit Exceeded没过
先看下我使用的两个方法:
方法1.穷举,直接用了4个for循环嵌套
private void calHumbleNumber(){long temp_h2, temp_h3, temp_h5, temp_h7;for(int a = 0; a < 32; a++){temp_h2 = power(h_2, a);if(temp_h2 > MAX_NUMBER)break;elselist.add(temp_h2);for(int b = 0; b < 32; b++){temp_h3 = power(h_3, b);long re_h3 = temp_h2 * temp_h3;if(re_h3 > MAX_NUMBER)break;elselist.add(re_h3);for(int c = 0; c < 32; c++){temp_h5 = power(h_5, c);long re_h5 = temp_h2 * temp_h3 * temp_h5;if(re_h5 > MAX_NUMBER)break;elselist.add(re_h5);for(int d = 0; d < 32; d++){temp_h7 = power(h_7, d);long re_h7 = temp_h2 * temp_h3 * temp_h5 * temp_h7;if(re_h7 > MAX_NUMBER)break;elselist.add(re_h7);}}}}System.out.println(list.toString());}
方法2.递归
private void calList(long[] hhh, int longSize, long re_h){if(longSize != 0){longSize--;int d = 0;while(d < 32){long temp_h = power(hhh[longSize], d);if(re_h > MAX_NUMBER)break;list.add(temp_h);calList(hhh, longSize, temp_h);re_h *= temp_h;d++;if(re_h > MAX_NUMBER)break;list.add(re_h);calList(hhh, longSize, re_h);}}}
再说下遇到的几个坑:
1.数据范围的限制MAX_NUMBER的值不能超过2,000,000,000,在这里,如果你用int值,int值的取值范围太小了,所以我使用了long
2.println里面1,2,3的结尾显示要做特殊处理下
if(n % 100 == 11 || n % 100 == 12 || n % 100 == 13)System.out.println("The " + n + "th humble number is " + acm.getHumbleNumber(n) + ".");else if(n % 10 == 1)System.out.println("The " + n + "st humble number is " + acm.getHumbleNumber(n) + ".");else if(n % 10 == 2)System.out.println("The " + n + "nd humble number is " + acm.getHumbleNumber(n) + ".");else if(n % 10 == 3)System.out.println("The " + n + "rd humble number is " + acm.getHumbleNumber(n) + ".");elseSystem.out.println("The " + n + "th humble number is " + acm.getHumbleNumber(n) + ".");
3.我刚开始用的数据类型是LinkedList,后来又改成TreeSet,TreeSet没有get方法,再取值的时候比较麻烦,不知道还有没有更好的数据类型
当眼泪流尽的时候,留下的应该是坚强。