这个题,我很无奈,不能special judge。好吧开始写了一个代码 WA,人说 sorry 不能sp,于是按照样例改了改。
思想就是
0
1
在序列中的每个数前面[样例]或者后面加上(0,1),(1,0),(0,1),(1,0),(0,1),(1,0)……即可[每个数,生成两个新的数],这样保证了只改变一个位数,因为上一轮的数是按照跪着的。所以这样就不会有问题。
附上两次的代码:
WA的代码[我相信是可以过的]:
class Solution { public: vector<int> grayCode(int n) { // Note: The Solution object is instantiated only once and is reused by each test case. vector<int> seq; seq.clear(); if(n == 0) { seq.push_back(0); return seq; } for(int i = 0;i < n;i++) { if(i == 0) { seq.push_back(0); seq.push_back(1); } else { vector<int>seq_copy; seq_copy.clear(); int increase = (int)pow(2.0,i); int state = 0; for(int j = 0;j < seq.size();j++) { if(state == 0) { seq_copy.push_back(seq[j] + 0); seq_copy.push_back(seq[j] + increase); state = 1; } else if(state == 1) { seq_copy.push_back(seq[j] + increase); seq_copy.push_back(seq[j] + 0); state = 0; } } seq.clear(); for(int j = 0;j < seq_copy.size();j++) { seq.push_back(seq_copy[j]); } } } return seq; } };
AC的代码:
class Solution { public: vector<int> grayCode(int n) { // Note: The Solution object is instantiated only once and is reused by each test case. vector<int> seq; seq.clear(); if(n == 0) { seq.push_back(0); return seq; } for(int i = 0;i < n;i++) { if(i == 0) { seq.push_back(0); seq.push_back(1); } else { vector<int>seq_copy; seq_copy.clear(); int state = 0; for(int j = 0;j < seq.size();j++) { if(state == 0) { seq_copy.push_back((seq[j]<<1) + 0); seq_copy.push_back((seq[j]<<1)+1); state = 1; } else if(state == 1) { seq_copy.push_back((seq[j]<<1)+1); seq_copy.push_back((seq[j]<<1) + 0); state = 0; } } seq.clear(); for(int j = 0;j < seq_copy.size();j++) { seq.push_back(seq_copy[j]); } } } return seq; } };