【算法】5位数字黑洞

1007.5位数字黑洞

Description

任意一个5位数，比如：34256，把它的各位数字打乱，重新排列，可以得到一个最大的数：65432，一个最小的数23456。求这两个数字的差，得：41976，把这个数字再次重复上述过程（如果不足5位，则前边补0）。如此往复，数字会落入某个循环圈（称为数字黑洞）。

比如，刚才的数字会落入：[82962, 75933, 63954, 61974] 这个循环圈。

请编写程序，找到5位数所有可能的循环圈，并输出，每个循环圈占1行。其中5位数全都相同则循环圈为 [0]，这个可以不考虑。循环圈的输出格式仿照：

[82962, 75933, 63954, 61974]

其中数字的先后顺序可以不考虑。

Input

Output

[74943, 62964, 71973, 83952]

[63954, 61974, 82962, 75933]

[53955, 59994]

[0]

模拟上述过程即可，注意优化

import java.util.Arrays;
public class T71 {
	static int[] data=new int[10000*10+1];
	public static void main(String[] args) {
		for (int i = 10000; i <= 100000; i++) {
			if (convert(i) == 0) { //对于 XXXXX这样的数（例如33333），不用处理。
				data[i] = 1;    //标记出现过num
				continue;
			}
			if (data[i] == 1){  //已出现过的数不再处理。
				continue;
			}
			getQuan(i);
		}
	}

	private static void getQuan(int k) {
		int[] arr=new int[1000];
		arr[0]=k;
		
		//主要的不同点：将每次做差得到的数依次放进数组中，然后输出圈的时候比较方便
		//老师的将得到的数做数组下标，放进圈中，然后打印圈什么的有点复杂
		while(data[k]!=1){
			data[k]=1;
			int m=convert(k);
			k=m;
			for (int i = 1; i < arr.length; i++) {
				if(arr[i]==0){//圈中没有的数，放进圈中
					arr[i]=m;
					break;
				}else{
					if(arr[i]==m){//找到了圈，打印
						System.out.print("[");
						for (int j = i; j < arr.length; j++) {
							if(arr[j]==0){
								System.out.println("]");
								return;
							}
							System.out.print(arr[j]);
							if(arr[j+1]!=0)
								System.out.print(",");
						}
					}
				}
			}
		}
	}

	private static int convert(int n) {

		int[] arr = new int[5];
		for (int i = 0; i < 5; i++) {
			arr[i] = n % 10;
			n /= 10;
		}
		Arrays.sort(arr);
		int max = 0;
		int min = 0;
		int tenN = 1;
		for (int i = 0; i < 5; i++) {
			min = 10 * min + arr[i];
			max += tenN * arr[i];
			tenN *= 10;
		}		
		return max - min;
	}
}

老师写的方法：

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class T7 {
static int[] visited = new int[100000]; // 放所有出现过的数
static int[] now = new int[100000];  	//存放当前数变换出的所有结果

//双击查看原图到并打印第一次出现的圈
private static void printCircle(int num) {
	int k = num;	
	while (visited[k] != 1  && now[k] != 1 )  //如果没有遇到圈(原来没有出现，且本轮也没有出现)，则继续变换
	{now[k] = num;	 //（1）标记本轮(num起点)出现过n
	visited[k] = 1; 	 //（2）标记出现过n
	k = convert(k);	 //（3）继续变换
	}  

	if(now[k]==num){	//本轮新出现的圈	
	Queue<Integer>  queue = new LinkedList<Integer>(); //放环中的元素
	queue.add(k);	 //k入队
	k = convert(k);
	while (k != queue.peek()) {
	queue.add(k);  
	k = convert(k); 
}

System.out.print( "[");
while( queue.size()>1) {
System.out.print( queue.poll() + ",");
}
System.out.println(queue.poll()+"]");
}
}

/** 
 * @param n
 * @return 返回n变换后的值。
 * 即各位数字打乱，重新排列，得到的最大数-最小数
 */
private static int convert(int n) {
int[] arr = new int[5];
for (int i = 0; i < 5; i++) {
arr[i] = n % 10;
n /= 10;
}

Arrays.sort(arr);
int max = 0;
int min = 0;
int tenN = 1;
for (int i = 0; i < 5; i++) {
min = 10 * min + arr[i];
max += tenN * arr[i];
tenN *= 10;
}	
return max - min;
}

public static void main(String[] args) {

for (int num = 10000; num < 100000; num++) {	//穷举五位数	

if (convert(num) == 0) { //对于 XXXXX这样的数（例如33333），不用处理。
visited[num] = 1;    //标记出现过num
continue;
}

if (visited[num] == 1)  //已出现过的数不再处理。
continue;

printCircle(num);	 //输出圈（只输出第一次出现的情况）
}
}
}