华为OD机试真题 新系统【Skill执行链完整性检测】
Skill执行链完整性检测(Py/Java/C/C++/Js/Go)题解
华为OD机试新系统真题 华为OD上机考试新系统真题 5月27号 100分题型
华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录｜机考题库 + 算法考点详解
题目内容
在A I AIAI助手的技能系统中，执行链由多个S k i l l SkillSkill按顺序排列。每个S k i l l SkillSkill有一个类型标记：
- t y p e [ i ] = 0 type[i] = 0type[i]=0: 基础类型S k i l l SkillSkill，无依赖，可以独立执行
- t y p e [ i ] = 1 type[i] = 1type[i]=1: 扩展类型S k i l l SkillSkill，依赖前一个S k i l l SkillSkill执行
- t y p e [ i ] = 2 type[i] = 2type[i]=2: 高级类型S k i l l SkillSkill，依赖前两个S k i l l SkillSkill执行
执行链的完整性规则：
- 首元素限制：执行链不能以扩展类型（t y p e = 1 type=1type=1）或高级类型（t y p e = 2 type=2type=2）开头，必须以基础类型（t y p e = 0 type=0type=0）开头
- 依赖传递：
- 扩展类型（t y p e = 1 type=1type=1）的直接前驱必须是基础类型（t y p e = 0 type=0type=0）
- 高级类型（t y p e = 2 type=2type=2）的前驱和前前驱都必须是基础类型（t y p e = 0 type=0type=0）
3.链式依赖：每两个相邻的基础类型之间最多允许存在一个扩展类型或高级类型
给定一个类型数组t y p e typetype，找到最长的连续S k i l l SkillSkill子链，使得子链满足完整性规则。返回该子链的长度。
数据规模0 00≤ type.length ≤2000 20002000
样例1
输入
0,0,0输出
3说明
全为基础类型,满足规则(不违反任何约束)
样例2
输入
0,1,0,1输出
4说明
0 → 1 ✓ 0 → 1 ✓0→1✓(基础后接扩展)
1 → 0 ✓ 1 → 0 ✓1→0✓(扩展后接基础)
0 → 1 ✓ 0 → 1 ✓0→1✓(基础后接扩展)
无违反规则,整个链有效
样例3
输入
2,0,0输出
2说明
首元素高级类型违规，从位置1 11开始[ 0 , 0 ] [0,0][0,0]长度2 22
样例4
输入
0,1,0,0,2输出
5说明
0 → 1 ✓ 0 → 1 ✓0→1✓(基础后接扩展)
1 → 0 ✓ 1 → 0 ✓1→0✓(扩展后接基础)
0 → 0 ✓ 0 → 0 ✓0→0✓(基础后接基础)
0 → 0 → 2 ✓ 0 →0 → 2 ✓0→0→2✓(基础、基础后接高级)
题解
思路：暴力枚举
- 由于本题数据量为
0 ≤ type.length ≤ 2000直接使用双for循环暴力枚举也不会超时。 - 第一层枚举左边界
left需要满足条件type[left] == 0,然后第二层right从left+1尝试右移，期间使用ans出现的最大长度即可。right右移逻辑如下:- 定义
lastZero记录上个0出现的位置，主要是为了进行链式依赖：每两个相邻的基础类型之间最多允许存在一个扩展类型或高级类型的判断。 - 接下来根据
value = type[right]进行判断- 当前
value == 0,并且right - lastZeroPos - 1 > 1时需要中断此时违背链式依赖限制。不中断情况下更新lastZeroPos = right - 当前
value==1，并且type[right-1] !=0需要中断 - 当前
value == 2，并且type[right - 1] != 0 或者 type[right - 2] != 0需要中断。需要注意right-2不能超过枚举起点。
- 当前
- 按照上述逻辑不存在中断就将right一直右移，不断更新
ans为合法的最大值即可。
- 定义
c++
#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vector<int> split(const string& str, const string& delimiter) { vector<int> result; size_t start = 0; size_t end = str.find(delimiter); while (end != string::npos) { result.push_back(stoi(str.substr(start, end - start))); start = end + delimiter.length(); end = str.find(delimiter, start); } // 添加最后一个部分 result.push_back(stoi(str.substr(start))); return result; } int getlengthValidSkillChain(vector<int>& type) { int ans = 0; int n = type.size(); // 枚举开头 for (int i = 0; i < n; i++) { // 必须以0开头 if (type[i] != 0) { continue; } int lastZeroPos = i; // 长度肯定不小于1 ans = max(ans, 1); // 确定能到达的最右边 for (int j = i + 1; j < n; j++) { int value =type[j]; if (value == 0) { // 相邻1之间中间存在多个1或2 if (j - lastZeroPos - 1 > 1) { break; } lastZeroPos = j; } else if (value == 1) { // 前一个不为0 if (type[j-1] != 0) { break; } } else { // 超过枚举起点 if (j - 2 < i) { break; } // 前两个不全为0 if (type[j-1] != 0 || type[j-2] != 0) { break; } } ans = max(ans, j - i + 1); } } return ans; } int main() { string input; getline(cin, input); vector<int> type; if (!input.empty()) { type = split(input, ","); } int res = getlengthValidSkillChain(type); cout << res; return 0; }Java
importjava.util.*;publicclassMain{publicstaticintgetLengthValidSkillChain(int[]type){intans=0;intn=type.length;// 枚举开头for(inti=0;i<n;i++){// 必须以0开头if(type[i]!=0){continue;}intlastZeroPos=i;// 长度肯定不小于1ans=Math.max(ans,1);// 确定能到达的最右边for(intj=i+1;j<n;j++){intvalue=type[j];if(value==0){// 相邻0之间中间存在多个1或2if(j-lastZeroPos-1>1){break;}lastZeroPos=j;}elseif(value==1){// 前一个不为0if(type[j-1]!=0){break;}}else{// 超过枚举起点if(j-2<i){break;}// 前两个不全为0if(type[j-1]!=0||type[j-2]!=0){break;}}ans=Math.max(ans,j-i+1);}}returnans;}publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);Stringinput=sc.nextLine();int[]type;if(input.length()==0){type=newint[0];}else{String[]arr=input.split(",");type=newint[arr.length];for(inti=0;i<arr.length;i++){type[i]=Integer.parseInt(arr[i]);}}System.out.println(getLengthValidSkillChain(type));}}Python
defget_length_valid_skill_chain(type_arr):ans=0n=len(type_arr)# 枚举开头foriinrange(n):# 必须以0开头iftype_arr[i]!=0:continuelast_zero_pos=i# 长度肯定不小于1ans=max(ans,1)# 确定能到达的最右边forjinrange(i+1,n):value=type_arr[j]ifvalue==0:# 相邻0之间中间存在多个1或2ifj-last_zero_pos-1>1:breaklast_zero_pos=jelifvalue==1:# 前一个不为0iftype_arr[j-1]!=0:breakelse:# 超过枚举起点ifj-2<i:break# 前两个不全为0iftype_arr[j-1]!=0ortype_arr[j-2]!=0:breakans=max(ans,j-i+1)returnans input_str=input().strip()type_arr=[]ifinput_str:type_arr=list(map(int,input_str.split(',')))print(get_length_valid_skill_chain(type_arr))JavaScript
constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});letlines=[];rl.on('line',(line)=>{lines.push(line);});rl.on('close',()=>{functiongetLengthValidSkillChain(type){letans=0;constn=type.length;// 枚举开头for(leti=0;i<n;i++){// 必须以0开头if(type[i]!==0){continue;}letlastZeroPos=i;// 长度肯定不小于1ans=Math.max(ans,1);// 确定能到达的最右边for(letj=i+1;j<n;j++){constvalue=type[j];if(value===0){// 相邻0之间中间存在多个1或2if(j-lastZeroPos-1>1){break;}lastZeroPos=j;}elseif(value===1){// 前一个不为0if(type[j-1]!==0){break;}}else{// 超过枚举起点if(j-2<i){break;}// 前两个不全为0if(type[j-1]!==0||type[j-2]!==0){break;}}ans=Math.max(ans,j-i+1);}}returnans;}constinput=lines[0].trim();lettype=[];if(input.length>0){type=input.split(',').map(Number);}console.log(getLengthValidSkillChain(type));});Go
packagemainimport("bufio""fmt""os""strconv""strings")funcgetLengthValidSkillChain(t[]int)int{ans:=0n:=len(t)// 枚举开头fori:=0;i<n;i++{// 必须以0开头ift[i]!=0{continue}lastZeroPos:=i// 长度肯定不小于1ifans<1{ans=1}// 确定能到达的最右边forj:=i+1;j<n;j++{value:=t[j]ifvalue==0{// 相邻0之间中间存在多个1或2ifj-lastZeroPos-1>1{break}lastZeroPos=j}elseifvalue==1{// 前一个不为0ift[j-1]!=0{break}}else{// 超过枚举起点ifj-2<i{break}// 前两个不全为0ift[j-1]!=0||t[j-2]!=0{break}}ifans<j-i+1{ans=j-i+1}}}returnans}funcmain(){in:=bufio.NewReader(os.Stdin)input,_:=in.ReadString('\n')input=strings.TrimSpace(input)t:=[]int{}iflen(input)>0{arr:=strings.Split(input,",")for_,s:=rangearr{num,_:=strconv.Atoi(s)t=append(t,num)}}fmt.Println(getLengthValidSkillChain(t))}C语言
#include<stdio.h>#include<string.h>#include<stdlib.h>#defineMAXN2005intsplit(char*str,intarr[]){intcnt=0;char*token=strtok(str,",");while(token){arr[cnt++]=atoi(token);token=strtok(NULL,",");}returncnt;}intgetLengthValidSkillChain(inttype[],intn){intans=0;// 枚举开头for(inti=0;i<n;i++){// 必须以0开头if(type[i]!=0){continue;}intlastZeroPos=i;// 长度肯定不小于1if(ans<1){ans=1;}// 确定能到达的最右边for(intj=i+1;j<n;j++){intvalue=type[j];if(value==0){// 相邻0之间中间存在多个1或2if(j-lastZeroPos-1>1){break;}lastZeroPos=j;}elseif(value==1){// 前一个不为0if(type[j-1]!=0){break;}}else{// 超过枚举起点if(j-2<i){break;}// 前两个不全为0if(type[j-1]!=0||type[j-2]!=0){break;}}if(ans<j-i+1){ans=j-i+1;}}}returnans;}intmain(){charinput[10005];fgets(input,sizeof(input),stdin);// 去除换行input[strcspn(input,"\n")]='\0';inttype[MAXN];intn=0;if(strlen(input)>0){n=split(input,type);}printf("%d\n",getLengthValidSkillChain(type,n));return0;}