首页 > itarticle > [leetcode]gray code

[leetcode]gray code

admin 11月 11, 2020 0

题目描述

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:

1
2
3
4
 
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.

1
2
3
4
5
6
7
8
9
 
Int    Grey Code    Binary
 0  　　  000        000
 1  　　  001        001
 2   　 　011        010
 3   　 　010        011
 4   　 　110        100
 5   　 　111        101
 6   　 　101        110
 7   　　 100        111

解法一

利用格雷码和二进制数的相互转换，G(i)=(i/2)^i

1
2
3
4
5
6
7
8
9
10
 
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;
    }
}

解法二

格雷码有镜射排列的性质，即n位元的格雷码可以从n-1位元的格雷码以上下镜射后加上新位元的方式快速得到，如下图所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
public class Solution {
    //镜面排列
    public List<Integer> grayCode(int n){
        List<Integer> res = new ArrayList<>();
        res.add(0);
        for(int i = 0; i < n; i++){
            int highBit = 1<<i;
            for(int j = res.size() - 1; j >= 0; j--){
                res.add(res.get(j)+highBit);
            }
        }
        
        return res;
    }
}

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能