前言
本文主要给大家介绍了关于利用java快速查找21位花朵数的相关内容，分享出来供大家参考学习，下面话不多说了，来一起看看详细的介绍吧。
以前备赛的时候遇到的算法题，求所有21位花朵数，分享一下，供大家参考，效率已经很高了。
示例代码
我要评论
package com.jianggujin;
import java.math.biginteger;
import java.util.arraylist;
import java.util.list;
/**
* 水仙花数
*
* @author jianggujin
*
*/
public class narcissusnumber
{
/**
* 记录10的0~n次方
*/
private biginteger[] powerof10;
/**
* 记录0到9中任意数字i的n次方乘以i出现的次数j的结果（i^n*j）
*/
private biginteger[][] pretable1;
/**
* 记录离pretable中对应数最近的10的k次方
*/
private int[][] pretable2;
/**
* 记录0到9中每个数出现的次数
*/
private int[] selected = new int[10];
/**
* 记录水仙花数的位数
*/
private int length;
/**
* 记录水仙花数
*/
private list<biginteger> results;
/**
* 记录当前的进制
*/
private int numbersystem = 10;
/**
* @param n
* 水仙花数的位数
*/
private narcissusnumber(int n)
{
powerof10 = new biginteger[n + 1];
powerof10[0] = biginteger.one;
length = n;
results = new arraylist<biginteger>();
// 初始化powerpowerof10
for (int i = 1; i <= n; i++)
{
powerof10[i] = powerof10[i - 1].multiply(biginteger.ten);
}
pretable1 = new biginteger[numbersystem][n + 1];
pretable2 = new int[numbersystem][n + 1];
// pretable[i][j] 0-i的n次方出现0-j次的值
for (int i = 0; i < numbersystem; i++)
{
for (int j = 0; j <= n; j++)
{
pretable1[i][j] = new biginteger(new integer(i).tostring()).pow(n)
.multiply(new biginteger(new integer(j).tostring()));
for (int k = n; k >= 0; k--)
{
if (powerof10[k].compareto(pretable1[i][j]) < 0)
{
pretable2[i][j] = k;
break;
}
}
}
}
}
public static list<biginteger> search(int num)
{
narcissusnumber narcissusnumber = new narcissusnumber(num);
narcissusnumber.search(narcissusnumber.numbersystem - 1, biginteger.zero, narcissusnumber.length);
return narcissusnumber.getresults();
}
/**
* @param currentindex
* 记录当前正在选择的数字(0~9)
* @param sum
* 记录当前值（如选了3个9、2个8 就是9^n*3+8^n*2）
* @param remaincount
* 记录还可选择多少数
*/
private void search(int currentindex, biginteger sum, int remaincount)
{
if (sum.compareto(powerof10[length]) >= 0)
{
return;
}
if (remaincount == 0)
{
// 没数可选时
if (sum.compareto(powerof10[length - 1]) > 0 && check(sum))
{
results.add(sum);
}
return;
}
if (!precheck(currentindex, sum, remaincount))
{
return;
}
if (sum.add(pretable1[currentindex][remaincount]).compareto(powerof10[length - 1]) < 0)// 见结束条件2
{
return;
}
if (currentindex == 0)
{
// 选到0这个数时的处理
selected[0] = remaincount;
search(-1, sum, 0);
}
else
{
for (int i = 0; i <= remaincount; i++)
{
// 穷举所选数可能出现的情况
selected[currentindex] = i;
search(currentindex - 1, sum.add(pretable1[currentindex][i]), remaincount - i);
}
}
// 到这里说明所选数currentindex的所有情况都遍历了
selected[currentindex] = 0;
}
/**
* @param currentindex
* 记录当前正在选择的数字(0~9)
* @param sum
* 记录当前值（如选了3个9、2个8 就是9^n*3+8^n*2）
* @param remaincount
* 记录还可选择多少数
* @return 如果当前值符合条件返回true
*/
private boolean precheck(int currentindex, biginteger sum, int remaincount)
{
if (sum.compareto(pretable1[currentindex][remaincount]) < 0)// 判断当前值是否小于pretable中对应元素的值
{
return true;// 说明还有很多数没选
}
biginteger max = sum.add(pretable1[currentindex][remaincount]);// 当前情况的最大值
max = max.divide(powerof10[pretable2[currentindex][remaincount]]);// 取前面一部分比较
sum = sum.divide(powerof10[pretable2[currentindex][remaincount]]);
while (!max.equals(sum))
{
// 检验sum和max首部是否有相同的部分
max = max.divide(biginteger.ten);
sum = sum.divide(biginteger.ten);
}
if (max.equals(biginteger.zero))// 无相同部分
{
return true;
}
int[] counter = getcounter(max);
for (int i = 9; i > currentindex; i--)
{
if (counter[i] > selected[i])// 见结束条件3
{
return false;
}
}
for (int i = 0; i <= currentindex; i++)
{
remaincount -= counter[i];
}
return remaincount >= 0;// 见结束条件4
}
/**
* 检查sum是否是花朵数
*
* @param sum
* 记录当前值（如选了3个9、2个8 就是9^n*3+8^n*2）
* @return 如果sum存在于所选集合中返回true
*/
private boolean check(biginteger sum)
{
int[] counter = getcounter(sum);
for (int i = 0; i < numbersystem; i++)
{
if (selected[i] != counter[i])
{
return false;
}
}
return true;
}
/**
* @param value
* 需要检验的数
* @return 返回value中0到9出现的次数的集合
*/
private int[] getcounter(biginteger value)
{
int[] counter = new int[numbersystem];
char[] sumchar = value.tostring().tochararray();
for (int i = 0; i < sumchar.length; i++)
{
counter[sumchar[i] - '0']++;
}
return counter;
}
/**
* 获得结果
*
* @return
*/
public list<biginteger> getresults()
{
return results;
}
public static void main(string[] args)
{
int num = 21;
system.err.println("正在求解" + num + "位花朵数");
long time = system.nanotime();
list<biginteger> results = narcissusnumber.search(num);
time = system.nanotime() - time;
system.err.println("求解时间:\t" + time / 1000000000.0 + "s");
system.err.println("求解结果:\t" + results);
}
}
运行查看结果：
正在求解21位花朵数
求解时间: 0.327537257s
求解结果: [128468643043731391252, 449177399146038697307]
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对移动技术网的支持。
如对本文有疑问， 点击进行留言回复！！
HashMap、Hashtable、ConcurrentHashMap三者间的异同
解决RecycleView 中Item包含Edittext时，滑动view复用导致数据错乱的问题
多线程、同步工作原理、死锁案例、Lock接口、线程的生命周期的讲解及实现
网友评论