QQ1. 生成格雷码
描述
在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同， 则称这种编码为格雷码(Gray Code)，请编写一个函数，使用递归的方法生成N位的格雷码。
给定一个整数n，请返回n位的格雷码，顺序为从0开始。
1
返回：["0","1"]
C++ 解法, 执行用时: 9ms, 内存消耗: 2732KB, 提交时间: 2022-04-19
class GrayCode {
public:
vector<string> getGray(int n) {
// write code here
vector<string> res;
string tmp = "";
for(int i=0;i<n;i++){
tmp += "0";
}
res.emplace_back(tmp);
for(int i=1;i<=n;i++){
//对称开始位置
int idx = pow(2,i-1);
for(int j = 1;j<=idx;j++){
//反着取res的值，再加入到res中
tmp = res[idx-j];
tmp[n-i] = '1';
res.emplace_back(tmp);
}
}
return res;
}
};
C++ 解法, 执行用时: 9ms, 内存消耗: 2740KB, 提交时间: 2022-05-08
class GrayCode {
public:
vector<string> getGray(int n) {
int m = 1 << n;
vector<string> res(m);
res[0] = string(n, '0');
for (int i = 1; i <= n; ++i) {
int idx = 1 << (i - 1);
for (int j = idx - 1; j >= 0; --j) {
string t = res[j];
t[n-i] = '1';
res[idx++] = t;
}
}
return res;
}
};
C++ 解法, 执行用时: 10ms, 内存消耗: 2640KB, 提交时间: 2020-11-01
class GrayCode {
public:
vector<string> getGray(int n) {
// write code here
if(n==0)
return vector<string>();
vector<string> svec(1<<n,"");
svec[0]=string(n,'0');
svec[1]=svec[0];
svec[1].back()='1';
for(int i=0;i<n;i++)
{
int num=1<<i;
for(int j=0;j<num;j++)
{
svec[num+j]=svec[num-j-1];
svec[num+j][n-1-i]='1';
}
}
return svec;
}
};
C++ 解法, 执行用时: 10ms, 内存消耗: 2652KB, 提交时间: 2020-08-26
class GrayCode {
public:
vector<string> getGray(int n) {
// write code here
if(n==0)
return vector<string>();
vector<string> svec(1<<n,"");
svec[0]=string(n,'0');
svec[1]=svec[0];
svec[1].back()='1';
for(int i=0;i<n;i++)
{
int num=1<<i;
for(int j=0;j<num;j++)
{
svec[num+j]=svec[num-j-1];
svec[num+j][n-1-i]='1';
}
}
return svec;
}
};
C++ 解法, 执行用时: 10ms, 内存消耗: 2656KB, 提交时间: 2020-07-12
class GrayCode {
public:
vector<string> getGray(int n) {
// write code here
if(n==0)
return vector<string>();
vector<string> svec(1<<n,"");
svec[0]=string(n,'0');
svec[1]=svec[0];
svec[1].back()='1';
for(int i=0;i<n;i++)
{
int num=1<<i;
for(int j=0;j<num;j++)
{
svec[num+j]=svec[num-j-1];
svec[num+j][n-1-i]='1';
}
}
return svec;
}
};