华为饭堂 末位淘汰
今天逛职场 App，无意间翻到一篇帖子：
点开图片之前，我还以为只是普通的争霸赛被网友解读为末位淘汰。
点开图片后我却发现 ...
可以看出，是深圳华为的行政部做的海报，里面清晰写到：员工的每次就餐都会决定谁去谁留，结尾还用了强调不是开玩笑的感叹号。
这，实在是好家伙 🤣
先不讨论对合作供应商采取这样的规则是否合理，就连员工就餐选择都增加了莫名的压力。
对此有些网友认为，这样的规则挺好，可以迫使饭堂商家把用餐品质和服务做好，最终让就餐员工受益。
但也有网友提出担心：不合理的竞争规则会加剧内卷化，最终可能会导致供应商利润被过分压缩，使得商家使用预制菜或者次品质原料来烹饪。
不同类型的餐饮业因为供应链不同，利润空间相差较大。
但餐饮业也是生意，正常情况下，企业往往有个设定好的利润标准，低于标准可能就不会考虑合作。
因此现实的情况可能比网友猜想还要恶劣一些：即使尚未达到利润边界，例如可能仍有超过 20% 的利润空间，但企业通过与其他合作伙伴（非华为的客户）的利润率做横向对比，仍然会在原料上做节省操作。
...
回归主线。
今天来一道稍稍麻烦的算法题。
题目描述
平台：LeetCode
题号：2003
有一棵根节点为 0 的家族树，总共包含 n 个节点，节点编号为 0 到 n - 1。
给你一个下标从 0 开始的整数数组 parents，其中
是节点 i 的父节点。
由于节点 0 是根 ，所以
。
总共有 个基因值，每个基因值都用闭区间 中的一个整数表示。
给你一个下标从 0 开始的整数数组 nums，其中
是节点 i 的基因值，且基因值互不相同。
请你返回一个数组 ans，长度为 n，其中
是以节点 i 为根的子树内缺失的最小基因值。
节点 x 为根的子树包含节点 x 和它所有的后代节点。
示例 1： 
输入：parents = [-1,0,0,2], nums = [1,2,3,4]
输出：[5,1,1,1]
解释：每个子树答案计算结果如下：
- 0：子树包含节点 [0,1,2,3] ，基因值分别为 [1,2,3,4] 。5 是缺失的最小基因值。
- 1：子树只包含节点 1 ，基因值为 2 。1 是缺失的最小基因值。
- 2：子树包含节点 [2,3] ，基因值分别为 [3,4] 。1 是缺失的最小基因值。
- 3：子树只包含节点 3 ，基因值为 4 。1是缺失的最小基因值。
示例 2： 
输入：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：
输入：parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
输出：[1,1,1,1,1,1,1]
解释：所有子树都缺失基因值 1 。
提示：
-
-
-
对于 i != 0，满足 -
-
parents表示一棵合法的树。 -
-
nums[i]互不相同。
DFS
破题
先用几句话破题。
共由
个节点组成一棵树（节点编号从
到
），parents 描述了该树的形态，同时每个节点有一个基因值
。
题目要我们求：以每个节点为根的子树中，权重集合在 范围内缺失的最小数。
❝需要重点注意：是权重集合在 范围内缺失的最小数，而不是在
❞nums中缺失的最小数。
举个 🌰，假设由
个节点组成树，基因值 nums = [2,3,4,5]，那么对应的 ans = [1,1,1,1]。
再次强调：我们求的是每个节点为根的子树中，权重集合在
范围内的最小缺失值，而非在 nums 中的缺失值。
结论一：当nums 中没有
，所有节点答案为
由于我们是求
范围内的最小缺失值，当 nums 中不存在
时，所有节点缺失的最小值为
。
结论二：nums 有
，所有该节点的“非祖先”节点，答案为
基因值互不相同，同时统计的是，以每个节点为“根”时，子树的权值情况，因此节点 只会对其“祖先”产生影响。
结论三：从「 节点」到「根节点」的路径中，答案必然满足“非递减”性质
这个结论不明显，但不难理解。
先假设存在某个节点 X，其最小缺失值为
：
再通过节点 X 的最小缺失值，推理出父节点 Fa 的情况：
综上，我们只需要考虑「节点 」到「根节点」这一节点答案即可。
并且由于从下往上，答案非递减，我们采取「先算子节点，再算父节点」的方式。
具体的，用变量 cur 代指当前节点，使用 ne 代指当前节点的子节点，vis 数组记录在子树中出现过的基因值，val 代表当前的节点的最小缺失值。
一些细节：由于题目只说了
，没说
与
的关系，因此我们开辟 vis 数组时需要开到
，或是干脆使用 Set 充当 vis。
Java 代码：
class Solution {
// 考虑到有不懂「链式前向星」的同学, 这里使用最简单的存图方式 {1: [2, 3]} 代表节点一有两个子节点 2 和 3
Map<Integer, List<Integer>> g = new HashMap<>();
public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
int n = nums.length, cur = -1;
int[] ans = new int[n];
Arrays.fill(ans, 1);
// 找节点 1, 建图
for (int i = 0; i < n; i++) {
if (nums[i] == 1) cur = i;
List<Integer> list = g.getOrDefault(parents[i], new ArrayList<>());
list.add(i);
g.put(parents[i], list);
}
// 若 nums 中没 1, 对应结论一
if (cur == -1) return ans;
boolean[] vis = new boolean[100010];
// 从节点 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[i]) continue;
ans[cur] = val = i;
break;
}
ne = cur; cur = parents[cur]; // 指针上移
}
return ans;
}
void dfs(int idx, int block, int[] nums, boolean[] vis) {
vis[nums[idx]] = true;
List<Integer> list = g.getOrDefault(idx, new ArrayList<>());
for (int x : list) {
if (x == block) continue;
dfs(x, block, nums, vis);
}
}
}
C++ 代码：
class 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 代码：
class 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 代码：
function 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 (![][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）：
class 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);
}
}
}
-
时间复杂度：找 和建图的复杂度为 ；构造从根节点到 节点的链条答案时，会对子树节点进行标记，同时每个节点的答案会从 范围内找缺失值，复杂度为 。 整体复杂度为 -
空间复杂度：
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台发布
