##WeChat Live Coding
实验室人的TST计划——微信面试题，一个小时内做出如下5道题，在collabedit上在线coding
拿来学习一下。。。啦啦啦啦啦啦
###思路
- 1、哈希表
- 2、递归解决，按照中序遍历的反方向查找
- 3、筛选法先选出素数，然后分解因子
- 4、经典LIS，使用STL技术缩减代码
- 5、经典Shuffle
###Code
/*
1. 有char a[n],char b[m]两个数组，n > m > 1000
b数组中的元素a中都有，现在需要生成数组c，
将a中有b中没有的元素都放到c里面，要求高效
*/
void solution(char a[], char b[], vector<char> c){
int len_a = strlen(a);
int len_b = strlen(b);
int hash_table[256];
memset(hash_table,0,sizeof(hash_table));
for(int i = 0; i < len_a; ++i){
hash_table[a[i]]++;
}
for(int i = 0; i < len_b; ++i){
if(hash_table[b[i]] != 0){
hash_table[b[i]] = -1;
}
}
for(int i = 0; i < 256; ++i){
while(hash_table[a[i]]--){
c.push_back(a[i]);
}
}
}/*
2. 在二叉排序树上面找出第3大的节点。注意：不能
把二叉树全量存储到另外的存储空间，比如存储到数组中，
然后取出数组的第三个元素。
*/
TreeNode* findkth(TreeNode* root,int k,int step){
if(root == nullptr){
return null;
}
findkth(root->right,k,step);
step++;
if(k == step){
return root;
}
return findkth(root->left,k,step);
}
//call
TreeNode* ret = findkth(root,3,0);/*
3. 求出100000以内符合下面条件的数字：
它是可以分解的整数，且所有数位上的数字和等于其全部质数因子的数字总和。
例如：9975=3*5*5*7*19，9+9+7+5=30，3+5+5+7+1+9=30
*/
void calc_prime(int n,vector<int>& prime){
vector<bool> is_prime(n,true);
//first prime
prime.push_back(2);
for(int i = 3; i < n; i += 2){
if(is_prime[i]){
prime.push_back(i);
for(int j = (i << 1); j < n; j += i){
is_prime[j] = false;
}
}
}
}
int sum_digit(int n){
int result = 0;
while(n){
result += n % 10;
n /= 10;
}
return result;
}
int sum_factor(int n,vector<int> prime){
int prime_len = prime.size();
int index = 0;
int result = 0;
for(index < prime_len && prime[index] < n){
while(n % prime[index] == 0){
result += sum_digit(prime[index]);
n /= prime[index];
}
++index;
}
return result;
}
void solution(int n){
vector<int> prime;
calc_prime(n,prime);
for(int i = 2; i < n; ++i){
if(sum_digit(i) == sum_factor(i,prime)){
cout<<i<<" ";
}
}
}/*
4. 给定一个无序的整数数组，求出数组中的最长递增子序列的长度；
例如， {7, 2, 3, 1, 5, 8, 9, 6}，最长递增子序列为{2, 3, 5, 8, 9}，长度为5
*/
int solution(vector<int> data){
int n = data.size(0);
vector<int> dp(n,INT_MAX);
for(int i = 0 ; i < n; ++i){
*lower_bound(dp.begin(),dp.begin()+n,data[i]) = data[i];
}
return lower_bound(dp.begin(),dp.begin()+n,INT_MAX) - dp.begin();
}/*
5. 编写一个扑克牌的随机发牌程序，要求将52张牌随机均等不重复的分给4个选手。
要求用C/C++编写。用1,2,…,13代表13张牌，结果存放在4个数组即可。
*/
//Suppose rand() is a perfect random generator
vector<vector<int> > solution(){
vector<vector<int> > result(4,vector(13,0));
int card[52];
for(int i = 0; i < 52; ++i){
card[i] = i;
}
for(int i = 0; i < 52; ++i){
int k = rand() % i;
swap(card[k],card[i]);
}
for(int i = 0; i < 52; ++i){
int index = i % 4;
result[index][i / 4] = card[i];
}
}
第一题好像一堆错哦。