2016腾讯校园招聘模拟考试(2016.03.25)

1.生成格雷码

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

测试样例: 1 返回:[“0”,”1”] 2 返回:[“00”,”01”,”11”,”10”] 3 返回:[“000”,”001”,”011”,”010”,110”,111”,101”,100”]

参考代码:

#include <vector>
#include <string>

class GrayCode {
    vector<string> grayCode;
public:
    vector<string> getGray(int n) {
       // write code here 
       string code;
       for(int i=0;i<n;++i){
            code+="0";
       }
       this->grayCode.push_back(code);
       this->inerGetGray(code,n,0);
       return this->grayCode;
    }

private:
    void inerGetGray(string& code,int codeLen,int pos){
        if(pos==codeLen)
           return;
        inerGetGray(code,codeLen,pos+1);
        if(code[pos]=='0')
            code[pos]='1';
        else
            code[pos]='0';
        this->grayCode.push_back(code);//进入vector向量容器
        inerGetGray(code,codeLen,pos+1);
   }
};

2.微信红包

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

测试样例: [1,2,3,2,2],5 返回:2

解法一: 可以先对输入的数组进行排序,如果存在出现次数超过数组长度一半的数,那么数组的中位数,即长度为n的数组中下标为 ⌈n/2⌉\left\lceil n/2 \right\rceil的数就是要求的数。

解法二: 根据数组特点,我们可以求出数组中出现次数最多的数。做法为:遍历数组时,保存两个值,一个是当前遍历的数,一个是次数。当我们遍历下一个数时,如果下一个数与我们当前保存的数相同,则次数加1,如果不同则次数减一。如果次数为零,我们保存下一个数并把次数设为1。遍历结束最后保存的数就是出现次数最多的数。

最后,再根据求出的出现次数最多的数来判断在数组中出现的次数是否超过数组长度一半。

参考代码:

//解法二
class Gift {
public:
    int getValue(vector<int> gifts, int n) {
        // write code here

        int res=gifts[0];
        int count=1;
        for(int i=1;i<n;++i){
            if(res==gifts[i])
                ++count;
            else
                --count;
            if(count==0){
                res=gifts[i];
                count=1;
            }
        }
        if(this->checkMoreThanHalf(gifts,n,res))
            return res;
        else 
            return 0;
    }

    bool checkMoreThanHalf(vector<int>& gifts,int len,int number){
        int times=0;
        for(int i=0;i<len;++i){
            if(gifts[i]==number)
                ++times;
        }
        bool isMoreThanHalf=true;
        if(times*2<=len)
            isMoreThanHalf=false;
        return isMoreThanHalf;
    }
};

参考文献

[1]格雷码. [2]剑指Offer.何海涛.电子工业出版社.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏为数不多的Android技巧

[译]厌倦了NullPointException?Optional拯救你!

有人说,当你处理过了空指针异常才真正成为一个Java开发者。抛开玩笑话不谈,空指针确实是很多bug的根源。Java SE 8引入了一个新的叫做java.util...

1232
来自专栏枕边书

用memoization优化递归算法[JS/PHP实现]

递归函数,通过把一个大而复杂问题简化为许多但规模较小的问题,以同一个相似模式来计算,降低了解题的难度;通过调用自身函数,极大地减少了函数代码量的优点而为开发者喜...

27610
来自专栏Java与Android技术栈

为了程序的健壮性,我们可以使用空对象模式

在写代码的时候我们经常会遇到空指针,为了避免空指针的发生需要做一些判断。如果是复杂对象的话,还需要一层层地去判断。这个时候我就无比怀念groovy、kotlin...

1072
来自专栏Java面试笔试题

两个对象值相同(x.equals(y) == true),但却可有不同的hash code,这句话对不对?

不对,如果两个对象x和y满足x.equals(y) == true,它们的哈希码(hash code)应当相同。Java对于eqauls方法和hashCode方...

1242
来自专栏码洞

《快学 Go 语言》第 3 课 —— 分支与循环

上面这个等式每一个初学编程的同学都从老师那里听说过。它并不是什么严格的数据公式,它只是对一般程序的简单认知。数据结构是内存数据关系的静态表示,算法是数据结构从一...

1073
来自专栏Fundebug

JavaScript正则表达式进阶指南

例如,正则表达式/F.*g/会匹配“以F开头,以g结尾的字符串”,因此可以匹配"Hello, Fundebug!"中的Fundebug,exec方法会返回一个数...

1906
来自专栏轮子工厂

卧槽,为什么你的程序执行到一半就退出了,原来是因为加了这个

快到月底了,相信有很多人都和呆博一样,不是“快揭不开锅了”,而是已经快要把锅都吃了〒▽〒。没关系我们可以一起吃掉这篇精神食粮啊,营养又健康,如果觉得味道还不错,...

2982
来自专栏数据结构与算法

1487 大批整数排序

个人博客:doubleq.win 1487 大批整数排序  时间限制: 3 s  空间限制: 16000 KB  题目等级 : 黄金 Gold 题解 题目描述 ...

2966
来自专栏日常学python

python中一切皆对象

众所周知python是一款面向对象语言,在python语言中,可以说python的一切皆对象是不会错的。如果你学过java的话,你也会知道java也是一款面向对...

1080
来自专栏aCloudDeveloper

一个交换程序的通用版本

Author:bakari   Date:2012.9.3       交换程序是每个开始学习编程的人必学习的一个初级算法。算法思想很简单,就是为两个交换的双方...

1776

扫码关注云+社区

领取腾讯云代金券