当前位置:首页 » Project Euler » 详细页

Cubic permutations 题号:62 难度: 15 中英对照

The cube, 41063625 (3453), can be permuted to produce two other cubes: 56623104 (3843) and 66430125 (4053). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

Solution

此题的意思是,求得一个最小的立方数,使得它的各个位的数所有重新排列的可能中,恰好还有 $5​$ 个都是立方数。返回这5个立方数中的最小值。可以通过如下的思路求解: * 可以将立方数各个位数进行各排序后值相同的立方数,定义为同一个“立方数类别”。(例如,$41063625(345^3)$ 排序后为 $01234566$,$56623104(384^3)$ 排序为也是$01234566$,则认为它们属于同一个立方数类别) * 对整数进行遍历,用数组 $count$ 和 $lowest$,分保存同属于一个“立方数类别”的立方数个数和某个“立方数类别”中的最小值。当满足一个“立方数类别”的立方数个数等于 $5$ 时,返回该类别中的最小立方数即可。 * 其中,每次都进行"立方数类别"的立方数个数判断十分浪费时间。可以当立方数的位数达到一个新高度时,才进行一次“立方数类别”的立方数个数判断,来减少运行时间。例如当立方数的位数达到 $4$ 位时,就可以进行一次判断,因为后续的立方数的位数都会不小于 $4$ ,位数小于 $3$ “立方数类别”的立方数个数不会再增加了。

Code

import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public final class p62 {
	
	public static void main(String[] args) {
		long start = System.nanoTime();
		BigInteger result = run();
        long end = System.nanoTime();
		System.out.println( result );
		System.out.println (( end - start )/1000000 +"ms");
	}
	
	//从0开始遍历,求每个数字的立方,并加入到相应的“立方数类别”中,若有个立方数类别有5个元素,则返回其中的最小值。
	public static BigInteger run() {
		int numDigits = 0;
		Map<String,Integer> lowest = new HashMap<>();   //记录同属于一个“立方数类别”的数中的最小值
		Map<String,Integer> counts = new HashMap<>();   //记录同属于一个“立方数类别”的数的个数
		for (int i = 0; ; i++) {
			String numClass = getCubeNumberClass(i);
			//如果当前数的立方值的位数,达到新值时,才对counts中的数目进行判断,减少判断的次数
			if (numClass.length() > numDigits) {
				int min = Integer.MAX_VALUE;  //答案的上限,设置为2147483647
				for (String nc : counts.keySet()) {  
					if (counts.get(nc) == 5)
						min = Math.min(lowest.get(nc), min);
				}
				if (min != Integer.MAX_VALUE)
					return cube(min);
				
				lowest.clear();
				counts.clear();
				numDigits = numClass.length();
			}
			
			if (!lowest.containsKey(numClass)) {
				lowest.put(numClass, i);
				counts.put(numClass, 0);
			}
			counts.put(numClass, counts.get(numClass) + 1);
		}
	}
	
	//对立方数的各个位进行排序,作为类别。如立方数排序后一样的,认为是同一类
	private static String getCubeNumberClass(int x) {
		char[] digits = cube(x).toString().toCharArray();
		Arrays.sort(digits);
		return new String(digits);
	}
	
	//获得立方数
	private static BigInteger cube(int x) {
		return BigInteger.valueOf(x).pow(3);
	}
	
}
127035954683
54ms