2017京东校园招聘笔试题

题目描述：

4和7是两个幸运数字，我们定义，十进制表示中，每一位只有4和7两个数的正整数都是幸运数字。前几个幸运数字是：4,7,44,47,74,77,444,447…

现在输入一个数字k，输出第k个幸运数

样例输入
3
5
100
10000000
样例输出
74
744747
44774447447477474444447

/**
 * 将4和7看成二进制0和1, 4->0 7->1
 *
 * 一位数有2个 pow(2,1)
 * 4->0
 * 7->1
 *
 * 2位数有4个 pow(2,2)
 * 44->00
 * 47->01
 * 74->10
 * 77->11
 *
 * 3位数有8个 pow(2,3)
 * 444->000
 * 447->001
 * 474->010
 * 477->011
 * 744->100
 * 747->101
 * 774->110
 * 777->111
 *
 * n位数有pow(2,n)个
 *
 * 求第k个幸运数,即求k的bits是几位数
 * for (i;i++) {
 *     count += Math.pow(2,i);
 *     if (k <= count) {
 *         break;
 *     }
 * }
 * bits = i;
 */
public class Main {

    //计算n的bits是几位数
    private static int getBits(long n) {
        long count = 0;
        int bits = 0;
        while (n > count) {
            ++bits;
            count += (long) Math.pow(2,bits);
        }
        return bits;
    }

    private static String solve(long k) {
        int bits = getBits(k);
        //位数小于bits的所有数的个数,
        long sum = (int)Math.pow(2,bits) - 2;
        //计算k在bits数中是第几个数
        long number = k - sum - 1;
        String bitstr = Long.toBinaryString(number);
        int len = bitstr.length();
        StringBuilder sb = new StringBuilder(bits);
        if (len < bits) {
            for (int i = 0,diff = bits - len; i < diff; i++) {
                sb.append('0');//补全位数
            }
        }
        sb.append(bitstr);
        bitstr = sb.toString();
        char[] bitchs = bitstr.toCharArray();
        StringBuilder res = new StringBuilder(bits);
        for (int i = 0; i < bits; i++) {
            if (bitchs[i] == '1') {
                res.append('7');
            }else {
                res.append('4');
            }
        }
        return res.toString();
    }

    public static void main(String[] arg) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            long k = scan.nextLong();
            System.out.println(solve(k));
        }
        scan.close();
    }

}