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 type1type1或高级类型t y p e 2 type2type2开头必须以基础类型t y p e 0 type0type0开头依赖传递扩展类型t y p e 1 type1type1的直接前驱必须是基础类型t y p e 0 type0type0高级类型t y p e 2 type2type2的前驱和前前驱都必须是基础类型t y p e 0 type0type03.链式依赖每两个相邻的基础类型之间最多允许存在一个扩展类型或高级类型给定一个类型数组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从left1尝试右移期间使用ans出现的最大长度即可。right右移逻辑如下:定义lastZero记录上个0出现的位置主要是为了进行链式依赖每两个相邻的基础类型之间最多允许存在一个扩展类型或高级类型的判断。接下来根据value type[right]进行判断当前value 0,并且right - lastZeroPos - 1 1时需要中断此时违背链式依赖限制。不中断情况下更新lastZeroPos right当前value1并且type[right-1] !0需要中断当前value 2并且type[right - 1] ! 0 或者 type[right - 2] ! 0需要中断。需要注意right-2不能超过枚举起点。按照上述逻辑不存在中断就将right一直右移不断更新ans为合法的最大值即可。c#includeiostream #includevector #includestring #include utility #include sstream #includealgorithm #includecmath #includemap using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vectorint split(const string str, const string delimiter) { vectorint 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(vectorint 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); vectorint type; if (!input.empty()) { type split(input, ,); } int res getlengthValidSkillChain(type); cout res; return 0; }Javaimportjava.util.*;publicclassMain{publicstaticintgetLengthValidSkillChain(int[]type){intans0;intntype.length;// 枚举开头for(inti0;in;i){// 必须以0开头if(type[i]!0){continue;}intlastZeroPosi;// 长度肯定不小于1ansMath.max(ans,1);// 确定能到达的最右边for(intji1;jn;j){intvaluetype[j];if(value0){// 相邻0之间中间存在多个1或2if(j-lastZeroPos-11){break;}lastZeroPosj;}elseif(value1){// 前一个不为0if(type[j-1]!0){break;}}else{// 超过枚举起点if(j-2i){break;}// 前两个不全为0if(type[j-1]!0||type[j-2]!0){break;}}ansMath.max(ans,j-i1);}}returnans;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);Stringinputsc.nextLine();int[]type;if(input.length()0){typenewint[0];}else{String[]arrinput.split(,);typenewint[arr.length];for(inti0;iarr.length;i){type[i]Integer.parseInt(arr[i]);}}System.out.println(getLengthValidSkillChain(type));}}Pythondefget_length_valid_skill_chain(type_arr):ans0nlen(type_arr)# 枚举开头foriinrange(n):# 必须以0开头iftype_arr[i]!0:continuelast_zero_posi# 长度肯定不小于1ansmax(ans,1)# 确定能到达的最右边forjinrange(i1,n):valuetype_arr[j]ifvalue0:# 相邻0之间中间存在多个1或2ifj-last_zero_pos-11:breaklast_zero_posjelifvalue1:# 前一个不为0iftype_arr[j-1]!0:breakelse:# 超过枚举起点ifj-2i:break# 前两个不全为0iftype_arr[j-1]!0ortype_arr[j-2]!0:breakansmax(ans,j-i1)returnans input_strinput().strip()type_arr[]ifinput_str:type_arrlist(map(int,input_str.split(,)))print(get_length_valid_skill_chain(type_arr))JavaScriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letlines[];rl.on(line,(line){lines.push(line);});rl.on(close,(){functiongetLengthValidSkillChain(type){letans0;constntype.length;// 枚举开头for(leti0;in;i){// 必须以0开头if(type[i]!0){continue;}letlastZeroPosi;// 长度肯定不小于1ansMath.max(ans,1);// 确定能到达的最右边for(letji1;jn;j){constvaluetype[j];if(value0){// 相邻0之间中间存在多个1或2if(j-lastZeroPos-11){break;}lastZeroPosj;}elseif(value1){// 前一个不为0if(type[j-1]!0){break;}}else{// 超过枚举起点if(j-2i){break;}// 前两个不全为0if(type[j-1]!0||type[j-2]!0){break;}}ansMath.max(ans,j-i1);}}returnans;}constinputlines[0].trim();lettype[];if(input.length0){typeinput.split(,).map(Number);}console.log(getLengthValidSkillChain(type));});Gopackagemainimport(bufiofmtosstrconvstrings)funcgetLengthValidSkillChain(t[]int)int{ans:0n:len(t)// 枚举开头fori:0;in;i{// 必须以0开头ift[i]!0{continue}lastZeroPos:i// 长度肯定不小于1ifans1{ans1}// 确定能到达的最右边forj:i1;jn;j{value:t[j]ifvalue0{// 相邻0之间中间存在多个1或2ifj-lastZeroPos-11{break}lastZeroPosj}elseifvalue1{// 前一个不为0ift[j-1]!0{break}}else{// 超过枚举起点ifj-2i{break}// 前两个不全为0ift[j-1]!0||t[j-2]!0{break}}ifansj-i1{ansj-i1}}}returnans}funcmain(){in:bufio.NewReader(os.Stdin)input,_:in.ReadString(\n)inputstrings.TrimSpace(input)t:[]int{}iflen(input)0{arr:strings.Split(input,,)for_,s:rangearr{num,_:strconv.Atoi(s)tappend(t,num)}}fmt.Println(getLengthValidSkillChain(t))}C语言#includestdio.h#includestring.h#includestdlib.h#defineMAXN2005intsplit(char*str,intarr[]){intcnt0;char*tokenstrtok(str,,);while(token){arr[cnt]atoi(token);tokenstrtok(NULL,,);}returncnt;}intgetLengthValidSkillChain(inttype[],intn){intans0;// 枚举开头for(inti0;in;i){// 必须以0开头if(type[i]!0){continue;}intlastZeroPosi;// 长度肯定不小于1if(ans1){ans1;}// 确定能到达的最右边for(intji1;jn;j){intvaluetype[j];if(value0){// 相邻0之间中间存在多个1或2if(j-lastZeroPos-11){break;}lastZeroPosj;}elseif(value1){// 前一个不为0if(type[j-1]!0){break;}}else{// 超过枚举起点if(j-2i){break;}// 前两个不全为0if(type[j-1]!0||type[j-2]!0){break;}}if(ansj-i1){ansj-i1;}}}returnans;}intmain(){charinput[10005];fgets(input,sizeof(input),stdin);// 去除换行input[strcspn(input,\n)]\0;inttype[MAXN];intn0;if(strlen(input)0){nsplit(input,type);}printf(%d\n,getLengthValidSkillChain(type,n));return0;}
华为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 type1type1或高级类型t y p e 2 type2type2开头必须以基础类型t y p e 0 type0type0开头依赖传递扩展类型t y p e 1 type1type1的直接前驱必须是基础类型t y p e 0 type0type0高级类型t y p e 2 type2type2的前驱和前前驱都必须是基础类型t y p e 0 type0type03.链式依赖每两个相邻的基础类型之间最多允许存在一个扩展类型或高级类型给定一个类型数组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从left1尝试右移期间使用ans出现的最大长度即可。right右移逻辑如下:定义lastZero记录上个0出现的位置主要是为了进行链式依赖每两个相邻的基础类型之间最多允许存在一个扩展类型或高级类型的判断。接下来根据value type[right]进行判断当前value 0,并且right - lastZeroPos - 1 1时需要中断此时违背链式依赖限制。不中断情况下更新lastZeroPos right当前value1并且type[right-1] !0需要中断当前value 2并且type[right - 1] ! 0 或者 type[right - 2] ! 0需要中断。需要注意right-2不能超过枚举起点。按照上述逻辑不存在中断就将right一直右移不断更新ans为合法的最大值即可。c#includeiostream #includevector #includestring #include utility #include sstream #includealgorithm #includecmath #includemap using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vectorint split(const string str, const string delimiter) { vectorint 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(vectorint 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); vectorint type; if (!input.empty()) { type split(input, ,); } int res getlengthValidSkillChain(type); cout res; return 0; }Javaimportjava.util.*;publicclassMain{publicstaticintgetLengthValidSkillChain(int[]type){intans0;intntype.length;// 枚举开头for(inti0;in;i){// 必须以0开头if(type[i]!0){continue;}intlastZeroPosi;// 长度肯定不小于1ansMath.max(ans,1);// 确定能到达的最右边for(intji1;jn;j){intvaluetype[j];if(value0){// 相邻0之间中间存在多个1或2if(j-lastZeroPos-11){break;}lastZeroPosj;}elseif(value1){// 前一个不为0if(type[j-1]!0){break;}}else{// 超过枚举起点if(j-2i){break;}// 前两个不全为0if(type[j-1]!0||type[j-2]!0){break;}}ansMath.max(ans,j-i1);}}returnans;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);Stringinputsc.nextLine();int[]type;if(input.length()0){typenewint[0];}else{String[]arrinput.split(,);typenewint[arr.length];for(inti0;iarr.length;i){type[i]Integer.parseInt(arr[i]);}}System.out.println(getLengthValidSkillChain(type));}}Pythondefget_length_valid_skill_chain(type_arr):ans0nlen(type_arr)# 枚举开头foriinrange(n):# 必须以0开头iftype_arr[i]!0:continuelast_zero_posi# 长度肯定不小于1ansmax(ans,1)# 确定能到达的最右边forjinrange(i1,n):valuetype_arr[j]ifvalue0:# 相邻0之间中间存在多个1或2ifj-last_zero_pos-11:breaklast_zero_posjelifvalue1:# 前一个不为0iftype_arr[j-1]!0:breakelse:# 超过枚举起点ifj-2i:break# 前两个不全为0iftype_arr[j-1]!0ortype_arr[j-2]!0:breakansmax(ans,j-i1)returnans input_strinput().strip()type_arr[]ifinput_str:type_arrlist(map(int,input_str.split(,)))print(get_length_valid_skill_chain(type_arr))JavaScriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letlines[];rl.on(line,(line){lines.push(line);});rl.on(close,(){functiongetLengthValidSkillChain(type){letans0;constntype.length;// 枚举开头for(leti0;in;i){// 必须以0开头if(type[i]!0){continue;}letlastZeroPosi;// 长度肯定不小于1ansMath.max(ans,1);// 确定能到达的最右边for(letji1;jn;j){constvaluetype[j];if(value0){// 相邻0之间中间存在多个1或2if(j-lastZeroPos-11){break;}lastZeroPosj;}elseif(value1){// 前一个不为0if(type[j-1]!0){break;}}else{// 超过枚举起点if(j-2i){break;}// 前两个不全为0if(type[j-1]!0||type[j-2]!0){break;}}ansMath.max(ans,j-i1);}}returnans;}constinputlines[0].trim();lettype[];if(input.length0){typeinput.split(,).map(Number);}console.log(getLengthValidSkillChain(type));});Gopackagemainimport(bufiofmtosstrconvstrings)funcgetLengthValidSkillChain(t[]int)int{ans:0n:len(t)// 枚举开头fori:0;in;i{// 必须以0开头ift[i]!0{continue}lastZeroPos:i// 长度肯定不小于1ifans1{ans1}// 确定能到达的最右边forj:i1;jn;j{value:t[j]ifvalue0{// 相邻0之间中间存在多个1或2ifj-lastZeroPos-11{break}lastZeroPosj}elseifvalue1{// 前一个不为0ift[j-1]!0{break}}else{// 超过枚举起点ifj-2i{break}// 前两个不全为0ift[j-1]!0||t[j-2]!0{break}}ifansj-i1{ansj-i1}}}returnans}funcmain(){in:bufio.NewReader(os.Stdin)input,_:in.ReadString(\n)inputstrings.TrimSpace(input)t:[]int{}iflen(input)0{arr:strings.Split(input,,)for_,s:rangearr{num,_:strconv.Atoi(s)tappend(t,num)}}fmt.Println(getLengthValidSkillChain(t))}C语言#includestdio.h#includestring.h#includestdlib.h#defineMAXN2005intsplit(char*str,intarr[]){intcnt0;char*tokenstrtok(str,,);while(token){arr[cnt]atoi(token);tokenstrtok(NULL,,);}returncnt;}intgetLengthValidSkillChain(inttype[],intn){intans0;// 枚举开头for(inti0;in;i){// 必须以0开头if(type[i]!0){continue;}intlastZeroPosi;// 长度肯定不小于1if(ans1){ans1;}// 确定能到达的最右边for(intji1;jn;j){intvaluetype[j];if(value0){// 相邻0之间中间存在多个1或2if(j-lastZeroPos-11){break;}lastZeroPosj;}elseif(value1){// 前一个不为0if(type[j-1]!0){break;}}else{// 超过枚举起点if(j-2i){break;}// 前两个不全为0if(type[j-1]!0||type[j-2]!0){break;}}if(ansj-i1){ansj-i1;}}}returnans;}intmain(){charinput[10005];fgets(input,sizeof(input),stdin);// 去除换行input[strcspn(input,\n)]\0;inttype[MAXN];intn0;if(strlen(input)0){nsplit(input,type);}printf(%d\n,getLengthValidSkillChain(type,n));return0;}
