首页 > 代码库 > ctrip的两道笔试题
ctrip的两道笔试题
第一个问题可以抽象为这样：给定一个数组A，和一个数t，用数组里的一些数求和得到t，数组里的数可以重复使用，写一个算法，使得使用A中最少的数来表示t。
比如：[2,4,6,9],18==>[9,9]
dfs问题
//numbers要从大到小，一个sort搞定，result存放结果bool dfs(vector<int>& numbers,int gap,int start,vector<int> &result){ if(0 == gap) { return true; } bool r = false; for(int i = start; i < numbers.size(); ++i) { if(gap < numbers[i]) continue; result.push_back(numbers[i]); r = dfs(numbers,gap-numbers[i],i,result); if(!r) { result.pop_back(); }else { return r; } } return r;}还有一个题是说给定若干有序区间，求第k个数，感觉可以用二分法做，但是没想出来，所以就进行遍历，时间复杂度为O(n)
void kth(vector<vector<int> > &numbers, vector<int> &pos,int k, int &result){ if(0 == k) return ; int index = 0; int min = INT_MAX; int indexx = -1; for(;index < numbers.size(); ++index) { if(pos[index] != -1 && numbers[index][pos[index]] < min) { min = numbers[index][pos[index]]; indexx = index; } } result = min; ++pos[indexx]; if(pos[indexx] == numbers[indexx].size()) { pos[indexx] = -1; } kth(numbers,pos,k-1,result);}int getkth(vector<vector<int> > &numbers, int k){ vector<int> pos(numbers.size(),0); int result = -1; kth(numbers,pos,k,result); cout<<result<<endl; return result;}
ctrip的两道笔试题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。