89.Gray Code

题目大意：格雷码。

法一（借鉴）：直接转换为格雷码。代码如下（耗时1ms）：

1     public List<Integer> grayCode(int n) {
2         List<Integer> res = new ArrayList<Integer>();
3         int num = (int) Math.pow(2, n);
4         for(int i = 0; i < num; i++) {
5             //(i>>1)^i转换为格雷码
6             res.add((i >> 1) ^ i);
7         }
8         return res;
9     }

View Code

其他解法。

刚开始以为只是找出01的全排列，所以写出了下面的解法：

 1 public List<Integer> grayCode(int n) {
 2         List<Integer> res = new ArrayList<Integer>();
 3         List<Integer> tmp = new ArrayList<Integer>();
 4         dfs(res, 0, n, tmp);
 5         return res;
 6     }
 7     public static void dfs(List<Integer> res, int cnt, int n, List<Integer> tmp) {
 8         if(cnt == n) {
 9             int num = 0;
10             for(int i = 0; i < n; i++) {
11                 num = num * 2 + tmp.get(i);
12             }
13             res.add(num);
14             return;
15         }
16         tmp.add(0);
17         dfs(res, cnt + 1, n, tmp);
18         tmp.remove(tmp.size() - 1);
19         tmp.add(1);
20         dfs(res, cnt + 1, n, tmp);
21         tmp.remove(tmp.size() - 1);
22     }

View Code