本次比赛囊括众多面试中高级知识点,具体为 差分数组,单调队列,双指针,单调栈,拓扑排序,DAG 上 dp
给定
个年份区间
,表示第
个人的出生年份到死亡年份
定义年份
的 人口 为这一年活着的人口数量,对于第
个人,若其被记入年份
的人口,则有
返回 人口最多 的 最早 年份
数据规定
问题等价于,给定多个区间
,对区间中所有年份人口加
,经过数次修改后,返回年份人口最大值的最小下标
区间修改定值,离线查询,可以考虑使用 差分数组
具体来讲,预计算差分数组
,给
加
,
减
,多次操作后使用 前缀和 还原原数组
之后,对数组排序,返回期望的下标即可,时间复杂度为
,其中
为年份的区间长度最大值
当然,本题的数据规模很小,可以使用暴力算法,暴力修改每一个区间的值,时间复杂度为
/* 差分数组 */
class Solution {
public:
int maximumPopulation(vector<vector<int>>& logs) {
vector<int> b(107);
vector<int> d(107);
for (int i = 0; i < logs.size(); ++i) {
d[logs[i][0] - 1950]++;
d[logs[i][1] - 1950]--;
}
for (int i = 1; i < 107; ++i) d[i] += d[i - 1];
for (int i = 0; i < 107; ++i) b[i] = i;
sort(b.begin(), b.end(), [&](int x, int y) {
if (d[x] == d[y]) return x < y;
return d[x] > d[y];
});
return 1950 + b[0];
}
};
/* 暴力算法 */
class Solution {
public:
int maximumPopulation(vector<vector<int>>& logs) {
vector<int> a(107);
vector<int> b(107);
for (int i = 0; i < logs.size(); ++i) {
for (int j = logs[i][0]; j < logs[i][1]; ++j) {
a[j - 1950]++;
}
}
for (int i = 0; i < 107; ++i) b[i] = i;
sort(b.begin(), b.end(), [&](int x, int y) {
if (a[x] == a[y]) return x < y;
return a[x] > a[y];
});
return 1950 + b[0];
}
};
给定两个 非递增 数组 A, B
,下标从 0
开始计数
若 A
的下标 i
,与 B
的下标 j
满足 i <= j, A[i] <= B[j]
,则称 i, j
为有效下标对,定义下标对的 距离 为 j - i
返回所有 有效 下标对的 最大距离,若不存在有效下标对,返回
数据保证
由于两个数组具有 单调性,因此可以考虑用双指针 动态扩充队列,队列维护
中元素的下标
具体来说,若 A[i] <= B[j]
,那么一定有 A[i + 1] <= B[j]
,因此可以动态扩充一个队列,对于队列中所有下标 j
,都满足 A[i] <= B[j]
A[i] <= B[j]
,指针 j
就可以右移,直到移动到 的右边界
j
不满足 i <= j
由于需要队尾入队,队首出队,可以使用 双端队列 来实现
对于 A[i]
,若队列不为空,每次拿队尾的下标 j
和 i
作差即可,维护答案最大值
时间复杂度为
class Solution {
public:
int maxDistance(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), m = nums2.size();
deque<int> dq;
int ans = 0;
for (int i = 0, j = 0; i < n; ++i) {
if (!dq.empty()) dq.pop_front();
while (j < m && nums1[i] <= nums2[j])
dq.push_back(j++);
if (!dq.empty()) {
ans = max(ans, dq.back() - i);
}
}
return ans;
}
};
定义一个数组
的 最小乘积 为数组中 最小值 乘以 数组的和
[3, 2, 5]
的最小值为 2
,数组和为 10
,因此最小乘积为 20
现在给定一个长为
的正整数数组 nums
,请计算 nums
中所有 非空子数组 的 最小乘积 的 最大值
[1, 2, 3, 2]
满足条件的子数组为 [2, 3, 2]
,答案为 2 * (2 + 3 + 2) = 14
题目保证,存储的答案可以使用 64
位有符号整数存储,但是最终的答案需要对
取余
数据保证
直观来想,如果枚举子数组,一共需要计算
次,不考虑区间查询最小值,已经是
的时间复杂度,无法通过全部数据规模
换个角度,枚举每一个元素
,考虑
所能 管辖的区域
具体来讲,我们需要为每一个
计算出一个区间
,使得
是
中的最小值
那么我们需要分别计算出 右侧和左侧第一个更小值,这个可以使用 单调栈 解决,详见(原文链接) 下一个更大元素 I
预处理每一个元素所管辖的区间,维护答案的最大值,时间复杂度
class Solution {
public:
typedef long long LL;
int maxSumMinProduct(vector<int>& nums) {
const int MOD = 1e9 + 7;
int n = nums.size();
vector<LL> a(n + 1), sum(n + 1);
for (int i = 1; i <= n; ++i) {
a[i] = nums[i - 1];
sum[i] = sum[i - 1] + a[i];
}
vector<int> rmin(n + 1, -1), lmin(n + 1, -1); // -1 表示没有更小的
stack<int> mono1, mono2; // 递增
for (int i = 1; i <= n; ++i) {
while (!mono1.empty() && a[mono1.top()] > a[i]) {
rmin[mono1.top()] = i;
mono1.pop();
}
mono1.push(i);
}
for (int i = n; i >= 1; --i) {
while (!mono2.empty() && a[mono2.top()] > a[i]) {
lmin[mono2.top()] = i;
mono2.pop();
}
mono2.push(i);
}
LL ans = 0;
for (int i = 1; i <= n; ++i) {
/* 若为 -1,则左/右边没有更小元素 */
/* 管辖范围可以拓展到边界 */
int L = (lmin[i] == -1 ? 1 : lmin[i] + 1);
int R = (rmin[i] == -1 ? n : rmin[i] - 1);
ans = max(ans, a[i] * (sum[R] - sum[L - 1]));
}
return ans % MOD;
}
};
这题我最早听说,是同学在今年春招面试美团后端时遇到的,后来牛客网上有同学爆料腾讯广告投放也出了这么一道题,如果不转换个枚举思路,这题是很难做的
给定一个
个节点,
条边的 有向图,其中
给定一个长为
,并且由 小写字母 构成的字符串
,表示节点
的颜色
在图论中,我们用 路径 表示一个点序列
,其中
表示点
和点
有单向连边,下标
满足
我们定义,路径中 出现次数最多的 颜色的节点数目为路径的 颜色值,请计算图中所有路径 最大颜色值,如果图里有环,返回
注意到给定的是 有向图
我们定义
表示到第
个节点,颜色
出现的最大次数,考虑节点
的所有 前继节点
,我们可以轻松的写出状态转移方程
其中
为指示变量,当节点
的颜色和
相等时,颜色个数要增
,当颜色不同时,只要继承前继节点的颜色数量即可,具体来讲
上面的分析要求给出 前继节点,这需要对图上节点的先后关系做分析,而拓扑排序正好可以帮助我们做到这点
在本题中,拓扑排序的作用有两个
我们在拓扑排序的过程中对状态进行转移,最后维护每个节点的颜色最大值即可
时间复杂度为
,其中
是字符集的大小
class Solution {
public:
int largestPathValue(string colors, vector<vector<int>>& edges) {
int n = colors.size();
int m = edges.size();
vector<int> ind(n);
vector<vector<int>> g(n);
vector<vector<int>> dp(n, vector<int>(26, 0));
queue<int> q;
for (int i = 0; i < m; ++i) {
ind[edges[i][1]]++;
g[edges[i][0]].push_back(edges[i][1]);
}
for (int i = 0; i < n; ++i) {
if (!ind[i]) {
q.push(i);
dp[i][colors[i] - 'a'] = 1;
}
}
int cnt = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
++cnt;
for (auto &i: g[u]) {
for (int j = 0; j < 26; ++j) {
int add = j == colors[i] - 'a' ? 1 : 0;
dp[i][j] = max(dp[i][j], dp[u][j] + add);
}
--ind[i];
if (!ind[i]) q.push(i);
}
}
if (cnt != n) return -1;
int ans = 0;
for (int i = 0; i < n; ++i)
ans = max(ans, *max_element(dp[i].begin(), dp[i].end()));
return ans;
}
};
这题很好想,注意到大部分 case
面向 有向无环图 (DAG),就会往 DAG 上 dp 考虑,而对于判环和节点的先后顺序,可以使用 拓扑排序 解决,由此一来,这道题也就水到渠成了