阿里笔试325
我没参赛，看你们的题目，不知道写的代码能不能AC
第一题用dp[n][3] 表示第i列选择第j个值能得到的最小绝对值差的和。
public static void minN(int[][] nums){
int c = nums[0].length;
int[][] dp = new int[c][3];
// 第i列
for (int i = 1; i < c; i++) {
//本次选择第j个数，第j行
for (int j = 0; j < 3; j++) {
//前一次选择第k个数的最小值
for (int k = 0; k < 3; k++) {
//没填充大值，用第一个数填充一下
if (k==0){
dp[i][j] = Math.abs(nums[j][i]-nums[k][i-1])+dp[i-1][k];
}else {
dp[i][j] = Math.min(Math.abs(nums[j][i]-nums[k][i-1])+dp[i-1][k], dp[i][j]);
}
}
}
}
System.out.println(Math.min(dp[c-1][0], Math.min(dp[c-1][1],dp[c-1][2])));
} 第二题就是循环按行列补充，直到没有新的值出现，没有检查该位置确实为0的情况，其实只需要看对应行列是否修改过就行。
public static void solve(int[][] nums){
int r = nums.length, c = nums[0].length;
boolean[] flag = new boolean[r+c];
while (rowSolve(nums,flag)||colunm(nums,flag)){
}
}
public static boolean rowSolve(int[][] nums, boolean[]flag){
int r = nums.length, c = nums[0].length;
boolean f = false;
for (int i = 0; i < r; i++) {
if (!flag[i]){
int[] pre = new int[2];
for (int j = 0; j < c; j++) {
if (nums[i][j]!=0&&pre[1]!=0){
int dif = (nums[i][j] - pre[1])/(j - pre[0]);
for (int k = j+1; k < c; k++) {
nums[i][k] = nums[i][k-1] + dif;
}
for (int k = j-1; k >= 0; k--) {
nums[i][k] = nums[i][k+1] - dif;
}
flag[i] = true;
f = true;
break;
}else if (nums[i][j]!=0){
pre[0] = j;
pre[1] = nums[i][j];
}
}
}
}
return f;
}
public static boolean colunm(int[][] nums, boolean[] flag){
int r = nums.length, c = nums[0].length;
boolean f = false;
for (int j = 0; j < c; j++) {
if (!flag[r+j]){
int[]pre = new int[2];
for (int i = 0; i < r; i++) {
if (nums[i][j]!=0&&pre[1]!=0){
int dif = (nums[i][j] - pre[1])/(i - pre[0]);
for (int k = i+1; k < r; k++) {
nums[k][j] = nums[k-1][j]+dif;
}
for (int k = i-1; k >= 0; k--) {
nums[k][j] = nums[k+1][j]-dif;
}
f = true;
flag[r+j]=true;
break;
}else if (nums[i][j]!=0){
pre[0] = i;
pre[1] = nums[i][j];
}
}
}
}
return f;
}
