[LeetCode] 89. Gray Code

轉自LeetCode

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.

<Solution>

這題是要找所謂的 gray code，也就是相鄰的數字，只會有一個 bit 是不一樣的(wiki)

有很多種解法，先來看第一種

首先利用 n 位元的 gray code，可以從 n-1 位元的 gray code 用鏡射的方式產生

這邊先釐清一個部分，以 n = 2 和 n = 3 來舉例

可以看到前面四個數字 : 00，01，11，10，其實等同於 000，001，011，010

用十進位表示都是 0，1，3，2

因此，當我們在做鏡射的時候，其實只要從後往前，將１放到 n-1 位元前，成為第n個位元，這樣就可以了

code 如下

	class Solution {
	public:
	vector<int> grayCode(int n) {
	vector<int> ans(1 << n, 0);
	int index = 1, size = 0;
	//> use mirror concept to construct gray code
	for(int i = 0; i < n; i++) {
	size = 1 << i;
	for(int j = size - 1; j >= 0; j--) {
	ans[index++] = ans[j] | (1 << i);
	}
	}
	return ans;
	}
	};

view raw grayCode_1.cpp hosted with ❤ by GitHub

這題還有公式解

gray code = (num / 2) XOR num
code如下

	class Solution {
	public:
	vector<int> grayCode(int n) {
	vector<int> ans(1 << n, 0);
	for(int i = 1; i < ans.size(); i++) {
	ans[i] = (i >> 1) ^ i;
	}
	return ans;
	}
	};

view raw grayCode_2.cpp hosted with ❤ by GitHub