最长不连续子串(C/C/Js/Java/Py/Go)题解华为OD机试新系统真题 华为OD上机考试新系统真题 8月5号 100分题型华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录机考题库 算法考点详解题目内容给定一个整数数组请找出最长的子串使得该子串中任意两个相邻元素的绝对差都严格大于1。输出这个最长子串的长度。例如数组[1, 3, 4, 5, 6, 5, 4]中子串[1, 3]满足条件 (|1-3|21)且是最长的因此答案为2。数组长度为n nn0 ≤ n ≤ 1000 0 \le n \le 10000≤n≤1000数组范围n u m s [ ] nums[]nums[]0 ≤ nums [ i ] ≤ 10000 0 \le \text{nums}[i] \le 100000≤nums[i]≤10000输入描述输入为一个整数数组输出描述输出满足条件的最长子串的长度样例1输入1,3,4,5,6,5,4输出2说明最长子串是[1,3],长度是2样例2输入1,3,5,7输出4说明最长子串是[1,3,5,7],长度是4题解思路双指针子串属于原字符串中连续片段可以明显分析出当abs(nums[i] - nums[i1]) 0这两个元素必须处于两个不同的不连续子串。基于此使用双指针计算最长不连续字符串长度初始设置left 0,right从前往后进行递增移动过程中位置[left, right]为合法子串逻辑如下当right left abs(nums[i] - nums[i1]) 1说明可以拓展当right left abs(nums[i] - nums[i1]) 1说明可以不拓展更新left right每一轮计算合法子串长度并记录最长合法子串长度c#includebits/stdc.h#includevectorusingnamespacestd;// 通用 切割函数 函数 将字符串str根据delimiter进行切割vectorintsplit(conststringstr,conststringdelimiter){vectorintresult;size_t start0;size_t endstr.find(delimiter);while(end!string::npos){result.push_back(stoi(str.substr(start,end-start)));startenddelimiter.length();endstr.find(delimiter,start);}// 添加最后一个部分result.push_back(stoi(str.substr(start)));returnresult;}intsolve(vectorintnums){intnnums.size();intans0;// 双指针intleft0;for(intright0;rightn;right){// 连续被断开if(rightleftabs(nums[right]-nums[right-1])1){leftright;}ansmax(ans,right-left1);}returnans;}intmain(){string input;getline(cin,input);vectorintnumssplit(input,,);coutsolve(nums);return0;}Javaimportjava.util.*;publicclassMain{publicstaticintsolve(int[]nums){intnnums.length;if(n0){return0;}intans0;// 双指针intleft0;for(intright0;rightn;right){// 连续被断开if(rightleftMath.abs(nums[right]-nums[right-1])1){leftright;}ansMath.max(ans,right-left1);}returnans;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);Stringinputsc.nextLine();int[]nums;if(!input.isEmpty()){String[]arrinput.split(,);numsnewint[arr.length];for(inti0;iarr.length;i){nums[i]Integer.parseInt(arr[i]);}}else{numsnewint[0];}System.out.println(solve(nums));sc.close();}}Pythonimportsysdefsolve(nums):nlen(nums)ifn0:return0ans0# 双指针left0forrightinrange(n):# 连续被断开ifrightleftandabs(nums[right]-nums[right-1])1:leftright ansmax(ans,right-left1)returnans# readline读取输入input_strsys.stdin.readline().strip()ifinput_str:numslist(map(int,input_str.split(,)))else:nums[]print(solve(nums))JavaScriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});functionsolve(nums){letnnums.length;if(n0){return0;}letans0;// 双指针letleft0;for(letright0;rightn;right){// 连续被断开if(rightleftMath.abs(nums[right]-nums[right-1])1){leftright;}ansMath.max(ans,right-left1);}returnans;}rl.on(line,(input){letnums;if(input.length0){numsinput.split(,).map(Number);}else{nums[];}console.log(solve(nums));rl.close();});Gopackagemainimport(bufiofmtosstrconvstrings)funcsolve(nums[]int)int{n:len(nums)ifn0{return0}ans:0// 双指针left:0forright:0;rightn;right{// 连续被断开ifrightleftabs(nums[right]-nums[right-1])1{leftright}ifright-left1ans{ansright-left1}}returnans}// 求绝对值funcabs(xint)int{ifx0{return-x}returnx}funcmain(){reader:bufio.NewReader(os.Stdin)input,_:reader.ReadString(\n)inputstrings.TrimSpace(input)nums:[]int{}ifinput!{arr:strings.Split(input,,)for_,s:rangearr{num,_:strconv.Atoi(s)numsappend(nums,num)}}fmt.Println(solve(nums))}C语言#includestdio.h#includestdlib.h#includestring.hintabs_int(intx){returnx0?-x:x;}intsolve(intnums[],intn){if(n0){return0;}intans0;// 双指针intleft0;for(intright0;rightn;right){// 连续被断开if(rightleftabs_int(nums[right]-nums[right-1])1){leftright;}intlenright-left1;if(lenans){anslen;}}returnans;}intmain(){charinput[100000];fgets(input,sizeof(input),stdin);input[strcspn(input,\n)]\0;intnums[1005];intn0;if(strlen(input)0){char*tokenstrtok(input,,);while(token!NULL){nums[n]atoi(token);tokenstrtok(NULL,,);}}printf(%d,solve(nums,n));return0;}