LeetCode Gray Code

LeetCode Gray Code

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,后面每个数和前一个数在二进制位上只相差一位。现在给定二进制编码为n位,要求输出一串格雷码。

在不了解格雷码的情况下,可以单纯根据上面格雷码的定义来列出这一串格雷码,我们需要尝试依次翻转n位中的每一位,如果翻转之后得到的编码之前没有出现过,则翻转成功,接着进入下一次尝试,直到产生所有格雷码。

假设一个二进制数为x,则翻转其第i位之后的二进制数为(x&(~(1 << i))) | (~x)&(1 << i),还是有点复杂的。

这种思路可以用递归的方法实现,完整代码如下:

class Solution {
public:
	void work(vector<int>& ans, unordered_set<int>& codes, int gray, int n) {
		for (int i = 0; i < n; ++i) {
			int new_gray = (gray&(~(1 << i))) | (~gray)&(1 << i); // flip i-th bit
			if (codes.find(new_gray) == codes.end()) {
				codes.insert(new_gray);
				ans.push_back(new_gray);
				work(ans, codes, new_gray, n);
				break;
			}
		}
	}
	vector<int> grayCode(int n) {
		vector<int> ans = { 0 };
		if (n == 0)return ans;
		unordered_set<int> codes = { 0 };
		work(ans, codes, 0, n);
		return ans;
	}
};

本代码提交AC,用时6MS。

查看格雷码的维基百科,有好多种方法都可以生成格雷码序列,其中一种很有意思,可以根据二进制长度为n-1的格雷码序列生成二进制长度为n的格雷码序列,如下图所示,这种方法叫做镜射排列。

仔细观察会发现,n长的格雷码序列的前一半序列和n-1长的格雷码序列,在十进制数上是完全一样的,二进制数上也只是多了一个前导零;而后半序列是n-1长的格雷码序列镜面对称之后,加上一位前导1得到的。所以很容易可以写出镜射排列的代码:

class Solution {
public:
	vector<int> grayCode(int n) {
		vector<int> ans = { 0 };
		if (n == 0)return ans;
		ans.push_back(1);
		for (int i = 2; i <= n; ++i) {
			int sz = ans.size();
			while (sz--) {
				ans.push_back(ans[sz] | (1 << (i - 1)));
			}
		}
		return ans;
	}
};

本代码提交AC,用时3MS。

Leave a Reply

Your email address will not be published. Required fields are marked *