89. Gray Code

Problem from leetcode 89. Gray Code

---

请看下图：

---

class Solution {
public:
    vector<int> grayCode(int n) {
        if(n==0) return vector<int>(1,0);
        vector<int> result;
        result.push_back(0); result.push_back(1);
        if(n==1) return result;

        int a = 1<<1;
        for(int i = 2; i <= n; i++) 
        { 
            int previousSize = result.size(); 
            for(int j = previousSize-1; j >= 0; j--)
                result.push_back(result[j]+a);
            a <<= 1;
        }
        return result;
    }
};

Java:

public class Solution {
    public List grayCode(int n) {
        List<Integer> result = new ArrayList<Integer>();
        if(n==0)
        {
            result.add(0);
            return result;
        }
        result.add(0); result.add(1);
        if(n==1) return result;

        int a = 1<<1;
        for(int i = 2; i <= n; i++) 
        { 
            int previousSize = result.size(); 
            for(int j = previousSize-1; j >= 0; j--)
                result.add(result.get(j)+a);
            a <<= 1;
        }
        return result;
    }
}

Python:

class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        result = []
        if n == 0:
            result.append(0)
            return result
        result.append(0)
        result.append(1)
        
        a = 2
        for i in range(2, n+1):
            length = len(result)
            for j in range(length-1, -1, -1):
                result.append(result[j]+a)
            a <<= 1
        return result