携程笔试

第一题
你需要编写一个程序来模拟目录的操作，一开始，你在根目录N，一共有两种命令：
cd s:s为一个目录名，表示从当前工作目录的路径进入名为s的目录。特别地,"cd .."表示返回上一级目录,若当前已为根目录,则无视该次操作。
pwd:表示查看当前文件路径
输入
第一个行是一个整数n,表示共会有n个操作。
接下来每行是一条命令，命令的种类为问题描述中的两种之一。
cd s直接有空格
输出
输入pwd 命令，查看当前路径

7
cd a
cd b
pwd
cd ..
pwd
cd ..
pwd

输出
\a\b
\a
\

思路:用一个LinkedList接受命令。

package XieCheng;

import java.util.LinkedList;
import java.util.Scanner;

public class one {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
            int k = scanner.nextInt();
            scanner.nextLine();
            LinkedList<String> res = new LinkedList<>();
            for(int i = 0;i<k;i++) {
                String[] opts = scanner.nextLine().split(" ");
                if (opts.length == 1) {
                    for (String s : res) {
                        System.out.print("\\" + s);
                    }
                    if (res.size() == 0) {
                        System.out.print("\\");
                    }
                    System.out.println();
                } else {
                    if (opts[1].equals("..")) {
                        if (res.size() > 0)
                            res.removeLast();
                    } else {
                        res.add(opts[1]);
                    }
                }
            }
    }
}

第二题
有个长度为n的字列A，序列中的第1个数为A问(1<=i< =n). 现在你可以将序列分成至多连续K段。对于每段， 我们定义这一段的不平衡度为段内的最大值减去段内的最小值，显然，对于长度为1的段，其不平衡度为0。对于种合法的分段方式，(即每段连续且不超过k段) ，我们定义这种分段方式的不平衡度为每段的不平衡度的最大值。现在你需要找到不平衡度最小的分段方式，输出这种分段方式的不平衡度即可。

输入：
第一行两个空格隔开的整数n，k,分别表示序列的长度和最多可分成的段；
第二行是n个用空格隔开的整数，第i个数表示A[i]的值

输出
一行一个整数，表示最小的不平衡度

5 3
3 5 5 2 5
输出
2

暴力，过了一小部分

package XieCheng;

import javax.security.sasl.SaslServer;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class two {
    static List<List<Integer>> res = new ArrayList<>();
    static LinkedList<Integer> track = new LinkedList<>();

    public static void main(String[] args) {
        Scanner sca = new Scanner(System.in);
        int len = sca.nextInt();
        int k = sca.nextInt();
        int[] num = new int[len];
        for(int i = 0;i<len;i++){
            num[i] = sca.nextInt();
        }
        backtrack(len-1,k-1,1);
        //System.out.println(res);
        kk(num,k);
    }

    private static void kk(int[] num, int k) {
        int min = Integer.MAX_VALUE;
        for(List<Integer> list : res){
            int max = Integer.MIN_VALUE;
            list.add(num.length);
            for(int i = 0;i<list.size();i++){
                int temp = 0;
                if(i == 0){
                    temp = cal(num,0,list.get(i));
                }else{
                    temp = cal(num,list.get(i-1),list.get(i));
                }
                max = Math.max(max,temp);
            }
            min = Math.min(max,min);
        }
        System.out.println(min);
    }

    private static int cal(int[] num, int i, int j) {
        if(j -i == 1){
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        while (i<j){
            max = Math.max(num[i],max);
            min = Math.min(num[i],min);
            i++;
        }
        return max-min;
    }

    private static void backtrack(int len, int k, int start) {
        if(track.size() == k){
            res.add(new ArrayList<>(track));
            return;
        }
        for(int i = start;i<=len;i++){
            track.add(i);
            backtrack(len,k,i+1);
            track.removeLast();
        }
    }
}

第三题
现在给你一个长度为01序列，可以通过消除连续的1的序列来获取一点的分数，题目给出规则，我们需要正确求解出对于的答案。

输入
11 2
11111101111
3 10
4 15

输出
35

package XieCheng;

import java.util.Scanner;

public class three {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()){
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            scanner.nextLine();
            String line = scanner.nextLine();
            String[] lines = line.split("0");
            int[] weight = new int[k];
            int[] value = new int[k];
            for(int i = 0;i<k;i++){
                String temp = scanner.nextLine();
                String[] split = temp.split(" ");
                weight[i] = Integer.parseInt(split[0]);
                value[i] = Integer.parseInt(split[1]);
            }
            //dp[i] : i 最大价值。
            int res = 0;
            for(int i = 0;i<lines.length;i++){
                int nn = lines[i].length();
                res += getMaxs(nn,weight,value);
            }
            System.out.println(res);
        }
    }

    private static int getMaxs(int nn, int[] weight, int[] value) {
        int[] dp = new int[nn+1];
        int flag = 0;
        for(int i = 1;i<=nn;i++){
            for(int j = 0;j<weight.length;j++){
                if(i - weight[j] < 0){
                    continue;
                }else{
                    dp[i] = Math.max(dp[i-weight[j]] + value[j],dp[i]);
                }
            }

        }
        return dp[nn];
    }
}