华为2022.9.21笔试题目

package com.example.huawei._9_21;

public class _2_anser {
    public static void main(String[] args) {
        char[][] map = new char[9][];
        map[0] = new char[]{'.','.','.','.','.','.','.','.','.'};
        map[1] = new char[]{'.','.','.','.','.','X','X','X','.'};
        map[2] = new char[]{'.','.','.','.','.','X','.','X','.'};
        map[3] = new char[]{'.','.','.','.','.','X','.','X','.'};
        map[4] = new char[]{'.','.','.','.','.','X','.','X','S'};
        map[5] = new char[]{'X','X','X','X','X','X','.','X','X'};
        map[6] = new char[]{'.','.','.','.','.','.','.','.','.'};
        map[7] = new char[]{'.','.','.','.','.','.','.','.','.'};
        map[8] = new char[]{'.','.','.','.','.','.','.','.','.'};
        System.out.println(getCount(map));


        char[][] map2 = new char[3][];
        map2[0] = new char[]{'S','.'};
        map2[1] = new char[]{'.','.'};
        map2[2] = new char[]{'.','.'};
        System.out.println(getCount(map2));
    }

    public static int getCount(char[][] map){
        int m = map.length;
        int n = map[0].length;

        int[][] timeBin = new int[m][n];
        int[][] timeMa = new int[m][n];
        for(int i = 0 ;i < m ;i ++){
            for(int j = 0 ; j < n;j ++){
                timeBin[i][j] = Integer.MAX_VALUE;
                timeMa[i][j] = Integer.MAX_VALUE;
            }
        }

        dfsBin(map,timeBin,timeMa,0,0,0);
        if(timeBin[m - 1][n - 1] == Integer.MAX_VALUE && timeMa[m - 1][n - 1] == Integer.MAX_VALUE){
            return -1;
        }
        return  Math.min(timeMa[m- 1][n-1],timeBin[m- 1][n-1]);

    }

    public static void dfsBin(char[][] map,int[][] timeBin,int[][] timeMa,int x, int y,int cost){
        if( x < 0 || x >= map[0].length || y < 0 || y >= map.length ){
            return;
        }
        if( map[y][x] == 'X'||timeBin[y][x] <= cost){
            return;
        }
        timeBin[y][x] = cost;
        cost++;

        if(map[y][x] == 'S'){
            dfsMa(map,timeBin,timeMa,x,y,cost);
        }
        dfsBin(map,timeBin,timeMa,x + 1,y,cost);
        dfsBin(map,timeBin,timeMa,x - 1,y,cost);
        dfsBin(map,timeBin,timeMa,x,y - 1,cost);
        dfsBin(map,timeBin,timeMa,x,y + 1,cost);

    }

    public static void dfsMa(char[][] map,int[][] timeBin,int[][] timeMa,int x, int y,int cost){
        if( x < 0 || x >= map[0].length || y < 0 || y >= map.length ){
            return;
        }
        if( map[y][x] == 'X'||timeMa[y][x] <= cost){
            return;
        }
        timeMa[y][x] = cost;
        cost++;
        if(map[y][x] == 'S'){
            dfsBin(map,timeBin,timeMa,x,y,cost);
        }

        dfsMa(map,timeBin,timeMa, x + 1,y - 2,cost);
        dfsMa(map,timeBin,timeMa, x - 1,y - 2,cost);


        dfsMa(map,timeBin,timeMa, x - 1,y + 2,cost);
        dfsMa(map,timeBin,timeMa, x + 1,y + 2,cost);

        dfsMa(map,timeBin,timeMa, x + 2,y + 1,cost);
        dfsMa(map,timeBin,timeMa, x + 2,y - 1,cost);

        dfsMa(map,timeBin,timeMa, x - 2,y + 1,cost);
        dfsMa(map,timeBin,timeMa, x - 2,y - 1,cost);
    }
}

package com.example.huawei._9_21;


public class _3_anser {
    public static void main(String[] args) {
        int n = 4;
        int[] pos = new int[]{2,3,4,5};
        int[] r= new int[]{1,1,1,2};
        int[] val = new int[]{50,10,40,70};
        System.out.println(getMaxValue(n,pos,val,r));

        n = 5;
        pos = new int[]{2,3,6,5,7};
        r= new int[]{1,1,3,1,1};
        val = new int[]{20,20,100,70,60};
        System.out.println(getMaxValue(n,pos,val,r));
    }

    public static int getMaxValue(int n,int[] pos,int[] val,int[] r){
        int res = 0;
        int[][] lance = new int[n][3];

        for(int i = 0; i < n;i++){
            lance[i][0] = pos[i] - r[i];
            lance[i][1] = pos[i] + r[i];
            lance[i][2] = val[i];
        }

                Arrays.sort(lance,(a,b)-> a[1] - b[1]);//注意数组是按照右边界进行排序的，只有保证右边界有序，dp方程才成立

        int[][] dp = new int[n][2];
        dp[0][0] = lance[0][2];//代表种树带来的价值
        dp[0][1] = 0;//代表不种树的价值

        for(int i = 1; i< n;i++){
            int tempValue = 0;
            for(int j = 0;j < i;j++){
                if(lance[j][1] <= lance[i][0])
                    tempValue = Math.max(tempValue,dp[j][0]);
            }
            dp[i][0] = tempValue + lance[i][2]; //加上自己的价值，表示 种了这棵树能达到的最大价值
            dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0]);//表示不种这棵树的价值

            res = Math.max(Math.max(res,dp[i][0]),dp[i][1]);
        }
        return res;
    }
}