关于算法:格雷码java代码

通常，人们习惯将所有 nn 位二进制串依照字典序排列，例如所有 22 位二进制串按字典序从小到大排列为：00，01，10，1100，01，10，11。

格雷码（Gray Code）是一种非凡的 nn 位二进制串排列法，它要求相邻的两个二进制串间 恰好 有一位 不同，特地地，第一个串与最初一个串也算作相邻。

所有 2 位二进制串按格雷码排列的一个例子为：00，01，11，10。

n 位格雷码不止一种，上面给出其中一种格雷码的生成算法：

1. 1 位格雷码由两个 1 位二进制串组成，程序为：0，10，1。
2. n+1 位格雷码的前 2n 个二进制串，能够由依此算法生成的 n 位格雷码（总共 2n 个 n 位二进制串）按 程序 排列，再在每个串前加一个前缀 0 形成。
3. n+1 位格雷码的后 2n 个二进制串，能够由依此算法生成的 n 位格雷码（总共 2n 个 n 位二进制串）按 逆序 排列，再在每个串前加一个前缀 1 形成。

综上，n+1 位格雷码，由 n 位格雷码的 2n 个二进制串按顺序排列再加前缀 0，和按逆序排列再加前缀 1 形成，共 2n+1 个二进制串。

另外，对于 n 位格雷码中的 2n 个二进制串，咱们按上述算法失去的排列程序将它们从 0 ∼ 2n−1 编号。

按该算法，2 位格雷码能够这样推出：

1. 已知 11 位格雷码为 0，10，1。
2. 前两个格雷码为 00，01。后两个格雷码为 11，10。合并失去 00，01，11，10 编号顺次为 0 ∼ 3。

同理，3 位格雷码能够这样推出：

1. 已知 2 位格雷码为：00，01，11，10。
2. 前四个格雷码为：000，001，011，010。后四个格雷码为：110，111，101，100 110，111，101，100。合并失去：000，001，011，010，110，111，101，100，编号顺次为 0 ∼ 7。

当初给出 n,k，请你求出按上述算法生成的 nn 位格雷码中的 kk 号二进制串。

输出格局

仅一行，蕴含两个整数 nn 和 kk。

输入格局

仅一行，一个 nn 位二进制串示意答案。

数据范畴

对于 50% 的数据：n≤10
对于 80% 的数据：k≤5×106
对于 95% 的数据：k≤263−1
对于 100% 的数据：1≤n≤64,0≤k<2n

输出样例 1：

2 3

输入样例 1：

10

输出样例 2：

3 5

输入样例 2：

111

样例解释

对于样例 1，2 位格雷码为：00，01，11，10，编号从 0 ∼ 3，因而 3 号串是 10。

对于样例 2，3 位格雷码为：000，001，011，010，110，111，101，100，编号从 0 ∼ 7，因而 5 号串是 111。

思路：读题，n 位格雷码能够由 n - 1 位格雷码得出，所以咱们很容易的想到递归思路，一种思路是在每次递归时利用一个数据获取以后位数所有格雷码，而后最初返回一个数组，利用 k 当成下标而后返回后果。

当然这是第一工夫的想法，也的确能够通过肯定的测试样例，然而咱们留神到：对于 95% 的数据：k≤263−1k≤263−1。这样子咱们应用数组的想法也就告吹了，因为前面用来寄存的数据太多了，超过了最大值，所以 pass。

这里咱们能够应用二分法解决这个问题，对于 n =3，k= 5 的状况，咱们思考当 k >=2²时，这个时候也就是说 k = 5 属于 n 的 8 个格雷码的后 4 个之一，这个时候最高位加上 1, 之后 n =n-1=2, 这里咱们留神到前四位格雷码的后两位是两头对称的。

也就是第三点：n+1 位格雷码的后 2n 个二进制串，能够由依此算法生成的 n 位格雷码（总共 2n 个 n 位二进制串）按 逆序 排列，再在每个串前加一个前缀 1 形成:

000，001，011，010，110，111，101，100000，001，011，010，110，111，101，100

好了咱们持续这个时候咱们失去第一位填 1，n=2，k 因为逆序所以是 k = 8(2³)-5(原 k)-1= 2, 因为 k >=2¹, 所以咱们接下来一位接着填 1。

目前，咱们失去一个格雷码 11_, 此时 n =1, 并且 k =4-2-1=1, 此时咱们曾经到了完结条件(n=1, 表明这是最初一位须要填入的), 很显然这个时候咱们失去的 k 不是 1 就是 0，咱们把 k 填入即可。

最初咱们对 n =3,k= 5 的输出失去的格雷码为 111, 而 111 就是 k = 5 对应的格雷码。

把下面的思路整顿成代码即可，咱们应用一个数组 ans 存储每一位的信息, 并初始化为 100 的长度。

然而咱们写完当前，咱们还留神到:对于 100% 的数据：1≤n≤64,0≤k<2ⁿ1≤n≤64,java 中最大的整数类型 long 的最大值是 2 ⁶³-1，而 k 的最大值是 2 ⁶⁴, 很显著，咱们也不能间接应用 Long 这个类型获取 k 的值。

那么问题来了，如果想要齐全做出这道题，咱们仿佛连获取 k 的值都变得十分困难起来，有一个思路是利用 char[]获取 k 的每一位, 然而这里我没有尝试应用这种思路, 我抉择应用 Java 的 BigInteger 来解决大数问题，那么这里咱们只须要将波及到 k 的解决改成 BigInteger 解决即可。

无关 BigInteger 的更多信息能够移步至上面的博客：
Java 中 BigInteger 办法总结:https://www.jianshu.com/p/8b8…

好了，最初的代码如下：

import java.util.Scanner;
import java.math.BigInteger;

public class Main {public static  int[] ans = new int[100];
        public static void main(String[] args){Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        // 获取输出
        // 留神 1≤n≤64,0≤k<2n
        int n = Integer.parseInt(s.split(" ")[0]);
        BigInteger k = new BigInteger((s.split(" ")[1]));

        // 利用数组找下标的形式会超时
        // 必须思考到数字超过 long 的状况
        // 所以还是得用 BigInteger 进行大数解决
        // 应用二分法解题
        dfs(n,k);
        // 应用数组存储后果
        for(int i=n;i>=1;i--){System.out.print(ans[i]);
        }
    }

    public static void dfs(int pos, BigInteger k){
        // 边界条件
        if(pos==1){ans[pos] = k.intValue();
            return;
        }
        BigInteger base  = BigInteger.valueOf(2);
        BigInteger bwt = base.pow(pos-1);
        // 如果处于前半部分
        if(k.subtract(bwt).longValue() < 0){ans[pos] = 0;
            dfs(pos-1, k);
        }else{
            // 处于后半局部须要逆序
            ans[pos] = 1;
            dfs(pos-1, (base.pow(pos)).subtract(k.add(BigInteger.valueOf(1))));
        }
    }
}