字节笔试第二四题解法

第二题A了80大佬们看下哪有问题。
我的思路是，对于每一次补水，求出其能达到的最远的距离，找出能达到的最远补水站。

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int D = scanner.nextInt();
        int W = scanner.nextInt();
        List<Integer> list = new ArrayList<Integer>();
        while (scanner.hasNext()) {
            list.add(scanner.nextInt());
        }

        // 如果初始水量就足够，无需补给
        if (W >= D) {
            System.out.println(0);
            return; // 这里加个return
        }
        if (W == 0) {
            System.out.println(-1);
            return;
        }

        int length = list.size();
        int N = length / 2;
        int[][] supplies = new int[N][2];
        for (int i = 0; i < N; ++i) {
            supplies[i][0] = list.get(i);
            supplies[i][1] = list.get(i + N);
        }

        // 按照补给站的远近排序
        Arrays.sort(supplies, (int[] arr1, int[] arr2)->{
            return arr1[0] - arr2[0];
        });

        int left = 0;
        int right = 0;
        int farest = W; // 目前能达到的最远距离
        int result = 0;
        // left（包括）和right（不包括）之间是初始水量能达到的所有补给站
        while (farest < D) {
            // 找到能达到的最远补给站
            left = right;
            while (right < N && supplies[right][0] <= farest) {
                ++right;
            }
            ++result;
            // 遍历left和right之间所有的水站，查看此次补给能补到的最大水量
            int temp = 0;
            for (int i = left; i < right; ++i) {
                temp = temp >= supplies[i][1] ? temp : supplies[i][1]; 
            }
            // 补不到任何水，说明到不了终点
            if (temp == 0) {
                System.out.println(-1);
                return;
            }
            farest += temp;
        }
        System.out.println(result);
    }

}

第四题还没编完就结束了，接着自己写完的，所以不知道能A多少，给的例子是能过的，大佬们见笑了。
思路是：对于每一次操作的两个点P1、P2，求出其纵横两个方向能达到的所有点。然后，遍历P1、P2所在的两列之间能否联通，再遍历P1、P2所在两行之间能否联通。如果能联通，就将P1、P2消去。

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        char[][] matrix = new char[n][m];
        for (int i = 0; i < n; ++i) {
            matrix[i] = scanner.next().toCharArray(); 
        }
        int q = scanner.nextInt();
        int[][] operation = new int[q][4];
        for (int i = 0; i < q; ++i) {
            operation[i][0] = scanner.nextInt() - 1; // 因为输入的坐标是从1开始的
            operation[i][1] = scanner.nextInt() - 1;
            operation[i][2] = scanner.nextInt() - 1;
            operation[i][3] = scanner.nextInt() - 1;
        }

        // 遍历每个操作
        for (int i = 0; i < q; ++i) {
            // 对于AB两个点，分别求出其纵横方向上能达到的所有点
            boolean[] rowA = new boolean[m];
            boolean[] colA = new boolean[n];
            boolean[] rowB = new boolean[m];
            boolean[] colB = new boolean[n];
            int rA = operation[i][0];
            int cA = operation[i][1];
            int rB = operation[i][2];
            int cB = operation[i][3];
            if (matrix[rA][cA] == '.' || matrix[rB][cB] == '.' || matrix[rA][cA] != matrix[rB][cB] ) {
                System.out.println("NO");
                continue;
            }

            // 求出A点纵横能达到的所有点
            // A的列
            colA[rA] = true;
            for (int up = rA - 1; up >= 0; --up) {
                if (matrix[up][cA] == '.') {
                    colA[up] = true; 
                } else {
                    break;
                }
            }
            for (int down = rA + 1; down < n; ++down) {
                if (matrix[down][cA] == '.') {
                    colA[down] = true; 
                } else {
                    break;
                }
            }
            // A的行
            rowA[cA] = true;
            for (int left = cA - 1; left >= 0; --left) {
                if (matrix[rA][left] == '.') {
                    rowA[left] = true; 
                } else {
                    break;
                }
            }
            for (int right = cA + 1; right < n; ++right) {
                if (matrix[rA][right] == '.') {
                    rowA[right] = true; 
                } else {
                    break;
                }
            }

            // 求出B点纵横能达到的所有点
            // B的列
            colB[rB] = true;
            for (int up = rB - 1; up >= 0; --up) {
                if (matrix[up][cB] == '.') {
                    colB[up] = true; 
                } else {
                    break;
                }
            }
            for (int down = rB + 1; down < n; ++down) {
                if (matrix[down][cB] == '.') {
                    colB[down] = true; 
                } else {
                    break;
                }
            }
            // B的行
            rowB[cB] = true;
            for (int left = cB - 1; left >= 0; --left) {
                if (matrix[rB][left] == '.') {
                    rowB[left] = true; 
                } else {
                    break;
                }
            }
            for (int right = cB + 1; right < n; ++right) {
                if (matrix[rB][right] == '.') {
                    rowB[right] = true; 
                } else {
                    break;
                }
            }

            // 判断A的列和B的列能否联通
            boolean flag = false;
            for (int j = 0; j < n && !flag; ++j) {
                if (colA[j] && colB[j]) {
                    int from = Math.min(cA, cB) + 1;
                    int to = Math.max(cA, cB);
                    boolean localFlag = true;
                    while (from < to) {
                        if (matrix[j][from] != '.') {
                            localFlag = false;
                            break;
                        }
                        ++from;
                    }
                    flag = localFlag;
                }
            }

            if (flag) {
                System.out.println("YES");
                matrix[rA][cA] = '.';
                matrix[rB][cB] = '.';
                continue;
            } else {
                // 判断A的行和B的行能否联通
                for (int j = 0; j < m && !flag; ++j) {
                    if (rowA[j] && rowB[j]) {
                        int from = Math.min(rA, rB) + 1;
                        int to = Math.max(rA, rB);
                        boolean localFlag = true;
                        while (from < to) {
                            if (matrix[from][j] != '.') {
                                localFlag = false;
                                break;
                            }
                            ++from;
                        }
                        flag = localFlag;
                    }
                }
                if (flag) {
                    System.out.println("YES");
                    matrix[rA][cA] = '.';
                    matrix[rB][cB] = '.';
                    continue;
                }
            }

            System.out.println("NO");
        }
    }
}