leetcode第240场周赛:DAG的判定与DAG上的DP

  |  

摘要: 本文是 leetcode 第 240 周赛的记录。主要涉及的算法包括扫描线算法、双指针、单调栈、动态规划。

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


总览

这是 leetcode 第 240 场周赛,本场比赛的赞助公司是特赞,前 300 名可获得简历内推机会:

特赞是一家专注于内容与数字营销创新领域的公司,融合内容创意与计数创新,赋能商业。搭建创意内容的数字新基建,实现创意内容生产、管理、流转、分发的数据化、平台化、智能化,通过内容体验驱动品牌增长。基于特赞内容科技的积累,我们不断建立自研可控的数字创意技术底层能力,实践“Tech + Design”。

详细信息可以参考官网:

1
https://www.tezign.com/

本场比赛,依然是前 3 题完成比较好,但是 D 题没解决,最终成绩如下:

本场比赛考查的算法点包括扫描线算法、双指针、单调栈、DAG 上的 DP 等。亮点是 D 题结合了 DAG 的判定与 DAG 上的 DP。

各题的算法点以及参考文章如下:


A 题

给你一个二维整数数组 logs ,其中每个 logs[i] = [birthi, deathi] 表示第 i 个人的出生和死亡年份。

年份 x 的 人口 定义为这一年期间活着的人的数目。第 i 个人被计入年份 x 的人口需要满足:x 在闭区间 [birthi, deathi - 1] 内。注意,人不应当计入他们死亡当年的人口中。

返回 人口最多 且 最早 的年份。

示例 1:
输入:logs = [[1993,1999],[2000,2010]]
输出:1993
解释:人口最多为 1 ,而 1993 是人口为 1 的最早年份。
示例 2:
输入:logs = [[1950,1961],[1960,1971],[1970,1981]]
输出:1960
解释:
人口最多为 2 ,分别出现在 1960 和 1970 。
其中最早年份是 1960 。

1
2
3
提示:
1 <= logs.length <= 100
1950 <= birthi < deathi <= 2050

算法: 扫描线算法

定义事件 Event,每个事件实例持有两个变量,一个年份 year,一个状态 kind,kind 为 1 表示出生,-1 表示死亡。

定义事件的排序规则,年份小的排在年份大的前面,当年份相同时,死亡排在出生前面。

遍历 logs 将其中的信息记录到事件数组 events 中,排序 events。然后遍历 events,过程中用 sum 维护当前活着的总人数,对每个事件 e,首先将 e.kind 累加到 sum,然后用 sum 与全局最大值对比,更新答案。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct Event
{
int kind; // -1: 死亡, 1: 出生
int year;
Event(int kind, int y):kind(kind), year(y){}
bool operator<(const Event& e) const
{
if(year == e.year)
return kind < e.kind;
return year < e.year;
}
};

class Solution {
public:
int maximumPopulation(vector<vector<int>>& logs) {
vector<Event> events;
for(const vector<int> &log: logs)
{
events.emplace_back(1, log[0]);
events.emplace_back(-1, log[1]);
}
sort(events.begin(), events.end());
int ans = 0;
int max_sum = 0;
int sum = 0;
for(const Event &e: events)
{
sum += e.kind;
if(sum > max_sum)
{
max_sum = sum;
ans = e.year;
}
}
return ans;
}
};

B 题

给你两个 非递增 的整数数组 nums1 和 nums2,数组下标均 从 0 开始 计数。

下标对 (i, j) 中 0 <= i < nums1.length 且 0 <= j < nums2.length 。如果该下标对同时满足 i <= j 且 nums1[i] <= nums2[j] ,则称之为 有效 下标对,该下标对的 距离 为 j - i​​ 。​​

返回所有 有效 下标对 (i, j) 中的 最大距离 。如果不存在有效下标对,返回 0 。

一个数组 arr ,如果每个 1 <= i < arr.length 均有 arr[i-1] >= arr[i] 成立,那么该数组是一个 非递增 数组。

