【每日阅读】2021年03月21日-华为2021年两道笔试题

数组扩散

思路：模拟扩散，暴力破解

/**
 * 题目：
 * 存在一个m*n的二维数组，其成员取值范围为0或1。其中值为1的成员具备扩散性，
 * 每经过1S，将上下左右值为0的成员同化为1。
 * 二维数组的成员初始值都为0，将第[i,j]和[k,l]两个位置上元素修改成1后，求矩阵的所有元素变为1需要多长时间。
 *
 * 输入描述：
 * 前两个数是矩阵m*n，中间两个数是第一个点的坐标，最后两个数是第二个点的坐标
 * 其中这两个点初始为1，其他点初始为0
 *
 * 输出描述:
 * 输出矩阵的所有元素变为1所需要秒数。
 */
public class MatrixDiffusion {
    public static void main(String[] args) {
        int[] input = new int[]{4, 4, 0, 0, 3, 3};

        int result = getTime(input);

        System.out.println(result);
    }

    /**
     * 思路：模拟扩散，暴力破解
     */
    private static int getTime(int[] input) {
        int xMax = input[0];
        int yMax = input[1];

        int xA = input[2];
        int yA = input[3];

        int xB = input[4];
        int yB = input[5];

        int[][] matrix = new int[xMax][yMax];

        // 初始化
        for (int x =0; x < xMax; x++) {
            for (int y = 0; y < yMax; y++) {
                matrix[x][y] = 0;

                // 把初始的两个点改成1
                if (x == xA && y == yA || x == xB && y == yB) {
                    matrix[x][y] = 1;
                }
            }
        }

        // 是否继续扩散
        boolean needContinue = true;
        // 扩散次数
        int count = 0;
        // 模拟扩散
        while (needContinue) {
            // 每次扩散前假设这次扩散后就结束了
            needContinue = false;
            // 本次操作是否真实的扩散了
            boolean curDid = false;

            // 先扩散成2（因为本次信扩散的点不能扩散）
            for (int x =0; x < xMax; x++) {
                for (int y = 0; y < yMax; y++) {
                    if (matrix[x][y] == 1) {
                        int topX = x - 1;
                        int topY = y;
                        if (topX >= 0 && topX < xMax && matrix[topX][topY] == 0) {
                            matrix[topX][topY] = 2;
                            curDid = true;
                        }

                        int leftX = x;
                        int leftY = y - 1;
                        if (leftY >= 0 && leftY < yMax && matrix[leftX][leftY] == 0) {
                            matrix[leftX][leftY] = 2;
                            curDid = true;
                        }

                        int belowX = x + 1;
                        int belowY = y;
                        if (belowX >= 0 && belowX < xMax && matrix[belowX][belowY] == 0) {
                            matrix[belowX][belowY] = 2;
                            curDid = true;
                        }

                        int rightX = x;
                        int rightY = y + 1;
                        if (rightY >= 0 && rightY < yMax && matrix[rightX][rightY] == 0) {
                            matrix[rightX][rightY] = 2;
                            curDid = true;
                        }
                    }
                }
            }

            // 本次扩散了就将扩散次数加一
            if (curDid) {
                count++;
            }

            // 善后：把2修改成1，让下一次正常扩散，并且判断需不需要进一步扩散
            for (int x =0; x < xMax; x++) {
                for (int y = 0; y < yMax; y++) {
                    if (matrix[x][y] == 2) {
                        matrix[x][y] = 1;
                    }

                    // 还有0的就继续扩散
                    if (matrix[x][y] == 0) {
                        needContinue = true;
                    }

                    // 输出扩散的中间结果
                    System.out.print(matrix[x][y] + " ");
                }
                // 输出扩散的中间结果
                System.out.println();
            }

            // 输出扩散的中间结果
            System.out.println("\n");
        }

        return count;
    }
}

身高排序

import java.util.ArrayList;
import java.util.List;

/**
 * 题目：
 * 小明今年升学到小学一年级，来到新班级后发现其他小朋友们身高参差不齐，
 * 然后就想基于各小朋友和自己的身高差对他们进行排序，请帮他实现排序。
 *
 * 输入：
 * 第一行为正整数H和N，0<H<200，为小明的身高，O<N<50,为新班级其他小朋友个数。
 * 第二行为N个正整数H1-HN，分别是其他小朋友的身高，取值范围O<Hi<200(1<=i<=N)，且N个正整数各不相同。
 *
 * 输出描述:
 * 输出排序结果，各正整数以空格分割，和小明身高差绝对值最小的小朋友排在前面，
 * 和小明身高差绝对值最大的小朋友排在最后，如果两个小朋友和小明身高差一样，则个子较小的小朋友排在前面。
 */
public class HeightSort {
    public static void main(String[] args) {
        String firstLine = "100 10";
        String secondLine = "95 96 97 98 99 101 102 103 104 105";

        String[] studentHeightArr = secondLine.split(" ");
        List<HeightDiff> heightDiffList = new ArrayList<>();
        int xiaoMingHeight = Integer.parseInt(firstLine.split(" ")[0]);

        for (String height : studentHeightArr) {
            heightDiffList.add(new HeightDiff(Integer.parseInt(height), xiaoMingHeight));
        }

        heightDiffList.sort((o1, o2) -> {
            if (o1.diff < o2.diff) {
                return -1;
            } else if (o1.diff > o2.diff) {
                return 1;
            } else if (o1.height < o2.height) {
                return -1;
            } else if (o1.height > o2.height) {
                return 1;
            }

            return 0;
        });

        System.out.println(heightDiffList);
    }

    static class HeightDiff {
        // 同学身高
        int height;

        // 和小明身高差
        int diff;

        /**
         * @param height 同学身高
         * @param xiaoMingHeight 小明身高
         */
        public HeightDiff(int height, int xiaoMingHeight) {
            this.height = height;
            this.diff = Math.abs(xiaoMingHeight - height);
        }

        @Override
        public String toString() {
            return height + "";
        }
    }
}