[leetcode] 89. Gray Code

[leetcode] 89. gray Code

Description

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.

Example 1:

Input: 2Output: [0,1,3,2]Explanation:00 - 001 - 111 - 310 - 2For a given n, a gray code sequence may not be uniquely defined.For example, [0,2,3,1] is also a valid gray code sequence.00 - 010 - 211 - 301 - 1

Example 2:

Input: 0Output: [0]Explanation: We define the gray code sequence to begin with 0. A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1. Therefore, for n = 0 the gray code sequence is [0].

分析一

题目的意思是：输出指定的格雷码序列。

当n=1时，为[0,1]当n=2时，为[00,01,11,10]当n=3时，为[000,001,011,010,110,111,101,100]由此可以看出新的序列其实是在前面序列基础上插入新的值其中前半部分的数值不变，后半部分的数值为上个序列中每个元素第n个位变1，逆向插入

代码一

class Solution {public: vector grayCode(int n) { vector result(pow(2,n)); for(int i=1;i<=n;i++){ int size=1<=size;j--){ result[j] = result[index++]|flag; //左部插入1 } } return result; }};

分析二

上面的规律可以转化为下面的移位，异或运算。

代码二

class Solution {public: vector grayCode(int n) { vector res; for(int i=0;i>1)^i); } return res; }};

参考文献

​​[编程题]gray-code​​​​[LeetCode] Gray Code 格雷码​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。