题解 | #生成格雷码#递归算法

生成格雷码

http://www.nowcoder.com/practice/50959b5325c94079a391538c04267e15

递归算法: i == 0 直接添加 0 1 i > 0 res中元素 依次在前面添加0 额外push_back新元素 倒叙同时前面添加1

class GrayCode {
public:
    vector<string> getGray(int n) {
        // write code here
        if(n <= 0) return res;
        res.reserve(pow(2,n));
        add(0,n);
        return res;
    }
    void add(int i, int n)
    {
        if(i >= n)
        {
            return;
        }
        if(i == 0)
        {
            res.push_back("0");
            res.push_back("1");
            add(i+1,n);
        }
        else
        {
            int size = res.size();
            vector<string> tmp(size);
            for(int i = 0; i < size; i++)
            {
                tmp[size-1-i] = '1' + res[i];
                res[i] = '0' + res[i];
                
            }
            for(string s: tmp)
            {
                res.push_back(s);
            }
            add(i+1,n);
        }
    }
    
    
private:
    vector<string> res;
};
全部评论

相关推荐

MScoding:你这个实习有一个是当辅导老师,这个和找技术岗没有关系吧?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务