寻找Coder——去哪儿2015研发工程师笔试题

题目描述：（题目链接：寻找Coder）

请设计一个高效算法，再给定的字符串数组中，找到包含"Coder"的字符串(不区分大小写)，并将其作为一个新的数组返回。结果字符串的顺序按照"Coder"出现的次数递减排列，若两个串中"Coder"出现的次数相同，则保持他们在原数组中的位置关系。

给定一个字符串数组A和它的大小n，请返回结果数组。保证原数组大小小于等于300,其中每个串的长度小于等于200。同时保证一定存在包含coder的字符串。

测试样例： ["i am a coder","Coder Coder","Code"],3 返回：["Coder Coder","i am a coder"]

分析： 这道编程题主要有以下几个考点： 1. 字符串查找，可以考虑用string的find函数，具体用法见C++中string::npos的一些用法总结。 2. 对查找结果的保存，可以使用自定义对象来排列，也可以用集合中的工具类。 3. 数组的排序，特别要注意的是：按出现次数降低排列+按原数组中的索引升序排列，且先次数排列再索引排列，对于排序来讲需要采用“稳定排序”。 以下给出一些方法的代码总结： 方法1：直接利用库函数里面的stable_sort函数对出现Coder的次数进行稳定排序，得到最终结果。 class Coder { public: static bool cmp(const pair<int, int> a, const pair<int, int> b) { return a.first > b.first; //降序排列 } vector<string> findCoder(vector<string> A, int n){ vector<string> B; vector<pair<int,int> > outA; string coder = "CODER"; for(vector<string>::size_type ix = 0; ix!=A.size(); ix++) { string::size_type pos = 0; unsigned int cnt = 0; string temp = A[ix]; transform(temp.begin(),temp.end(),temp.begin(),::toupper);// 全部转化为大写 while ((pos = temp.find(coder, pos)) != string::npos) { ++cnt; pos=pos+coder.size(); } outA.push_back(make_pair<int,int>(cnt,ix)); } stable_sort(outA.begin(),outA.end(),cmp); for(vector<int>::size_type ix = 0; ix!=outA.size(); ix++) B.push_back(A[outA[ix].second]); return B; } }; 方法2：采用冒泡排序的办法 class Coder { public: vector<string> findCoder(vector<string> A, int n) { vector<string> result;//result存储字符串结果 vector<int> resultInt;//resultInt存储对应字符串的coder数目 vector<string>::iterator iter = A.begin(); for (; iter != A.end(); iter++) { string s = *iter; int count = 0; for (int i = 0; i < s.length() && (i + 4) < s.length();) { if (toupper(s[i]) == 'C' && toupper(s[i + 1]) == 'O' && toupper(s[i + 2]) == 'D' && toupper(s[i + 3]) == 'E' && toupper(s[i + 4]) == 'R') { //统一转化为大写 count++; i += 5; } else i += 1; } if (count > 0) { result.push_back(*iter); resultInt.push_back(count); } } // 以下为冒泡排序 bool flag = true; for (int i = 0; i < result.size(); i++) { if (!flag) { break; } flag = false; for (int j = 0; j < result.size() - i - 1; j++) { if (resultInt[j] < resultInt[j + 1]) { int temp = resultInt[j + 1]; resultInt[j + 1] = resultInt[j]; resultInt[j] = temp; string tmp = result[j + 1]; result[j + 1] = result[j]; result[j] = tmp; flag = true; } } } return result; } }; 方法3：同样是冒泡排序，字符串对应下标和字符串的数目同时变化。 class Coder { public: void swap(int &a, int &b) { int temp = a; a = b; b = temp; } vector<string> findCoder(vector<string> A, int n) { vector<int> cnt; for(int i = 0; i < A.size(); ++i) { string temp = A[i]; transform(temp.begin(), temp.end(), temp.begin(), ::toupper); int index = 0; int temp_cnt = 0; while((index = temp.find("CODER", index)) != -1) { ++index; ++temp_cnt; } cnt.push_back(temp_cnt); } vector<int> order; for(int i = 0; i < n; ++i) order.push_back(i); for(int i = 0; i < n - 1; ++i) for(int j = n - 1; j > i; --j) { if(cnt[j] > cnt[j - 1]) { swap(cnt[j], cnt[j - 1]); swap(order[j], order[j -1]); } } vector<string> result; for(int i = 0; i < n; ++i) result.push_back(A[order[i]]); return result; } }; 方法4：采用pair类型和stable_sort函数。 class Coder { public: static bool compare(const pair<string,int> a,const pair<string,int> b){ return a.second>b.second; } vector<string> findCoder(vector<string> A, int n) { int count=0; vector<pair<string,int>> tmp; vector<string> result; for(int i=0;i<n;i++){ for(int j=0;j<A[i].size()-4;j++){ if(tolower(A[i][j])=='c' && tolower(A[i][j+1])=='o' && tolower(A[i][j+2])=='d' && tolower(A[i][j+3])=='e' && tolower(A[i][j+4])=='r'){ count++; } } if(count>0) tmp.push_back(make_pair(A[i],count)); count=0; } stable_sort(tmp.begin(),tmp.end(),compare); for(int i=0;i<tmp.size();i++) result.push_back(tmp[i].first); return result; } }; 方法5：使用multimap class Coder { public: vector<string> findCoder(vector<string> A, int n) { multimap<int,int,greater<int>> maps; for (int i=0;i<n;i++){ int L=A[i].length(); int count=0; for (int j=0;j<=L-5;j++){ if (toupper(A[i][j])=='C'&&toupper(A[i][j+1])=='O'&&toupper(A[i][j+2])=='D'&&toupper(A[i][j+3])=='E'&&toupper(A[i][j+4])=='R'){ count++; j=j+4; } } maps.insert(make_pair(count,i)); } vector<string> result; for (multimap<int,int,greater<int>>::iterator pos=maps.begin();pos!=maps.end();pos++){ result.push_back(A[pos->second]); } return result; } }; 方法6：不使用排序 class Coder { public: int counting(string &A){ //统计字符串中Coder出现的次数 int c=0; int pos=A.find("Coder",0); while(pos!=string::npos){ c++; if(pos+5<A.size()) pos=A.find("Coder",pos+5); else break; } pos=A.find("coder",0); while(pos!=string::npos){ c++; if(pos+5<A.size()) pos=A.find("coder",pos+5); else break; } return c; } vector<string> findCoder(vector<string> A, int n) { vector<string> result; vector<int> res(n,0); int maxval=0; for(int i=0;i<n;i++){ res[i]=counting(A[i]); if(res[i]>maxval) maxval=res[i]; //出现次数的最大值 } while(maxval>0){ //按照最大值到最小值逐渐存入到result中 for(int j=0;j<res.size();j++){ if(res[j]==maxval) result.push_back(A[j]); } maxval--; } return result; } };