去哪儿研发工程师笔试题-2015年

编程题

1、对于一个有序数组，我们通常采用二分查找的方式来定位某一元素，请编写二分查找的算法，在数组中查找指定元素。

给定一个整数数组A及它的大小n，同时给定要查找的元素val，请返回它在数组中的位置(从0开始)，若不存在该元素，返回-1。若该元素出现多次，请返回第一次出现的位置。

测试样例：

[1,3,5,7,9],5,3

返回：1

2、对于一个字符串，请设计一个高效算法，找到第一次重复出现的字符。

给定一个字符串(不一定全为字母)A及它的长度n。请返回第一个重复出现的字符。保证字符串中有重复字符，字符串的长度小于等于500。

测试样例：

"qywyer23tdd",11

返回：y

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

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

测试样例：

["i am a coder","Coder Coder","Code"],3

返回：["Coder Coder","i am a coder"]

参考答案

1、参考代码：

public class BinarySearch {
    public int getPos(int[] A, int n, int val) {
        // write code here
        if(n<=0 || A==null) return -1;
        int mid=0,L=0,R=n-1;
        while(L<R){
            mid = (L+R)/2;
            if(A[mid]>val){
                R=mid-1;
            }else if(A[mid]<val){
                L=mid+1;
            }else{
                 
                R=mid;
            }
        }
        if(A[L]==val) return L;
        return -1;
    }
     
}

2、参考代码：

classFirstRepeat {
 
public:
 
    charfindFirstRepeat(string A, intn) {
 
        bool times[256] = {0};
 
        if(A.size()==0|| n==0)
 
            return0;
 
        for(inti=0;i<n;i++) {
 
            if(!times[A[i]])
 
                times[A[i]] = 1;
 
            else
 
                returnA[i];
 
        }
 
    }
 
};

3、参考代码：

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;}
    }
}