阿里笔试3.25场（附两道题代码，第2题要用解方程思路）
看了讨论区的题目，简单写了写代码：
注：由于没参加笔试，也不知道具体的数据边界条件，所以不保证是AC代码，只能说思路应该是对的。
第一题：
题目：给定一个3行N列的数组，每1列选1个数，求所有相邻列的差的绝对值的和最小值：
/*
dp法：对于每一列上的3行，分别计算这从累积到前一列的3行的分数+(i-1)->(i)的转移分数并取最小
时间复杂度：O(n)
空间复杂度：O(1)
*/
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
long long minval(vector<vector<long long> > &M) {
if(M[0].size() == 1) {
return 0;
}
long long dp[3] = {0};
long long tmp[3];
int i, j;
for(i = 1; i < M[0].size(); i++) {
for(j = 0; j < 3; j++) {
tmp[j] = min(min(abs(M[j][i] - M[0][i-1]) + dp[0],
abs(M[j][i] - M[1][i-1]) + dp[1]),
abs(M[j][i] - M[2][i-1]) + dp[2]);
}
for(j = 0; j < 3; j++) {
dp[j] = tmp[j];
}
}
return min(min(dp[0], dp[1]),dp[2]);
}
int main() {
int n;
cin>>n;
vector<vector<long long> > M;
vector<long long> vtmp;
long long tmp;
int i, j;
for(i = 0; i < 3; i++) {
for(j = 0; j < n; j++) {
cin>>tmp;
vtmp.push_back(tmp);
}
M.push_back(vtmp);
vtmp.clear();
}
cout<<minval(M)<<endl;
return 0;
} 题目：给定一个N行M列的矩阵，矩阵每行、每列都是等差数列，所有缺失值被标记为0，现在访问矩阵的N个位置(i,j)，如果该位置值能给出，输出该值，否则输出“Unknown"。
我认为行列交替观察补齐矩阵的思路是不够充分的，举例如矩阵为：
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
此时矩阵有唯一解使横纵均为等差数列成立（即全1矩阵），而行列交替补齐是无法得到这一结果的
那么何时可以判断矩阵可以被补齐呢？实际上矩阵所有的值由4个参数固定，因此要考虑给的点是不是能使得4元方程可解
基于这种思路代码如下（写的比较麻烦，也不确定是否还有bug，请各位指导优化）：
/*
对于一个行列均为等差数列的矩阵，通过四个值即可以固定所有的数字，假设左上角2*2区域的4个数字分别为：
a00, a00+d1
a00+d2, a00+d2+d3
则对于矩阵中的任意位置(i,j)，其值应该为：a00 + j*d1 + i*((d2 + j*d3) - j*d1)，整理得：
aij = [1, j-i*j, i, i*j]*[a00, d1, d2, d3]^T
因此，根据给出的点，如果能求出[a00,d1,d2,d3]即可求出整个矩阵，否则不能
对于N个给出的点，我们可以得到N组方程，因此只要能得到4*4的满秩矩阵求解（这里假设题目不需要判断非法情况，即不会超定）
如果无法求解（即欠定），则最多可能是有1行+1列能被解出，我们只需要记录这1行和1列的通项，被访问时判断是否访问了该行该列
代码未做错误情况处理，即保证可解+各元素均为整数。
*/
/*
一个不断更新确定行列的方法解决不了的case:
矩阵为：
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
这个矩阵可以得到确定解，全1矩阵，
（简单反证，不妨假设存在a00>1,则a10>1, a30<1; 由a10>1,有a11>1，进而a21>1, a31>1，此时有矛盾：
a30<1,a31>1,a32=1，显然不满足等差数列，因此a00不可能>1，同理a00不可能<1)
*/
#include<iostream>
#include<vector>
using namespace std;
struct prs {
int x;
int y;
int v;
};
//满秩，则原矩阵所有元素都可以由四个参数+该元素位置确定
vector<int> params(vector<vector<int> > &U, vector<int> &c) {
vector<int> sM = {0,0,0,0};
sM[3] = c[3]/U[3][3];
sM[2] = (c[2] - sM[3]*U[2][3])/U[2][2];
sM[1] = (c[1] - sM[2]*U[1][2] - sM[3]*U[1][3])/U[1][1];
sM[0] = (c[0] - sM[1]*U[0][1] - sM[2]*U[0][2] - sM[3]*U[0][3])/U[0][0];
return sM;
}
//类似高斯消元，求秩和上三角阵
bool isfullmat(vector<vector<int> > &U, vector<int> &c, prs p) {
vector<int> tmp = {1, p.y - p.x*p.y, p.x, p.x*p.y};
int ctmp = p.v;
if(U.empty()) {
U.push_back(tmp);
c.push_back(ctmp);
return 0;
}
int i, j;
int prm;
for(i = 0; i < U.size(); i++) {
if(U[i][i] != 0) {
prm = tmp[i];
for(j = i; j < 4; j++) {
tmp[j] = prm*U[i][j] - U[i][i]*tmp[j];
}
ctmp = prm*c[i] -U[i][i]*ctmp;
}
else {
break;
}
}
if(tmp[0] + tmp[1] + tmp[2] + tmp[3] != 0) {
U.push_back(tmp);
c.push_back(ctmp);
}
if(U.size() == 3) {
if((U[1][1] == 0 && U[2][1] != 0) || (U[1][1] == 0 && U[1][2] == 0)) {
tmp = U[1];
U[1] = U[2];
U[2] = tmp;
}
}
else if(U.size() == 4) {
if(U[3][1] != 0) {
U.insert(U.begin()+1, U[3]);
U.erase(U.end()-1, U.end());
}
else if(U[3][2] != 0){
U.insert(U.begin()+2, U[3]);
U.erase(U.end()-1, U.end());
}
}
if(U.size() == 4) {
return 1;
}
else {
return 0;
}
}
//一点优化：每一行或每一列，只要有2个非0元素出现了，就不再算新的元素了，因为不能提高矩阵的秩
void mysolve(vector<vector<int> > &M, vector<int> &sM, vector<int> &scol, vector<int> &srow) {
int i, j;
int rec_row[M.size()];
int rec_col[M[0].size()];
int start_row[M.size()][2];
int start_col[M[0].size()][2];
vector<vector<int> > U;
vector<int> c;
prs ptmp;
bool flag = 0;
for(i = 0; i < M.size(); i++) {
rec_row[i] = 0;
start_row[M.size()][0] = 0;
start_row[M.size()][1] = 0;
}
for(i = 0; i < M[0].size(); i++) {
rec_col[i] = 0;
start_col[M[0].size()][0] = 0;
start_col[M[0].size()][1] = 0;
}
for(i = 0; i < M.size() && flag == 0; i++) {
for(j = 0; j < M[0].size() && flag == 0; j++) {
if(M[i][j] != 0) {
rec_row[i]++;
rec_col[j]++;
if(rec_row[i] <= 2 && rec_col[j] <= 2) {
ptmp.x = i;
ptmp.y = j;
ptmp.v = M[i][j];
flag = isfullmat(U, c, ptmp);
if(rec_row[i] == 1) {
start_row[i][0] = M[i][j];
start_row[i][1] = j;
}
else {
srow.push_back(i);
srow.push_back((M[i][j] - start_row[i][0])/(j - start_row[i][1]));
srow.push_back(M[i][j] - j*srow[1]);
}
if(rec_col[j] == 1) {
start_col[j][0] = M[i][j];
start_col[j][1] = i;
}
else {
scol.push_back(j);
scol.push_back((M[i][j] - start_col[j][0])/(i - start_col[j][1]));
scol.push_back(M[i][j] - i*scol[1]);
}
}
}
}
}
if(flag == 1) {
sM = params(U, c);
}
return;
}
//询问的时候分类讨论
void ask_case(vector<prs> &qs, vector<vector<int> > &M, vector<int> &sM, vector<int> &scol, vector<int> &srow) {
int i;
if(!sM.empty()) {
for(i = 0; i < qs.size(); i++) {
cout<<sM[0] + (qs[i].y - qs[i].x*qs[i].y)*sM[1] + qs[i].x*qs[i].y*sM[2] + qs[i].x*qs[i].y*sM[3]<<endl;
}
}
else {
for(i = 0; i < qs.size(); i++) {
if(!scol.empty() && qs[i].y == scol[0]) {
cout<<scol[2] + scol[1]*qs[i].x<<endl;
}
else if(!srow.empty() && qs[i].x == srow[0]) {
cout<<srow[2] + srow[1]*qs[i].y<<endl;
}
else if(M[qs[i].x][qs[i].y] != 0) {
cout<<M[qs[i].x][qs[i].y]<<endl;
}
else {
cout<<"Unknown"<<endl;
}
}
}
return;
}
int main() {
int n,m,k;
cin>>n>>m>>k;
int tmp;
vector<int> vtmp;
vector<vector<int> > M;
prs ptmp;
vector<prs> qs;
int i,j;
vector<int> sM;
vector<int> scol;
vector<int> srow;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
cin>>tmp;
vtmp.push_back(tmp);
}
M.push_back(vtmp);
vtmp.clear();
}
for(i = 0; i < k; i++) {
cin>>ptmp.x>>ptmp.y;
ptmp.x = ptmp.x - 1;
ptmp.y = ptmp.y - 1;
qs.push_back(ptmp);
}
mysolve(M, sM, scol, srow);
ask_case(qs, M, sM, scol, srow);
return 0;
} （注：重写代码的大神们，麻烦注明转载哈）
#阿里笔试##阿里巴巴##笔试题目##实习#
投递牛客等公司10个岗位 >
