京东幸运数问题
位填充法
-
文字描述:
将队列法所描述得序列拿来比较会发现一个规律,如下:
初始序列: 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。
解决:得到上边规律后,我们按如下思路去做
- 首先获得第 N 个幸运数得位数,加1位幸运数个数,2位幸运数个数,3位幸运数个数…一直加到 M 位幸运数个数,在加上 M+1 位幸运数个数会大于 N ,则位数位 M
- 接着创建M元素数组用于存放每一位元素
-
利用 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)); } }
#京东#