Leetcode 89. Gray Code

Tyan

发布于 2019-05-26 10:44:24

3080

发布于 2019-05-26 10:44:24

文章被收录于专栏：SnailTyanSnailTyan

文章作者：Tyan

博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

Version 1

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> result;
        bitset<32> code;
        traverse(result, code, n - 1);
        return result;
    }

private:
    void traverse(vector<int>& result, bitset<32>& code, int pos) {
        if(pos < 0) {
            int value = code.to_ulong();
            result.push_back(value);
            return;
        }
        traverse(result, code, pos - 1);
        code.flip(pos);
        traverse(result, code, pos - 1);
    }
};

Version 2

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> result;
        int code = 0;
        traverse(result, code, n - 1);
        return result;
    }

private:
    void traverse(vector<int>& result, int& code, int pos) {
        if(pos < 0) {
            result.push_back(code);
            return;
        }
        traverse(result, code, pos - 1);
        code ^= (1 << pos);
        traverse(result, code, pos - 1);
    }
};