题解 | 生成格雷码

#include <vector>
class GrayCode {
public:
    vector<string> getGray(int n) {
        // write code here
        vector<string> res;
        if (n == 1) {
            res.push_back("0");
            res.push_back("1");
            return res;
        }

        vector<string> prev = getGray(n - 1);
        for (int i = 0; i < prev.size(); i++) {
            res.push_back("0" + prev[i]);
        }
        for (int i = prev.size() - 1; i >= 0; i--) {
            res.push_back("1" + prev[i]);
        }
        return res;
    }
};

解题思路

观察规律可得，

一位格雷码为["0", "1"]

n 位格雷码可以由 n-1 位格雷码生成：将 n-1 位格雷码前面加"0"，得到前一半将 n-1 位格雷码逆序，前面加"1"，得到后一半。

这样可以保证相邻的二进制只有一个不同