企业官网建设流程全解析

绍兴做微网站,广告设计公司职位,自己做商城网站,深圳市公司网站建设2025-12-16#xff1a;数组的最小稳定性因子。用go语言#xff0c;给定一个整数数组 nums 和一个整数 maxC。把满足以下条件的连续区间称为“稳定子数组”#xff1a;区间内所有数的最大公约数#xff08;GCD#xff09;至少为 2。 定义数组的“稳定性因子”为其最长稳定子…2025-12-16数组的最小稳定性因子。用go语言给定一个整数数组 nums 和一个整数 maxC。把满足以下条件的连续区间称为“稳定子数组”区间内所有数的最大公约数GCD至少为 2。定义数组的“稳定性因子”为其最长稳定子数组的长度。你可以最多对数组中的 maxC 个位置改成任意整数。问题是在不超过 maxC 次修改后能够把稳定性因子降到多小返回这个最小可能的稳定性因子如果最终不存在任何稳定子数组则返回 0。补充说明子数组指数组的连续片段。数组的最大公约数指能同时整除所有元素的最大整数。长度为 1 的子数组若其唯一元素 ≥ 2也视为稳定子数组。1 n nums.length 100000。1 nums[i] 1000000000。0 maxC n。输入nums [3,5,10], maxC 1。输出1。解释稳定的子数组 [5, 10] 的 HCF 5其稳定性因子为 2。由于 maxC 1一个最优策略是将 nums[1] 改为 7得到 nums [3, 7, 10]。现在没有长度大于 1 的子数组的 HCF 2。因此最小可能稳定性因子是 1。题目来自力扣3605。 算法步骤详解初始化与预处理函数首先获取数组长度n并初始化一个与nums等长的切片leftMin。这个切片用于记录一个关键信息对于每个位置ileftMin[i]表示以i为区间右端点时能够使得区间内所有元素的最大公约数GCD大于等于2的、最靠左的起点位置。变量left和bottom初始化为0它们共同维护一个滑动窗口或处理区间。rightGcd初始化为0因为任何数与0的GCD是其本身。计算 leftMin 数组这是算法的核心步骤。它通过一次遍历下标i从0到n-1来计算leftMin数组。更新GCD对于当前元素nums[i]代码通过rightGcd gcd(rightGcd, nums[i])来累积计算从某个起点到i的整个区间的GCD。收缩左边界使用一个内层循环for left i gcd(nums[left], rightGcd) 1来调整左边界left。这个条件的目的是检查当前窗口[left, i]的GCD是否因为包含了nums[left]而变为1即不满足稳定子数组条件。如果变为1就需要向右移动left指针直到窗口内的GCD再次大于等于2或者窗口为空。记录左边界将最终确定的左边界left记录到leftMin[i]中。栈式重建关键优化当需要移动left指针并且bottom可以理解为上一次重建的起始点小于或等于当前的left时会触发一个重建操作。这个操作从i-1到left1逆序地重新计算区间GCD这类似于维护一个隐式的栈结构用于高效地更新GCD信息避免每次都从头计算。完成后bottom被更新为irightGcd重置为0。二分查找最小稳定性因子在得到leftMin数组后算法使用二分搜索来确定最小的稳定性因子即最长稳定子数组的长度上限upper。搜索范围二分查找的下界是0上界可以设为n/(maxC1)这是一个合理的估计因为修改maxC个点最多能将数组分成maxC1段。检查函数对于每一个候选的upper值函数模拟修改操作检查是否能在最多maxC次修改后使得数组中所有稳定子数组的长度都不超过upper。贪心模拟检查过程采用贪心策略。从左到右遍历数组当遇到一个稳定子数组的长度超过upper时即i - leftMin[i] 1 upper就在这个子数组的末尾之后进行一次“修改”实际上是通过将索引i跳转upper 1位来模拟并消耗一次修改次数。如果修改次数在遍历完数组前用完则说明当前upper值太小需要增大否则说明upper值可行可以尝试更小的值。返回结果二分查找结束后找到的最小满足条件的upper值就是题目要求的最小可能稳定性因子将其返回。⏱ 复杂度分析时间复杂度计算leftMin数组主循环遍历每个元素一次。虽然内部有循环和重建操作但每个元素最多被加入和移出“栈”一次GCD计算可以看作是常数时间因为整数大小有限GCD操作很快。因此这部分的时间复杂度可以看作是O(n)。二分查找与检查二分查找的迭代次数是O(log n)。每次检查需要遍历整个数组是O(n)。所以这部分的总时间复杂度是O(n log n)。综合整个算法的总时间复杂度为 O(n log n)。空间复杂度算法主要使用了leftMin数组其大小为O(n)。其他变量如left,bottom,rightGcd等占用常数空间。在计算GCD的递归或栈模拟过程中没有使用与输入规模成比例的额外数据结构。因此算法的总额外空间复杂度为 O(n)。Go完整代码如下packagemainimport(fmtsort)funcminStable(nums[]int,maxCint)int{n:len(nums)leftMin:make([]int,n)varleft,bottom,rightGcdintfori,x:rangenums{rightGcdgcd(rightGcd,x)forleftigcd(nums[left],rightGcd)1{ifbottomleft{// 重新构建一个栈// 由于 left 即将移出窗口只需计算到 left1forj:i-1;jleft;j--{nums[j]gcd(nums[j],nums[j1])}bottomi rightGcd0}left}leftMin[i]left}ans:sort.Search(n/(maxC1),func(upperint)bool{c:maxC i:upperforin{ifi-leftMin[i]1upper{ifc0{returnfalse}c--iupper1}else{i}}returntrue})returnans}funcgcd(a,bint)int{fora!0{a,bb%a,a}returnb}funcmain(){nums:[]int{3,5,10}maxC:1result:minStable(nums,maxC)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-importmathfromtypingimportListimportbisectdefminStable(nums:List[int],maxC:int)-int:nlen(nums)leftMin[0]*n left0bottom0rightGcd0foriinrange(n):xnums[i]rightGcdmath.gcd(rightGcd,x)whileleftiandmath.gcd(nums[left],rightGcd)1:ifbottomleft:# 重新构建一个栈# 由于 left 即将移出窗口只需计算到 left1forjinrange(i-1,left,-1):nums[j]math.gcd(nums[j],nums[j1])bottomi rightGcd0left1leftMin[i]left# 二分查找defcheck(upper:int)-bool:cmaxC iupperwhilein:ifi-leftMin[i]1upper:ifc0:returnFalsec-1iupper1else:i1returnTrue# 使用二分查找找到最小满足条件的值low,high0,n//(maxC1)1whilelowhigh:mid(lowhigh)//2ifcheck(mid):highmidelse:lowmid1returnlow# 另一种更简洁的二分查找实现方式defminStable_alternative(nums:List[int],maxC:int)-int:nlen(nums)leftMin[0]*n left0bottom0rightGcd0foriinrange(n):xnums[i]rightGcdmath.gcd(rightGcd,x)whileleftiandmath.gcd(nums[left],rightGcd)1:ifbottomleft:# 重新构建一个栈forjinrange(i-1,left,-1):nums[j]math.gcd(nums[j],nums[j1])bottomi rightGcd0left1leftMin[i]left# 使用 Python 的 bisect 风格二分查找ansbisect.bisect_left(range(n//(maxC1)1),True,keylambdaupper:check(upper))defcheck(upper:int)-bool:cmaxC iupperwhilein:ifi-leftMin[i]1upper:ifc0:returnFalsec-1iupper1else:i1returnTruereturnans# 测试代码if__name____main__:nums[3,5,10]maxC1resultminStable(nums,maxC)print(fminStable result:{result})# 测试更多用例test_cases[([3,5,10],1),([2,3,4,5],2),([1,2,3,4,5],1),([6,10,15],0),]fornums,maxCintest_cases:resultminStable(nums.copy(),maxC)print(fnums{nums}, maxC{maxC}- result{result})C完整代码如下#includeiostream#includevector#includealgorithm#includefunctional#includenumericusingnamespacestd;intgcd(inta,intb){while(a!0){inttempa;ab%a;btemp;}returnb;}intminStable(vectorintnums,intmaxC){intnnums.size();vectorintleftMin(n,0);intleft0,bottom0,rightGcd0;for(inti0;in;i){intxnums[i];rightGcdgcd(rightGcd,x);while(leftigcd(nums[left],rightGcd)1){if(bottomleft){// 重新构建一个栈// 由于 left 即将移出窗口只需计算到 left1for(intji-1;jleft;j--){nums[j]gcd(nums[j],nums[j1]);}bottomi;rightGcd0;}left;}leftMin[i]left;}// 二分查找autocheck[](intupper)-bool{intcmaxC;intiupper;while(in){if(i-leftMin[i]1upper){if(c0){returnfalse;}c--;iupper1;}else{i;}}returntrue;};intlow0,highn/(maxC1)1;while(lowhigh){intmidlow(high-low)/2;if(check(mid)){highmid;}else{lowmid1;}}returnlow;}// 使用C标准库的binary_search风格intminStable2(vectorintnums,intmaxC){intnnums.size();vectorintleftMin(n,0);intleft0,bottom0,rightGcd0;for(inti0;in;i){intxnums[i];rightGcdgcd(rightGcd,x);while(leftigcd(nums[left],rightGcd)1){if(bottomleft){// 重新构建一个栈for(intji-1;jleft;j--){nums[j]gcd(nums[j],nums[j1]);}bottomi;rightGcd0;}left;}leftMin[i]left;}// 使用lower_bound风格的二分查找vectorintrange(n/(maxC1)1);for(inti0;irange.size();i){range[i]i;}autoitlower_bound(range.begin(),range.end(),true,[](intupper,bool){intcmaxC;intiupper;while(in){if(i-leftMin[i]1upper){if(c0){returntrue;// 返回true表示upper不够大}c--;iupper1;}else{i;}}returnfalse;// 返回false表示upper足够大});return(it!range.end())?*it:n;}intmain(){vectorintnums{3,5,10};intmaxC1;intresultminStable(nums,maxC);coutminStable result: resultendl;// 测试更多用例vectorpairvectorint,inttestCases{{{3,5,10},1},{{2,3,4,5},2},{{1,2,3,4,5},1},{{6,10,15},0},};for(autotestCase:testCases){vectorintnumsCopytestCase.first;intmaxCtestCase.second;intresultminStable(numsCopy,maxC);coutnums[;for(size_t i0;itestCase.first.size();i){couttestCase.first[i];if(itestCase.first.size()-1)cout, ;}cout], maxCmaxC - resultresultendl;}return0;}