阿里巴巴3.25笔试
第一题
看明白了较为简单,暴力可以做,但是知道肯定要超时,所以不敢做,然后去做了第二题,做的同时在想第一题,然后想到了用了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%,思路大致是:
- 遍历行,有两个不为0的那么这一行可以改,但是要排除全都不是0的情况
- 然后遍历列,方法同上
- 利用是否修改了行/列的标志chan来记录这一行/这一列是否修改了
- 如果都未修改,推出循环。
- 先做的第二题,想尝试优化,但是看时间只有20多分钟了,直接去做第一题了。。。。太菜了。。。
- 优化方案:将已经修改过的行/列记录到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"); } } }