示例 1:
输入:nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]
输出:2
解释:有效下标对是 (0,0), (2,2), (2,3), (2,4), (3,3), (3,4) 和 (4,4) 。
最大距离是 2 ,对应下标对 (2,4) 。
示例 2:
输入:nums1 = [2,2,2], nums2 = [10,10,1]
输出:1
解释:有效下标对是 (0,0), (0,1) 和 (1,1) 。
最大距离是 1 ,对应下标对 (0,1) 。
示例 3:
输入:nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]
输出:2
解释:有效下标对是 (2,2), (2,3), (2,4), (3,3) 和 (3,4) 。
最大距离是 2 ,对应下标对 (2,4) 。
示例 4:
输入:nums1 = [5,4], nums2 = [3,2]
输出:0
解释:不存在有效下标对,所以返回 0 。

1
2
3
4
5
提示:
1 <= nums1.length <= 1e5
1 <= nums2.length <= 1e5
1 <= nums1[i], nums2[j] <= 1e5
nums1 和 nums2 都是 非递增 数组

算法: 双串单向双指针

两个数组各维护一个从左向右推进的指针,nums1 的指针 i 和 nums2 的指针 j。首先 i 和 j 均初始化为 0,然后一轮一轮地持续推进,直到 i 或 j 推进到了数组末尾。

1
2
3
4
5
6
对于每一轮推进,刚开始的时候需要保证 i <= j:
首先尽可能往前推进 j: 只要满足 `nums1[i] <= nums2[j]` 条件就向前推进 j,直到条件不满足或 j 到达末尾
用 `(j - 1) - i` 更新答案
如果 j 到达末尾则跳出循环
调整 i,尽可能向前推进: 只要满足 `nums1[i] > nums2[j]` 条件就向前推进 i,直到条件不满足或 i 到达末尾
调整 j: 因为 i 调整后可能会大于 j,将 j 调整为 `max(j, i)`,此时 j 可能到达或超出 nums2 的长度,这样自然不会进入下一轮推进

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
int maxDistance(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size(), n2 = nums2.size();
int i = 0, j = 0;
int ans = 0;
while(i < n1 && j < n2)
{
// 此时保证 i <= j
// 尽可能往前推进 j
while(j < n2 && nums1[i] <= nums2[j])
++j;
ans = max(ans, (j - 1) - i);
if(j == n2)
break;
// 向前调整 i
while(i < n1 && nums1[i] > nums2[j])
++i;
// 调整 i 后如果 i > j,需要调整 j
j = max(j, i);
// 此时 j 可能 >= n2
}
return ans;
}
};

C 题

一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。

比方说,数组 [3,2,5] (最小值是 2)的最小乘积为 2 (3+2+5) = 2 10 = 20 。
给你一个正整数数组 nums ,请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大,请你返回答案对 1e9 + 7 取余 的结果。

请注意,最小乘积的最大值考虑的是取余操作 之前 的结果。题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数 保存。

子数组 定义为一个数组的 连续 部分。

示例 1:
输入:nums = [1,2,3,2]
输出:14
解释:最小乘积的最大值由子数组 [2,3,2] (最小值是 2)得到。
2 (2+3+2) = 2 7 = 14 。
示例 2:
输入:nums = [2,3,3,1,2]
输出:18
解释:最小乘积的最大值由子数组 [3,3] (最小值是 3)得到。
3 (3+3) = 3 6 = 18 。
示例 3:
输入:nums = [3,1,5,6,4,2]
输出:60
解释:最小乘积的最大值由子数组 [5,6,4] (最小值是 4)得到。
4 (5+6+4) = 4 15 = 60 。

1
2
3
提示:
1 <= nums.length <= 1e5
1 <= nums[i] <= 1e7

算法: 单调栈

对每个 nums 中的元素 nums[i],求一次以 nums[i] 为最小值的【非空子数组 的最小乘积 的 最大值】,这些值中的最大值为所求答案。

