[leetcode] Gray Code | 生成相邻两个数只有1位不同的序列，每个数有n bit

Posted by: lexigrey on: October 19, 2013

• In: leetcode
• 2 Comments

这题上来没法下手，咬牙看了半天用dfs写出了个差不多的，最后卡在两个list merge上。实在看不出规律（后来发现是自己例子都写错了！！），上网一查，大神回复：

假设有n-1的答案为：G0, G1, …, Gn，想得到n的答案，只需要在G0…Gn左边加上一个0，再把G0…Gn颠倒顺序，在左边加上一个1即可。比如n=3（在分界线上倒映）：

000
001
011
010
---
110
111
101
100

用dfs可以每次求出左边是0，然后求出左边是1的，合一起就是了。两个教训：

1. 这种数学题找规律，千万别自己把例子写错了。那样打死也看不出规律的。
2. 拿到一题往死里想个10分钟总能想出点眉目的，别放弃。

public ArrayList<Integer> grayCode(int n) {
    if (n == 0) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(0);
        return list;
    }
    return getGrayCode(n - 1);
}
private ArrayList<Integer> getGrayCode(int pos) {
    if (pos == 0) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(0);
        list.add(1);
        return list;
    }
    ArrayList<Integer> result = new ArrayList<Integer>();
    ArrayList<Integer> startsWithZero = getGrayCode(pos - 1);
    ArrayList<Integer> startsWithOne = new ArrayList<Integer>();
    for (int i = startsWithZero.size() - 1; i >= 0; i--) {
        startsWithOne.add(startsWithZero.get(i) + (1 << pos));
    }
    result.addAll(startsWithZero);
    result.addAll(startsWithOne);
    return result;
}

Tags: bit, math, 二分法