华为OD机试 2024E卷题库疯狂收录中,刷题点这里
专栏导读
本专栏收录于《华为OD机试真题(Python/JS/C/C++)》。
刷的越多,抽中的概率越大,私信哪吒,备注华为OD,加入华为OD刷题交流群,每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景,发现新题目,随时更新,全天CSDN在线答疑。
一、题目描述
主办方设计了一个获取食物的游戏。
游戏的地图由 N×N×N 个方格组成,每个方格上至多 222 个传送门,通过传送门可将参与者传送至指定的某些方格。同时,每个方格上标注了三个数字:
- 第一个数字为 id idd: 代表方格的编号,从 000 到 N×N×N−1,每个方格各不相同;
- 第二个数字为 parent-id parent-id parent-id:代表从编号为 parent-id parent-id parent-id 的方格可以通过传送门传送到当前方格(-1-1-1 则表示没有任何方格可以通过传送门传送到此方格,这样的方格在地图中只有一个);
- 第三个数字为 value value value:取值在 [100,100] | [100,100] | [100,100] 的整数值,正整数代表参与者得到相应数值的食物,负数代表失去相应数值的食物(当某个方格有负数的情况时,000 则代表无变化)。
此外,地图设计时保证了参与者不可能通过传送门形成环次,并且至少有一个方格的 value 是正整数。
游戏结束时,参与者从任意选择一个方格为出发点,当遇到下列情况之一退出游戏:
- 参与者踏出地图的方格后传送门;
- 参与者在任意方格上主动宣布退出游戏。
请计算参与者退出游戏后,最多可以获得多少单位的食物。
二、输入描述
第一行,方块个数 N
接下来输入 N 行 (id < N parent-id < N),每行记录了相应方格上标注的3个数字,即 id (0 <= id < 10000)、parent-id (0 <= parent-id < 10000) 和 value (-100 <= value <= 100)
特殊的 parent-id 可以取 -1,则表示没有任何方格可以通过传送门传送到此方格,这样的方格在地图中有且仅有一个。
三、输出描述
输出为一个整数,表示参与者退出游戏后最多可以获得多少单位的食物。
四、测试用例
测试用例1:
1、输入
7
0 1 8
1 -1 -2
2 1 9
4 0 -2
5 4 3
3 0 -3
6 2 -3
2、输出
9
3、说明
参与者从方格 000 出发,通过传送门到达方格 444,再通过传送门到达方格 555。一共获得 8 + (-2) + 3 = 9。8+(-2)+3=9 单位食物,得到食物最多。
或者参与者在游戏开始时处于方格 222,直接主动宣布退出游戏,也可以获得 999 个单位食物。
测试用例2:
1、输入
3
0 -1 3
1 0 1
2 0 2
2、输出
5
3、说明
参与者从方格 000 出发,通过传送门到达方格 222,一共可以获得 3 + 2 = 5。3 + 2 = 5 个单位食物,此时得到食物最多。
五、解题思路
本题涉及在一个无环图(DAG)中寻找路径,使得路径上节点的数值之和最大。具体来说,参与者可以从任意一个方格出发,沿着传送门移动,最终选择退出游戏。目标是找到这样一条路径,使得路径上所有方格的数值之和最大。
1、数据结构与算法
图的表示:使用邻接表(List<List>)来表示图,其中每个节点的列表存储其子节点(即可以通过传送门到达的方格)。
节点信息存储:使用数组或映射来存储每个节点的数值(value)。
拓扑排序:由于图是无环的,可以使用拓扑排序来遍历节点。
2、为什么选择这几个数据结构?
邻接表适用于表示稀疏图,且易于进行拓扑排序和遍历。
拓扑排序确保在处理每个节点时,其所有的父节点已经被处理,便于进行动态规划。
动态规划能够高效地计算出每个节点的最大路径和,最终求得全局最大值。
3、主要步骤:
- 输入解析:读取所有方格的信息,包括 id、parent-id 和 value。
- 图构建:根据 parent-id 构建图的邻接表。每个 parent-id 指向其子节点 id。
- 拓扑排序:计算每个节点的入度,使用队列进行拓扑排序,确保节点按依赖顺序处理。
- 动态规划:
- 初始化每个节点的最大食物数为其自身的 value。
- 按拓扑顺序遍历每个节点,更新其子节点的最大食物数为 当前节点的最大食物数 + 子节点的 value(如果更大)。
- 结果计算:遍历所有节点的最大食物数,找出其中的最大值即为最终结果。
4、关键点注意
无环保证:题目保证了图中不存在环,这使得拓扑排序成为可行的方案。
多起点:参与者可以从任意节点出发,因此需要初始化每个节点的最大食物数为其自身的 value。
负数处理:路径上的某些节点可能会减少总食物数,但由于参与者可以选择随时退出,因此路径的最大和可能不包括所有节点。
六、Python算法源码
# 导入所需的模块
import sys
from collections import dequedef main():# 读取所有输入并按行分割input_lines = sys.stdin.read().splitlines()# 如果没有输入,直接返回if not input_lines:print(0)return# 读取方块个数 NN = int(input_lines[0].strip())# 初始化数组存储每个节点的 value,假设 id 范围为 0 到 9999values = [0] * 10000# 初始化邻接表,存储每个节点的子节点graph = [[] for _ in range(10000)]# 初始化集合记录所有节点的 idnodeIds = set()# 初始化数组记录每个节点的入度inDegree = [0] * 10000# 逐行读取 N 行方块信息for i in range(1, N + 1):parts = input_lines[i].strip().split()id = int(parts[0]) # 方块编号parentId = int(parts[1]) # 父方块编号value = int(parts[2]) # 方块的 valuevalues[id] = value # 存储方块的 valuenodeIds.add(id) # 记录方块的 id# 如果 parentId 不为 -1,构建图的边并更新入度if parentId != -1:graph[parentId].append(id) # parentId 指向 idinDegree[id] += 1 # 增加 id 的入度# 初始化队列用于拓扑排序queue = deque()# 初始化最大食物数数组,每个节点的初始最大食物数为其自身的 valuemaxFood = [0] * 10000for id in nodeIds:maxFood[id] = values[id] # 设置初始值if inDegree[id] == 0:queue.append(id) # 入度为 0 的节点入队# 初始化全局最大食物数为最小可能值globalMax = -float('inf')# 进行拓扑排序并计算最大食物数while queue:current = queue.popleft() # 获取当前节点if maxFood[current] > globalMax:globalMax = maxFood[current] # 更新全局最大食物数# 遍历当前节点的所有子节点for child in graph[current]:# 如果通过当前节点到子节点的路径更优,更新子节点的最大食物数if maxFood[current] + values[child] > maxFood[child]:maxFood[child] = maxFood[current] + values[child]inDegree[child] -= 1 # 减少子节点的入度if inDegree[child] == 0:queue.append(child) # 入度为 0 的子节点入队# 输出全局最大食物数print(globalMax)# 调用主函数
if __name__ == "__main__":main()
七、JavaScript算法源码
// 使用 Node.js 的 readline 模块读取标准输入
const readline = require('readline');// 创建接口实例
const rl = readline.createInterface({input: process.stdin,output: process.stdout,terminal: false
});let inputLines = []; // 存储输入的每一行// 监听每一行输入
rl.on('line', function(line){inputLines.push(line.trim()); // 去除首尾空白并存储
}).on('close', function(){// 如果没有输入,输出 0 并退出if(inputLines.length === 0){console.log(0);return;}// 读取方块个数 Nconst N = parseInt(inputLines[0]);// 初始化数组存储每个节点的 value,假设 id 范围为 0 到 9999const values = Array(10000).fill(0);// 初始化邻接表,存储每个节点的子节点const graph = Array.from({length: 10000}, () => []);// 初始化集合记录所有节点的 idconst nodeIds = new Set();// 初始化数组记录每个节点的入度const inDegree = Array(10000).fill(0);// 逐行读取 N 行方块信息for(let i = 1; i <= N; i++){const parts = inputLines[i].split(/\s+/);const id = parseInt(parts[0]); // 方块编号const parentId = parseInt(parts[1]); // 父方块编号const value = parseInt(parts[2]); // 方块的 valuevalues[id] = value; // 存储方块的 valuenodeIds.add(id); // 记录方块的 id// 如果 parentId 不为 -1,构建图的边并更新入度if(parentId !== -1){graph[parentId].push(id); // parentId 指向 idinDegree[id] += 1; // 增加 id 的入度}}// 初始化队列用于拓扑排序const queue = [];// 初始化最大食物数数组,每个节点的初始最大食物数为其自身的 valueconst maxFood = Array(10000).fill(0);nodeIds.forEach(id => {maxFood[id] = values[id]; // 设置初始值if(inDegree[id] === 0){queue.push(id); // 入度为 0 的节点入队}});// 初始化全局最大食物数为最小可能值let globalMax = -Infinity;// 进行拓扑排序并计算最大食物数while(queue.length > 0){const current = queue.shift(); // 获取当前节点if(maxFood[current] > globalMax){globalMax = maxFood[current]; // 更新全局最大食物数}// 遍历当前节点的所有子节点graph[current].forEach(child => {// 如果通过当前节点到子节点的路径更优,更新子节点的最大食物数if(maxFood[current] + values[child] > maxFood[child]){maxFood[child] = maxFood[current] + values[child];}inDegree[child] -= 1; // 减少子节点的入度if(inDegree[child] === 0){queue.push(child); // 入度为 0 的子节点入队}});}// 输出全局最大食物数console.log(globalMax);
});
八、C算法源码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>// 定义最大方块数量和最大ID
#define MAX_BLOCKS 10000
#define MAX_LINE_LENGTH 100int main(){int N;// 读取方块个数 Nif(scanf("%d", &N) != 1){// 如果读取失败,输出0并退出printf("0\n");return 0;}// 初始化数组存储每个节点的 value,假设 id 范围为 0 到 9999int values[MAX_BLOCKS];memset(values, 0, sizeof(values));// 初始化邻接表,使用二维数组存储每个节点的子节点int graph[MAX_BLOCKS][222]; // 每个节点最多有222个子节点int graphSize[MAX_BLOCKS];memset(graphSize, 0, sizeof(graphSize));// 初始化数组记录每个节点的入度int inDegree[MAX_BLOCKS];memset(inDegree, 0, sizeof(inDegree));// 初始化数组记录节点是否存在int exists[MAX_BLOCKS];memset(exists, 0, sizeof(exists));char line[MAX_LINE_LENGTH];// 逐行读取 N 行方块信息for(int i = 0; i < N; i++){if(scanf("%s", line) != 1){// 如果读取失败,跳过continue;}// 使用 sscanf 解析 id, parentId, valueint id, parentId, value;sscanf(line, "%d %d %d", &id, &parentId, &value);values[id] = value; // 存储方块的 valueexists[id] = 1; // 标记节点存在// 如果 parentId 不为 -1,构建图的边并更新入度if(parentId != -1){graph[parentId][graphSize[parentId]++] = id; // parentId 指向 idinDegree[id]++; // 增加 id 的入度}}// 初始化队列用于拓扑排序,使用数组模拟队列int queue[MAX_BLOCKS];int front = 0, rear = 0;// 初始化最大食物数数组,每个节点的初始最大食物数为其自身的 valueint maxFood[MAX_BLOCKS];for(int i = 0; i < MAX_BLOCKS; i++){if(exists[i]){maxFood[i] = values[i]; // 设置初始值if(inDegree[i] == 0){queue[rear++] = i; // 入度为 0 的节点入队}}}// 初始化全局最大食物数为最小可能值int globalMax = -1000000; // 根据题目,最小可能为 -100 * N// 进行拓扑排序并计算最大食物数while(front < rear){int current = queue[front++]; // 获取当前节点if(maxFood[current] > globalMax){globalMax = maxFood[current]; // 更新全局最大食物数}// 遍历当前节点的所有子节点for(int i = 0; i < graphSize[current]; i++){int child = graph[current][i];// 如果通过当前节点到子节点的路径更优,更新子节点的最大食物数if(maxFood[current] + values[child] > maxFood[child]){maxFood[child] = maxFood[current] + values[child];}inDegree[child]--; // 减少子节点的入度if(inDegree[child] == 0){queue[rear++] = child; // 入度为 0 的子节点入队}}}// 输出全局最大食物数printf("%d\n", globalMax);return 0;
}
九、C++算法源码
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(0);int N;// 读取方块个数 Ncin >> N;// 初始化数组存储每个节点的 value,假设 id 范围为 0 到 9999int values[10000];memset(values, 0, sizeof(values));// 初始化邻接表,存储每个节点的子节点vector<vector<int>> graph(10000, vector<int>());// 初始化数组记录每个节点的入度int inDegree[10000];memset(inDegree, 0, sizeof(inDegree));// 初始化数组记录节点是否存在bool exists[10000];memset(exists, false, sizeof(exists));// 逐行读取 N 行方块信息for(int i = 0; i < N; i++){int id, parentId, value;cin >> id >> parentId >> value;values[id] = value; // 存储方块的 valueexists[id] = true; // 标记节点存在// 如果 parentId 不为 -1,构建图的边并更新入度if(parentId != -1){graph[parentId].push_back(id); // parentId 指向 idinDegree[id]++; // 增加 id 的入度}}// 初始化队列用于拓扑排序queue<int> q;// 初始化最大食物数数组,每个节点的初始最大食物数为其自身的 valueint maxFood[10000];for(int i = 0; i < 10000; i++){if(exists[i]){maxFood[i] = values[i]; // 设置初始值if(inDegree[i] == 0){q.push(i); // 入度为 0 的节点入队}}}// 初始化全局最大食物数为最小可能值int globalMax = INT32_MIN;// 进行拓扑排序并计算最大食物数while(!q.empty()){int current = q.front(); q.pop(); // 获取当前节点if(maxFood[current] > globalMax){globalMax = maxFood[current]; // 更新全局最大食物数}// 遍历当前节点的所有子节点for(auto &child : graph[current]){// 如果通过当前节点到子节点的路径更优,更新子节点的最大食物数if(maxFood[current] + values[child] > maxFood[child]){maxFood[child] = maxFood[current] + values[child];}inDegree[child]--; // 减少子节点的入度if(inDegree[child] == 0){q.push(child); // 入度为 0 的子节点入队}}}// 输出全局最大食物数cout << globalMax << "\n";return 0;
}
🏆下一篇:华为OD机试真题 - 简易内存池(Python/JS/C/C++ 2024 E卷 200分)
🏆本文收录于,华为OD机试真题(Python/JS/C/C++)
刷的越多,抽中的概率越大,私信哪吒,备注华为OD,加入华为OD刷题交流群,每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景,发现新题目,随时更新,全天CSDN在线答疑。