去哪儿网2014笔试算法题汇总[附答案] - 高飞网
217 人阅读

去哪儿网2014笔试算法题汇总[附答案]

2017-07-28 02:09:46

相对路径转绝对路径

    写一个函数,转换相对路径为绝对路径,比如:/home/abs/../temp/new/../,输出路径:/home/temp。

    思路:该问题主要用到了栈的基本操作,如果遇到的是普通的目录,就入栈,如果是遇到..,即向上一级,就弹栈,一直进行到最后,然后把栈遍历一遍即可。

import java.util.*;
/**
 * 转换相对路径为绝对路径,比如:/home/abs/../temp/new/../,输出路径为:/home/temp
 */
public class Rp2ap{
    public static void main(String[] args){
        String path1 = "/home/abs/../temp/new/../";
        String path2 = relativePath2AbsolutePath(path1);
        System.out.printf("relativePath 2 AbsolutePath: from [%s] to [%s]\n",path1,path2);  
    }   

    public static String relativePath2AbsolutePath(String path){
        String[] ps = path.split("/");
        Stack<String> stack = new Stack<String>();
        Iterator<String> ite = stack.iterator();
        for(String p :ps){
            if("".equals(p)){
                continue;
            }   
            if(p.equals("..")){//弹出
                stack.pop();
            }else{//压入
                stack.push(p);
            }   
        }   
        StringBuffer sb = new StringBuffer("/");
        for(String p:stack){
            sb.append(p).append("/");
        }   
        return sb.toString();
    }   
}


同色五星连珠

    一个10*10的矩阵(可以理解为棋盘),随时生成一组数据填入矩阵,任何一个位置的数字除4进行计算,按余数着色,余数为0着色为red,1为blue,2为green,3为black,可以理解为生成4中颜色的棋子放入棋盘,如果存在其中同色五星连珠的情况(规则通五子棋),找出任意一组,输出5个棋子的位置下标值。

    思路:第一步首先要生成10*10的矩阵,第二步就是比较,可以分为横向、纵向、正斜、反斜来找同色五星连珠情况。比较时,可以两两相邻比较,只要一直相同就计数。计数大于等于5就输出

import java.util.*;
public class FiveInARow{
    public static void main(String[] args){
        int[][] board = new int[10][10];
        Random r = new Random();
        for(int i=0;i<10;i++){
            for(int j=0;j<10;j++){
                int num = r.nextInt(10000)%4;
                board[i][j]= num;
            }
        }
        for(int i=0;i<10;i++){
            for(int j=0;j<10;j++){
                System.out.printf("%2s",board[i][j]);
            }   
            System.out.println();
        }   
        //横
        for(int i=0;i<10;i++){
            int cnt = 1;
            int start = board[i][0];
            for(int j=1;j<10;j++){
                if(board[i][j]!=start){
                    start = board[i][j];
                    cnt = 1;
                }else{
                    cnt++;
                }   
                if(cnt>=5){
                    System.out.printf("横:[%d][%d]~[%d][%d]==%d\n",i,j-cnt+1,i,j,start);
                }   
            }   
        }   
        //纵
        for(int j=0;j<10;j++){
            int cnt = 1;           
	    int start = board[0][j];
            for(int i=1;i<10;i++){
                if(board[i][j]!=start){
                    start = board[i][j];
                    cnt = 1;
                }else{
                    cnt++;
                }
                if(cnt>=5){
                    System.out.printf("纵:[%d][%d]~[%d][%d]==%d\n",i,j,i-cnt+1,j,start);
                }
            }
        }
    }
}



模式匹配

有两个文件context.txt和words.conf,请尝试将他们合并成为一段文字,并打印出来。

这两个文件内容如下:

context.txt
“并不是每个人都需要$(qunar)自己的粮食,$(flight.1)每个人都需要做自己穿的$(flight.2),我们说着别人发明的$(hotel),使用别人发明的数学……我们一直在$(tuan)别人的成果。使用人类的已有经验和知识$(travel.1)来进行,是一件$(travel.2)的事情” 

word.conf
flight=也不是:衣服
qunar=种植
hotel=语言
tuan=使用
travel=发明创造:很了不起

思路:我认为主要考的是正则表达式的匹配问题。首先对work.conf做一下处理,以=前的为key,=后的为value,value是一个数组。然后对context中的文本,从前往后进行模式匹配$(单词[.数字]),取出后,根据key和相应的数字,找到work.conf中的值,替换。

