LC 2003. 每棵子树内缺失的最小基因值
题目描述
这是 LeetCode 上的 2003. 每棵子树内缺失的最小基因值 ,难度为 困难。
有一棵根节点为 0
的 家族树 ,总共包含 n
个节点,节点编号为 0
到 n - 1
。
给你一个下标从 0
开始的整数数组 parents
,其中 $parents[i]$ 是节点 i
的父节点。由于节点 0
是根 ,所以 $parents[0] = -1$。
总共有 $10^5$ 个基因值,每个基因值都用 闭区间 $[1, 10^5]$ 中的一个整数表示。
给你一个下标从 0
开始的整数数组 nums
,其中 $nums[i]$ 是节点 i
的基因值,且基因值 互不相同 。
请你返回一个数组 ans
,长度为 n
,其中 $ans[i]$ 是以节点 i
为根的子树内缺失的最小基因值。
节点 x
为根的子树包含节点 x
和它所有的后代节点。
示例 1:
1 |
|
示例 2:1
2
3
4
5
6
7
8
9
10
11输入:parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
输出:[7,1,1,4,2,1]
解释:每个子树答案计算结果如下:
- 0:子树内包含节点 [0,1,2,3,4,5] ,基因值分别为 [5,4,6,2,1,3] 。7 是缺失的最小基因值。
- 1:子树内包含节点 [1,2] ,基因值分别为 [4,6] 。 1 是缺失的最小基因值。
- 2:子树内只包含节点 2 ,基因值为 6 。1 是缺失的最小基因值。
- 3:子树内包含节点 [3,4,5] ,基因值分别为 [2,1,3] 。4 是缺失的最小基因值。
- 4:子树内只包含节点 4 ,基因值为 1 。2 是缺失的最小基因值。
- 5:子树内只包含节点 5 ,基因值为 3 。1 是缺失的最小基因值。
示例 3:1
2
3
4
5输入:parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
输出:[1,1,1,1,1,1,1]
解释:所有子树都缺失基因值 1 。
提示:
- $n = parents.length = nums.length$
- $2 <= n <= 10^5$
- 对于
i != 0
,满足 $0 <= parents[i] <= n - 1$ - $parents[0] = -1$
parents
表示一棵合法的树。- $1 <= nums[i] <= 10^5$
nums[i]
互不相同。
DFS
破题
先用几句话破题。
共由 $n$ 个节点组成一棵树(节点编号从 $0$ 到 $n - 1$),parents
描述了该树的形态,同时每个节点有一个基因值 $nums[i]$。
题目要我们求:以每个节点为根的子树中,权重集合在 $[1, n + 1]$ 范围内缺失的最小数。
需要重点注意:是权重集合在 $[1, n + 1]$ 范围内缺失的最小数,而不是在
nums
中缺失的最小数。
举个 🌰,假设由 $4$ 个节点组成树,基因值 nums = [2,3,4,5]
,那么对应的 ans = [1,1,1,1]
。
再次强调:我们求的是每个节点为根的子树中,权重集合在 $[1, n + 1]$ 范围内的最小缺失值,而非在 nums
中的缺失值。
结论一:当nums
中没有 $1$,所有节点答案为 $1$
由于我们是求 $[1, n + 1]$ 范围内的最小缺失值,当 nums
中不存在 $1$ 时,所有节点缺失的最小值为 $1$。
结论二:nums
有 $1$,所有该节点的“非祖先”节点,答案为 $1$
基因值互不相同,同时统计的是,以每个节点为“根”时,子树的权值情况,因此节点 $1$ 只会对其“祖先”产生影响。
结论三:从「$1$ 节点」到「根节点」的路径中,答案必然满足“非递减”性质
这个结论不明显,但不难理解。
先假设存在某个节点 X
,其最小缺失值为 $k$:
再通过节点 X
的最小缺失值,推理出父节点 Fa
的情况:
综上,我们只需要考虑「节点 $1$」到「根节点」这一节点答案即可。
并且由于从下往上,答案非递减,我们采取「先算子节点,再算父节点」的方式。
具体的,用变量 cur
代指当前节点,使用 ne
代指当前节点的子节点,vis
数组记录在子树中出现过的基因值,val
代表当前的节点的最小缺失值。
一些细节:由于题目只说了 $1 \leq nums[i] \leq 1e5$,没说 $nums[i]$ 与 $n$ 的关系,因此我们开辟 vis
数组时需要开到 $100010$,或是干脆使用 Set
充当 vis
。
Java 代码:
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
40class Solution {
public:
// 考虑到有不懂「链式前向星」的同学, 这里使用最简单的存图方式 {1: [2, 3]} 代表节点一有两个子节点 2 和 3
unordered_map<int, vector<int>> g;
vector<int> smallestMissingValueSubtree(std::vector<int>& parents, std::vector<int>& nums) {
int n = nums.size(), cur = -1;
vector<int> ans(n, 1);
// 找节点 1, 建图
for (int i = 0; i < n; i++) {
if (nums[i] == 1) cur = i;
g[parents[i]].push_back(i);
}
// 若 nums 中没 1, 对应结论一
if (cur == -1) return ans;
unordered_set<int> vis;
// 从节点 1 开始往根找(从深到浅), idx 代表当前节点, ne 代表 cur 在该链路下的子节点
int ne = cur, val = 1;
while (cur != -1) {
// 每次对当前节点所在子树的进行标记
dfs(cur, ne, nums, vis);
// 在 [val, n+1] 范围内找第一个未被标记基因值
for (int i = val; i <= n + 1; i++) {
if (vis.count(i)) continue;
ans[cur] = val = i;
break;
}
ne = cur; cur = parents[cur]; // 指针上移
}
return ans;
}
void dfs(int idx, int block, vector<int>& nums, unordered_set<int>& vis) {
vis.insert(nums[idx]);
for (int x : g[idx]) {
if (x == block) continue;
dfs(x, block, nums, vis);
}
}
};
Python 代码: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
40class Solution:
def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
# 虑到有不懂「链式前向星」的同学, 这里使用最简单的存图方式 {1: [2, 3]} 代表节点 1 有两个子节点 2 和 3
g = defaultdict(list)
def dfs(idx, block):
nonlocal val
vis.add(nums[idx])
for x in g[idx]:
if x == block:
continue
dfs(x, block)
n, cur = len(nums), -1
ans = [1] * n
# 找节点 1, 建图
for i in range(n):
if nums[i] == 1:
cur = i
g[parents[i]].append(i)
# 若 nums 中没 1, 对应结论一
if cur == -1:
return ans
vis = set()
# 从节点 1 开始往根找(从深到浅), idx 代表当前节点, ne 代表 cur 在该链路下的子节点
ne, val = cur, 1
while cur != -1:
# 每次对当前节点所在子树的进行标记
dfs(cur, ne)
# 在 [val, n+1] 范围内找第一个未被标记基因值
for i in range(val, n + 2):
if i in vis:
continue
ans[cur] = val = i
break
ne, cur = cur, parents[cur] # 指针上移
return ans
TypeScript 代码: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
44function smallestMissingValueSubtree(parents: number[], nums: number[]): number[] {
// 考虑到有不懂「链式前向星」的同学, 这里使用最简单的存图方式 {1: [2, 3]} 代表节点 1 有两个子节点 2 和 3
const g = {};
const dfs = function (g: { [key: number]: number[] }, idx: number, block: number, nums: number[], vis: Set<number>): void {
vis.add(nums[idx]);
if (Array.isArray(g[idx])) {
for (let x of g[idx]) {
if (x == block) continue;
dfs(g, x, block, nums, vis);
}
}
}
let n = nums.length, cur = -1;
const ans = new Array(n).fill(1);
// 找节点 1, 建图
for (let i = 0; i < n; i++) {
if (nums[i] === 1) cur = i;
if (!g[parents[i]]) g[parents[i]] = [];
g[parents[i]].push(i);
}
// 若 nums 中没 1, 对应结论一
if (cur == -1) return ans;
const vis = new Set<number>();
// 从节点 1 开始往根找(从深到浅), idx 代表当前节点, ne 代表 cur 在该链路下的子节点
let ne = cur, val = 1;
while (cur !== -1) {
// 每次对当前节点所在子树的进行标记
dfs(g, cur, ne, nums, vis);
// 在 [val, n+1] 范围内找第一个未被标记基因值
for (let i = val; i <= n + 1; i++) {
if (vis.has(i)) continue;
ans[cur] = val = i;
break;
}
ne = cur; cur = parents[cur]; // 指针上移
}
return ans;
}
Java 代码(链式向前星,使用 Set
充当 vis
):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
39class Solution {
int N = 100010, M = N, idx = 1;
int[] he = new int[N], e = new int[M], ne = new int[M];
void add(int a, int b) {
e[idx] = b;
ne[idx] = he[a];
he[a] = idx++;
}
public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
Arrays.fill(he, -1);
int n = parents.length, cur = -1, val = 1;
int[] ans = new int[n];
Arrays.fill(ans, 1);
for (int i = 0; i < n; i++) {
if (i >= 1) add(parents[i], i);
if (nums[i] == 1) cur = i;
}
if (cur == -1) return ans;
Set<Integer> vis = new HashSet();
while (cur != -1) {
dfs(cur, vis, nums);
for (int i = val; i <= n + 1; i++) {
if (vis.contains(i)) continue;
ans[cur] = val = i;
break;
}
cur = parents[cur];
}
return ans;
}
void dfs(int u, Set<Integer> vis, int[] nums) {
vis.add(nums[u]);
for (int i = he[u]; i != -1; i = ne[i]) {
int j = e[i];
if (vis.contains(nums[j])) continue;
dfs(j, vis, nums);
}
}
}
- 时间复杂度:找 $1$ 和建图的复杂度为 $O(n)$;构造从根节点到 $1$节点的链条答案时,会对子树节点进行标记,同时每个节点的答案会从 $[val, n + 1]$ 范围内找缺失值,复杂度为 $O(n)$。 整体复杂度为 $O(n)$
- 空间复杂度:$O(n)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.2003
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!