对于 nums[i],所求值 t 就是 nums[i] 乘以另一个值 y,这个 y 就是某个包含 i 的子区间 [j1, j2] 上的元素和,其中 nums 在 [j1, j2] 上的值都要大于等于 nums[i]t = nums[i] * y ,要想使得所求值 t 最大,y 需要在满足条件的情况下取到最大。因为所有数都是正数,所以可以将 [j1, j2] 区间撑到最大。

问题变成了对每个 nums[i],问其左侧第一个小于 nums[i] 的值在什么位置 s1, 其右侧第一个小于 nums[i] 的值在什么位置 s2,[s1 + 1, s2 - 1] 就是 [j1, j2]

1
2
3
4
5
从左到右枚举 nums[i],过程中维护一个栈,里面存放 [0..i-1] 的某些下标,这些下标在 nums 中的对应值是单调上升的:
首先将 x = nums[st.top()] 大于 nums[i] 的都弹出栈
栈顶的元素就是 x 左侧第一个小于 x 的值,nums[i] 就是 x 右侧第一个小于 x 的值
这样就可以用 s1 = st.top(), s2 = i 来更新 x 对应的答案了
特殊值处理: 如果栈是空的,s1 为 0,如果 i 已经走到了 n,s2 为 n - 1

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
int maxSumMinProduct(vector<int>& nums) {
// 对每个 nums[i],求以 nums[i] 为最小值的区间
// 即求 [j1, j2],对 j1 <= j<= j2 有 nums[i] <= nums[j]
int n = nums.size();
stack<int> st;
using ll = long long;
const int MOD = 1e9 + 7;
ll ans = 0;
vector<ll> sums(n + 1);
for(int i = 0; i < n; ++i)
sums[i + 1] = sums[i] + nums[i];
for(int i = 0; i < n; ++i)
{
while(!st.empty() && nums[st.top()] > nums[i])
{
ll min_x = nums[st.top()];
st.pop();
int right = i - 1;
int left = 0;
if(!st.empty())
left = st.top() + 1;
ans = max(ans, min_x * (sums[right + 1] - sums[left]));
}
st.push(i);
}
while(!st.empty())
{
ll min_x = nums[st.top()];
st.pop();
int right = n - 1;
int left = 0;
if(!st.empty())
left = st.top() + 1;
ans = max(ans, min_x * (sums[right + 1] - sums[left]));
}
return ans % MOD;
}
};

D 题

1857. 有向图中最大颜色值

给你一个 有向图 ,它含有 n 个节点和 m 条边。节点编号从 0 到 n - 1 。

给你一个字符串 colors ,其中 colors[i] 是小写英文字母,表示图中第 i 个节点的 颜色 (下标从 0 开始)。同时给你一个二维数组 edges ,其中 edges[j] = [aj, bj] 表示从节点 aj 到节点 bj 有一条 有向边 。

图中一条有效 路径 是一个点序列 x1 -> x2 -> x3 -> … -> xk ,对于所有 1 <= i < k ,从 xi 到 xi+1 在图中有一条有向边。路径的 颜色值 是路径中 出现次数最多 颜色的节点数目。

请你返回给定图中有效路径里面的 最大颜色值 。如果图中含有环,请返回 -1 。

示例 1:
输入:colors = “abaca”, edges = [[0,1],[0,2],[2,3],[3,4]]
输出:3
解释:路径 0 -> 2 -> 3 -> 4 含有 3 个颜色为 “a” 的节点(上图中的红色节点)。
示例 2:
输入:colors = “a”, edges = [[0,0]]
输出:-1
解释:从 0 到 0 有一个环。

1
2
3
4
5
6
7
提示:
n == colors.length
m == edges.length
1 <= n <= 1e5
0 <= m <= 1e5
colors 只含有小写英文字母。
0 <= aj, bj < n

算法: DAG 判定, DAG上的DP

