经楼下朋友提醒，我这个算法求出的正好是21位水仙花数。于是我对其进行了稍微的修订，使得其支持任意位数的水仙花数求值，效果还不错，理论上的水仙花最大数为34位(我算了下，至少到39位还有解)，我的求解花了半分多钟，而21位数的求解只化了2秒多。
[原题]
http://www.iteye.com/problems/50018
写道
一个21位的整数,它的各个位数的21次方的和加起来等于它本身. 要求:程序在三分钟内完成,Java语言实现.
[解决思路]
这个我最初的思路也是想找出其中是否有数学规律，无奈大学数学就混过来的，只能穷举解决了。
虽然是穷举，但是不同的实现，效果也不一样，如果要从100000000000000000000穷举到999999999999999999999，我想肯定麻烦大了。
这里我主要是换个思路，穷举这个数中的每个位置上的数字的总数。从一开始，我们假设共有该数中存在9个9，我们将这个数的信息存到几个特定的数组中去：
private int[] countArray = new int[10]; // 个数列表
private int[] countSumArray = new int[10]; // 个数总数
private BigInteger[] sumArray = new BigInteger[10];// 值总数
private int offset = 0;// 浮标
countArray记录依次从9到0每个数的个数，countSumArray是countArray中的各个数与其之前所有数的个数的总和(即countSumArray[n]=countSumArray[n-1]+countNum)，sumArray是当前数的总值(即sumArray[n]=sumArray[n-1]+num)。offset是浮标，即当前判定的数的位置
我们对该个数进行判断，9个9后面还有12位数，那么9个9最小就是9个9的平方+12个0的平方，最大是9个9的平方+12个8的平方。我们从以下三个方面来判断：
1. 最小值不大于999999999999999999999
2. 最大值不小于100000000000000000000
3. 最大值与最小值从首部是否相同的部分，如777700000000000000000与777799999999999999999，存在7777相同的部分，如果该相同的部分中有某个数的个数大于offset中相同的值的个数，那么该值也判定为失败
还有一个很重要的判断就是，如果countSumArray中对应的offset中的值为21，那么即所有的位数都有值，那么直接判定如果该值=其各个位置上的数的21次方之和，如果不等返回失败，反之，这个数就是要求的数。
总体判断如上所述，如果失败我们即查询下一个数next()，countSumArray[offset]=21，那么就是查到头了，就返回查找back()。
用到了几个技巧，就是将BigInteger的运算结果直接存储到hashtable中去，可以节约大量运算时间。题中给予了4分钟的时间，以为很需要一段时间，就设置了多线程，后来发现，不使用多线程也只要花费2秒种，多线程的意义也就不复存在了。
应楼下朋友要求，贴图描述解题思路，很少画图，更没用Dia画过图，有粗制滥造之嫌，请勿怪了。。。
[代码实现]
import java.math.BigInteger;
import java.util.Hashtable;
public class Main {
private static final int SIZE = 21;
private int[] countArray = new int[10]; // 个数列表
private int[] countSumArray = new int[10]; // 个数总数
private BigInteger[] sumArray = new BigInteger[10];// 值总数
private int offset = 0;// 浮标
/**
* 设置当前浮标对应的个数，个数的总数，值总数
*
* @param num
* 个数
*/
private void setValue(int num) {
countArray[offset] = num;
if (offset == 0) {
countSumArray[offset] = num;
sumArray[offset] = p(9 - offset).multiply(n(num));
} else {
countSumArray[offset] = countSumArray[offset - 1] + num;
sumArray[offset] = sumArray[offset - 1].add(p(9 - offset).multiply(n(num)));
}
}
/**
* 检验当前数据是否匹配
*
* @return
*/
private boolean checkPersentArray() {
BigInteger minVal = sumArray[offset];// 当前已存在值
BigInteger maxVal = sumArray[offset].add(p(9 - offset).multiply(n(SIZE - countSumArray[offset])));// 当前已存在值+可能存在的最大值
// 最小值匹配
if (minVal.compareTo(MAX) > 0) {
return false;
}
// 最大值匹配
if (maxVal.compareTo(MIN) < 0) {
return false;
}
String minStr = minVal.compareTo(MIN) > 0 ? minVal.toString() : MIN.toString();
String maxStr = maxVal.compareTo(MAX) < 0 ? maxVal.toString() : MAX.toString();
// 找到最小值与最大值间首部相同的部分
int[] sameCountArray = new int[10];
for (int i = 0; i < SIZE; i++) {
char c;
if ((c = minStr.charAt(i)) == maxStr.charAt(i)) {
sameCountArray[c - '0'] = sameCountArray[c - '0'] + 1;
} else {
break;
}
}
// 判断如果相同部分有数据大于现在已记录的位数，返回false
for (int i = 0; i <= offset; i++) {
if (countArray[i] < sameCountArray[9 - i]) {
return false;
}
}
// 如果当前值的总数为SIZE位，那么判断该值是不是需要查找的值
if (countSumArray[offset] == SIZE) {
String sumStr = sumArray[offset].toString();
BigInteger sum = ZERO;
for (int i = 0; i < sumStr.length(); i++) {
sum = sum.add(p(sumStr.charAt(i) - '0'));
}
return sum.compareTo(sumArray[offset]) == 0;
}
return true;
}
/**
* 退出循环，打印
*
* @return
*/
private void success() {
System.out.println("find a match number:" + sumArray[offset]);
}
/**
* 将浮标指向下一位数
*
* @return
*/
private void next() {
offset++;
setValue(SIZE - countSumArray[offset - 1]);
}
/**
*
* 回退浮标，找到最近的浮标，并减一
*
* @return
*/
private boolean back() {
// 回退浮标，找到最近的浮标，并减一
if (countArray[offset] == 0) {
while (countArray[offset] == 0) {
if (offset > 0) {
offset--;
} else {
return true;
}
}
}
if (offset > 0) {
setValue(countArray[offset] - 1);
return false;
} else {
return true;
}
}
/**
* 测试程序
*
* @param startValue
* 测试匹配数中包含9的个数
* @param startTime
* 程序启动时间
*/
private void test(int startValue, long startTime) {
// 设置9的个数
offset = 0;
setValue(startValue);
while (true) {
if (checkPersentArray()) {// 检查当前提交数据是否匹配
// 匹配且总数正好为SIZE的位数，那么就是求解的值
if (countSumArray[offset] == SIZE) {
success();
}
// 总数不为SIZE，且当前值不在第10位（即不等于0）
if (offset != 9) {
next();
continue;
}
// 总数不为SIZE，且当前值在第10位。
if (back()) {
break;
}
} else {
if (back()) {
break;
}
}
}
System.out.println(Thread.currentThread() + " End,Spend time " + (System.currentTimeMillis() - startTime) / 1000 + "s");
}
/**
* 主函数
*/
public static void main(String[] args) {
final long startTime = System.currentTimeMillis();
int s = MAX.divide(p(9)).intValue();
for (int i = 0; i <= s; i++) {
// new Main().test(i, startTime);
// 启动十个线程同时运算
final int startValue = i;
new Thread(new Runnable() {
public void run() {
new Main().test(startValue, startTime);
}
}).start();
}
}
private static final BigInteger ZERO = new BigInteger("0");
private static final BigInteger MIN;
private static final BigInteger MAX;
/**
* 0-SIZE间的BigInteger
*/
private static final BigInteger n(int i) {
return (BigInteger) ht.get("n_" + i);
}
/**
* 0-9的次方的BigInteger
*/
private static final BigInteger p(int i) {
return (BigInteger) ht.get("p_" + i);
}
/**
* 用于缓存BigInteger数据，并初始化0-SIZE间的BigInteger和0-9的次方的BigInteger
*/
private static Hashtable<String, Object> ht = new Hashtable<String, Object>();
static {
int s = SIZE < 10 ? 10 : SIZE;
for (int i = 0; i <= s; i++) {
ht.put("n_" + i, new BigInteger(String.valueOf(i)));
}
for (int i = 0; i <= 10; i++) {
ht.put("p_" + i, new BigInteger(String.valueOf(i)).pow(SIZE));
}
MIN = n(10).pow(SIZE - 1);
MAX = n(10).pow(SIZE).subtract(n(1));
}
}
[结论]
运算结果如下：
Thread[Thread-0,5,main] End,Spend time 0s
Thread[Thread-9,5,main] End,Spend time 0s
Thread[Thread-5,5,main] End,Spend time 0s
Thread[Thread-8,5,main] End,Spend time 0s
find a match number:449177399146038697307
Thread[Thread-4,5,main] End,Spend time 1s
Thread[Thread-7,5,main] End,Spend time 1s
Thread[Thread-6,5,main] End,Spend time 1s
Thread[Thread-3,5,main] End,Spend time 2s
find a match number:128468643043731391252
Thread[Thread-2,5,main] End,Spend time 3s
Thread[Thread-1,5,main] End,Spend time 3s
分享到：
相关推荐
标题中的“一道算法题，亏在二叉树的构造和递归算法上了”暗示了这个问题主要涉及计算机科学中的数据结构，特别是二叉树，以及使用递归算法解决相关问题。在编程领域，二叉树是一种基础且重要的数据结构，常用于实现...
贪心算法 每天一道算法题：分治算法，回归算法，贪心算法，回溯算法.zip
### hadoop2面试题 - 2012腾讯笔试的一道算法题 #### 背景与题目概述 本文档提供了2012年腾讯笔试中一道关于字符串处理的算法题，该题目要求将字符串中的所有大写字母移动到字符串的末尾，同时保持其他字符的相对...
board=Algorithm&gid=8898发信人: snoowball (Snowball), 信区: Algorithm标 题: Re: 问一道算法题
说实话，一天做完一道算法题还是很吃力的，并且每个人都自己的规划和任务，也不是都有时间刷题。所以，大家可以根据具体情况来安排个人时间，有时间了多做一些，没时间就少做或不做。 目前构想的题目知识模块有：
在准备面试时，掌握一些常见的算法题是至关重要的，尤其是对于技术面试来说。这份压缩包“考试类精品--总结一下面试常考的算法题”显然为面试者提供了一个宝贵的资源，帮助他们提升自身的编程和算法解决能力。在这个...
每天一道算法题 为了应付面试，开始写博客，准备开三个系列，第一个 JS算法系列，主要整理一些面试过程中常见的算法题 ； 第二个 ECMAScript规范解析，主要是想从ES规范的角度来解析JS代码的实际执行过程，只有真正...
详细解析与解答：对于每一道算法题，提供清晰、详尽的解题思路、代码实现以及时间复杂度分析是非常重要的。这不仅能帮助用户理解问题本质，还能学习到高效的解决策略。 互动学习平台：一些资源还提供了在线的编程...
12-02-28网易笔试一道算法题,附件代码是我自己的解题
这个问题是去哪儿网2014年笔试中的一道算法题，其目标是编写一个函数`RP2AP`，接收一个相对路径字符串作为输入，并返回其对应的绝对路径。 该函数的核心逻辑如下： 1. 首先，检查输入和输出指针是否为NULL，如果...
每日一道算法题 2021-1-16, 阅读【算法图解】，刷一道二分查找的题目，. 2021-2-8，Leetcode，题号15，刷一道数组的题目，. 2020-2-17，Leetcode，题号16，刷一道数组的题目， 2020-2-18，Leetcode，题号18，刷一道...
描述中的“AlgorithmSet”和“每天一道算法题”表明这是一个系统化的算法学习资源，可能是某个开源项目或者学习计划，旨在帮助用户通过每天解决一道算法题来提升自己的编程和算法能力。"Algorithm.playground"可能是...
【标题】"YunDang-Algorithm:群策群力，每日解决一道算法题" 提供了一个关于算法学习和实践的项目，旨在帮助开发者通过每天解决一个算法问题来提升自己的编程技能。该项目的核心理念是集体智慧，鼓励团队成员共同...
LeetCode Everyday项目就是这样一个极好的资源，它鼓励开发者每天都解决一道算法题，以此来保持对编程的热情和敏锐度。这个项目不仅局限于LeetCode上的题目，而是涵盖了更广泛的算法题目，帮助程序员拓宽视野，深入...
坚持每天刷一道算法题，冲鸭！！！ day1 验证回文字符串 day2 亲密字符串 柠檬水找零 day3 反转字符串中的单词 day4 三数之和 day5 数组中的第k个最大元素 day6 环形链表II day7 无重复字符的最长子串 day8 排序链表...
Code4God:微信平台一天一道算法题的服务器源码，部署在百度云