leetcode——89.格雷编码

效率不是很好的样子

回溯

用时一小时15分钟

public List<Integer> grayCode(int n) {
        List<Integer> list = new ArrayList<>();
        if(n == 0){
            list.add(0);
            return list;
        }
        //当n>1时
        //编码结果的取值范围0-（2的n次方-1）
        int m = (int)Math.pow(2,n)-1;
        //设置一个boolean[]
        boolean[] used = new boolean[m+1];
        list.add(0);//以0开始
        used[0] = true;
        //如何将整数转换为2进制数?确定长度的二进制数
        StringBuilder b = new StringBuilder();  //对0进行n位的二进制字符串表示
        for(int i = 0;i< n ;i++){
            b.append(0);
        }
        //这里应该写一个函数的吧
        transfer(used,b,list,n);
        return list;
    }

    private void transfer(boolean[] used, StringBuilder b, List<Integer> list, int n) { //b为二进制数
        for(int i = n-1;i>=0;i--){
            //从后往前进行每一位的遍历
            if (b.charAt(i) == '0') {
                b.replace(i, i + 1, "1");
            } else {
                b.replace(i, i + 1, "0");
            }
            int t = Integer.valueOf(b.toString(),2);  //将b转为十进制数
            if(!used[t]) {
                list.add(t);
                used[t] = true;  //t已经被访问过
                transfer(used,b,list,n);
            }else{
                //还原b
                if (b.charAt(i) == '0') {
                    b.replace(i, i + 1, "1");
                } else {
                    b.replace(i, i + 1, "0");
                }
            }
        }
    }

利用格雷编码的镜像关系，如下编码，哇太厉害了太厉害了！！！

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

——2020.7.10