微软面试高频模拟题:Leetcode 89 格雷码

09/22 09:27
阅读数 45

 

一般这道题目,在面试时,会给出n=4之前的格雷码,然后找规律:

规律是n+1位格雷码的前一半是在n位格雷码的前面添0,后一半是轴对称翻转一次后前面添1。

所以可以这样实现:

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res;
        res.push_back(0);
        int t = 1;
        while (n -- )
        {
            vector<int> newRes;
            for (int i = 0; i < res.size(); i ++ )
                newRes.push_back(res[i]);
            for (int i = res.size() - 1; i >= 0; i -- )
                newRes.push_back(t + res[i]);
            res = newRes;
            t *= 2;
        }
        return res;
    }
};

 

 

 

在前面填1的操作转为位运算比较复杂,在后面填0和填1就比较简单。

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res(1);
        while(n--){
            int n = res.size();
            for(int i=n-1;i>=0;i--){
                res[i] = res[i]*2;
                res.push_back(res[i]+1);
            }
        }
        return res;
    }
};

 

 

展开阅读全文
打赏
1
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
1
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部