递归算法: i == 0 直接添加 0 1 i > 0 res中元素 依次在前面添加0 额外push_back新元素 倒叙同时前面添加1
class GrayCode {
public:
vector<string> getGray(int n) {
// write code here
if(n <= 0) return res;
res.reserve(pow(2,n));
add(0,n);
return res;
}
void add(int i, int n)
{
if(i >= n)
{
return;
}
if(i == 0)
{
res.push_back("0");
res.push_back("1");
add(i+1,n);
}
else
{
int size = res.size();
vector<string> tmp(size);
for(int i = 0; i < size; i++)
{
tmp[size-1-i] = '1' + res[i];
res[i] = '0' + res[i];
}
for(string s: tmp)
{
res.push_back(s);
}
add(i+1,n);
}
}
private:
vector<string> res;
};