去哪儿笔试技术岗15研发工程师

1、编程题1、对于一个有序数组，我们通常采用二分查找的方式来定位某一元素，请编写二分查找的算法，在数组中查找指定元素。 给定一个整数数组 A 及它的大小 n，同时给定要查找的元素 val，请返回它在数组中的位置(从 0 开始)，若不存在该元素，返回-1。若该元素出现多次，请返回第一次出现的位置。 测试样例：2、对于一个字符串，请设计一个高效算法，找到第一次重复出现的字符。给定一个字符串(不一定全为字母)A 及它的长度 n。请返回第一个重复出现的字符。保证字符串中有重复字符，字符串的长度小于等于 500。 测试样例：3、请设计一个高效算法，再给定的字符串数组中，找到包含Coder的字符串(不区分大小

2、写)，并将其作为一个新的数组返回。结果字符串的顺序按照Coder出现的次数递减排列，若两个串中Coder出现的次数相同，则保持他们在原数组中的位置关系。 给定一个字符串数组 A 和它的大小 n，请返回结果数组。保证原数组大小小于等于 300,其中每个串的长度小于等于 200。同时保证一定存在包含 coder 的字符串。 测试样例：参考答案刺猬实习1. i am a coder,Coder Coder,Code,31. 返回：Coder Coder,i am a coder1. qywyer23tdd,111. 返回：y1. 1,3,5,7,9,5,31. 返回：11、参考代码：2、参考代码：刺

3、猬实习1. classFirstRepeat 2.3. public:4.5.charfindFirstRepeat(string A, intn) 6.7.bool times256 = 0;8.9.if(A.size()=0| n=0)10.11.return0;12.13.for(inti=0;in;i+) 14.15.if(!timesAi) 16.17.timesAi = 1;18.1. public class BinarySearch 2. public int getPos(int A, int n, int val) 3. / write code here4. if(n=0

4、 | A=null) return -1;5.int mid=0,L=0,R=n-1;6.while(Lval)9. R=mid-1;10. else if(Amidval)11. L=mid+1;12. else13.13.14.R=mid;15.16.17. if(AL=val) return L;18. return -1;、参考代码：刺猬实习1. import java.util.*;2. public class Coder 3. public String findCoder(String A, int n) 4. ArrayList result = new

5、ArrayList();5. for(int i=0;i= 0 & start a.length()12. count+;13.start = a.indexOf(coder, start) + coder.length();14.15.result.add(new Recorder(Ai, i, count);9. /使用Collections 提供的对 List 的归并排序 20. /需实现其Comparator 接口参数 21. Collections.sort(result, new Comparator() 22. Override23. public int c

6、ompare(Recorder o1, Recorder o2)24. /先比coder个数, count 大者排前面 25. if(o1.getCount() != o2.getCount()26. return o2.getCount() - o1.getCount();27. /再比index, index 小者排前面 28. else return o1.getIndex() - o2.getIndex();29.30.);19.else20.21.returnAi;5.26.27.;刺猬实习31. String sorted = new Stringresult.

7、size();32. for(int i=0;iresult.size();i+)33. String s = result.get(i).getData();34. sortedi = s;35.36.return sorted;37.38. class Recorder39. private String data; /字符串 40. private int index; /在原数组中的位置 41. private int count;/含有多少个coder-142. public Recorder(String data, int index, int count)43. this.data = data;44. this.index = index;45. this.count = count;46.47. pub