利用Java快速查找21位花朵数示例代码

前言

本文主要给大家介绍了关于利用Java快速查找21位花朵数的相关内容，分享出来供大家参考学习，下面话不多说了，来一起看看详细的介绍吧。

以前备赛的时候遇到的算法题，求所有21位花朵数，分享一下，供大家参考，效率已经很高了。

示例代码

package com.jianggujin;import java.math.BigInteger;import java.util.ArrayList;import java.util.List;public class NarcissusNumber{  private BigInteger[] powerOf10;  private BigInteger[][] preTable1;  private int[][] preTable2;  private int[] selected = new int[10];  private int length;  private List<BigInteger> results;  private int numberSystem = 10;  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(); }  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; }  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 }  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; }  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; }  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); }}