@@ -0,0 +1,1669 @@
+/***%0A * The gray code is a binary numeral system where two successive values differ in only one bit.%0A *%0A * 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.%0A *%0A * For example, given n = 2, return %5B0,1,3,2%5D. Its gray code sequence is:%0A *%0A * 00 - 0%0A * 01 - 1%0A * 11 - 3%0A * 10 - 2%0A * Note:%0A * For a given n, a gray code sequence is not uniquely defined.%0A *%0A * For example, %5B0,2,3,1%5D is also a valid gray code sequence according to the above definition.%0A *%0A * For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.%0A */%0Aimport java.util.List;%0Aimport java.util.ArrayList;%0A%0Apublic class Solution %7B%0A    // Solution 1: O(2%5En,) O(1)%0A    /*%0A    public List%3CInteger%3E grayCode(int n) %7B%0A        List%3CInteger%3E ret = new ArrayList%3CInteger%3E(); %0A        ret.add(0);%0A        if (n == 0) return ret;%0A        int size = 1 %3C%3C n;%0A        // generates a series of binary natural code, then convert to gray code%0A        for (int i = 1; i %3C size; i++)%0A            ret.add(binaryToGray(i));%0A        return ret;%0A    %7D%0A%0A    private int binaryToGray(int n) %7B%0A        return n %5E (n %3E%3E 1);%0A    %7D%0A    */%0A%0A    // Solution 2: O(2%5En) O(1)%0A    public List%3CInteger%3E grayCode(int n) %7B%0A        List%3CInteger%3E ret = new ArrayList%3CInteger%3E(); %0A        ret.add(0);%0A        if (n == 0) return ret;%0A        for (int i = 0; i %3C n; i++) %7B%0A            int highest_bit = 1 %3C%3C i;%0A            for (int j = ret.size() - 1; j %3E= 0; j--) %7B%0A                ret.add(highest_bit %7C ret.get(j));%0A            %7D%0A        %7D%0A        return ret;%0A    %7D%0A    // n = 2, ret = %7B0, 1, 3, 2%7D%0A%7D%0A

add GrayCode.java