Lexi's Leetcode solutions

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

Posted on: October 19, 2013

这题上来没法下手,咬牙看了半天用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;
}

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

写得好,怒赞!

startzeros那部分没必要写吧,这是十进制,左边加0等于没加。

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: