标签搜索

目 录CONTENT

文章目录

腾讯---生成格雷码.md

小小城
2022-05-02 / 0 评论 / 0 点赞 / 2 阅读 / 990 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

生成格雷码.md
date: 2021-08-22 12:10:07.812
updated: 2021-08-22 12:10:07.812
url: /2021/08/22/腾讯---生成格雷码md
categories:
tags:

腾讯---生成格雷码

@[toc]

一、题目描述

在一组数的编码中,若任意两个相邻的代码只有一位二进制数不同, 则称这种编码为格雷码(Gray Code),请编写一个函数,使用递归的方法生成N位的格雷码

给定一个整数n,请返回n位的格雷码,顺序为从0开始

测试样例:

1
返回:["0","1"]

二、分析

既然是递归,就相当于找规律!

首先递归的出口在哪里??

  •  当n==1时就是递归的出口
    gray码为(0,1)

那么n== 2时和n==1时的格雷码有什么关系呢?用脑袋去递归是想显摆你内存大吗。所以先写出来找规律:

  •  n==2时
    gray码为(00,01,11,10)

目前规律不明显,那就把n==3的格雷码写出来:

  •  当n==3时
    gray码为(000,001,011,010,110,111,101,100)

到这里规律就出来了!!!

  •  n== 3时的格雷码是在n==2的格雷码的头部添加0或者1
  •  但是你还需要注意添加0和1的区别:
  •  添加0时:直接在n==2的每个格雷码头部添加0
  •  添加1时:直接在n==2的每个格雷码头部添加1,再反转一下顺序使其满足题意
  •  最后把添加0和1的所有情况组合起来

三、代码

class GrayCode {
public:
    vector<string> getGray(int n) {
        // write code here
        if(n == 1)
        {
            return {"0","1"};
        }
        vector<string> s1 = getGray(n - 1);//递归调用
        vector<string> s2(2 * s1.size());
        
        for(int i = 0;i < s1.size();i++)
        {
            s2[i] = "0" + s1[i];//首位添加0
            
            //首位添加1,注意需要顺序反向
            s2[i + s1.size()] = "1" + s1[s1.size() - 1 - i];
        }
        return s2;
    }
};
0

评论区