import java.io.*;
import java.util.*;
import java.util.regex.*;
public class FormatP{
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("context.txt")));
        String context = null;
        if(br.ready()){
            context = br.readLine();
        }   
        br = new BufferedReader(new InputStreamReader(new FileInputStream("word.conf")));
        Map<String,String[]> params = new HashMap<String,String[]>();
        while(br.ready()){
            String paramLine = br.readLine();
            int indexEq = paramLine.indexOf("=");
            String key = paramLine.substring(0,indexEq);
            String[] values = paramLine.substring(indexEq+1).split(":");
            params.put(key,values);
        }   
        Pattern p = Pattern.compile("\\$\\((\\w+[\\.\\d+]*)\\)");
        Matcher m = p.matcher(context);
        while (m.find()) {
            String k = m.group(1);
            String kk[] = k.split("\\.");
            String key = kk[0];
            int index = kk.length>1?Integer.parseInt(kk[1])-1:0;
            context = context.replace("$("+k+")",params.get(key)[index]);
        }   
        System.out.println(context);
    }   
}



数字游戏与排序

一个文件里有10万个随机正整数,按照以下规则能组合出一份新的数据:
A. 如果当前数字能被3整除,那么它和文件中所有数字(包括自己)两两相加后生成一组数字替代自己的位置。
B. 如果不能被3整除,则它只需要乘以二,生成一个数字替代自己的位置。
例如:[3,7,6] 会组合出[6,10,9,14,9,13,12]
再如:[5,12,9,6,2]会组合出[10,17,24,21,18,14,14,21,18,15,11,11,18,15,12,8,4]

写一个程序找出并打印出新数据的最小的前200个数字。请考虑优化算法复杂度。

思路:第一步,数字游戏部分,首先对原来的数组进行预处理,每个数组元素变为一个链表,初始状态只有一个值。第二步,按要求,能被3整除的,就与数组中的数字进行两两相加,得到的结果放到链表当中;不能被3整除的,自身乘以2替换原值即可。  第二部分,简单的做法对数组进行快速排序,取前200个即可。

import java.util.*;
public class NumGame{
    public static void main(String[] args){
        int[] arr = {5,12,9,6,2};
        print(arr);
        int[] arr2 = game(arr);
        print(arr2);
        sort(arr2,0,arr2.length-1);
        print(arr2);
    }   

    public static int[] game(int[] arr){
        List<Integer>[] listArr = new List[arr.length];
        //初始化
        for(int i=0;i<arr.length;i++){
            listArr[i] = new ArrayList();
            listArr[i].add(arr[i]); 
        }   
        //计算
        int len = 0;
        for(int i=0;i<arr.length;i++){
            int v = arr[i];
            if(v%3==0){
                List<Integer> newList = new ArrayList<Integer>();
                for(int vv:arr){
                    newList.add(v+vv);
                }   
                listArr[i]=newList;
                len+=newList.size();
            }else{
                listArr[i].set(0,v*2);
                len++;
            }   
        }   
        int[] newArr = new int[len];
        int k=0;
        for(int i=0;i<listArr.length;i++){
            for(int x:listArr[i]){
	                    newArr[k++]=x;
            }
        }
        return newArr;
    }
    public static void print(int[] arr){
        for(int a:arr){
            System.out.printf("%s,",a);
        }
        System.out.println();
    }



    private static int[] sort(int[] arr, int low, int high) {
        while (low < high) {
            int pivot = partition(arr, low, high);
            sort(arr, low, pivot - 1);
            low = pivot + 1;
        }
        return arr;
    }

    /**
     * 分割,使得pivotkey左边的小于它,右边的大于它
     * @param arr
     * @param low
     * @param high
     * @return
     * /
    private static int partition(int[] arr, int low, int high) {
        //9值取中法得到枢轴值
        int mid = low + (high - low);
        if (arr[low] > arr[high]) {
            swap(arr, low, high);
	            }
        if (arr[mid] > arr[high]) {
            swap(arr, mid, high);
        }
        if (arr[low] < arr[mid]) {
            swap(arr, low, mid);
        }
        int pivotkey = arr[low];
        // 比较,使得pivotkey左边的小于它,右边的大于它
        while (low < high) {
            while (low < high && arr[high] >= pivotkey) {
                high--;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] <= pivotkey) {
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = pivotkey;
        return low;
    }

    private static void swap(int[] arr, int low, int high) {
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }


}


单词排序

已知字母序列【d, g, e, c, f, b, o, a】,请实现一个函数针对输入的一组字符串 input[] = {“bed”, “dog”, “dear”, “eye”},按照字母顺序排序并打印。

本例的输出顺序为:dear, dog, eye, bed。









还没有评论!
23.20.162.200