蚂蚁金服暑期实习生 3面和阿里笔试 3.25

昨天电话约了今天的电话面试，11:30，聊了40分钟。
昨天下午做了阿里的线上笔试，晚上做了测评。

笔试

笔试难度不大，在牛客网上完成，2道算法题，LeetCode medium难度。

给3xn的矩阵，每列选择其中的一个数, 形成最后的数组。
使得最后的

$\sum_{i = 0}^{n-1} |b_{i+1} - b_i|$
最小。
输出最小的这个值。

DP求解即可。

时间复杂度: O(3N),
空间复杂度: O(3).

```cpp
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<ll> last_dp(3, 0);
    vector<vector<ll>> matrix(3, vector<ll> (n));
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> matrix[i][j];
        }
    }
    for (int i = 1; i < n; ++i) {
        vector<ll> dp(3);
        for (int dp_index = 0; dp_index < 3; ++dp_index) {
            dp[dp_index] = abs(matrix[dp_index][i] - matrix[0][i-1]) + last_dp[0];
            for (int j = 1; j < 3; ++j) {
                ll new_value = abs(matrix[dp_index][i] - matrix[j][i-1]) + last_dp[j];
                if (new_value < dp[dp_index]) {
                    dp[dp_index] = new_value;
                }
            }
        }
        last_dp = move(dp);
    }
    cout <<  min({last_dp[0], last_dp[1], last_dp[2]}) << endl;
    return 0;
}

一个n x m的矩阵，每列每行都是等差数列，公差为整数。
输入n x m个数，如果为0表示不知道，否则知道。
q个查询，特定位置（下标1开始）的值是否可确定。

递归求解，进行推测即可。可以用一些数组维护：每行/列是否已经被推断、每行/列已知道的数的下标、行列信息。

时间复杂度: O(N * M),
空间复杂度: O(N * M).

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;
using ll = long long;
const int INF = 0x3f3f3f3f;

int main() {
    int n, m, q;
    cin >>  n >> m >> q;
    vector<vector<int>> A(n, vector<int> (m, INF));
    vector<int> row(n, -1);
    vector<bool> row_ok(n, false);
    vector<int> col(m, -1);
    vector<bool> col_ok(m, false);
    function<void(int, int, int)> fill = [&](int i, int j, int value) -> void {
        A[i][j] = value;
        if (col_ok[j] && row_ok[i]) {
            return;
        } else {
            if (!col_ok[j]) {
                if (col[j] == -1 || col[j] == i) {
                    col[j] = i;
                } else {
                    col_ok[j] = true;
                    int diff = (A[i][j] - A[col[j]][j]) / (i - col[j]);
                    for (int r = i - 1; r >= 0; --r) {
                        fill(r, j, A[r + 1][j] - diff);
                    }
                    for (int r = i + 1; r < n; ++r) {
                        fill(r, j, A[r - 1][j] + diff);
                    }
                }
            }
            if (!row_ok[i]) {
                if (row[i] == -1 || row[i] == j) {
                    row[i] = j;
                } else {
                    row_ok[i] = true;
                    int diff = (A[i][j] - A[i][row[i]]) / (j - row[i]);
                    for (int c = j - 1; c >= 0; --c) {
                        fill(i, c, A[i][c + 1] - diff);
                    }
                    for (int c = j + 1; c < m; ++c) {
                        fill(i, c, A[i][c - 1] + diff);
                    }
                }
            }
        }
    };
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int v;
            cin >> v;
            if (v != 0) {
                fill(i, j, v);
            }
        }
    }
    for (int i = 0; i < q; ++i) {
        int r, c;
        cin >> r >> c;
        --r;
        --c;
        if (A[r][c] == INF) {
            cout << "Unknown" << endl;
        } else {
            cout << A[r][c] << endl;
        }
    }
    return 0;
}