华为笔试 08.31 期待大佬解答

第一题 （65%）

索引替换，感觉挺简单的题目，不知哪里出了问题。

刚刚想到，句子是不是可能出现下面这种情况（哭），我这里没有考虑到这种情况。

A "bb" ccc
bb左侧有引号，右侧有引号。两个引号旁边均有空格，是符合题意的，但做的时候没想到这个。

    public static void main1(String[] args) {
        Scanner s = new Scanner(System.in);
        String line = s.nextLine();
        String tmp = s.nextLine();
        String values[] = tmp.split(" ");
        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i < values.length; i++) {
            map.put(values[i].toLowerCase(), i);
        }
        String strValues[] = line.split(" ");
        boolean jump = false;
        for(int i = 0; i < strValues.length; i++) {
            String strTmp = strValues[i];
            if(strTmp.equals("\"")) {
                jump = !jump;
            }else{
                if(jump) continue;
                int len = strTmp.length();
                if(!Character.isAlphabetic(strTmp.charAt(len-1))) {
                    if(strTmp.length() == 1) continue;
                    String real = strTmp.substring(0, len-1).toLowerCase();
                    if(map.containsKey(real)) {
                        strValues[i] = (new StringBuilder().append(map.get(real)).append(strTmp.charAt(len-1))).toString();
                    }
                }else{
                    String real = strTmp.toLowerCase();
                    if(map.containsKey(real)) {
                        strValues[i] = String.valueOf(map.get(real));
                    }
                }
            }
        }
        for(int i = 0; i < strValues.length-1; i++) {
            System.out.print(strValues[i] + " ");
        }
        System.out.println(strValues[strValues.length-1]);
    }

第二题 （60%）

暴力深搜，期待大佬解答真正的方法！！！

第二题据说，分层图+最短路算法。

finebuaa 大佬AC代码

    static int arr[][];
    static int ret;
    static int n, m;
    public static void main2(String[] args) {
        Scanner s = new Scanner(System.in);
        n = s.nextInt();
        m = s.nextInt();
        arr = new int[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                arr[i][j] = s.nextInt();
            }
        }
        ret = 626;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(arr[i][j] == 2) {
                    dfs(i, j, new boolean[n][m], 0);
                }
            }
        }
        System.out.println(ret);
    }
    static int[][] direction = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};

    static void dfs(int x, int y, boolean[][] visited, int cnt) {
        if(visited[x][y] || cnt >= ret) return ;
        if(arr[x][y] == 3) {
            ret = Math.min(ret, cnt);
            return;
        }
        visited[x][y] = true;
        int nextCnt = cnt+1;
        int tmp[] = new int[4];
        if(arr[x][y] == 6) {
            for(int i = 0; i < 4; i++) {
                int tx = direction[i][0] + x;
                int ty = direction[i][1] + y;
                if(tx >= 0 && ty >= 0 && tx < n && ty < m){
                    tmp[i] = arr[tx][ty];
                    arr[tx][ty] = 0;
                }
            }
        }else if(arr[x][y] == 4) {
            nextCnt += 2;
        }
        for(int i = 0; i < 4; i++) {
            int tx = direction[i][0] + x;
            int ty = direction[i][1] + y;
            if(tx >= 0 && ty >= 0 && tx < n && ty < m && arr[tx][ty] != 1) {
                dfs(tx, ty, visited, nextCnt);
            }
        }
        if(arr[x][y] == 6) {
            for(int i = 0; i < 4; i++) {
                int tx = direction[i][0] + x;
                int ty = direction[i][1] + y;
                if(tx >= 0 && ty >= 0 && tx < n && ty < m){
                    arr[tx][ty] = tmp[i];
                }
            }
        }
        visited[x][y] = false;
    }

第三题（72%）

不知哪里的case出错了，想不到。

我的思路是，status 这个Map用来存各个加油站各个剩余油状态对应的最小时间。

有个大佬给了代码 kevindebury 大佬AC代码

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int d = s.nextInt() / 100;
        int n = s.nextInt();
        double arr[][] = new double[n+1][2];
        for(int i = 0; i < n; i++){
            arr[i][0] = s.nextDouble() / 100;
            arr[i][1] = s.nextDouble();
        }
        arr[n][0] = d;

        Map<Double, Double> status = new HashMap<>();
        status.put(10.0, 0.0);

        double p = 0; // position
        for(int i = 0; i <= n; i++) {
            double sub = arr[i][0] - p;
            double tmp10 = Double.MAX_VALUE;
            if(sub == 0) tmp10 = status.get(10.0);

            Map<Double, Double> newState = new HashMap<>();
            for(double time : status.keySet()) {
                if(time >= sub) {
                    newState.put(time-sub, status.get(time) + sub);
                    tmp10 = Math.min(tmp10, status.get(time));
                }
            }
            if(tmp10 != Double.MAX_VALUE){
                newState.put(10.0, tmp10 + arr[i][1] + 1.0 + sub);
            }else{
                System.out.println(-1);
                return;
            }
            status = newState;
//            System.out.println(status);
            p = arr[i][0];
        }
        double ret = Double.MAX_VALUE;
        for(double v: status.values()) {
            ret = Math.min(v, ret);
        }
        System.out.println((int)ret);
    }