利用Java快速查找21位花朵数示例代码
前言
本文主要给大家介绍了关于利用Java快速查找21位花朵数的相关内容，分享出来供大家参考学习，下面话不多说了，来一起看看详细的介绍吧。
以前备赛的时候遇到的算法题，求所有21位花朵数，分享一下，供大家参考，效率已经很高了。
示例代码
packagecom.jianggujin;
importjava.math.BigInteger;
importjava.util.ArrayList;
importjava.util.List;
/**
*水仙花数
*
*@authorjianggujin
*
*/
publicclassNarcissusNumber
{
/**
*记录10的0~N次方
*/
privateBigInteger[]powerOf10;
/**
*记录0到9中任意数字i的N次方乘以i出现的次数j的结果（i^N*j）
*/
privateBigInteger[][]preTable1;
/**
*记录离PreTable中对应数最近的10的k次方
*/
privateint[][]preTable2;
/**
*记录0到9中每个数出现的次数
*/
privateint[]selected=newint[10];
/**
*记录水仙花数的位数
*/
privateintlength;
/**
*记录水仙花数
*/
privateListresults;
/**
*记录当前的进制
*/
privateintnumberSystem=10;
/**
*@paramn
*水仙花数的位数
*/
privateNarcissusNumber(intn)
{
powerOf10=newBigInteger[n+1];
powerOf10[0]=BigInteger.ONE;
length=n;
results=newArrayList();
//初始化powerPowerOf10
for(inti=1;i<=n;i++)
{
powerOf10[i]=powerOf10[i-1].multiply(BigInteger.TEN);
}
preTable1=newBigInteger[numberSystem][n+1];
preTable2=newint[numberSystem][n+1];
//preTable[i][j]0-i的N次方出现0-j次的值
for(inti=0;i=0;k--)
{
if(powerOf10[k].compareTo(preTable1[i][j])<0)
{
preTable2[i][j]=k;
break;
}
}
}
}
}
publicstaticListsearch(intnum)
{
NarcissusNumbernarcissusNumber=newNarcissusNumber(num);
narcissusNumber.search(narcissusNumber.numberSystem-1,BigInteger.ZERO,narcissusNumber.length);
returnnarcissusNumber.getResults();
}
/**
*@paramcurrentIndex
*记录当前正在选择的数字(0~9)
*@paramsum
*记录当前值（如选了3个9、2个8就是9^N*3+8^N*2）
*@paramremainCount
*记录还可选择多少数
*/
privatevoidsearch(intcurrentIndex,BigIntegersum,intremainCount)
{
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(inti=0;i<=remainCount;i++)
{
//穷举所选数可能出现的情况
selected[currentIndex]=i;
search(currentIndex-1,sum.add(preTable1[currentIndex][i]),remainCount-i);
}
}
//到这里说明所选数currentIndex的所有情况都遍历了
selected[currentIndex]=0;
}
/**
*@paramcurrentIndex
*记录当前正在选择的数字(0~9)
*@paramsum
*记录当前值（如选了3个9、2个8就是9^N*3+8^N*2）
*@paramremainCount
*记录还可选择多少数
*@return如果当前值符合条件返回true
*/
privatebooleanpreCheck(intcurrentIndex,BigIntegersum,intremainCount)
{
if(sum.compareTo(preTable1[currentIndex][remainCount])<0)//判断当前值是否小于PreTable中对应元素的值
{
returntrue;//说明还有很多数没选
}
BigIntegermax=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))//无相同部分
{
returntrue;
}
int[]counter=getCounter(max);
for(inti=9;i>currentIndex;i--)
{
if(counter[i]>selected[i])//见结束条件3
{
returnfalse;
}
}
for(inti=0;i<=currentIndex;i++)
{
remainCount-=counter[i];
}
returnremainCount>=0;//见结束条件4
}
/**
*检查sum是否是花朵数
*
*@paramsum
*记录当前值（如选了3个9、2个8就是9^N*3+8^N*2）
*@return如果sum存在于所选集合中返回true
*/
privatebooleancheck(BigIntegersum)
{
int[]counter=getCounter(sum);
for(inti=0;igetResults()
{
returnresults;
}
publicstaticvoidmain(String[]args)
{
intnum=21;
System.err.println("正在求解"+num+"位花朵数");
longtime=System.nanoTime();
Listresults=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]
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对毛票票的支持。