[leetcode_89]Gray Code

这个题，我很无奈，不能special judge。好吧开始写了一个代码 WA，人说 sorry 不能sp，于是按照样例改了改。
思想就是

1
在序列中的每个数前面[样例]或者后面加上（0，1），（1，0），（0，1），（1，0），（0，1），（1，0）……即可[每个数，生成两个新的数]，这样保证了只改变一个位数，因为上一轮的数是按照跪着的。所以这样就不会有问题。
附上两次的代码：
WA的代码[我相信是可以过的]：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50


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的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


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;
    }
};