leetcode筆記：Gray Code（2016騰訊軟件開發筆試題）

leetcode筆記：Gray Code（2016騰訊軟件開發筆試題）

一.題目描述

The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of
gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
• For a given n, a gray code sequence is not uniquely defined.
• For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
• For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

二.題目分析

昨天騰訊也剛考了這道題，因為不是本人考試，所以不是很記得題目是否有其他限制，這裡只是按照騰訊的基本要求：用遞歸實現格雷碼的生成，純屬拋磚引玉。

這裡，主要函數只是實現了0~2^(n-1)的自然數到格雷碼排列的映射，還需要一個函數，將int型數據轉換為n位二進制數，最後輸出結果。

關於格雷碼的定義，百度有較為詳細的解釋，傳送門：http://baike.baidu.com/link?url=_X6MWv6OPt93bbuMIXnmXIqMKeQgnI2xPa1xkgPlrZR_7uG8xYKec3B67zm8JhqqEdylnUBC7Op8oWp0vQe_bq

以下列出1位到4位的格雷碼，可以從中發現一些規律：

可以發現，一組n位格雷碼有 2^n 個二進制排列組成，其前 2^(n-1) 個數，除去最高位的0，剩下的位數與 n - 1 位格雷碼完全一致；

其次，一組n位格雷碼，其後 2^(n-1) 個數，除去最高位的1，剩下的位數與 n - 1 位格雷碼的倒序完全一致；

基於以上兩點性質，我們有理由相信，一組 n 位的格雷碼，可以遞歸地從 n-1 位的格雷碼生成。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPjxzdHJvbmc+yP0uyrXA/bT6wus8L3N0cm9uZz48L3A+DQo8cD7G5NbQo6zW99KqtcS6r8r9o7ogPGNvZGU+YnVpbGRHcmF5Q29kZSgpPC9jb2RlPta7ysfKtc/Wwcs8Y29kZT4wfjJeKG4tMSk8L2NvZGU+tcTX1Mi7yv21vbjxwNfC68XFwdC1xNOzyeSho77ZuPbA/dfTo6y21NPaPGNvZGU+MjwvY29kZT7Ou7XEuPHA18Lro6zG5Dxjb2RlPmludDwvY29kZT7Qzcr9vt21xMXFwdDLs9DyzqqjuiA8Y29kZT4wIDEgMyAyPC9jb2RlPqGjtvi6r8r9PGNvZGU+QmluYXJ5Y291dCgpPC9jb2RlPiCjrL2rPGNvZGU+MCAxIDMgMjwvY29kZT4g16q7u86qo7o8Y29kZT4wMCAwMSAxMSAxMDwvY29kZT4goaM8L3A+DQo8cHJlIGNsYXNzPQ=="brush:java;"> #include #include using namespace std; class Solution { public: vector buildGrayCode(int n) { if (n == 0) { vector result; result.push_back(0); return result; } else { vector k = buildGrayCode(n - 1); vector result(k); for (int i = k.size(); i > 0; --i) result.push_back(int(pow(2, n - 1) + k[i - 1])); return result; } } vector Binarycout(int n, const int bit_num) // int to binaries { vector result; for (int i = bit_num - 1; i >= 0; i--) { result.push_back((n >> i) & 1); } return result; } };

簡單的測試代碼：

#include GrayCode.h

int main()
{
    Solution s;
    int n;
    cout << Please input the value of bit: ;
    cin >> n;

    vector k = s.buildGrayCode(n);
    cout << The gray code is:  << endl;

    vector > result;  // int to binaries
    for (vector>::size_type i = 0; i < k.size() ; i++)
        result.push_back(s.Binarycout(k[i], n));

    for (vector>::size_type x = 0; x < result.size(); x++) // vector>::size_type
    {
        for (vector::size_type y = 0; y < result[x].size(); y++) // vector::size_type
            cout << result[x][y] <<  ;
        cout <<  :  << k[x] << endl;
    }
}

結果：

四.小結

格雷碼的實現方法有多種，例如利用一些數學公式，將0~2^(n-1) 之間的所有整數轉化為格雷碼。再有是使用移位計算的技巧進行實現。