腾讯2016研发工程师编程题

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

  1. 格雷码的输出

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

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

    测试样例:

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    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;
    }
    };
T B
站点访问量: / , 本页阅读量:
T B