89. Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

一刷
题解:
利用backtracking, 从0到n,先计算用0开头的数,再计算用1开头的数, n++, 然后再在原先的基础上,开头添上0或1

Time Complexity - O(2n)

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<Integer>();
        if(n<0) return res;
        if(n == 0){
            res.add(0);
            return res;
        }
        
        List<Integer> last = grayCode(n-1);
        res.addAll(last);//begin with 0
        int prefix = (1<<n-1);// begin with 1
        
        for(int i=last.size() -1; i>=0; i--){
            res.add(last.get(i) + prefix);
        }
        
        return res;
    }
}

二刷
1 <= i < 2^n
G(i) = i ^ i/2;

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        for(int i=0; i<1<<n; i++){
            res.add(i ^ (i>>1));
        }
        return res;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 9,934评论 0 23
  • 就是那一瞬间的回眸 我们相逢 就是那一瞬间的微笑 我们会意 邂逅在 那瞬间的停留 你像夜空中的流星 即使瞬间 依然...
    孕育随笔阅读 279评论 0 1
  • 昨天,一朋友说我不缺贵人!我安静的想了想,确实,我一路上遇到了许许多多的贵人。 给我生命的父母。为了给我们创造良好...
    米勒Li阅读 190评论 1 1
  • 曾经想要个女儿,以为这样可以成为慈父,有个女儿可以成为这个家族中的掌上明珠,但是个儿子,似乎有些遗憾,然而第一次抱...
    顾晴枫阅读 10,186评论 12 18
  • 安装 选项 -E:只进行预处理,不编译-S:只编译,不汇编-c:只编译、汇编,不链接-g:编译器在编译的时候产生调...
    第八区阅读 2,034评论 0 1