騰訊—生成格雷碼

文章目錄

• • 騰訊---生成格雷碼
  • 一、題目描述
  • 二、分析
  • 三、代碼

一、題目描述

在一組數的編碼中，若任意兩個相鄰的代碼只有一位二進制數不同， 則稱這種編碼為格雷碼(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 hereif(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;} };

總結

以上是生活随笔為你收集整理的腾讯---生成格雷码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。