腾讯编程

ranranblog 2021-09-08 原文

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

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

测试样例：

返回：["0","1"]

格雷码
1 “0” “1”
2 “00” “01” “11” “10”
3 ”000“ ”001“ ”011“ ”010“ ”110“ ”111“ ”101“ ”100“

 1 class GrayCode {
 2 public:
 3     vector<string> getGray(int n)
 4 {
 5     // write code here
 6     if (n == 0)
 7     {
 8         vector<string> res0;
 9         res0.push_back("0");
10         return res0;
11     }
12     else if (n == 1)
13     {
14         vector<string> res1;
15         res1.push_back("0");
16         res1.push_back("1");
17         return res1;
18     }
19     else
20     {
21         vector<string>v1 = getGray(n - 1);
22         vector<string>v2;
23         int num = pow(2, n - 1);
24         for (int i = 0; i < num; i++)
25         {
26             string str1 = v1[i];
27             str1.insert(0, "0");
28             v2.push_back(str1);
29 
30         }
31         for (int i = num - 1; i >= 0; i--)
32         {
33             string str2 = v1[i];
34             str2.insert(0, "1");
35             v2.push_back(str2);
36 
37         }
38         return v2;
39     }
40 }
41 };

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

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

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

测试样例：

[1,2,3,2,2],5

返回：2

 1 class Gift {
 2 public:
 3     int getValue(vector<int> gifts, int n) {
 4         // write code here
 5         sort(gifts.begin(),gifts.end());
 6         int res=gifts[(n-1)/2];
 7         int count=0;
 8         for(int i=0;i<n;i++)
 9          {
10             if(gifts[i]==res)
11                 count++;
12         }
13         if(count*2>n)
14             return res;
15         else
16             return 0;
17         
18     }
19 };
20 添加笔记