Gray Code

medium 原题链接：https://leetcode.com/problems/gray-code/

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.

例子

Input: 2

Output: [0,1,3,2]

Explanation:

00 - 0

01 - 1

11 - 3

10 - 2

For 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 - 0

10 - 2

11 - 3

01 - 1

解法

class Solution {
public:
     vector<int> grayCode(int n) {
        vector<int>res(1,0);
        for(int i=0;i<n;i++){
            int size=res.size();
            for(int j=size-1;j>=0;j--){
                res.push_back(res[j]|1<<i);
            }
        }
        return res;
    }
};

出处

The middle two numbers only differ at their highest bit, while the rest numbers of part two are exactly symmetric of part one： Say the example input is 3.

0 000 1 001 3 011 2 010

6 110 7 111 5 101 4 100

For the pair of (2, 6), (3, 7), (1, 5) and (0, 4), the last 2 bits are the same. The only difference is 6,7,5 and 4 set the first bit on.