生成格雷码
在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同， 则称这种编码为格雷码(Gray Code)，请编写一个函数，使用递归的方法生成N位的格雷码。
给定一个整数n，请返回n位的格雷码，顺序为从0开始。
测试样例：
1
返回：[“0”,”1”]
递归实现：
vector<string> getGray(int n){
static int m=0;
static vector<string> vec;
if(m==0){
vec.push_back("0");
vec.push_back("1");
m++;
getGray(n-1);
}else{
if(n==0){
for(int i=0;i<vec.size();i++)
cout<<vec[i]<<" ";
return vec;
}else{
int s=vec.size();
for(int i=0;i<s;i++) //插入0
vec.push_back("0"+vec[i]);
for(int i=s-1;i>=0;i--) //插入1
vec.push_back("1"+vec[i]);
vector<string>::iterator it=vec.begin(); //把先前的删除掉
vec.erase(it,it+s);
getGray(n-1);
}
}
return vec;
}
非递归实现：
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<string> getGray(int n){
vector<string> vec;
for(int j=0;j<n;j++){
if(j==0){
vec.push_back("0");
vec.push_back("1");
}else{
int s=vec.size();
for(int i=0;i<s;i++) //插入0
vec.push_back("0"+vec[i]);
for(int i=s-1;i>=0;i--) //插入1
vec.push_back("1"+vec[i]);
vector<string>::iterator it=vec.begin(); //把先前的删除掉
vec.erase(it,it+s);
}
}
//for(int i=0;i<vec.size();i++)
// cout<<vec[i]<<" ";
return vec;
}
int main(){
getGray(3);
//vector<string> vec;
//for(int i=0;i<vec.size();i++)
// cout<<vec[i]<<" ";
//cout<<endl;
system("pause");
}
微信红包
春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。
给定一个红包的金额数组gifts及它的大小n，请返回所求红包的金额。
若没有金额超过总数的一半，返回0。
测试样例：
[1,2,3,2,2],5
返回：2
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int getValue(vector<int> gifts,int n){
map<int,int> mapgift;
for(int i=0;i<n;i++)
mapgift[gifts[i]]++;
map<int,int>::iterator it;
for(it=mapgift.begin();it!=mapgift.end();it++){
if(it->second>n/2){
return it->first;
}
}
return 0;
}
int main(){
int n=5;
int arr[5]={1,2,3,2,2};
vector<int> gifts(arr,arr+5);
cout<<getValue(gifts,n)<<endl;
system("pause");
}