阿里笔试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;
}
(注:重写代码的大神们,麻烦注明转载哈)
#阿里笔试##阿里巴巴##笔试题目##实习#
全部评论
这哪怕不限时也很难想出来。。。
2 回复
分享
发布于 2020-03-26 11:11
🤣太强了太强了太强了太强了。本以为行列行列就可以填满了,没想到还有这种情况
1 回复
分享
发布于 2020-03-26 10:24
乐元素
校招火热招聘中
官网直投
膜拜大佬
点赞 回复
分享
发布于 2020-03-26 10:30
NBNB膜拜大佬
点赞 回复
分享
发布于 2020-03-26 11:21
NB
点赞 回复
分享
发布于 2020-03-26 12:41
一个小时你就让我写这个?
点赞 回复
分享
发布于 2020-03-26 18:23
补充:一些循环的跳出、选点计算的方法实际上应该还有进一步优化的地方
点赞 回复
分享
发布于 2020-03-27 10:29
太强了!!
点赞 回复
分享
发布于 2020-03-27 13:55
优秀
点赞 回复
分享
发布于 2020-03-27 16:02
https://blog.csdn.net/m0_38065572/article/details/105101287这是我的博客,文末写了这个方程什么时候有解的结论。具体证明可以探讨。
点赞 回复
分享
发布于 2020-03-28 18:21

相关推荐

12 23 评论
分享
牛客网
牛客企业服务