阿里笔试7.29 线性复杂度
第一题
给 n 个恐龙蛋及恐龙蛋的大小，按降序排列。第 i 个恐龙蛋每天增大 i，问最少几天会出现两个同样大小的恐龙蛋。
分析：根据题意，相邻的恐龙蛋增长速度相差为1。因此，如果相邻蛋的大小差异数组d为{d1, d2, …, dn-1}，那么每经过1天，数组d中每个元素都会减少1。
当d中首次出现0元素时，就是首次出现两个相同大小恐龙蛋的时候。这很容易证明，因为根据题设，d中的元素均非负。在d中出现0元素之前，恐龙蛋大小是严格递减的，不存在相同大小的蛋。
很显然，d中首次出现0元素的天数，就是数组d中的最小值。数组d及其最小值可以在O(n)时间内计算得到。算法的时间复杂度为O(n)。
int solve() {
int n, ret = INT_MAX;
cin >> n;
for (int i = 0, prev = INT_MAX, cur = 0; i < n; i++) {
cin >> cur;
ret = min(ret, prev - cur);
prev = cur;
}
return ret;
}
第二题
n 个客栈依次排列，给出 n - 1 条路的权重。从任意一处出发，每走过一条路，该路的权重减 1，但得到1 点利益。不能走权重为 0 的路。求最大利益。
分析：题中涉及到一个图An，An的n个顶点是n个客栈。其中第k-1个客栈到第k个客栈的边的权重用v[k-1]表示。我们采用动态规划去求解这个问题。假设Lk是由第0,…,k个客栈所组成的An的子图，Rk是由第k, …,n-1个客栈所组成的An的子图。
定义以下变量：
f_l[k] // 从第k个客栈出发，在L_k中获得的最大利益
f_r[k] // 从第k个客栈出发，在R_k中获得的最大利益
g_l[k] // 从第k个客栈出发，并在第k个客栈结束，在L_k中获得的最大利益
g_r[k] // 从第k个客栈出发，并在第k个客栈结束，在R_k中获得的最大利益
如果v[k-1]是奇数，那么
f_l[k] = f_l[k-1] + v[k-1] // 首先在客栈k-1和k中反复横跳耗尽该边的权重
g_l[k] = (v[k-1] > 1) ? (g_l[k-1] + v[k-1] - 1) : 0
// 因为要回到出发点，v[k-1]只能遍历偶数次
如果v[k-1]是偶数，那么
g_l[k] = (v[k-1] > 0) ? (g_l[k-1] + v[k-1]) : 0
//在客栈k-1和k中反复横跳耗尽该边的权重
f_l[k] = max((v[k-1] > 0) ? (f_l[k-1] + v[k-1] - 1) : 0, g_l[k])
// 要么最终回到客栈k；要么不回到客栈k，但此时v[k-1]只能遍历奇数次
我们可以令k=0,1,...,n-1，利用DP计算出所有的f_l[k], g_l[k]。初始条件显然有f_l[0] = g_l[0] = 0。
对f_r[k]和g_r[k]的计算是完全对称的，只不过按照k=n-1,...,1,0逆序计算。时间复杂度为O(n)。
在计算出了f_l, f_r, g_l, g_r后，我们考虑计算原问题的解。假设我们从第k个客栈出发，并在第k’个客栈结束。
如果k’≤k，最大收益为f_l[k]+g_r[k]。因为对于客栈k右边的权值，我们必须从第k个客栈出发开始遍历，并最终回到第k个客栈。类似地，如果k’≥k，最大收益为f_r[k]+g_l[k]。
因此，原问题的解为))
，可以在O(n)的时间内求解。
int solve() {
int n, ret = 0;
cin >> n;
vector<int> v(n - 1), f_l(n, 0), f_r(n, 0), g_l(n, 0), g_r(n, 0);
for (int i = 0; i < n - 1; i++) cin >> v[i];
for (int k = 1; k < n; k++) {
if (v[k - 1] & 1) {
f_l[k] = f_l[k - 1] + v[k - 1];
g_l[k] = v[k - 1] > 1 ? g_l[k - 1] + v[k - 1] - 1 : 0;
}
else {
g_l[k] = v[k - 1] ? g_l[k - 1] + v[k - 1] : 0;
f_l[k] = max(g_l[k], v[k - 1] ? f_l[k - 1] + v[k - 1] - 1 : 0);
}
}
for (int k = n - 2; k >= 0; k--) {
if (v[k] & 1) {
f_r[k] = f_r[k + 1] + v[k];
g_r[k] = v[k] > 1 ? g_r[k + 1] + v[k] - 1 : 0;
}
else {
g_r[k] = v[k] ? g_r[k + 1] + v[k] : 0;
f_r[k] = max(g_r[k], v[k] ? f_r[k + 1] + v[k] - 1 : 0);
}
}
for (int k = 0; k < n; k++)
ret = max(ret, max(f_l[k] + g_r[k], f_r[k] + g_l[k]));
return ret;
}
华为一面43人在聊