拼多多笔试1,3题分享
拼多多笔试分享(c++)版本.
1 求n个数中方差最小的三个数.
解题思路:排序然后遍历一次即可
// first problem double std3(int a,int b,int c){ double mean = double(a+b+c) /3; double ret = (a-mean)*(a-mean) +(b-mean)*(b-mean)+(c-mean)*(c-mean); return ret; } double minstd(int num, int*numbers){ sort(numbers,numbers+num); double ret = std3(numbers[0],numbers[1],numbers[2]),temp; for(int i=1; i<num-2;i++){ temp = std3(numbers[i],numbers[i+1],numbers[i+2]); if (temp<ret) ret = temp; } return ret; }3 求单调递增序列且和等于n的个数.
解题思路:第一种暴力搜索dfs,ret 即返回值,通过率5%.
//third problem: 求递增且和邓素numsum 的序列个数; void dfs(int numlen,int cur,int numSum,int &ret,int* nums){ if(numSum<0 ) return; if(cur == numlen){ if (numSum ==0) ret +=1; return; } if(cur ==0){ for(int i=1;i<=int((numSum)/numlen);i++){ nums[0] = i; dfs(numlen,cur+1,numSum-i,ret,nums); } } else{ for(int i=nums[cur-1]+1;i<=int(numSum/(numlen-cur));i++){ nums[cur] = i; dfs(numlen,cur+1,numSum-i,ret,nums); } } return; }第二种:动态规划,保留上次的结果.
int count_sequences_satisfy_condition(int numlen, int numSum,unsigned long int** visited ){ if(numlen==1) return 1; if(2*numSum<numlen*(numlen-1)) return 0; if(numlen == 2){ visited[numSum][2] = (numSum-1)/2; return (numSum-1)/2; } if(visited[numSum][numlen]) return visited[numSum][numlen]; int firstNumMax = numSum/numlen; int sumcount = 0; for(int i=1;i<=firstNumMax;i++){ visited[numSum-numlen*i][numlen-1] = count_sequences_satisfy_condition(numlen-1,numSum-numlen*i,visited); sumcount += visited[numSum-numlen*i][numlen-1]; } return sumcount; }