AllinToyou

这个屌丝很懒，什么也没留下！

热门标签

【Py/Java/C++三种语言OD独家2024D卷真题】20天拿下华为OD笔试之【DFS/BFS】2024D-寻找最富裕的小家庭【欧弟算法】全网注释最详细分类最全的华为OD真题题解

作者：AllinToyou | 2024-05-30 07:09:23

踩

寻找最富裕的小家庭

从2024年4月15号开始，OD机考全部配置为2024D卷。
注意两个关键点：

会遇到C卷复用题。虽然可能存在幸存者偏差，但肯定还会有一大部分的旧题。
现在又支持做完题目之后倒回去改了。就是可以先做200的再做100的，然后可以反复提交。

在这里插入图片描述

有LeetCode算法/华为OD考试扣扣交流群可加 948025485
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
绿色聊天软件戳 od1336了解算法冲刺训练

题目描述与示例

题目描述

在一棵树中，每个节点代表一个家庭成员，节点的数字表示其个人的财富值，一个节点及其直接相连的子节点被定义为一个小家庭。

现给你一棵树，请计算出最富裕的小家庭的财富和。

输入描述

第一行为一个数N，表示成员总数，成员编号1-N，1<=N<=1000

第二行为N个空格分隔的数，表示编号1-N的成员的财富值，0<=财富值<=1000000

接下来N-1行，每行两个空格分隔的整数(N1,N2)，表示N1是N2的父节点。

输出描述

最富裕的小家庭的财富和

示例

输入

4
100 200 300 500
1 2
1 3
2 4
1
2
3
4
5

输出

700
1

说明

在这里插入图片描述

所构建出的树如上图所示，其中最小富裕家庭为节点2和节点4构成的小家庭。

解题思路

常规搜索解法

题目所给的数据形式，非常容易想到转化为邻接表来储存数据。

另外，由于数据所给的编号是从1开始的，为了方便后续对应上财富列表的索引（从0开始），可以把-1之后的结果作为编号来储存。

neighbor_dic = defaultdict(list)
for _ in range(n-1):
    fa, ch = map(int, input().split())
    neighbor_dic[fa-1].append(ch-1)
1
2
3
4

另外，由于本题的输入没有告知根节点root，我们需要根据输入的n-1条边来找到根节点。

根节点root存在特点：根节点root不是任何一个节点的子节点。因此，我们可以根据n-1条边中的所有子节点，反推出唯一那个不是子节点的节点，即为根节点。具体代码如下

neighbor_dic = defaultdict(list)
children_set = set()
for _ in range(n-1):
    fa, ch = map(int, input().split())
    neighbor_dic[fa-1].append(ch-1)
    children_set.add(ch-1)

for i in range(n):
    if i not in children_set:
        root = i
        break
1
2
3
4
5
6
7
8
9
10
11

剩下的就是常规的DFS和BFS过程了。由于本题所给数据是树型结构（有向无环图），不会出现同一个节点多次进入的情况，因此无需额外使用check_list来维护节点重复进入。

对于DFS而言，核心函数为

def dfs(neighbor_dic, money_list, i):
    global ans
    little_family_sum = money_list[i]

    for child in neighbor_dic[i]:
        dfs(neighbor_dic, money_list, child)
        little_family_sum += money_list[child]

    ans = max(ans, little_family_sum)
1
2
3
4
5
6
7
8
9

对于BFS而言，核心过程为

q = deque([root])

ans = 0
while q:
    node = q.popleft()
    little_family_sum = money_list[node]
    
    for child in neighbor_dic[node]:
        q.append(child)
        little_family_sum += money_list[child]
        
    ans = max(ans, little_family_sum)
1
2
3
4
5
6
7
8
9
10
11
12

可以发现都涉及相似的过程：

考虑当前小家庭的父节点i
初始化当前小家庭的总财富值little_family_sum = money_list[i]
考虑i的所有子节点child
1. 对child进行递归（DFS）/将child加入队列中（BFS）
2. 根据子节点的财富money_list[ch]，更新当前小家庭的总财富值little_family_sum
基于当前小家庭的总财富值little_family_sum，更新全局的答案ans

无需搜索的简单解法

另外，本题还存在一种非常简单的解法，无需进行DFS/BFS搜索。

由于每一个小家庭仅由父节点和其子节点构成，这里的对应关系可以从边的对应关系中直接得到。

