请设计一个高效算法，再给定的字符串数组中，找到包含"Coder"的字符串(不区分大小写)，并将其作为一个新的数组返回。结果字符串的顺序按照"Coder"出现的次数递减排列，若两个串中"Coder"出现的次数相同，则保持他们在原数组中的位置关系。
给定一个字符串数组A和它的大小n，请返回结果数组。保证原数组大小小于等于300,其中每个串的长度小于等于200。同时保证一定存在包含coder的字符串。
["i am a coder","Coder Coder","Code"],3
返回：["Coder Coder","i am a coder"]
import java.util.*;
public class Coder {
public String[] findCoder(String[] A, int n) {
ArrayList<Recorder> result = new ArrayList<Recorder>();
for(int i=0;i<n;i++){
String a = A[i].toLowerCase(); //转小写
if(a.contains("coder")){
int count = 0;
int start = 0;
//遍历a查找"coder"
while (a.indexOf("coder", start) >= 0 && start < a.length()) {
count++;
start = a.indexOf("coder", start) + "coder".length();
}
result.add(new Recorder(A[i], i, count));
}
}
//使用Collections提供的对List的归并排序
//需实现其Comparator接口参数
Collections.sort(result, new Comparator<Recorder>() {
@Override
public int compare(Recorder o1, Recorder o2){
//先比"coder"个数, count大者排前面
if(o1.getCount() != o2.getCount())
return o2.getCount() - o1.getCount();
//再比index, index小者排前面
else return o1.getIndex() - o2.getIndex();
}
});
String sorted[] = new String[result.size()];
for(int i=0;i<result.size();i++){
String s = result.get(i).getData();
sorted[i] = s;
}
return sorted;
}
class Recorder{
private String data; //字符串
private int index; //在原数组中的位置
private int count; //含有多少个coder-1
public Recorder(String data, int index, int count){
this.data = data;
this.index = index;
this.count = count;
}
public String getData(){return data;}
public int getIndex(){return index;}
public int getCount(){return count;}
}
}
测试用例用的全是小写 "coder"，投机取巧了
struct node{
int id;
int num;
node(int _id, int _num):id(_id), num(_num){}
};
struct compare{
bool operator()(node p, node q){
return p.num > q.num;
}
}mycompare;
class Coder {
public:
vector<string> findCoder(vector<string> A, int n) {
// write code here
vector<string> ans;
vector<node> v;
for(int i = 0; i < n; ++i){
size_t pos = -5;
int count = 0;
while((pos = A[i].find("coder", pos+5)) != string::npos)
count++;
if(count)
v.push_back(node(i, count));
}
std::stable_sort(v.begin(), v.end(), mycompare);
for(int i = 0; i < v.size(); ++i)
ans.push_back(A[v[i].id]);
return ans;
}
};
bool cmp(const pair<string,int>& a,const pair<string,int>& b){
return a.second>b.second;
}
class Coder {
public:
string change(string str){
string ans=str;
for(int i=0;i<str.length();i++)
if(str[i]>='A'&&str[i]<='Z')
ans[i]=str[i]+32;
return ans;
}
vector<string> findCoder(vector<string> A, int n) {
vector<pair<string,int> > array;
for(int i=0;i<n;i++){
string str=change(A[i]);
int length=0;
int pos=str.find("coder");
while(pos!=-1){
str=str.substr(pos+5);
pos=str.find("coder");
length++;
}
if(length!=0)
array.push_back(make_pair(A[i],length));
}
stable_sort(array.begin(),array.end(),cmp);
vector<string> ans;
for(int i=0;i<array.size();i++){
ans.push_back(array[i].first);
}
return ans;
}
};
首先将字符串全部表示为小写形式、接下来利用string 的find函数循环查找是否包含coder，并统计包含coder的个数。最后利用stable_sort函数进行稳定排序。
vector<string> B;
vector<int> cnt_arr;
//所有大写变成小写
for(int i=0;i<n;i++){
string tmp = A[i];
int len = A[i].length();
for(int j=0; j<len; j++)
tmp[j] = tolower(tmp[j]);
B.push_back(tmp);
}
//计算出现的次数并保存到一个新的vector中
int max = 0;
for(int i=0;i<n;i++){
string tmp = B[i];
int cnt = 0;
while(1) {
int index = tmp.find("coder");
if(index == -1) break;
tmp = tmp.substr(index + 5);
cnt += 1;
}
if(cnt > max) max = cnt;
cnt_arr.push_back(cnt);
}
B.clear();
//按次数由大到小输出
for(int i=max;i>=1;i--)
for(int j=0;j<n;j++)
if(cnt_arr[j]==i) B.push_back(A[j]);
return B;
class Coder {
public:
vector<string> findCoder(vector<string> A, int n) {
// write code here
// result存储字符串结果
vector<string> result;
// resultInt存储对应字符串的coder数目
vector<int> resultInt;
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
i += 5;
}
else {
// 未匹配i+1
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;
}
};
建立一个辅助的vector，用于辅助排序。
//还是我这个方法好，前几天刚看别人代码学的,
//往往在最外层循环增加一层常数次数循环，可以很好的解决问题哦,记着吧！！！
public class Coder {
public String[] findCoder(String[] A, int n) {
// write code here
int[] count = new int[n];//与A数组同样大小的计数数组
ArrayList<String> res = new ArrayList<>();
for(int i=0;i<n;i++){
count[i] = containsCodeCount(A[i]);
}
int max = 0;
for(int i=0;i<n;i++){
if(count[i]>max){
max = count[i];
}
}
for(int i=max;i>=1;i--){//外层不断的减小最大值，直到1为止，这样每次都遍历一遍A数组
for(int j=0;j<n;j++){
if(count[j]==i){
res.add(A[j]);
}
}
}
return res.toArray(new String[res.size()]);
}
private int containsCodeCount(String s){
String ss = s.toLowerCase();
if(!ss.contains("coder")){
return 0;
}
String rep = ss.replaceAll("coder","*");//哈哈投机了，测例中幸好没有*
int count = 0;
for(int i=0;i<rep.length();i++){
if(rep.charAt(i)=='*'){
count++;
}
}
return count;
}
}
class Coder {
public:
vector<string> findCoder(vector<string> A, int n) {
vector<string> B;
int C[300][2] = {0};
string strr;
int i,j,temp,k=0;
for(i=0;i<n;i++){
temp = 0;
for(j=0;j<A[i].size();j++){
strr = A[i].substr(j,5);//.substr(起始位置，截取长度)；
if( (strr[0] == 'c' || strr[0] == 'C') && (strr[1] == 'o' || strr[1] == 'O') && (strr[2] == 'd' || strr[2] == 'D') && (strr[3] == 'e' || strr[3] == 'E') && (strr[4] == 'r' || strr[4] == 'R') ){
temp++;
j += 4;
}
}
if( temp > 0 ){
C[k][0] = i;
C[k][1] = temp;
k++;
}
}
for(i=0;i<k-1;i++){
for(j=0;j<k-1-i;j++){
if(C[j][1] < C[j+1][1]){
temp = C[j][1]; C[j][1] = C[j+1][1]; C[j+1][1] = temp;
temp = C[j][0]; C[j][0] = C[j+1][0]; C[j+1][0] = temp;
}
}
}
for(i=0;i<k;i++)
B.push_back( A[ C[i][0] ]);
return B;
}
};
///方法二，自定义比较函数，用stable_sort进行排序。
bool cmp(const pair<string,int>& a,const pair<string,int>& b){
return a.second > b.second;
}
class Coder {
public:
vector<string> findCoder(vector<string> A, int n) {
vector< pair<string,int> > B;
vector<string> C;
string strr;
int i,j,temp;
for(i=0;i<n;i++){
temp = 0;
for(j=0;j<A[i].size();j++){
strr = A[i].substr(j,5);//.substr(起始位置，截取长度)；
if( (strr[0] == 'c' || strr[0] == 'C') && (strr[1] == 'o' || strr[1] == 'O') && (strr[2] == 'd' || strr[2] == 'D') && (strr[3] == 'e' || strr[3] == 'E') && (strr[4] == 'r' || strr[4] == 'R') ){
temp++;
j += 4;
}
}
if( temp > 0 )
B.push_back( make_pair(A[i],temp) );
}
stable_sort(B.begin(),B.end(),cmp);//sort排序不稳定，因此要用stable_sort
for(i=0;i<B.size();i++)
C.push_back( B[i].first );
return C;
}
};
import java.util.*;
import java.util.Map.Entry;
public class Coder {
public static String[] findCoder(String[] A, int n) {
// write code here
//LinkedHashMap保证放入的顺序和原输入是一致的
LinkedHashMap<String,Integer> map = new LinkedHashMap<String, Integer>();
char[] target = "coder".toCharArray();
for(int i = 0 ; i < n ; i++){
//保证大小写都匹配
char[] chars = A[i].toLowerCase().toCharArray();
int count = 1;
int k = 0;
//对chars进行匹配，每当匹配到一个就写入map
for(int j = 0 ; j < chars.length ; ){
if(chars[j] == target[k]){
j++;
k++;
if(k >= target.length){
map.put(A[i], count++);
k = 0;
}
}else{
//特别注意遍历的顺序，特别是j的顺序，在k>0的时候，说明已经匹配了若干字符但没有匹配满
//最然此时的j不能和之前匹配的匹配，但不能算作一开始就不匹配，因此不能++，只能将k置零
//后返回到原来的j进行匹配判断，这点很容易出错。
if(k > 0)
k = 0;
else
j++;
}
}
}
Set<Entry<String,Integer>> entrySet = (map.entrySet());
Iterator<Entry<String,Integer>> it = entrySet.iterator();
Entry<String,Integer>[] result = new Entry[map.size()];
for(int i = 0 ; i < result.length ; i++){
result[i] = it.next();
}
//对result进行稳定排序，使用的是归并排序。
Entry<String,Integer>[] temp = new Entry[map.size()];
mergeSort(result,temp,0,result.length -1);
String [] resultString = new String[result.length];
for(int i = 0 ; i < result.length ; i ++)
resultString[i] = result[i].getKey();
return resultString;
}
public static void mergeSort(Entry<String,Integer>[] result,Entry<String,Integer>[] temp,int from ,int to){
if(from < to){
int mid = ( from + to ) >>1 ;
mergeSort(result, temp,from, mid);
mergeSort(result,temp, mid+1, to);
merge(result, temp,from, mid, to);
}
}
public static void merge(Entry<String,Integer>[] result,Entry<String,Integer>[] temp,int from ,int mid, int to){
int leftFrom = from;
int leftTo = mid ;
int rightFrom = mid + 1;
int rightTo = to;
int number = to - from + 1;
int currentP = leftFrom;
while(leftFrom <= leftTo && rightFrom <= rightTo){
//归并的稳定体现，这里只能用>=而不能用>,因为那样就会导致相等时交换左右，显然不稳定。
if(result[leftFrom].getValue() >= result[rightFrom].getValue())
temp[currentP++] = result[leftFrom++];
else
temp[currentP++] = result[rightFrom++];
}
while(leftFrom <= leftTo){
temp[currentP++] = result[leftFrom++];
}
while(rightFrom <= rightTo){
temp[currentP++] = result[rightFrom++];
}
for(int i = 0 ; i < number ; i++,rightTo--)
result[rightTo] = temp[rightTo];
}
}
//先转换成小写，再查找统计目标串出现的个数，最后用stable_sort根据个数排序
bool mycmp(const pair<string, int> &a, const pair<string, int> &b) {
return a.second > b.second;
}
class Coder {
public:
vector<string> findCoder(vector<string> A, int n) {
vector<pair<string, int> > svec;
vector<string> res;
string mods = "Coder";
//将模式串转换成小写
string mods1(mods.size(), 0);
transform(mods.begin(), mods.end(), mods1.begin(), ::tolower);
for (int i = 0; i<n; i++) {
//将目标串转换成小写
string objs = A[i];
string objs1(objs.size(),0);
transform(objs.begin(),objs.end(),objs1.begin(),::tolower);
int cnt = -1;//记录匹配个数
int pos = 0, j = 0;
//模式匹配
while (pos != string::npos) {
cnt++;
pos = objs1.find(mods1, j);
j =pos+ 5;
}
if (cnt > 0) {
pair<string, int> pr(A[i], cnt);
svec.push_back(pr);
}
}
//稳定排序
stable_sort(svec.begin(),svec.end(), mycmp);
for (int i = 0; i<svec.size(); i++)
res.push_back(svec[i].first);
return res;
}
};
刚开始看错题目，以为是把句子划分成单词，然后判断有多少单词是coder。
后来发现原串并不是句子，可能就是无序的字符组成的，第一想到的是
KMP、字符串哈希什么的...但是感觉好复杂。后来看到人家直接find（），
很简便...学习了。
bool MyCompare(const pair<int, int>& lhs, const pair<int, int>& rhs){
return lhs.second > rhs.second;
}
class Coder {
public:
vector<string> findCoder(vector<string> A, int n) {
//write code here
vector<string> ret;
vector<pair<int, int> > record;
for (int i = 0; i < n; ++i){
int cnt = 0;
string tmp = A[i];
myToLower(tmp);
size_t pos = -5;
while((pos=tmp.find("coder", pos+5)) != string::npos) //如果在某个位置找到了，返回该位置pos，并在pos+5的位置继续寻找
cnt++; //如果一个没有找到，则返回值等于npos
if (cnt)
record.push_back(make_pair(i, cnt));
}
stable_sort(record.begin(), record.end(), MyCompare);
for (int i = 0; i < record.size(); ++i)
ret.push_back(A[ record[i].first ]);
return ret;
}
void myToLower(string& str){
for(int i = 0; i < str.size(); ++i)
str[i] = tolower(str[i]);
}
};
// 主要还是利用string的成员函数和ATL库，难点在于找到一个含coder的string之后，如何
// 在这个string里面寻找coder出现的次数,在这里我使用的是string成员函数find进行查找。
class Coder {
public:
vector<string> findCoder(vector<string> A, int n) {
// write code here
int count = 0;
vector<string> svec;
string temp;
vector<pair<int, string>> v;
for ( auto it = A.begin(); it != A.end(); ++it )
{
temp = *it; // 临时的string，这样不会改变原有额string
transform( temp.begin(), temp.end(), temp.begin(), ::tolower ); // 把临时的string全变为小写
auto pos = temp.find("coder"); // 开始查找coder在不在当前的string中
if ( pos != string::npos ) // 如果coder在当前的string中的话，我们就开始记录它出现的次数
{ // 如果不在当前访问的string中，下面代码不执行，直接++it
while ( pos != string::npos )
{
++count;
temp.erase( pos, 5 ); // 每次遍历完之后删除对应的coder，再进行下次遍历
pos = temp.find( "coder" ); // 下次再查找临时string中还有没有coder
}
v.push_back( make_pair( count, *it ) ); // 存储当前的次数和原始的含coder的string
count = 0; // 把对应的计数值变为0，以便下次对其他string中的coder再进行重新计数
}
}
// 这里使用lambda表达式传递谓词函数，进行从大到小的排序
stable_sort(v.begin(),v.end(),[](pair<int,string> p1, pair<int,string> p2){return p1.first > p2.first;});
for ( auto c : v ) // 使用范围for语句把对应含coder的string放到容器中
svec.push_back( c.second );
return svec;
}
};
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)
{
// write code here
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;
}
};
class Coder {
public:
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;
}
void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
};
# -*- coding:utf-8 -*-
class Coder:
def findCoder(self, A, n):
# write code here
res = dict()
for i in range(n):
if "coder" in A[i].lower():
res[A[i]] = (A[i].lower().count("coder"), i)
return [pair[0] for pair in sorted(res.items(), key=lambda x: (-x[1][0], x[1][1]))] 
class Coder:
def findCoder(self, A, n):
# 三行代码解决!!! It's so pythonic !!!
string_count = [(string, string.lower().count('coder')) for string in A]
# 这行代码的要点：
# 1. 因题目要求不区分大小写，所以先用 lower() 全部转变为小写
# 2. count('coder') 将能计算出包含'Coder'的个数
# 3. 列表解析式得到：[("i am a coder", 1), ("Coder Coder", 2), ("Code", 0)]
string_count.sort(key=lambda x:x[1], reverse=True)
# 这行代码的要点：前面已经计算过包含'Coder'的个数，用它来排序
# 1. reverse=True：个数多的排前面
# 2. lambda 表达式：相当于 def getkey(x): return x[1]
# 3. lambda x:x[0] 就会获取到"i am a coder"来排序
# 4. lambda x:x[1] 就会获取到个数来排序
# 排序后会得到：[("Coder Coder", 2), ("i am a coder", 1), ("Code", 0)]
return [item[0] for item in string_count if item[1] > 0]
# 这行代码的要点：再次使用列表解析式
# if item[1] > 0，按题目要求，把个数为 0 的丢弃掉
# item[0]，只把 "Coder Coder" 这些字符串放入列表，不用带上个数
# 最终返回：["Coder Coder", "i am a coder"]
import java.util.*;
public class Coder {
static class Node{
String str;
int count;
public Node(String str,int count){
this.str=str;
this.count=count;
}
}
public String[] findCoder(String[] A, int n) {
ArrayList<Node> nodes=new ArrayList<Node>();
for(int i=0;i<n;i++){
String str=A[i];
str=str.toLowerCase().replace("coder","");
if(str.length()<A[i].length()){
int count=(str.length()-A[i].length())/4;
Node node=new Node(A[i],count);
nodes.add(node);
}
}
Collections.sort(nodes,new Comparator<Node>(){
public int compare(Node node1,Node node2){
if(node1.count>node2.count)
return 1;
else if(node1.count<node2.count)
return -1;
else
return 0;
}
});
String[] result=new String[nodes.size()];
for(int i=0;i<nodes.size();i++){
result[i]=nodes.get(i).str;
}
return result;
}
}
import java.util.*;
public class Coder {
public String[] findCoder(String[] A, int n) {
Map<Integer,Integer> map=new TreeMap<Integer,Integer>(new Comparator<Integer>(){ @Override public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
for(int i=0;i<n;i++)
{
String str=A[i];
str=str.toLowerCase();
int count=0; //初始化
int index; //判断
while((index=str.indexOf("coder"))!=-1)
{
count++;
str=str.substring(index+5);
}
map.put(300*count-i, i); //题目上给出A的长度不大于300，所以保证了先检验的字符串键大于后检验的字符串的键
}
int[] a=new int[n];
int index2=0;
for(Map.Entry<Integer,Integer> x:map.entrySet())
{
a[index2++]=x.getValue();
}
String str2[]=new String[n];
for(int i=0;i<n;i++)
{
str2[i]=A[a[i]];
}
return str2;
}
}
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
