题目1
给定一个数组n,然后给三个长度为n的数组,每1列选1个数，求所有相邻列的差的绝对值的和最小值。
输入案例
5 9 5 4 4
4 7 4 10 3
2 10 9 2 3
这里选择5 7 5 4 4.所以输出等于 |7-5|+|5-7|+|4-5|+|4-4|=5所以输出就是5。
这个问题可以看成是在矩阵中寻找一个路径,要求整个路径的前向之差绝对值最小。可以想如何把问题规模缩小,显然下一个数的选择,可以有三条路径,如果从第一行过来,那么就需要用到选了第一行的路径的和的最小值,同样也需要求出用到第二行和第三行过来的路径的最小值。
<mark>可见这是一个动态规划问题。我们定义一个动态规划数组,dpij表示选择了矩阵中(i,j)位置的元素,最小的路径绝对值之和。显然最终的结果就是最后一列三个路径最小值。</mark>
import java.util.Arrays;
import java.util.Scanner;
/*
dp法：对于每一列上的3行，分别计算这从累积到前一列的3行的分数
+(i-1)->(i)的转移分数并取最小
时间复杂度：O(n)
空间复杂度：O(1)
*/
public class Test19 {
public static void main(String[] args) {
Scanner sn = new Scanner(System.in);
// int n = sn.nextInt();
// int[][] arr = new int[3][n];
// for(int i=0;i<3;++i){
// for(int j=0;j<n;++j){
// arr[i][j] = sn.nextInt();
// }
// }
int n = 5;
int[][] arr ={
{
5,9,5,4,4},{
4,7,4,10,3},{
2,10,9,2,3}};
long[][]dp = new long[n][3];
for(long[] v:dp){
Arrays.fill(v, Long.MAX_VALUE);
}
dp[0][0] = 0;
dp[0][1] = 0;
dp[0][2] = 0;
for(int i=1;i<n;++i) {
for(int j=0;j<3;++j) {
dp[i][j] = Math.min(dp[i][j],dp[i-1][0]+
Math.abs(arr[0][i-1]-arr[j][i]));
dp[i][j] = Math.min(dp[i][j],dp[i-1][1]+
Math.abs(arr[1][i-1]-arr[j][i]));
dp[i][j] = Math.min(dp[i][j],dp[i-1][2]+
Math.abs(arr[2][i-1]-arr[j][i]));
}
}
long ans = Long.MAX_VALUE;
for(int i=0;i<3;++i) {
ans = Math.min(ans, dp[n-1][i]);
}
System.out.println(ans);
}
}
题目2
给出一个二维矩阵,这个矩阵的每一行和每一列都是一个独立的等差数列,其中一些数据缺失了,现在需要推理隐藏但是可以被唯一确定的数字,然后对输入的查询进行回答。
输入描述:
第一行,n,m,q分别表示矩阵的行数,列数和查询的条数。
接下来的n行,每行m个数表示这个矩阵,0表示缺失数据。-109≤Aij≤109
接下来q行,每行两个数字表示对矩阵中第行第列的数字进行查询。
输出描述:
如果可以确定该位置的数字,则输出数字,如果不能确定则输出 UNKNOWN
输入示例：
2 3 6
1 0 3
0 0 0
1 1
1 2
1 3
2 1
2 2
2 3
输出示例：
1
2
3
Unknown
Unknown
Unknown
<mark>这道题就是可以求解的方法是如果一个矩阵中可以确定两行或者两列的话那么可以完全确定这个矩阵。如何确认这两行或者两列呢，如果有两个以上的数字那么可以求出这行的公差。则整行或者列可以确认。</mark>
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Test21 {
public static void main(String[] args) {
Scanner sn = new Scanner(System.in);
//int n = sn.nextInt();
//int m = sn.nextInt();
//int q = sn.nextInt();
int n = 2;
int m = 3;
int q = 6;
//int[][] arr = new int[n][m];
// for(int i=0;i<n;++i){
// for(int j=0;j<m;++j){
// arr[i][j] = sn.nextInt();
// }
// }
int[][] arr= {
{
1,0,3},{
1,0,0}};
List<Integer> index = new ArrayList<>();
for(int i=0;i<n;++i) {
index.clear();
for(int j=0;j<m;++j) {
if(arr[i][j]!=0){
index.add(j);
}
if(index.size()==2){
break;
//一行有2个就跳出
}
}
if(index.size()==2) {
int s = index.get(0),e = index.get(1);
//差值
int gocha = (arr[i][e]-arr[i][s])/(e-s);
//进行填空
for(int k=s-1;k>=0;k--){
arr[i][k] = arr[i][k+1]-gocha;
}
for(int k=s+1;k<m;k++){
arr[i][k] = arr[i][k-1]+gocha;
}
}
}
for(int j=0;j<m;++j) {
index.clear();
for(int i=0;i<n;++i) {
if(arr[i][j]!=0){
index.add(i);
}
if(index.size()==2){
break;
}
}
if(index.size()==2) {
int s = index.get(0),e = index.get(1);
//差值
int gocha = (arr[e][j]-arr[s][j])/(e-s);
//进行填空
for(int k=s-1;k>=0;k--){
arr[k][j] = arr[k+1][j]-gocha;
}
for(int k=s+1;k<n;k++){
arr[k][j] = arr[k-1][j]+gocha;
}
}
}
while(q!=0) {
int x = sn.nextInt()-1,y = sn.nextInt()-1;
if(arr[x][y]==0){
System.out.println("Unknown");
}
else{
System.out.println(arr[x][y]);
}
q--;
}
}
京公网安备 11010502036488号