news 2026/4/27 19:34:32

华为OD新系统机试真题 4.26 - 项目模块依赖构建顺序规划

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
华为OD新系统机试真题 4.26 - 项目模块依赖构建顺序规划

华为OD新系统机试真题 - 项目模块依赖构建顺序规划(C/C++/Py/Java/Js/Go)

华为OD机试真题 华为OD上机考试真题 4月26号 200分题型

华为OD机试真题目录点击查看: 华为OD机试真题题库目录｜机考题库 + 算法考点详解

题目描述

某公司正在开发一个大型软件系统，系统包含 N个模块，每个模块之间存在构建依赖关系。例如，模块 A 可能依赖于模块 B，这意味着必须先构建模块 B，才能构建模块 A。

请根据依赖关系，输出所有可能的模块构建顺序（按照构建顺序排列模块名称），要求：

  1. 每个合法的构建顺序作为一个结果
  2. 多个结果按字典序排序后输出
  3. 如果存在循环依赖（依赖成环的情况），则说明没有合法的构建顺序，返回NULL

输入描述

第一行输入：所有模块名称，模块名只会由数字、大写字母、小写字母构成，无分隔符。模块名称互不相同。（模块数量 N≤100）多个模块之间使用逗号分割。

第二行输入依赖关系，每个依赖关系为依赖模块,被依赖模块，表示前者依赖后者。被依赖模块必须在依赖模块之前构建。多个依赖关系使用空格分割。依赖关系数量 <100

输出描述

输出所有合法的构建顺序，模块之间用空格分隔，按字典序排序。（保证合法构建顺序结果 <10!）存在循环依赖时输出NULL

10!=10×9×8×7×6×5×4×3×2×1

用例1

输入

user,auth,database,api user,auth auth,database api,database

输出

database api auth user database auth api user database auth user api

说明

依赖关系：user→auth→database，api→database

database所有模块都依赖，需要第一个构建

合法拓扑排序有 3种，按字典序排序后输出

用例2

输入

A,B,C A,B B,C C,A

输出

NULL

说明

形成环 A→B→C→A，存在循环依赖，无法完成构建，输出NULL。

题解

思路：拓扑排序 + 递归回溯

  1. 这道题本质是带限制的合法路径枚举， 路径枚举采用递归回溯实现，题目限制的每个模块之间存在构建依赖关系。例如，模块 A 可能依赖于模块 B，这意味着必须先构建模块 B，才能构建模块 A。通过拓扑排序中的入度进行解决。
  2. 本题的具体实现步骤为：
    • 通过给出依赖构建有向图，统计每个模块的入度(有多少前置模块数量)
    • 通过递归回溯枚举所有合法路径，当枚举路径模块数量 == 总模块数量时结束
      • 按从前往后选择入度为0的路径加入当前枚举路径
      • 更新其后置模块的入度
      • 递归进行搜索
      • 回溯状态
    • 最后对当前结果按照字典序排序。

c++

#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<unordered_map> #include<set> using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vector<string> split(const string& str, const string& delimiter) { vector<string> result; size_t start = 0; size_t end = str.find(delimiter); while (end != string::npos) { result.push_back(str.substr(start, end - start)); start = end + delimiter.length(); end = str.find(delimiter, start); } // 添加最后一个部分 result.push_back(str.substr(start)); return result; } void dfs(vector<string>& name, unordered_map<string, vector<string>>& graph, unordered_map<string, int>& indegree, vector<string>& path, vector<string>& res) { if (path.size() == name.size()) { string currentPath; for (int i = 0; i < name.size(); i++) { currentPath += path[i]; if (i != name.size() - 1) { currentPath += " "; } } res.push_back(currentPath); return; } for (auto& currentName : name) { if (indegree[currentName] != 0) { continue; } indegree[currentName] = -1; path.push_back(currentName); // 更新被依赖入度 for (auto& nx : graph[currentName]) { indegree[nx]--; } dfs(name, graph, indegree, path, res); // 回溯 // 恢复入度 for (auto& nx : graph[currentName]) { indegree[nx]++; } path.pop_back(); indegree[currentName] = 0; } } vector<string> getAllBuid(vector<string>& name, vector<vector<string>>& dependencyGraph) { unordered_map<string, vector<string>> graph; // 统计入度 unordered_map<string, int> indegree; for (auto& n : name) { indegree[n] = 0; } // 用于边去重 set<pair<string, string>> edges; // 处理边和入度 for (auto& dependency : dependencyGraph) { string a = dependency[0]; string b = dependency[1]; if (!edges.count({b, a})) { edges.insert({b,a}); graph[b].push_back(a); indegree[a]++; } } vector<string> res; vector<string> path; dfs(name, graph, indegree, path, res); // 结果排序 sort(res.begin(), res.end()); return res; } int main() { string input1; string input2; getline(cin, input1); getline(cin, input2); vector<string> name = split(input1, ","); vector<string> dependency = split(input2, " "); vector<vector<string>> dependencyGraph; for (int i = 0; i < dependency.size(); i++) { dependencyGraph.push_back(split(dependency[i], ",")); } vector<string> res = getAllBuid(name, dependencyGraph); if (res.empty()) { cout << "NULL"; return 0; } // 输出结果 for (auto seq : res) { cout << seq << endl; } return 0; }

