首页 > 笔经面经 > 阿里巴巴3.25笔试

阿里巴巴3.25笔试

头像
陈先生1996 #阿里笔试第三场0325#
编辑于 2020-03-26 21:29:29 APP内打开
赞 1 | 收藏 3 | 回复1 | 浏览1104
第一题

看明白了较为简单,暴力可以做,但是知道肯定要超时,所以不敢做,然后去做了第二题,做的同时在想第一题,然后想到了用了dp,dp就三行,挺简单的。
不过这个也只过了75%。。。。求大佬们双AC的解法
对了这道题要注意的地方是,dp数组要用long,用int的话通过率更低
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])));
    }
第二题

也是暴力,30%,思路大致是:
  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");
        }
    }
}


1条回帖

回帖
加载中...
话题 回帖

推荐话题

相关热帖

笔经面经近期热帖

近期精华帖

热门推荐