去哪儿研发工程师编程题-2016年

编程题

1、写一段代码，判断一个包括'{','[','(',')',']','}'的表达式是否合法(注意看样例的合法规则。)

给定一个表达式A,请返回一个bool值，代表它是否合法。

测试样例：

"[a+b*(5-4)]*{x+b+b*(({1+2)}}"

返回：true

2、从小明家所在公交站出发有n路公交到公司，现给出每路公交的停站数(不包括起点和终点)，及每次停的时间(一路车在每个站停的时间相同)和发车的间隔，先假定每辆车同时在相对时间0分开始发车，且所有车在相邻两个站之间的耗时相同,都为5分钟。给定小明起床的相对时间(相对0的分钟数)，请计算他最早到达公司的相对时间。

给定每路车的停站数stops,停站时间period,发车间隔interval及公交路数n，出发时间s。请返回最早到达时间。保证公交路数小于等于500，停站数小于等于50。

给定一个字符串A，同时给定它的长度n及参数字符数组arg，请返回替换后的字符串。保证参数个数大于等于占位符个数。保证原串由大小写英文字母组成，同时长度小于等于500。

"A%sC%sE",7,['B','D','F']

返回："ABCDEF"

4、现在有一个字符串列表，和一个关键词列表，请设计一个高效算法，检测出含关键字列表中关键字(一个或多个)的字符串。

给定字符串数组A及它的大小n以及关键词数组key及它的大小m，请返回一个排好序的含关键词的字符串序号的列表。保证所有字符串长度小于等于100，关键词个数小于等于100，字符串个数小于等于200。保证所有字符串全部由小写英文字符组成。若不存在含关键字的字符串，请返回一个只含-1的数组。

测试样例：

["nowcoder","hello","now"],3,["coder",now],2

返回：[0,2]

5、血型遗传对照表如下：

父母血型	子女会出现的血型	子女不会出现的血型
O与O	O	A,B,AB
A与O	A,O	B,AB
A与A	A,O	B,AB
A与B	A,B,AB,O	——
A与AB	A,B,AB	O
B与O	B,O	A,AB
B与B	B,O	A,AB
B与AB	A,B,AB	O
AB与O	A,B	O,AB
AB与AB	A,B,AB	O

请实现一个程序，输入父母血型，判断孩子可能的血型。

给定两个字符串father和mother，代表父母的血型,请返回一个字符串数组，代表孩子的可能血型(按照字典序排列)。

”A”,”A”

返回：[”A”,“O”]

参考答案

1、参考代码：

import java.util.*;
 
public class ChkExpression {
    public boolean chkLegal(String A) {
        // write code here
       
        Stack<Character> stack = new Stack<Character>();
        HashMap<Character,Character> map = new HashMap<Character,Character>();
        map.put('[',']');
        map.put('{','}');
        map.put('(',')');
        for(int i =0;i<A.length();i++){
            char ch = A.charAt(i);
            if(map.containsKey(ch)){
                stack.push(ch);
            }else if(map.containsValue(ch)){
                if(stack.isEmpty())
                    return false;
                char top = stack.peek();
               // if(map.get(top).equals(ch)){
                    stack.pop();
               // }else{
                //    return false;
                //}
            }
        }
        return stack.isEmpty();
    }
}

2、参考代码：

import java.util.*;
 
public class TakeBuses {
    public int chooseLine(int[] stops, int[] period, int[] interval, int n, int s) {
        // write code here
        int min = Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            int missTime = s%interval[i];
            int waitCost = missTime==0?0:interval[i]-missTime;
            min = Math.min(min,waitCost+(stops[i]+1)*5+stops[i]*period[i]);
        }
        return min+s;
    }
}

3、参考代码：

public String formatString(String A, int n, char[] arg, int m) {       
         int i = 0;
        while (A.indexOf("%s") >= 0) {
            A = A.replaceFirst("%s", String.valueOf(arg[i]));
            i++;
        }
        while (i < m) {
            A += arg[i];
            i++;
        }
        return A;
}

4、参考代码：

import java.util.*;
 
public class KeywordDetect {
    public int[] containKeyword(String[] A, int n, String[] keys, int m) {
        List<Integer> list = new ArrayList<Integer>();
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                if(A[i].indexOf(keys[j])>-1){
                    list.add(i);
                    break;
                }
            }
        }
        if(list.isEmpty())
            return new int[]{-1};
        int[] r = new int[list.size()];
        for(int i = 0;i<list.size();i++)
            r[i] = list.get(i);
        return r;
         
    }
}

5、参考代码：

public String[] chkBlood(String father, String mother) {
    // write code here
    Map<String, String[]> bloodMap = new HashMap<String, String[]>();
    bloodMap.put("OO", new String[] { "O" });
    bloodMap.put("AO", new String[] { "A", "O" });
    bloodMap.put("AA", new String[] { "A", "O" });
    bloodMap.put("AB", new String[] { "A", "AB", "B", "O" });
    bloodMap.put("AAB", new String[] { "A", "AB", "B" });
    bloodMap.put("BO", new String[] { "B", "O" });
    bloodMap.put("BB", new String[] { "B", "O" });
    bloodMap.put("BAB", new String[] { "A", "AB", "B" });
    bloodMap.put("ABO", new String[] { "A", "B" });
    bloodMap.put("ABAB", new String[] { "A", "AB", "B" });
    if (bloodMap.get(father + mother)==null) {
            return bloodMap.get(mother+father);
    }
    return bloodMap.get(father + mother);
}