学步园

题目：

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
01 - 1
11 - 3
10 - 2

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.

解题思路：

如上图，低位进行着0,1和1,0交替；中位依然进行着0,1和1,0交替；高位也是。

那么如果还有更高位，依然会进行着0,1和1,0交替。只不过越来越慢。

因此可以使用递归方式求解。

思路比较简单，没有过多的问题。

AC代码：

<pre name="code" class="java">public class Gray_Code {
    private List<String> rst = new LinkedList<String>();

    private void yarg(String prefix, int n) {
        if (n == 0)
            rst.add(prefix);
        else {
            gray(prefix + "1", n - 1);
            yarg(prefix + "0", n - 1);
        }
    }

    private void gray(String prefix, int n) {
        if (n == 0)
            rst.add(prefix);
        else {
            gray(prefix + "0", n - 1);
            yarg(prefix + "1", n - 1);
        }
    }

    private int toInt(String str) {
        char[] chars = str.toCharArray();
        int p = chars.length - 1;
        int rst = 0;
        for (char aChar : chars) {
            rst += Integer.parseInt("" + aChar) * Math.pow(2, p);
            p--;
        }
        return rst;
    }

    public List<Integer> grayCode(int n) {
        gray("", n);
        List<Integer> rst2 = new LinkedList<Integer>();
        for (String str : rst) {
            int num = toInt(str);
            rst2.add(num);
        }
        return rst2;
    }

    public static void main(String[] args){
        Gray_Code gray_code = new Gray_Code();
        int n = 5;
        System.out.println(gray_code.grayCode(n));
    }
}