记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步目录9/21 3524. 求出数组的 X 值 I9/22 3525. 求出数组的 X 值 II9/23 1658. 将 x 减到 0 的最小操作数9/24 1096. 花括号展开 II9/25 3550. 数位和等于下标的最小下标9/26 1807. 替换字符串中的括号内容9/27 1190. 反转每对括号间的子串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:vval%k nxt[0]*k nxt[v]1forrinrange(k):nxt[r*v%k]cnt[r]cntnxtforrinrange(k):ans[r]cnt[r]returnans9/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] nlen(nums)a[x%kforxinnums]prod[1]*(4*n)cnt[[0]*kfor_inrange(4*n)]defpull(p):l,rp*2,p*21prod[p]prod[l]*prod[r]%k ccnt[p]foriinrange(k):c[i]cnt[l][i]lpprod[l]foriinrange(k):c[i*lp%k]cnt[r][i]defbuild(p,l,r):iflr:prod[p]a[l]cnt[p][a[l]]1returnm(lr)//2build(p*2,l,m)build(p*21,m1,r)pull(p)defupdate(p,l,r,i,v):iflr:forjinrange(k):cnt[p][j]0prod[p]v cnt[p][v]1returnm(lr)//2ifim:update(p*2,l,m,i,v)else:update(p*21,m1,r,i,v)pull(p)defquery(p,l,r,ql,qr):ifqllandrqr:returnprod[p],cnt[p][:]m(lr)//2ifqrm:returnquery(p*2,l,m,ql,qr)ifqlm:returnquery(p*21,m1,r,ql,qr)lp,lcquery(p*2,l,m,ql,qr)rp,rcquery(p*21,m1,r,ql,qr)nclc[:]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])returnans9/23 1658. 将 x 减到 0 的最小操作数suml,sumr用来记录前缀 后缀的和l,r记录前缀[0,l] 后缀的位置[r,n]初始空前缀l-1,全后缀r0遍历每一个前缀l如果sumlsumrx 则减少后缀defminOperations(nums,x): :type nums: List[int] :type x: int :rtype: int nlen(nums)ssum(nums)ifsx:return-1suml,sumr0,s r0ansn1forlinrange(-1,n-1):ifl!-1:sumlnums[l]whilernandsumlsumrx:sumr-nums[r]r1ifsumlsumrx:ansmin(ans,l1n-r)return-1ifansnelseans9/24 1096. 花括号展开 II递归解析add用来生成两个set相加如果遇到, 说明前后两部分相或如果遇到{ 往后找到其对应的} 将这部分递归解析如果前面为, 则将两部分相或 否则相加其他符号则为表达式相连 根据前一个符号来决定相或 相加defbraceExpansionII(expression): :type expression: str :rtype: List[str] defadd(a,b):ansset()foriina:forjinb:ans.add(ij)returnansdefcheck(ex):tmpset()ansset()loc0last,whileloclen(ex):ifex[loc],:ansans|tmp tmpset()loc1elifex[loc]{:cur1xloc1whilecur0:ifex[x]{:cur1elifex[x]}:cur-1x1iflast,:tmptmp|check(ex[loc1:x-1])else:tmpadd(tmp,check(ex[loc1:x-1]))locx last}else:swhileloclen(ex)andex[loc]!,andex[loc]!{:sex[loc]loc1iflast,:tmp.add(s)else:tmp{isforiintmp}lastex[loc-1]returnans|tmpreturnsorted(check(expression))9/25 3550. 数位和等于下标的最小下标从左到右依次判断 func用来计算num的数位和defsmallestIndex(nums): :type nums: List[int] :rtype: int deffunc(num):res0whilenum0:resnum%10num//10returnresforiinrange(len(nums)):ififunc(nums[i]):returnireturn-19/26 1807. 替换字符串中的括号内容按序遍历 m存储knowledge一一对应的内容遇到(时 获取括号内容 在m中查询defevaluate(s,knowledge): :type s: str :type knowledge: List[List[str]] :rtype: str loc0nlen(s)ansm{}fork,vinknowledge:m[k]vwhilelocn:ifs[loc](:loc1curwhiles[loc]!):curs[loc]loc1ifcurinm:ansm[cur]else:ans?else:anss[loc]loc1returnans9/27 1190. 反转每对括号间的子串1.遇到字母就往结果里追加。遇到左括号记下当前结果写到了哪。遇到右括号就把对应左括号之后追加的那一段原地翻转。从内到外每对括号翻转一次。2.遇到左括号把当前攒好的串压栈开始攒括号里面的新串。遇到右括号把里面攒的串翻转再接到栈里弹出的外层串后面。最后剩下的就是答案。defreverseParentheses(s): :type s: str :rtype: str l[]ans[]loc0foriinrange(lenss(s)):ifs[i]aands[i]z:ans.append(s[i])loc1elifs[i](:l.append(loc)else:startl.pop()ifstart0:ansans[::-1]else:ans[start:loc]ans[loc-1:start-1:-1]return.join(ans)defreverseParentheses2(s): :type s: str :rtype: str ans[]numforiins:ifi(:ans.append(num)numelifi):aans.pop()numnum[::-1]numanumelse:numireturnnum