网易4/22Web后端

第一题

public int putGems (int[] price, int k) {
        // write code here
        return dfs_max(price, k, 0, price.length - 1) - dfs_min(price, k, 0, price.length - 1);
    }

    public int dfs_max(int[] price, int k, int begin, int end){
        int res = 0;
        if(k == 1){
            return price[begin] + price[end];
        }
        //putGems(new int[]{2, 3, 5, 4}, 2)
        for(int i = begin; i <= end; i++){
            if(end - i + 1 >= k){
                res = Math.max(dfs_max(price, 1, begin, i) + dfs_max(price, k - 1, i + 1, end), res);
            }
        }
        return res;
    }

    public int dfs_min(int[] price, int k, int begin, int end){
        int res = Integer.MAX_VALUE;
        if(k == 1){
            return price[begin] + price[end];
        }
        for(int i = begin; i <= end; i++){
            if(end - i + 1 >= k){
                res = Math.min(dfs_min(price, 1, begin, i) + dfs_min(price, k - 1, i + 1, end), res);
            }
        }
        return res;
    }

第二题

public int getEstTime (int[][] map, int a_x, int a_y, int b_x, int b_y) {
        // write code here

        m = map.length;
        n = map[0].length;

        dfs(map, a_x, a_y, b_x, b_y, 0);

        if(res == Integer.MAX_VALUE){
            return -1;
        }
        if(res % 2 == 0){
            return res / 2;
        }
        return res / 2 + 1;
    }

    public void dfs(int[][] map, int a_x, int a_y, int b_x, int b_y, int step){

        if(a_x < 0 || a_x == m || a_y < 0 || a_y == n || map[a_x][a_y] == 0){
            return;
        }
        if(a_x == b_x && a_y == b_y && res > step){
            res = step;
            return;
        }
        map[a_x][a_y] = 0;
        dfs(map, a_x + 1, a_y, b_x, b_y, step + 1);
        dfs(map, a_x, a_y + 1, b_x, b_y, step + 1);
        dfs(map, a_x - 1, a_y, b_x, b_y, step + 1);
        dfs(map, a_x, a_y - 1, b_x, b_y, step + 1);
        map[a_x][a_y] = 1;
    }