[leetcode]89. Gray Code

电玩女神 2022-07-24 07:28 154阅读 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:

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.

解法：

这题的关键在于用什么样的方式把这2^n个数入队列使得任意两个相邻的数只有一个的二进制码只有一位不同。

可以这样考虑：对于已经处理好的n=k-1的情况，2^(k-1)个数已经在队列中，接下来只需从队列末端开始反向遍历该队列并在该数最高位前加一个1再入队列即可满足n=k时的情况。

example：

n=3时，\[000,001,011,010,110,111,101,100\]

n=4时，\[0000,0001,0011,0010,0110,0111,0101,0100,  1100,10101,10111,10110,10010,10011,10001,10000\]

于是，在保证初始队列中有一个0后，从n=1开始做上述动作知道n=XX即可。（XX是用户输入的数）

public class Solution {
        public List<Integer> grayCode(int n) {
            List<Integer> res = new ArrayList<Integer>();
            int last = 0;
            res.add(last);
            for(int i = 1; i <= n; i++){
                Integer base =  (int) Math.pow(2, i-1);
                for(int j = res.size()-1 ; j >= 0; j--){
                	res.add(res.get(j) + base);
                }
            }
            return res;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，154人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode89——Gray Code

LeetCode89——Gray Code 通过二进制和递归两种方式求解n位生成格雷码（十进制表示）.. 原题 > The gray code is a bina

逃离我推掉我的手/ 2022年08月20日 12:23/ 0 赞/ 30 阅读

相关 LeetCode89/60 Gray Code/Permutation Sequence--迭代

一：Leetcode 89 [Gray Code][] 题目：The gray code is a binary numeral system where two succe

悠悠/ 2022年08月07日 16:40/ 0 赞/ 137 阅读

相关 Leetcode: Gray Code

题目： The gray code is a binary numeral system where two successive values differ in onl

古城微笑少年丶/ 2022年08月07日 12:56/ 0 赞/ 51 阅读

相关 LeetCode-Gray Code

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

悠悠/ 2022年08月04日 09:19/ 0 赞/ 92 阅读

相关 leetcode 89. Gray Code

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

淩亂°似流年/ 2022年07月30日 13:15/ 0 赞/ 196 阅读

相关【LeetCode】89. Gray Code解法及注释

89. Gray Code Total Accepted: 58433 Total Submissions: 161645 Difficulty: Medium Th

蔚落/ 2022年07月27日 11:50/ 0 赞/ 196 阅读

相关 [leetcode]89. Gray Code

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

电玩女神/ 2022年07月24日 07:28/ 0 赞/ 155 阅读

相关 LeetCode 89.Gray Code （格雷编码）

题目描述：格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0

ゞ浴缸里的玫瑰/ 2022年05月10日 10:16/ 0 赞/ 211 阅读

相关【Leetcode】89. Gray Code（规律）（二进制相邻位变换）

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

布满荆棘的人生/ 2022年02月22日 10:23/ 0 赞/ 161 阅读

相关 [转载]LeetCode: Gray Code

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

骑猪看日落/ 2021年12月22日 09:43/ 0 赞/ 178 阅读