在拿到一条边(fa, ch)的时候，实际上我们可以马上知道父节点fa和子节点ch对应的财富money_list[fa]和money_list[ch]。

仅需额外构建一个列表little_family_list，little_family_list[i]表示以i为父节点的小家庭的财富。

初始化litte_family_list[i] = money_list[i]（这样才能避免父节点的重复计算），然后对于所有的边(fa, ch)，将fa的孩子ch的财富加入到这个小家庭中（只往小家庭中加入子节点），即litte_family_list[fa] += money_list[ch]。

最后找到litte_family_list中的最大值即为答案。整体的核心代码如下

little_family_list = money_list.copy()
for _ in range(n-1):
    fa, ch = map(int, input().split())
    little_family_list[fa-1] += money_list[ch-1]

print(max(little_family_list))
1
2
3
4
5
6

代码

解法一：DFS

python

# 题目：2023C-寻找最富裕的小家庭
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：DFS
# 代码看不懂的地方，请直接在群上提问


# DFS函数
def dfs(neighbor_dic, money_list, i):
    global ans
    # 初始化当前小家庭的财富值为money_list[i]
    little_family_sum = money_list[i]

    # 考虑所有节点i的子节点child，做两件事情：
    # 1. 对child进行递归
    # 2. 更新little_family_sum的值
    for child in neighbor_dic[i]:
        dfs(neighbor_dic, money_list, child)
        little_family_sum += money_list[child]

    # 更新ans
    ans = max(ans, little_family_sum)

from collections import defaultdict

# 输入节点个数
n = int(input())
# 输入各个节点对应的财富
money_list = list(map(int, input().split()))
# 初始化邻接表
neighbor_dic = defaultdict(list)
# 储存子节点的集合，用来找根节点
children_set = set()

# 建树，输入n-1行
for _ in range(n-1):
    # 输入某一条边对应的父节点和子节点
    # 注意编号是从1开始的，为了方便使用，可以令所有的编号-1
    # 使得编号从0开始
    fa, ch = map(int, input().split())
    # 父节点的邻接表延长
    neighbor_dic[fa-1].append(ch-1)
    # ch是fa的子节点，必然不是根节点，存入children_set中
    children_set.add(ch-1)

# 寻找整棵树的根节点，唯一一个不位于children_set中的节点即为根节点
for i in range(n):
    if i not in children_set:
        root = i
        break

# 初始化ans为0
ans = 0
# 递归调用入口
dfs(neighbor_dic, money_list, root)
print(ans)
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
55
56

java

import java.util.*;

public class Main {
    static int ans = 0;

    static void dfs(HashMap<Integer, List<Integer>> neighborDic, List<Integer> moneyList, int i) {
        // 初始化当前小家庭的财富值为moneyList.get(i)
        int littleFamilySum = moneyList.get(i);

        // 考虑所有节点i的子节点child，做两件事情：
        // 1. 对child进行递归
        // 2. 更新littleFamilySum的值
        List<Integer> children = neighborDic.get(i);
        if (children != null) {
            for (int child : children) {
                dfs(neighborDic, moneyList, child);
                littleFamilySum += moneyList.get(child);
            }
        }

        // 更新ans
        ans = Math.max(ans, littleFamilySum);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer> moneyList = new ArrayList<>();
        HashMap<Integer, List<Integer>> neighborDic = new HashMap<>();
        HashSet<Integer> childrenSet = new HashSet<>();

        for (int i = 0; i < n; i++) {
            moneyList.add(scanner.nextInt());
        }

        for (int i = 0; i < n - 1; i++) {
            int fa = scanner.nextInt();
            int ch = scanner.nextInt();
            if (!neighborDic.containsKey(fa - 1)) {
                neighborDic.put(fa - 1, new ArrayList<>());
            }
            neighborDic.get(fa - 1).add(ch - 1);
            childrenSet.add(ch - 1);
        }

        int root = -1;
        for (int i = 0; i < n; i++) {
            if (!childrenSet.contains(i)) {
                root = i;
                break;
            }
        }

        dfs(neighborDic, moneyList, root);
        System.out.println(ans);
    }
}
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
55
56
57

cpp

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

int ans = 0;

