92
[LeetCode]89.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.
【題意】
格雷碼是一個二進製數字集合，相鄰兩數間隻有一個位元改變。
給定一個非負整數n代表的比特位的總數，打印格雷碼序列。格雷碼序列必須從0開始。
例如，給定n=2，返回[0,1,3,2]。它的格雷碼序列為：
00 - 0 01 - 1 11 - 3 10 - 2注意：
對於給定的n，格雷碼序列不是唯一地。
例如，按上述定義[0,2,3,1]也是一個有效的格雷碼序列。
現在，判定係統隻能夠判斷基於格雷碼序列的一個實例。我們對此深感抱歉。
【分析】
思路1：
格雷碼 (Gray Code) 的定義請參考 wikipedia https://en.wikipedia.org/wiki/Gray_code。
-
自然二進製碼轉換為格雷碼：
保留自然二進製碼的最高位作為格雷碼的最高位，格雷碼次高位為二進製碼的高位與次高位異或，其餘各位與次高位的求法類似。
例如，將自然二進製碼 1001，轉換為格雷碼的過程是：
保留最高位；然後將第 1 位的 1 和第 2 位的 0 異或，得到 1，作為格雷碼的第 2 位；將第 2 位的 0 和第 3 位的 0 異或，得到 0，
作為格雷碼的第 3 位；將第 3 位的 0 和第 4 位的 1 異或，得到 1，作為格雷碼的第 4 位，最終，格雷碼為 1101。
- 格雷碼轉換為自然二進製碼：
保留格雷碼的最高位作為自然二進製碼的最高位，次高位為自然二進製高位與格雷碼次高位異或，其餘各位與次高位的求法類似。
例如，將格雷碼 1000 轉換為自然二進製碼的過程是：
保留最高位 1，作為自然二進製碼的最高位；然後將自然二進製碼的第 1 位 1 和格雷碼的第 2 位 0 異或，得到1，
作為自然二進製碼的第 2 位；將自然二進製碼的第 2 位 1 和格雷碼的第 3 位 0 異或，得到 1，作為自然二進製碼的第 3 位；
將自然二進製碼的第 3 位 1 和格雷碼的第 4 位 0 異或，得到 1，作為自然二進製碼的第 4 位，最終，自然二進製碼為 1111。
-
格雷碼有數學公式，整數 n 的格雷碼是
這題要求生成 n 比特的所有格雷碼。最簡單的方法，利用數學公式，對從 0~ 2^n - 1的所有整數，轉化為格雷碼。
思路2：
n 比特的格雷碼，可以遞歸地從 n - 1 比特的格雷碼生成。
n位元的格雷碼可以從n-1位元的格雷碼以上下鏡射後加上新位元的方式快速的得到，如右圖所示一般。
紅色的最高位加一即保持不變。
藍色的最高位加一；n = 1時原格雷碼十進製加1 ; n = 2時 加2 ; n = 3時 加 4 ;n= 4時 加 8............
【代碼1】
/*********************************
* 日期：2014-01-23
* 作者：SJF0115
* 題號: Gray Code
* 來源：https://oj.leetcode.com/problems/gray-code/
* 結果：AC
* 來源：LeetCode
* 總結：
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
//數學公式，時間複雜度 O(2^n)，空間複雜度 O(1)
vector<int> grayCode(int n) {
int count = 1 << n;
vector<int> code;
for(int i = 0;i < count;i++){
code.push_back(binaryToGrayCode(i));
}
return code;
}
private:
int binaryToGrayCode(int n){
return n ^ (n >> 1);
}
};
int main() {
Solution solution;
vector<int> result;
result = solution.grayCode(3);
int n = result.size();
for(int i = 0;i < n;i++){
printf("%d ",result[i]);
}
printf("\n");
return 0;
}
【代碼2】
/*********************************
* 日期：2014-01-23
* 作者：SJF0115
* 題號: Gray Code
* 來源：https://oj.leetcode.com/problems/gray-code/
* 結果：AC
* 來源：LeetCode
* 總結：
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
//鏡射排列
vector<int> grayCode(int n) {
int i,j,count,c;
vector<int> code;
//初始為0位
code.push_back(0);
for(i = 0;i < n;i++){
count = code.size();
c = 1 << i;
//添加鏡麵反射的那一部分(最高位加1)
//要反著遍曆才能對稱
for(j = count - 1;j >= 0;j--){
code.push_back(code[j] + c);
}
}
return code;
}
};
int main() {
Solution solution;
vector<int> result;
result = solution.grayCode(3);
int n = result.size();
for(int i = 0;i < n;i++){
printf("%d ",result[i]);
}
printf("\n");
return 0;
}
格雷碼轉二進製數
二進製碼第n位 = 二進製碼第（n+1）位+格雷碼第n位。因為二進製碼和格雷碼皆有相同位數，所以二進製碼可從最高位的左邊位元取0，以進行計算。（注：遇到1+1時結果視為0）
例如： 格雷碼0111，為4位數，所以其所轉為之二進製碼也必為4位數，因此可取轉成之二進製碼第五位為0，即0 b3 b2 b1 b0。
0+0=0，所以b3=0
0+1=1，所以b2=1
1+1取0，所以b1=0
0+1取1，所以b0=1
因此所轉換為之二進製碼為0101
最後更新：2017-04-03 12:54:47