华为OD机试 新系统真题 【不同Tag类型统计】

不同Tag类型统计(C++/Go/C/Js/Java/Py)题解

华为OD机试新系统真题 华为OD上机考试新系统真题 7月22号 100分题型

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

题目内容

给定一个数组，元素为数字，数组的内容表示多个连续的TLV（tag-length-value）；
关于TLV，单个TLV具备以下特征：

• tag：占位1个数组元素，代表类型；
• length：占位1个数组元素，代表长度，且长度值大于0；
• value：占位后面连续的length个数组元素；
• tlv长度限制：单个TLV所占的数组元素必须是4的倍数，不足的部分可用任意数字补齐；
• 数值取值范围0-99；
  例如：单个TLV数组：2130，第一个数字2是tag，第二个数字1是length，第三个数字3是value，第四个数字0是补齐；
  现在要求把给定的数组进行分析，解析出整个数组中存在多少种不同类型的tag，如果解析过程出现数组元素不符合规范，则返回0。

输入描述

1. 数组元素不超过10000
2. TLV的总数不超过1000

输出描述

解析出的不同tag类型的数量，若格式错误则输出0

样例1

输入

2,1,3,0,3,1,3,0,0

输出

0

说明
格式不对

样例2

输入

2,1,3,0,3,1,3,0

输出

2

说明
格式正确，2个Tag类型，分别是2、3

题解

思路：模拟

1. 初始化index = 0从前往后遍历，依次确定各个部分的值以及进行合法性检验
   • tag[index]为该TLV的tag
   • 判断index + 1 < n确保length片段没有丢失，并得到length的值
   • 通过length的值可以得到整个TLV的长度为tagLen = (2 + length + 3) / 4 * 4,并检查index + tagLen > n确保剩余片段是否能组成完成TLV
   • 检验[index, index + tagLen -1]的值是否满足[0,99]
   • 使用集合或者数组保存出现过的tag
   • 更新index + tagLen，重复执行以上策略
2. 按照2模拟处理输入tag，无不合法情况下输出tag种类即可。

c++

#include<bits/stdc++.h>#include<string>#include<vector>usingnamespacestd;// 通用 切割函数 函数 将字符串str根据delimiter进行切割vector<int>split(conststring&str,conststring&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)));returnresult;}intcountTagCategories(vector<int>&tag){// 用于tag去重set<int>s;intn=tag.size();intindex=0;while(index<n){// 不完整不包含lengthif(index+1>=n){return0;}intlength=tag[index+1];// 不符合length > 0要求if(length<=0){return0;}// 补齐之后，tag的实际长度inttagLen=(2+length+3)/4*4;// 剩余长度无法满足完整tag要求if(index+tagLen>n){return0;}// 检验值范围是否合法for(intj=index;j<index+tagLen;j++){if(tag[j]<0||tag[j]>99){return0;}}s.insert(tag[index]);index+=tagLen;}returns.size();}intmain(){string input;getline(cin,input);vector<int>tag=split(input,",");cout<<countTagCategories(tag);return0;}

Java

importjava.util.*;publicclassMain{staticintcountTagCategories(int[]tag){// 用于tag去重Set<Integer>set=newHashSet<>();intn=tag.length;intindex=0;while(index<n){// 不完整不包含lengthif(index+1>=n){return0;}intlength=tag[index+1];// 不符合length > 0要求if(length<=0){return0;}// 补齐之后，tag的实际长度inttagLen=((2+length+3)/4)*4;// 剩余长度无法满足完整tag要求if(index+tagLen>n){return0;}// 检验值范围是否合法for(intj=index;j<index+tagLen;j++){if(tag[j]<0||tag[j]>99){return0;}}set.add(tag[index]);index+=tagLen;}returnset.size();}publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);Stringinput=sc.nextLine();String[]arr=input.split(",");int[]tag=newint[arr.length];for(inti=0;i<arr.length;i++){tag[i]=Integer.parseInt(arr[i]);}System.out.println(countTagCategories(tag));}}

Python

# 用于tag去重defcountTagCategories(tag):s=set()n=len(tag)index=0whileindex<n:# 不完整不包含lengthifindex+1>=n:return0length=tag[index+1]# 不符合length > 0要求iflength<=0:return0# 补齐之后，tag的实际长度tagLen=((2+length+3)//4)*4# 剩余长度无法满足完整tag要求ifindex+tagLen>n:return0# 检验值范围是否合法forjinrange(index,index+tagLen):iftag[j]<0ortag[j]>99:return0s.add(tag[index])index+=tagLenreturnlen(s)input_str=input().strip()tag=list(map(int,input_str.split(",")))print(countTagCategories(tag))

JavaScript

constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});functioncountTagCategories(tag){// 用于tag去重constset=newSet();constn=tag.length;letindex=0;while(index<n){// 不完整不包含lengthif(index+1>=n){return0;}constlength=tag[index+1];// 不符合length > 0要求if(length<=0){return0;}// 补齐之后，tag的实际长度consttagLen=Math.floor((2+length+3)/4)*4;// 剩余长度无法满足完整tag要求if(index+tagLen>n){return0;}// 检验值范围是否合法for(letj=index;j<index+tagLen;j++){if(tag[j]<0||tag[j]>99){return0;}}set.add(tag[index]);index+=tagLen;}returnset.size;}rl.on("line",function(line){consttag=line.split(",").map(Number);console.log(countTagCategories(tag));});

Go

packagemainimport("fmt""strconv""strings")funccountTagCategories(tag[]int)int{// 用于tag去重set:=make(map[int]bool)n:=len(tag)index:=0forindex<n{// 不完整不包含lengthifindex+1>=n{return0}length:=tag[index+1]// 不符合length > 0要求iflength<=0{return0}// 补齐之后，tag的实际长度tagLen:=((2+length+3)/4)*4// 剩余长度无法满足完整tag要求ifindex+tagLen>n{return0}// 检验值范围是否合法forj:=index;j<index+tagLen;j++{iftag[j]<0||tag[j]>99{return0}}set[tag[index]]=trueindex+=tagLen}returnlen(set)}funcmain(){varinputstringfmt.Scanln(&input)parts:=strings.Split(input,",")tag:=make([]int,len(parts))fori,s:=rangeparts{tag[i],_=strconv.Atoi(s)}fmt.Println(countTagCategories(tag))}

C语言

#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAXN100000// 通用 切割函数 函数 将字符串str根据delimiter进行切割intsplit(char*str,constchar*delimiter,intnums[]){intcnt=0;char*token=strtok(str,delimiter);while(token!=NULL){nums[cnt++]=atoi(token);token=strtok(NULL,delimiter);}returncnt;}intcountTagCategories(inttag[],intn){// 用于tag去重intvis[100]={0};intindex=0;while(index<n){// 不完整不包含lengthif(index+1>=n){return0;}intlength=tag[index+1];// 不符合length > 0要求if(length<=0){return0;}// 补齐之后，tag的实际长度inttagLen=((2+length+3)/4)*4;// 剩余长度无法满足完整tag要求if(index+tagLen>n){return0;}// 检验值范围是否合法for(intj=index;j<index+tagLen;j++){if(tag[j]<0||tag[j]>99){return0;}}vis[tag[index]]=1;index+=tagLen;}intans=0;for(inti=0;i<100;i++){if(vis[i]){ans++;}}returnans;}intmain(){charinput[MAXN];fgets(input,sizeof(input),stdin);input[strcspn(input,"\n")]='\0';inttag[MAXN];intn=split(input,",",tag);printf("%d\n",countTagCategories(tag,n));return0;}