JAVA

import java.util.*; public class Main { // DFS 搜索所有拓扑排序结果 static void dfs(List<String> name, Map<String, List<String>> graph, Map<String, Integer> indegree, List<String> path, List<String> res) { if (path.size() == name.size()) { StringBuilder currentPath = new StringBuilder(); for (int i = 0; i < name.size(); i++) { currentPath.append(path.get(i)); if (i != name.size() - 1) { currentPath.append(" "); } } res.add(currentPath.toString()); return; } for (String currentName : name) { if (indegree.get(currentName) != 0) continue; indegree.put(currentName, -1); path.add(currentName); // 更新被依赖入度 for (String nx : graph.getOrDefault(currentName, new ArrayList<>())) { indegree.put(nx, indegree.get(nx) - 1); } dfs(name, graph, indegree, path, res); // 回溯：恢复入度 for (String nx : graph.getOrDefault(currentName, new ArrayList<>())) { indegree.put(nx, indegree.get(nx) + 1); } path.remove(path.size() - 1); indegree.put(currentName, 0); } } static List<String> getAllBuild(List<String> name, List<List<String>> dependencyGraph) { Map<String, List<String>> graph = new HashMap<>(); Map<String, Integer> indegree = new HashMap<>(); // 初始化入度 for (String n : name) { indegree.put(n, 0); } // 边去重 Set<String> edges = new HashSet<>(); for (List<String> dep : dependencyGraph) { String a = dep.get(0); String b = dep.get(1); String key = b + "->" + a; if (!edges.contains(key)) { edges.add(key); graph.computeIfAbsent(b, k -> new ArrayList<>()).add(a); indegree.put(a, indegree.get(a) + 1); } } List<String> res = new ArrayList<>(); dfs(name, graph, indegree, new ArrayList<>(), res); // 结果排序 Collections.sort(res); return res; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String input1 = sc.nextLine(); String input2 = sc.nextLine(); List<String> name = Arrays.asList(input1.split(",")); String[] deps = input2.split(" "); List<List<String>> dependencyGraph = new ArrayList<>(); for (String d : deps) { dependencyGraph.add(Arrays.asList(d.split(","))); } List<String> res = getAllBuild(name, dependencyGraph); if (res.isEmpty()) { System.out.print("NULL"); return; } for (String s : res) { System.out.println(s); } } }

Python

importsys# DFS 搜索所有拓扑排序结果defdfs(name,graph,indegree,path,res):iflen(path)==len(name):# 拼接路径res.append(" ".join(path))returnforcurrentinname:ifindegree[current]!=0:continueindegree[current]=-1path.append(current)# 更新被依赖入度fornxingraph.get(current,[]):indegree[nx]-=1dfs(name,graph,indegree,path,res)# 回溯：恢复入度fornxingraph.get(current,[]):indegree[nx]+=1path.pop()indegree[current]=0defgetAllBuild(name,dependencyGraph):graph={}indegree={}# 初始化入度forninname:indegree[n]=0edges=set()# 构建图 + 边去重fora,bindependencyGraph:if(b,a)notinedges:edges.add((b,a))graph.setdefault(b,[]).append(a)indegree[a]+=1res=[]dfs(name,graph,indegree,[],res)res.sort()returnresif__name__=="__main__":input1=sys.stdin.readline().strip()input2=sys.stdin.readline().strip()name=input1.split(",")deps=input2.split()dependencyGraph=[d.split(",")fordindeps]res=getAllBuild(name,dependencyGraph)ifnotres:print("NULL")else:forrinres:print(r)

JavaScript

constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});letlines=[];rl.on('line',(line)=>{lines.push(line);});rl.on('close',()=>{// DFS 搜索所有拓扑排序结果functiondfs(name,graph,indegree,path,res){if(path.length===name.length){res.push(path.join(" "));return;}for(letcurrentofname){if(indegree[current]!==0)continue;indegree[current]=-1;path.push(current);// 更新被依赖入度for(letnxof(graph[current]||[])){indegree[nx]--;}dfs(name,graph,indegree,path,res);// 回溯：恢复入度for(letnxof(graph[current]||[])){indegree[nx]++;}path.pop();indegree[current]=0;}}functiongetAllBuild(name,dependencyGraph){letgraph={};letindegree={};// 初始化入度for(letnofname){indegree[n]=0;}letedges=newSet();for(let[a,b]ofdependencyGraph){letkey=b+"->"+a;if(!edges.has(key)){edges.add(key);if(!graph[b])graph[b]=[];graph[b].push(a);indegree[a]++;}}letres=[];dfs(name,graph,indegree,[],res);res.sort();returnres;}letname=lines[0].split(",");letdeps=lines[1].split(" ");letdependencyGraph=deps.map(d=>d.split(","));letres=getAllBuild(name,dependencyGraph);if(res.length===0){console.log("NULL");}else{res.forEach(r=>console.log(r));}});

Go

packagemainimport("bufio""fmt""os""sort""strings")// DFS 搜索所有拓扑排序结果funcdfs(name[]string,graphmap[string][]string,indegreemap[string]int,path[]string,res*[]string){iflen(path)==len(name){*res=append(*res,strings.Join(path," "))return}for_,current:=rangename{ifindegree[current]!=0{continue}indegree[current]=-1path=append(path,current)// 更新被依赖入度for_,nx:=rangegraph[current]{indegree[nx]--}dfs(name,graph,indegree,path,res)// 回溯：恢复入度for_,nx:=rangegraph[current]{indegree[nx]++}path=path[:len(path)-1]indegree[current]=0}}funcgetAllBuild(name[]string,dependencyGraph[][]string)[]string{graph:=make(map[string][]string)indegree:=make(map[string]int)// 初始化入度for_,n:=rangename{indegree[n]=0}edges:=make(map[string]bool)for_,dep:=rangedependencyGraph{a,b:=dep[0],dep[1]key:=b+"->"+aif!edges[key]{edges[key]=truegraph[b]=append(graph[b],a)indegree[a]++}}res:=[]string{}dfs(name,graph,indegree,[]string{},&res)sort.Strings(res)returnres}funcmain(){scanner:=bufio.NewScanner(os.Stdin)scanner.Scan()input1:=scanner.Text()scanner.Scan()input2:=scanner.Text()name:=strings.Split(input1,",")deps:=strings.Split(input2," ")vardependencyGraph[][]stringfor_,d:=rangedeps{dependencyGraph=append(dependencyGraph,strings.Split(d,","))}res:=getAllBuild(name,dependencyGraph)iflen(res)==0{fmt.Println("NULL")return}for_,r:=rangeres{fmt.Println(r)}}

C语言

#include<stdio.h>#include<string.h>#include<stdlib.h>#defineMAXN105charnames[MAXN][20];intn;// 图（邻接矩阵）intgraph[MAXN][MAXN];// 入度intindegree[MAXN];// 路径intpath[MAXN];intused[MAXN];// 结果存储charres[400000][200];intresSize=0;// 字符串排序（保证字典序）intcmp(constvoid*a,constvoid*b){returnstrcmp((char*)a,(char*)b);}// DFS 搜索所有拓扑排序结果voiddfs(intdepth){if(depth==n){// 拼接路径chartemp[200]={0};for(inti=0;i<n;i++){strcat(temp,names[path[i]]);if(i!=n-1)strcat(temp," ");}strcpy(res[resSize++],temp);return;}for(inti=0;i<n;i++){if(indegree[i]!=0||used[i])continue;used[i]=1;path[depth]=i;// 更新被依赖入度for(intj=0;j<n;j++){if(graph[i][j])indegree[j]--;}dfs(depth+1);// 回溯恢复for(intj=0;j<n;j++){if(graph[i][j])indegree[j]++;}used[i]=0;}}intmain(){charinput1[10000],input2[10000];fgets(input1,sizeof(input1),stdin);fgets(input2,sizeof(input2),stdin);// 解析模块名char*token=strtok(input1,",\n");while(token){strcpy(names[n++],token);token=strtok(NULL,",\n");}// 解析依赖关系token=strtok(input2," \n");while(token){chara[20],b[20];sscanf(token,"%[^,],%s",a,b);intai=-1,bi=-1;for(inti=0;i<n;i++){if(strcmp(names[i],a)==0)ai=i;if(strcmp(names[i],b)==0)bi=i;}if(bi!=-1&&ai!=-1){graph[bi][ai]=1;indegree[ai]++;}token=strtok(NULL," \n");}qsort(names,n,sizeof(names[0]),cmp);dfs(0);if(resSize==0){printf("NULL\n");return0;}for(inti=0;i<resSize;i++){printf("%s\n",res[i]);}return0;}
版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/4/27 19:33:31

C语言写传感器驱动的7个致命错误（92%农用IoT项目因第4条返工超3轮）

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;C语言农业物联网传感器驱动开发概述 在智慧农业场景中&#xff0c;C语言因其高效性、可移植性与对底层硬件的精细控制能力&#xff0c;成为传感器驱动开发的首选语言。农业物联网节点常运行于资源受限的…

作者头像 李华
网站建设 2026/4/27 19:31:23

让你的Windows任务栏焕然一新：TranslucentTB透明化美化全攻略

让你的Windows任务栏焕然一新&#xff1a;TranslucentTB透明化美化全攻略 【免费下载链接】TranslucentTB A lightweight utility that makes the Windows taskbar translucent/transparent. 项目地址: https://gitcode.com/gh_mirrors/tr/TranslucentTB 你是否厌倦了Wi…

作者头像 李华
网站建设 2026/4/27 19:31:19

阿里巴巴最新Spring全家桶学习笔记全网首次公开！

Spring框架自从诞生以来就一直备受开发者青睐&#xff0c;它涵盖了Spring、Springboot、SpringCloud等诸多解决方案&#xff0c;一般我们都会统称为Spring全家桶&#xff01;出于Spring框架在Java开发者心中中的统治地位&#xff0c;所以不管是面试还是工作&#xff0c;Spring都…

作者头像 李华
网站建设 2026/4/27 19:27:29

STM32+ESP8266项目复盘：我的温室监控系统踩了哪些坑？

STM32ESP8266温室监控系统实战复盘&#xff1a;从硬件选型到云上传的避坑指南 去年夏天&#xff0c;我接手了一个智能温室监控系统的开发项目。客户要求实时监测温湿度、土壤墒情、光照和CO2浓度&#xff0c;并通过WiFi上传到云端。听起来像是典型的物联网应用&#xff0c;但实…

作者头像 李华
网站建设 2026/4/27 19:26:28

LLM在软件开发中的挑战与优化实践

1. 项目概述大型语言模型&#xff08;LLM&#xff09;正在深刻改变软件工程领域的问题解决方式。作为一名在AI和软件开发交叉领域工作多年的从业者&#xff0c;我见证了从早期基于规则的代码生成到如今GPT-4级别模型的演进过程。LLM不仅能自动补全代码片段&#xff0c;还能协助…

作者头像 李华
网站建设 2026/4/27 19:25:34

ResNet残差连接原理与深度学习实践指南

1. ResNet&#xff1a;深度学习中的捷径革命2015年&#xff0c;当ResNet在ImageNet竞赛中以3.57%的错误率首次超越人类表现时&#xff0c;整个计算机视觉领域都为之震动。这个看似简单的"残差连接"设计&#xff0c;彻底解决了困扰深度学习多年的梯度消失难题。我在实…

作者头像 李华