格雷码

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

示例 1:

输入: 2输出: [0,1,3,2]解释:00 - 001 - 111 - 310 - 2

思路： 使用镜像翻转后的序列在最前边加0或者1。或者使用格雷码公式:G(i) = i^(i/2)。

class Solution { public: vector<int> grayCode(int n) { vector<int>result; if(n == 0){ result.push_back(0); return result; } vector<vector<int>> bins; bins = grayBinary(n); for(int i = 0; i < bins.size(); i++){ result.push_back(bin2int(bins[i])); } return result; } int bin2int(vector<int> bins){ int re = 0; for(int i = 0; i < bins.size(); i++){ re += bins[i]*pow(2,bins.size()-1-i); } return re; } vector<vector<int> > grayBinary(int n){ vector<vector<int>>result; vector<vector<int>>pre_result; if( n == 1){ vector<int> tmp; tmp.push_back(0); result.push_back(tmp); vector<int> tmp1; tmp1.push_back(1); result.push_back(tmp1); return result; } pre_result = grayBinary(n-1); for(int i = 0; i < pre_result.size(); i++){ vector<int> temp = pre_result[i]; temp.insert(temp.begin(), 0); result.push_back(temp); } for(int i = pre_result.size()-1; i >=0; i--){ vector<int> temp = pre_result[i]; temp.insert(temp.begin(), 1); result.push_back(temp); } return result; } };

 

转载于:https://www.cnblogs.com/Shinered/p/11395004.html

相关资源：C经典算法之格雷码（Gray Code）