声明：题目来源牛客网

生成格雷码

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

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

题1

思想：首先要知道格雷码的规律

格雷码

由图可知，从2开始的格雷码的格式都是 前一个数格雷码前面加0，前一个数格雷码逆置后加1 。所以这就是一个递归的子问题了，使用递归一直递归到1，然后递归退层，在返回本层时用上述方法进行处理，最后就能够返回传入位数的格雷码了。

C++代码实现：

递归函数

启动函数

微信红包

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

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

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

题2

思想：这道题的方法很多，但是要求算法尽可能的高效，我就想到了用map来实现。根据map的特点：底层是红黑树，查找，插入快；map是key-value结构，key用来存红包金额，value用来存其出现的次数；map重载了[]运算，其相当于(*((this->insert(make_pair(x,T()))).first)).second即调用[]的时候传入的值没有就会进行插入，有的话就会返回该值的value。知道了这三个特性这道题就非常简单了。遍历传入的gifts数组，每一个值都插入map中，调用重载的[]，获取value，直接前置++（如果没有元素，插入时的数据是0，++后变成1，如果有元素，插入时直接++value），判断++后的值是否大于n/2（这里采用的是移位运算，这样写算法会快一点），如果大于直接返回该值，遍历完数组后都没有返回那就说明没有金额的个数超过金额数组大小的一半，直接返回0。

// C++代码

int getValue(vector<int> gifts, int n) {

map<int, int> m;

for (size_t i = 0; i < n; ++i) {

if(++m[gifts[i]]>(n>>1))return gifts[i];

}

return 0;

}

总结：这两道题总体来说是比较简单的，主要是考察算法的时间复杂度。

结束语：

如果喜欢这篇头条，一定要收藏哟^O^

点击关注，了解更多关于编程的知识^O^

如果有不懂的地方，可以留言，相互探讨，相互学习，共同进步^O^