[leetcode_89] Gray Code

This problem was frustrating — no special judge allowed. So I initially wrote a solution that got WA. They said sorry, no special judge, so I adjusted based on the sample output.
The idea is:

1
Prepend (or append) (0, 1), (1, 0), (0, 1), (1, 0), (0, 1), (1, 0)… to each number in the sequence [as shown in the sample]. Each number generates two new numbers. This ensures only one bit changes at a time, because the numbers from the previous round follow the pattern. So there won’t be any issues.
Here are both versions of the code:
WA code (I believe it should pass):

 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 code:

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