89. Gray Code --迭代和 back tracking 两种方法

发布时间：2020-12-14 04:14:41 所属栏目：大数据来源：网络整理

导读：产生格雷码，格雷码就是前后两个数在二进制上只有一个bit 的差别先看看格雷码的规律：? n =0,? [0] n=1， [0 1] n=2:? ? ?00 ? ? ? ? ? ? 01 ? ? ? ? ? ? 11 ? ? ? ? ? ? 10 n=3:? ? 000 ? ? ? ? ? ?001 ? ? ? ? ? ?011 ? ? ? ? ? ?010 ------------------

产生格雷码，格雷码就是前后两个数在二进制上只有一个bit 的差别

先看看格雷码的规律：?

n =0,? [0]

n=1， [0 1]

n=2:? ? ?00

? ? ? ? ? ? 01

? ? ? ? ? ? 11

? ? ? ? ? ? 10

n=3:? ? 000

? ? ? ? ? ?001

? ? ? ? ? ?011

? ? ? ? ? ?010

-----------------------------

? ? ? ? ? ?110

? ? ? ? ? ?111

? ? ? ? ? ?101

? ? ? ? ? ?100

可以发现规律，比如 n=3 时相比于 n=2 时，前面 4个数字和 n=2 时一样，后四个数字就是在n=2 时结果从后往前前2 bits 不变，然后在最高位上添加1，因此很容易得到一个迭代的算法，code 如下：

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        if(n <0) return  result;   
        result.add(0);
        for(int i=0; i<n; i++){
           int inc = 1<<i;
           int size = result.size(); 
           for(int j=size-1; j>=0;j--){
               result.add(result.get(j)+inc);
           } 
        }
        return result;    
    }
}

code 虽然简单，但一开始被我写错了两处：

1.? 2^n 写成了 2<<n,正确的是 1<<i

2.? for(int j = result.size()-1; j>=0; j--) : 因为 result.size() 会不断增加，所以得先取出 size 。

back tracking 解法：

画一个递归数就明白了：本质上就是一个二叉树，问题是每次到底是先放 0 还是先放1。观察可以发现规律：如果当前路径下? 1的个数为偶数个，就放 left =0,right =1,如果当前路径下 1的个数为奇数，就放left = 1,right =0.

为了统计当前路径下 1的个数，设计了一个Node 节点，里面的count 表示当前 1的个数。

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        dfs(new Node(),result,n);
        return result;
    }
    
    private void dfs(Node curResult,List<Integer> result,int n){
        if(curResult.list.size() == n){
            int sum=0;
            for(int i=0; i<n; i++){
                sum += curResult.list.get(n-i-1) << i;
            }
            result.add(sum);
            return;
        }
        
       
         if(curResult.count%2 ==0){ // 1的个数为偶数个，先放0 再放1
             //left ：
             curResult.list.add(0);
             dfs(curResult,n);
             curResult.list.remove(curResult.list.size()-1);
             
             //right
             curResult.list.add(1);
             curResult.count ++;
             dfs(curResult,n);
             curResult.list.remove(curResult.list.size()-1);
             curResult.count --;
         }
        else {   // 1的个数为奇数个， 先放1， 再放0
             //left
             curResult.list.add(1);
             curResult.count ++;
             dfs(curResult,n);
             curResult.list.remove(curResult.list.size()-1);
             curResult.count --;            
            
             //right 
             curResult.list.add(0);
             dfs(curResult,n);
             curResult.list.remove(curResult.list.size()-1);   
        }
        //right tree
    }
}

class Node {
    List<Integer> list;
    int count;
    Node(){
        list = new ArrayList<>();
        count = 0;
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

89. Gray Code --迭代 和 back tracking 两种方法

89. Gray Code --迭代和 back tracking 两种方法