企业官网建设流程全解析

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

9/21 3524. 求出数组的 X 值 I

删掉任意前缀和后缀、中间不能空，剩下的就是一段连续子数组。题目其实是：统计所有非空子数组，按乘积模 k 分组，result[x] 是余数为 x 的个数。
从左往右扫，记下目前以当前位置结尾、乘积模 k 分别有多少段。
当前数既可以自己单开一段，也可以接到前面那些段后面（余数变成 旧余数*当前数 % k）。每扫完一个位置，把这些段数加进答案。

defresultArray(nums,k):""" :type nums: List[int] :type k: int :rtype: List[int] """ans=[0]*k cnt=[0]*kforvalinnums:v=val%k nxt=[0]*k nxt[v]+=1forrinrange(k):nxt[r*v%k]+=cnt[r]cnt=nxtforrinrange(k):ans[r]+=cnt[r]returnans

9/22 3525. 求出数组的 X 值 II

每次询问先改 nums[index]（这次改动会一直留下），再丢掉左边前缀，只看 nums[start…n-1]。
右边还可以再丢掉一段后缀，数组不能空，所以剩下的一定是从 nums[start] 开头、到某个位置 r 为止的一段。
问题变成：有多少个 r，使得 nums[start]*…*nums[r] 模 k 等于 x。
k 最大只有 5，用线段树每个节点记下两样东西：这段整体乘积模 k，以及「从这段左端点出发的各个前缀，乘积模 k 分别有多少个」。
合并左右两段时，左段前缀原样留下；右段每个前缀前面要先乘上左段整体乘积，再加进计数。单点修改后查询 [start, n-1] 即可。

defresultArray(nums,k,queries):""" :type nums: List[int] :type k: int :type queries: List[List[int]] :rtype: List[int] """n=len(nums)a=[x%kforxinnums]prod=[1]*(4*n)cnt=[[0]*kfor_inrange(4*n)]defpull(p):l,r=p*2,p*2+1prod[p]=prod[l]*prod[r]%k c=cnt[p]foriinrange(k):c[i]=cnt[l][i]lp=prod[l]foriinrange(k):c[i*lp%k]+=cnt[r][i]defbuild(p,l,r):ifl==r:prod[p]=a[l]cnt[p][a[l]]=1returnm=(l+r)//2build(p*2,l,m)build(p*2+1,m+1,r)pull(p)defupdate(p,l,r,i,v):ifl==r:forjinrange(k):cnt[p][j]=0prod[p]=v cnt[p][v]=1returnm=(l+r)//2ifi<=m:update(p*2,l,m,i,v)else:update(p*2+1,m+1,r,i,v)pull(p)defquery(p,l,r,ql,qr):ifql<=landr<=qr:returnprod[p],cnt[p][:]m=(l+r)//2ifqr<=m:returnquery(p*2,l,m,ql,qr)ifql>m:returnquery(p*2+1,m+1,r,ql,qr)lp,lc=query(p*2,l,m,ql,qr)rp,rc=query(p*2+1,m+1,r,ql,qr)nc=lc[:]foriinrange(k):nc[i*lp%k]+=rc[i]returnlp*rp%k,nc build(1,0,n-1)ans=[]foridx,val,start,xinqueries:update(1,0,n-1,idx,val%k)ans.append(query(1,0,n-1,start,n-1)[1][x])returnans

9/23 1658. 将 x 减到 0 的最小操作数

suml,sumr用来记录前缀 后缀的和
l,r记录前缀[0,l] 后缀的位置[r,n]
初始空前缀l=-1,全后缀r=0
遍历每一个前缀l
如果suml+sumr>x 则减少后缀

defminOperations(nums,x):""" :type nums: List[int] :type x: int :rtype: int """n=len(nums)s=sum(nums)ifs<x:return-1suml,sumr=0,s r=0ans=n+1forlinrange(-1,n-1):ifl!=-1:suml+=nums[l]whiler<nandsuml+sumr>x:sumr-=nums[r]r+=1ifsuml+sumr==x:ans=min(ans,l+1+n-r)return-1ifans>nelseans

9/24 1096. 花括号展开 II

递归解析
add用来生成两个set相加
如果遇到, 说明前后两部分相或
如果遇到{ 往后找到其对应的} 将这部分递归解析
如果前面为, 则将两部分相或 否则相加
其他符号则为表达式相连 根据前一个符号来决定相或 相加

defbraceExpansionII(expression):""" :type expression: str :rtype: List[str] """defadd(a,b):ans=set()foriina:forjinb:ans.add(i+j)returnansdefcheck(ex):tmp=set()ans=set()loc=0last=","whileloc<len(ex):ifex[loc]==",":ans=ans|tmp tmp=set()loc+=1elifex[loc]=="{":cur=1x=loc+1whilecur>0:ifex[x]=="{":cur+=1elifex[x]=="}":cur-=1x+=1iflast==",":tmp=tmp|check(ex[loc+1:x-1])else:tmp=add(tmp,check(ex[loc+1:x-1]))loc=x last="}"else:s=""whileloc<len(ex)andex[loc]!=","andex[loc]!="{":s+=ex[loc]loc+=1iflast==",":tmp.add(s)else:tmp={i+sforiintmp}last=ex[loc-1]returnans|tmpreturnsorted(check(expression))

9/25 3550. 数位和等于下标的最小下标

从左到右依次判断 func用来计算num的数位和

defsmallestIndex(nums):""" :type nums: List[int] :rtype: int """deffunc(num):res=0whilenum>0:res+=num%10num//=10returnresforiinrange(len(nums)):ifi==func(nums[i]):returnireturn-1

9/26 1807. 替换字符串中的括号内容

按序遍历 m存储knowledge一一对应的内容
遇到(时 获取括号内容 在m中查询

defevaluate(s,knowledge):""" :type s: str :type knowledge: List[List[str]] :rtype: str """loc=0n=len(s)ans=""m={}fork,vinknowledge:m[k]=vwhileloc<n:ifs[loc]=="(":loc+=1cur=""whiles[loc]!=")":cur+=s[loc]loc+=1ifcurinm:ans+=m[cur]else:ans+="?"else:ans+=s[loc]loc+=1returnans

9/27 1190. 反转每对括号间的子串

1.遇到字母就往结果里追加。
遇到左括号记下当前结果写到了哪。
遇到右括号，就把对应左括号之后追加的那一段原地翻转。
从内到外每对括号翻转一次。
2.遇到左括号把当前攒好的串压栈，开始攒括号里面的新串。
遇到右括号把里面攒的串翻转，再接到栈里弹出的外层串后面。
最后剩下的就是答案。

defreverseParentheses(s):""" :type s: str :rtype: str """l=[]ans=[]loc=0foriinrange(lenss(s)):ifs[i]>='a'ands[i]<='z':ans.append(s[i])loc+=1elifs[i]=='(':l.append(loc)else:start=l.pop()ifstart==0:ans=ans[::-1]else:ans[start:loc]=ans[loc-1:start-1:-1]return''.join(ans)defreverseParentheses2(s):""" :type s: str :rtype: str """ans=[]num=''foriins:ifi=='(':ans.append(num)num=''elifi==')':a=ans.pop()num=num[::-1]num=a+numelse:num+=ireturnnum