void dfs(unordered_map<int, vector<int>>& neighborDic, vector<int>& moneyList, int i) {
    // 初始化当前小家庭的财富值为moneyList[i]
    int littleFamilySum = moneyList[i];

    // 考虑所有节点i的子节点child，做两件事情：
    // 1. 对child进行递归
    // 2. 更新littleFamilySum的值
    for (int child : neighborDic[i]) {
        dfs(neighborDic, moneyList, child);
        littleFamilySum += moneyList[child];
    }

    // 更新ans
    ans = max(ans, littleFamilySum);
}

int main() {
    int n;
    cin >> n;
    vector<int> moneyList(n);
    unordered_map<int, vector<int>> neighborDic;
    unordered_set<int> childrenSet;

    for (int i = 0; i < n; i++) {
        cin >> moneyList[i];
    }

    for (int i = 0; i < n - 1; i++) {
        int fa, ch;
        cin >> fa >> ch;
        neighborDic[fa - 1].push_back(ch - 1);
        childrenSet.insert(ch - 1);
    }

    int root = -1;
    for (int i = 0; i < n; i++) {
        if (childrenSet.find(i) == childrenSet.end()) {
            root = i;
            break;
        }
    }

    dfs(neighborDic, moneyList, root);
    cout << ans << endl;

    return 0;
}
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
55
56

时空复杂度

时间复杂度：O(N)。需要遍历整棵树。

空间复杂度：O(N)，递归编译栈所占空间。

解法二：BFS

python

# 题目：2023C-寻找最富裕的小家庭
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：BFS
# 代码看不懂的地方，请直接在群上提问

from collections import defaultdict, deque

# 输入节点个数
n = int(input())
# 输入各个节点对应的财富
money_list = list(map(int, input().split()))
# 初始化邻接表
neighbor_dic = defaultdict(list)
# 储存子节点的集合，用来找根节点
children_set = set()

# 建树，输入n-1行
for _ in range(n-1):
    # 输入某一条边对应的父节点和子节点
    # 注意编号是从1开始的，为了方便使用，可以令所有的编号-1
    # 使得编号从0开始
    fa, ch = map(int, input().split())
    # 父节点的邻接表延长
    neighbor_dic[fa-1].append(ch-1)
    # ch是fa的子节点，必然不是根节点，存入children_set中
    children_set.add(ch-1)

# 寻找整棵树的根节点，唯一一个不位于children_set中的节点即为根节点
for i in range(n):
    if i not in children_set:
        root = i
        break


# 初始化队列，包含根节点root的编号
q = deque([root])

ans = 0
# 进行BFS搜索
while q:
    # 弹出队头节点，为当前小家庭的父节点
    node = q.popleft()
    # 初始化当前小家庭的财富值为money_list[node]
    little_family_sum = money_list[node]
    # 遍历node的所有子节点child，做两件事情：
    # 1. 令child入队
    # 2. 更新little_family_sum的值
    for child in neighbor_dic[node]:
        q.append(child)
        little_family_sum += money_list[child]
    # 更新ans
    ans = max(ans, little_family_sum)

print(ans)
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
55

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] moneyList = new int[n];
        Map<Integer, List<Integer>> neighborDic = new HashMap<>();
        Set<Integer> childrenSet = new HashSet<>();

        for (int i = 0; i < n; i++) {
            moneyList[i] = scanner.nextInt();
            neighborDic.put(i, new ArrayList<>());
        }

        for (int i = 0; i < n - 1; i++) {
            int fa = scanner.nextInt() - 1;
            int ch = scanner.nextInt() - 1;
            neighborDic.get(fa).add(ch);
            childrenSet.add(ch);
        }

        int root = 0;
        for (int i = 0; i < n; i++) {
            if (!childrenSet.contains(i)) {
                root = i;
                break;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(root);

        int ans = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            int littleFamilySum = moneyList[node];
            for (int child : neighborDic.get(node)) {
                queue.offer(child);
                littleFamilySum += moneyList[child];
            }
            ans = Math.max(ans, littleFamilySum);
        }

        System.out.println(ans);
    }
}
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

