My code:
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<Integer> grayCode(int n) {
ArrayList<Integer> ret = new ArrayList<Integer>();
if (n < 0)
return null;
else if (n == 0) {
ret.add(0);
return ret;
}
int[] seq = helper(n);
for (int i = 0; i < seq.length; i++)
ret.add(seq[i]);
return ret;
}
private int[] helper(int n) {
if (n == 1) {
int[] ret = new int[2];
ret[0] = 0;
ret[1] = 1;
return ret;
}
int[] tmp = helper(n - 1);
int[] ret = new int[2 * tmp.length];
int base = (int) Math.pow(2, n - 1);
for (int i = 0; i < tmp.length; i++)
ret[i] = tmp[i];
for (int i = tmp.length; i < 2 * tmp.length; i++)
ret[i] = base + tmp[2 * tmp.length - i - 1];
return ret;
}
public static void main(String[] args) {
Solution test = new Solution();
System.out.println(test.grayCode(3));
}
}
终于自己做对一道medium题目了。。。
做完后看了下提示，和我的思路一样，是backtracing.我的理解就是DFS。
这是有规律的。
n = 1
0
1
n = 2
0 0
0 1
1 1
1 0
n = 3
0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0
可以看出来，n = 3 时， 先把 n = 2 的这块数组，加上0，作为n = 3时的上半部分。
然后将n = 2 这块数组reverse，然后加上 2 ^ (n - 1); 作为n = 3时的下半部分。
然后这条状态和上条状态之间的关系就很清楚了。就可以用DFS了。
**
总结： DFS
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public List<Integer> grayCode(int n) {
List<Integer> ret = new ArrayList<Integer>();
if (n < 0) {
return ret;
}
else if (n == 0){
ret.add(0);
return ret;
}
List<Integer> pre = grayCode(n - 1);
int num = (1 << (n - 1));
for (int i = pre.size() - 1; i >= 0; i--) {
pre.add(pre.get(i) + num);
}
return pre;
}
}
reference:
https://discuss.leetcode.com/topic/31329/java-easy-version-to-understand
自己没能想出来。发现这些解法都比以前自己的解法要简洁易懂直接高效。
这个的话有点类似于找规律。
n = 3
0 0 0 = 0
0 0 1 = 1
0 1 1 = 3
0 1 0 = 2
————————————
1 1 0 = 6
1 1 1 = 7
1 0 1 = 5
1 0 0 = 4
可以看到，下半部分，等于上半部分，从下往上开始，每个元素加上 4
Anyway, Good luck, Richardo! -- 09/17/2016
