京东幸运数问题

位填充法

  • 文字描述:
    将队列法所描述得序列拿来比较会发现一个规律,如下:
    初始序列: 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));
	}
}

#京东#
全部评论
把K+1后转二进制发现,“1”的位置上换成“7”,“0”的位置上换成“4”,忽略最前面一位的。比如“64”加一后的二进制为“1000001”,对应的是“444447”,可以不用迭代更快
点赞 回复 分享
发布于 2016-09-06 15:35
可以啊小范
点赞 回复 分享
发布于 2016-09-06 18:02
序列:4,7,44,47,74,77... 4生成44,47 7生成74,77 44生成444,447 ... 从序列首个数字开始,每个幸运数生成两个新的幸运数添加到序列末尾即可,复杂度为O(n) 更进一步,发现第一个数生成第3,4个数,第二个生成第5,6...有规律:第n个数生成第2n+1,2n+2个数。根据给定的k可以逆推生成规律,其余的幸运数不必遍历,复杂度为O(logN)
点赞 回复 分享
发布于 2016-09-06 15:50
我也是这么做的,然而并没有ac
点赞 回复 分享
发布于 2016-09-06 13:55

相关推荐

点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务