格雷码:
1位:0 1
2位:(0)0 (0)1 (1)1 (1)0
3位:(0)00 (0)01 (0)11 (0)10 + (1)10 (1)11 (1)01 (1)00
后一位的直接在前一位的格雷码前+0 或者+1(+1要把数组反向),就可以生成格雷码。
用动态规划做的,内存占用有点儿大。
class GrayCode { public: vector<string> getGray(int n) { vector<string> vec[102]; if(n==0)return vec[0]; vec[1].push_back("0"); vec[1].push_back("1"); for(int i=2;i<=n;i++){ for(int j=0;j<vec[i-1].size();j++){ vec[i].push_back("0"+vec[i-1][j]); vec[i+1].push_back("1"+vec[i-1][j]); } for(int j=0;j<vec[i-1].size();j++){ vec[i].push_back(vec[i+1][vec[i+1].size()-1-j]); }vec[i+1].clear(); } return vec[n]; } };