京东幸运数问题

位填充法

• 文字描述：
  将队列法所描述得序列拿来比较会发现一个规律，如下：
  初始序列： 4 , 7 4,7
  得序列2： 44 , 47 , 74 , 77
  得序列3： 444 , 447 , 474 , 477 , 744 , 747 , 774 , 777
  规律：每个序列是包含当前位数得所有幸运数，而且想较前一个序列是以2的倍数递增，每个序列得前一半以 4 开头，后一半是以 7 开头，当把头位去掉以后，剩下得幸运数正好是上一个序列，例如序列3包含所有位数为 3 3 得幸运数，而且前 4 个幸运数是以 4 开头，后 4 个以 7 7 开头，当把头位( 4 / 7 )去掉,剩下 44 , 47 , 74 , 77 ，正好是序列2。
  解决：得到上边规律后，我们按如下思路去做

1. 首先获得第 N 个幸运数得位数,加1位幸运数个数,2位幸运数个数,3位幸运数个数…一直加到 M 位幸运数个数，在加上 M+1 位幸运数个数会大于 N ，则位数位 M
2. 接着创建M元素数组用于存放每一位元素
3. 利用 T = N − 2^ 1 − 2^ 2 − … − 2^( M − 1) 值 确 定 T=N−2^1−2^2−…−2^(M−1)值确定 N 幸 运 数 距 离 序 列 幸运数距离序列 M开头的个数，接着填充数组
   • 首先判断序列 M 个数 2^( M − 1) 是否大于 T ,若大于则此位为 7 , T 减去 2^( M − 1) ,递归
   • 否则为 4 ， T 不变，递归
   • 一递归到最后一位

public static String getFortuneNum(long num) {
	// 确定位数
	int bits = 1;
	for (int i = 2; i <= num; i += Math.pow(2, bits))
		bits++;
	
	// 创建容器
	char[] ret = new char[bits];
	
	// 确定T(num-cur)
	int cur = 0;
	for (int i = 1; i < bits; i++)
		cur += Math.pow(2, i);
	
	//位填充
	fill(ret, 0, num - cur);
	return String.valueOf(ret);
}
public static void fill(char[] ret, int start, double num) {
	if (start == ret.length)
		return;
	int curBits = ret.length - start;
	if (Math.pow(2, curBits - 1) >= num) {
		ret[start] = '4';
		fill(ret, start + 1, num);
	} else {
		ret[start] = '7';
		fill(ret, start + 1,  num - Math.pow(2, curBits - 1));
	}
}