腾讯2016研发工程师编程题

腾讯笔试编程题：链接 腾讯2016研发工程师编程题

1. 格雷码的输出

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

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

   测试样例：

   输入：1
   返回：[“0”,”1”]

   这是一个简单的递归的使用，摸清规律，并搞清楚先后顺序即可

class GrayCode {
public:
    vector<string> result;
    vector<string> getGray(int n) {
        // write code here
        if(n == 1)
        {
            result.push_back("0");
            result.push_back("1");
            return result;
        }
        else
        {
            getGray(n -1);
            vector<string> tmp(result);//复制两份
            vector<string> tmp1(result);
            result.clear();
            for(int i = 0; i < tmp.size(); ++i) // 从前往后开始遍历 在首部添加0
            {
                result.push_back("0"+tmp[i]);
            }
            for(int i = tmp1.size() - 1; i >= 0 ; --i)//从后往前开始遍历 在首部添加1
            {
                result.push_back("1"+tmp1[i]); //将复制的两份添加数字后放到result中
            }
        }
        return result;
    }
};

2. 寻找出现次数超过一半的红包

   春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。

   给定一个红包的金额数组gifts及它的大小n，请返回所求红包的金额。

   若没有金额超过总数的一半，返回0。

   测试样例：

   输入： [1,2,3,2,2],5
   返回：2

   思路： 用 count 来维持一个一直出现的红包x的数量，若 x 再次出现则count++ 若x不再出现则count– 如果count为0了，则重置count并更新 x 这样就能够找到出现次数最多的 x 。该思路对于超过一半的x一定能找到其值，但如果出现次数最多的x数量没有过半，则不一定能找到x

class Gift {
public:
    int getValue(vector<int> gifts, int n) {
        // write code here
        if( n <= 0)
            return 0;
        int count = 0,tmp;
        for(int i = 0; i < n; ++i)
        {
            if(count == 0)
            {
                tmp = gifts[i];
                count++;
            }
            else
            {
                if(tmp == gifts[i])
                    count++;
                else
                    count--;
            }
        }
        int size =0;
        for(int i = 0; i < n; ++i)
        {
            if(gifts[i] == tmp)
                size++;
        }
        if(size > n/2)
            return tmp;
        else
            return 0;
    }
};