格雷码——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>=22时,这个时候也就是说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(23)-5(原k)-1= 2,因为k>=21,所以我们接下来一位接着填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<2n1≤n≤64,java中最大的整数类型long的最大值是263-1,而k的最大值是264,很明显,我们也不能直接使用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))));
        }
    }
}

你可能感兴趣的