Leetcode 89. 格雷编码

98 阅读 0 评论 65 点赞

我是靠谱客的博主大胆薯片，这篇文章主要介绍Leetcode 89. 格雷编码，现在分享给大家，希望可以做个参考。

X_Y 如果X中1的个数是奇数那么_从1开始遍历，否则从0开始
以三为例

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
X为空从0开始{_Y【0、1】
    X = 0偶数个{0_Y【0、1】
        X = 00偶数个{00_【0、1】
            000 001
        }
        X = 01奇数个{01_【1、0】
            011 010
        }
    }
    X = 1奇数个{ 1_Y【1、0】
        X = 11偶数个{11_【0、1】
            110 111
        }
        X = 10奇数个{10_【1、0】
            101 100
        }
    }
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> ans;
    void dfs(int index, int f, int x) {
        if (index <0) {
            ans.push_back(x);
            return;
        }
        dfs(index - 1, 0, x + (1 << index)*f);
        dfs(index - 1, 1, x + (1 << index)*(f ^ 1));
    }
    vector<int> grayCode(int n) {
        dfs(n - 1, 0, 0);
        return ans;
    }
};