LeetCode89 Gray Code

LeetCode89 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.

本题重点是理解格雷码的生成规律,先试着写出3位格雷码:
000 - 0
001 - 1
011 - 3
010 - 2
110 - 6
111 - 7
101 - 5
100 - 4

000 - 0
001 - 1
011 - 3
010 - 2
110 - 6
100 - 4
101 - 5
111 - 7

一开始我很纠结到底是哪种。。。网上查阅+自己对于2位的情况后,确定应该使用第一种!!!

然后看0132与6754
发现诶?!!!
6754-4444=2310

0132与2310正好是逆序!!!

有没有很神奇?!!

ok

了解这点以后,可以采用回溯,对于n位greycode:
1 先dfs(n-1)获取n-1位greycode
2 将n-1位的greycode都加入n位的list中
3 将n-1位的值都加上2^(n-1)次方的offset后,再加入list中

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

推荐阅读更多精彩内容

  • **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 9,959评论 0 23
  • 沈若雪回到家中,愤愤的坐在椅上倒了杯茶悯了一口。雪儿谁欺负你了告诉父亲沈海笑着说。沈若雪把报纸甩在父亲的跟前,爸你...
    开心晓杰阅读 198评论 0 0
  • 骑着自行车
    95f13bbaba63阅读 219评论 0 1
  • 皑皑白雪 淹没了昨日时光 油纸伞下的倩影 恰似一朵梅花 在银装素裹的世界 傲然绽放 你是冬的天使 飘飞的雪花 是你...
    桂花上酸菜阅读 312评论 15 24
  • 概念表述## 你刚捡到100元钱,刚好刮来一阵风把刚捡到的钱吹走了,你会很郁闷,甚至会影响一天的心情。 刚得到的快...
    铁川阅读 893评论 0 0