7月 14 2015

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

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

The original problem is here.

The original code is here.

My Solution

I solve this problem in C++, as below:

/*
*Gray Code
*Author: shuaijiang
*Email: zhaoshuaijiang8@gmail.com
*/
#include<iostream>
#include<vector>
#include<math>
#include<stdlib.h>
using namespace std;

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> result;
        if(n<0)
            return result;
        
        result.push_back(0);
        if(n==0)
            return result;
        result.push_back(1);
        if(n==1)
            return result;
        
        for(int i=2;i<=n;i++){
            int size = result.size();
            int addNum = pow(2,i-1);
            for(int j=size-1;j>=0;j--){
                int num = result[j] + addNum;
                result.push_back(num);
            }
        }
        return result;
    }
};

Note

The Gray Code of n contains two parts: One part is the codes which add 0 to front of all codes of n-1; The other part is the codes which add 1 to front of all codes of n-1 in the reverse order.

For example, when n=2, the Grad code is

So, when n=3, the Gray code is