给定有向图 D,判定 D 是否为 DAG。有 DFS 和 BFS 两种方法。

(1) DFS 方法

维护一个全局的 visited 数组,定义如下。

1
2
3
visited[i] = 0 未考查过
visited[i] = 1 在当前搜索路径中
visited[i] = 2 已经考查过

枚举所有节点 u,如果 visited[u] 为 0,则以 u 为起点进行 DFS

DFS 过程中当前点为 u,如果在 for(int v: g[u]) 中发现 visited[v] == 1 则找到环。判定失败。

如果所有点都判定成功,则考察的图是 DAG

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class DAGChecker_dfs
{
bool dfs(const vector<vector<int> >& g, int node, vector<int>& visited)
{
if(visited[node] == 2)
return true;
if(visited[node] == 1) // 环
return false;
visited[node] = 1;
for(int son: g[node])
if(!dfs(g, son, visited))
return false;
visited[node] = 2;
return true;
}

public:
bool operator()(const vector<vector<int>>& g)
{
int n = g.size();
vector<int> visited(n, 0);
for(int i = 0; i < n; ++i)
{
if(visited[i] != 0) continue;
if(!dfs(g, i, visited))
return false;
}
return true;
}
};

(2) BFS 方法

如果拓扑排序后的排序列表长度小于 n,则无法拓扑排序,即 D 不是 DAG。

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class DAGChecker_bfs
{
public:
bool operator()(const vector<vector<int>>& g, vector<int> indegrees)
{
int n = g.size();
queue<int> q;
for(int i = 0; i < n; ++i)
if(indegrees[i] == 0)
q.push(i);

while(!q.empty())
{
int cur = q.front();
q.pop();
--n;
for(int son: g[cur])
{
--indegrees[son];
if(indegrees[son] == 0)
q.push(son);
}
}
return n == 0;
}
};
1
dp[u][s] := 以 u 开头,颜色 s 的最大颜色值是多少

以每个入度为 0 的点为起点 u 进行 dfs,dfs(u) 计算以 u 为起点,所有颜色可以取到的最大颜色值,保存在 dp[u][0~25] 中。dfs(u) 返回后,用 max(dp[u][0~25]) 更新答案。

在计算 dfs(u) 过程中,首先对 u 的所有子节点 v 递归地计算 dfs(v)dfs(v) 返回后用所得的 dp[v][0~25] 信息更新 dp[u][0~25]

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class DAGChecker_dfs; // 模板
class DAGChecker_bfs; // 模板

class Solution {
public:
int largestPathValue(string colors, vector<vector<int>>& edges) {
int n = colors.size();
vector<vector<int>> g(n);
vector<int> indegrees(n, 0);
for(vector<int> &e: edges)
{
++indegrees[e[1]];
g[e[0]].push_back(e[1]);
}
DAGChecker_bfs dag_checker;
// DAGChecker_dfs dag_checker;
if(!dag_checker(g, indegrees))
return -1;
// g 是DAG
int ans = 1;
// dp[u][s] := 以 u 开头,颜色 s 的最大颜色值是多少
dp = vector<vector<int>>(n, vector<int>(26, -1));
for(int u = 0; u < n; ++u)
{
if(indegrees[u] > 0)
continue;
dfs(g, colors, u); // 以 i 为起点的最大颜色值
for(int s = 0; s < 26; ++s)
{
ans = max(ans, dp[u][s]);
}
}
return ans;
}

private:
vector<vector<int>> dp;

void dfs(const vector<vector<int>>& g, const string& colors, int node)
{
if(dp[node][0] != -1)
return;
// node 开头的链还没算过
for(int s = 0; s < 26; ++s)
dp[node][s] = 0;
for(int son: g[node])
{
dfs(g, colors, son);
for(int s = 0; s < 26; ++s)
dp[node][s] = max(dp[node][s], dp[son][s]);
}
++dp[node][colors[node] - 'a'];
}
};

Share