cpp

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <set>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> moneyList(n);
    unordered_map<int, vector<int>> neighborDic;
    set<int> childrenSet;

    for (int i = 0; i < n; ++i) {
        cin >> moneyList[i];
        neighborDic[i] = vector<int>();
    }

    for (int i = 0; i < n - 1; ++i) {
        int fa, ch;
        cin >> fa >> ch;
        neighborDic[fa - 1].push_back(ch - 1);
        childrenSet.insert(ch - 1);
    }

    int root = 0;
    for (int i = 0; i < n; ++i) {
        if (childrenSet.find(i) == childrenSet.end()) {
            root = i;
            break;
        }
    }

    queue<int> q;
    q.push(root);

    int ans = 0;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        int littleFamilySum = moneyList[node];
        for (int child : neighborDic[node]) {
            q.push(child);
            littleFamilySum += moneyList[child];
        }
        ans = max(ans, littleFamilySum);
    }

    cout << ans << endl;

    return 0;
}
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

时空复杂度

时间复杂度：O(N)。需要遍历整棵树。

空间复杂度：O(N)。q最大所占空间。

解法三：直接模拟（最简单）

python

# 题目：2023C-寻找最富裕的小家庭
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：直接模拟
# 代码看不懂的地方，请直接在群上提问


# 输入节点个数
n = int(input())
# 输入各个节点对应的财富
money_list = list(map(int, input().split()))
# 构建小家庭财富列表，初始化为每一个节点i的财富
# little_family_list[i]表示以节点i为父节点的小家庭的财富
little_family_list = money_list.copy()

# 输入n-1行
for _ in range(n-1):
    # 输入某一条边对应的父节点和子节点
    # 注意编号是从1开始的，为了方便使用，可以令所有的编号-1
    # 使得编号从0开始
    fa, ch = map(int, input().split())
    little_family_list[fa-1] += money_list[ch-1]

# 取little_family_list中的最大值即可
print(max(little_family_list))
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

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] moneyList = new int[n];
        int[] littleFamilyList = new int[n];

        for (int i = 0; i < n; i++) {
            moneyList[i] = scanner.nextInt();
            littleFamilyList[i] = moneyList[i];
        }

        for (int i = 0; i < n - 1; i++) {
            int fa = scanner.nextInt();
            int ch = scanner.nextInt();
            littleFamilyList[fa - 1] += moneyList[ch - 1];
        }

        int maxWealth = Integer.MIN_VALUE;
        for (int wealth : littleFamilyList) {
            maxWealth = Math.max(maxWealth, wealth);
        }

        System.out.println(maxWealth);
    }
}
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

JavaScript

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
 
void (async function () {
  const n = parseInt(await readline());
  const moneyList = (await readline()).split(" ").map(Number);
  const littleFamilyList = [...moneyList];
 
  for (let i = 0; i < n - 1; i++) {
    const [fa, ch] = (await readline()).split(" ").map(Number);
    littleFamilyList[fa-1] += moneyList[ch-1];
  }
 
  console.log(Math.max(...littleFamilyList));
})();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> moneyList(n);
    vector<int> littleFamilyList(n);

    for (int i = 0; i < n; i++) {
        cin >> moneyList[i];
        littleFamilyList[i] = moneyList[i];
    }

    for (int i = 0; i < n - 1; i++) {
        int fa, ch;
        cin >> fa >> ch;
        littleFamilyList[fa - 1] += moneyList[ch - 1];
    }

    int maxWealth = *max_element(littleFamilyList.begin(), littleFamilyList.end());
    cout << maxWealth << endl;

    return 0;
}
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

时空复杂度

时间复杂度：O(N)。需要遍历所有边。

空间复杂度：O(N)。little_family_list所占空间。

华为OD算法/大厂面试高频题算法练习冲刺训练

华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务300+同学成功上岸！
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！
60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
可查看链接大厂真题汇总 & OD真题汇总(持续更新)
绿色聊天软件戳 od1336了解更多

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/645784

【Py/Java/C++三种语言OD独家2024D卷真题】20天拿下华为OD笔试之【DFS/BFS】2024D-寻找最富裕的小家庭【欧弟算法】全网注释最详细分类最全的华为OD真题题解

文章目录

题目描述与示例

题目描述

输入描述

输出描述

示例

输入

输出

说明

解题思路

常规搜索解法

无需搜索的简单解法

代码

解法一：DFS

python

java

cpp

时空复杂度

解法二：BFS

python

java

cpp

时空复杂度

解法三：直接模拟（最简单）

python

java

JavaScript

cpp

时空复杂度

华为OD算法/大厂面试高频题算法练习冲刺训练