阿里巴巴3.25笔试

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] num = new int[3][n];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < n; j++) {
                num[i][j] = sc.nextInt();
            }
        }
        long[][] dpNum = new long[n][3];
        for (int i = 1; i < n; i++) {
            dpNum[i][0] = Math.min(Math.abs(num[0][i] - num[0][i - 1]) + dpNum[i - 1][0], Math.min(Math.abs(num[0][i] - num[1][i - 1]) + dpNum[i - 1][1], Math.abs(num[0][i] - num[2][i - 1]) + dpNum[i - 1][2]));
            dpNum[i][1] = Math.min(Math.abs(num[1][i] - num[0][i - 1]) + dpNum[i - 1][0], Math.min(Math.abs(num[1][i] - num[1][i - 1]) + dpNum[i - 1][1], Math.abs(num[1][i] - num[2][i - 1]) + dpNum[i - 1][2]));
            dpNum[i][2] = Math.min(Math.abs(num[2][i] - num[0][i - 1]) + dpNum[i - 1][0], Math.min(Math.abs(num[2][i] - num[1][i - 1]) + dpNum[i - 1][1], Math.abs(num[2][i] - num[2][i - 1]) + dpNum[i - 1][2]));
        }
        System.out.println(Math.min(dpNum[n - 1][0], Math.min(dpNum[n - 1][1],dpNum[n - 1][1])));
    }

1. 遍历行，有两个不为0的那么这一行可以改，但是要排除全都不是0的情况
2. 然后遍历列，方法同上
3. 利用是否修改了行/列的标志chan来记录这一行/这一列是否修改了
4. 如果都未修改，推出循环。
5. 先做的第二题，想尝试优化，但是看时间只有20多分钟了，直接去做第一题了。。。。太菜了。。。
6. 优化方案：将已经修改过的行/列记录到map中，时间复杂度可优化为2mn级别，应该可以ac

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        int[][] nums = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                nums[i][j] = sc.nextInt();
            }
        }
        int[][] ques = new int[q][2];
        for (int i = 0; i < q; i++) {
            ques[i][0] = sc.nextInt();
            ques[i][1] = sc.nextInt();
        }
        sc.close();
        boolean chan = true;
        while (chan) {
            chan = false;
            boolean chaned = false;
            boolean chaned2 = false;
            //遍历行
            for (int i = 0; i < n; i++) {
                int left = -1, right = -1;
                for (int j = 0; j < m; j++) {
                    if (nums[i][j] != 0) {
                        if (left == -1) left = j;
                        else if (right == -1) right = j;
                    }else chaned = true;
                }
                if (left != -1 && right != -1 && chaned) {
                    int cut = (nums[i][right] - nums[i][left]) / (right - left);
                    for (int k = 0; k < m; k++) {
                        if(!chan && nums[i][k] == 0) chan = true;
                        nums[i][k] = nums[i][left] + cut * (k - left);
                    }
                }
            }
            //遍历列
            for (int j = 0; j < m; j++) {
                int up = -1, down = -1;
                for (int i = 0; i < n; i++) {
                    if(nums[i][j] != 0){
                        if (up == -1) up = i;
                        else if (down == -1) down = i;
                        else continue;
                    }else chaned2 = true;
                }
                if(up != -1 && down != -1 && chaned2){
                    int cut = (nums[down][j] - nums[up][j]) / (down - up);
                    for (int k = 0; k < n; k++) {
                        if(nums[k][j] == 0) chan = true;
                        nums[k][j] = nums[k][up] + cut * (k - up);
                    }
                }
            }
        }
        for (int i = 0; i < q; i++) {
            if(nums[ques[i][0] - 1][ques[i][1] - 1] != 0){
                System.out.println(nums[ques[i][0] - 1][ques[i][1] - 1]);
            }else System.out.println("Unknown");
        }
    }
}