Gray Code

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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. For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0  00 ^ 00
01 - 1  00 ^ 01
11 - 3  01 ^ 10
10 - 2  01 ^ 11
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.
3位数情况
000
001
011
010
110
111 //如果按照题意的话，只是要求有一位不同，这里也可以是100
101
100

代码：

 //Iteration  
 class Solution {  
 public:  
   vector<int> grayCode(int n) {    
     vector<int> result;     
     result.push_back(0);   
     for (int i = 0; i < n; i++) {   
       int highestBit = 1 << i;   
       int len = result.size();   
       for (int i = len - 1; i >= 0; i--) {  // reverse  
         result.push_back(highestBit + result[i]); // highest bit  
       }    
     }   
     return result;   
   }  
 };  
   
 //Recursion  
 class Solution {  
 public:  
   vector<int> reverse(const vector<int> & r) {  
     vector<int> rev;  
     for (int i = r.size() - 1; i >= 0; --i) {  
       rev.push_back(r[i]);  
     }  
     return rev;  
   }  
     
   vector<int> grayCode(int n) {  
     vector<int> result;  
     if (n <= 1) {  
       for (int i = 0; i <= n; ++i)  
         result.push_back(i);  
       return result;  
     }  
     result = grayCode(n - 1);  
     vector<int> r1 = reverse(result);  
     for (int i = 0; i < r1.size(); ++i) {  
       int x = 1 << (n - 1);  
       r1[i] += x;  
     }  
   
     for (int i = 0; i < r1.size(); ++i) {  
       result.push_back(r1[i]);  
     }  
     return result;  
   }  
 };