企业官网建设流程全解析

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

7/6 1288. 删除被覆盖区间

先按区间左端点升序排序；如果左端点相同，按右端点降序排序。
遍历排序后的区间，维护当前看到的最大右端点 max_r：
若当前区间右端点 r <= max_r，说明它被前面的某个区间覆盖，跳过。
否则它没有被覆盖，答案加 1，并更新 max_r = r。

defremoveCoveredIntervals(intervals):""" :type intervals: List[List[int]] :rtype: int """intervals.sort(key=lambdax:(x[0],-x[1]))ans=0max_r=-1for_,rinintervals:ifr<=max_r:continueans+=1max_r=rreturnans

7/7 3754. 连接非零数字并乘以其数字和 I

遍历数字的每一位，将非零数字连接起来，并乘以其数字和

defsumAndMultiply(n):""" :type n: int :rtype: int """s=0num=0d=0whilen:digit=n%10s+=digitifdigit>0:num=num+digit*(10**d)d+=1n=n//10returnnum*s

7/8 3756. 连接非零数字并乘以其数字和 II

预处理三个前缀数组：
sum_d[i]：前 i 个字符中所有数字之和
cnt_n0[i]：前 i 个字符中非零数字个数
p[i]：前 i 个字符中非零数字拼接后的值（对 MOD 取模）
并预处理 pow10[k] = 10^k % MOD。
对于查询 [l, r]：
n0 = cnt_n0[r+1] - cnt_n0[l]，即子串非零位个数
sd = sum_d[r+1] - sum_d[l]，即子串非零位的数字和
由p[r+1] = p[l] * 10^n0 + x
x = p[r+1] - p[l] * 10^n0
取模后即为子串拼接值
返回 x * sd % MOD

defsumAndMultiply(s,queries):""" :type s: str :type queries: List[List[int]] :rtype: List[int] """MOD=10**9+7n=len(s)sum_d=[0]*(n+1)cnt_n0=[0]*(n+1)p=[0]*(n+1)pow10=[1]*(n+1)fori,chinenumerate(s):d=ord(ch)-ord('0')sum_d[i+1]=sum_d[i]+d pow10[i+1]=(pow10[i]*10)%MODifd==0:cnt_n0[i+1]=cnt_n0[i]p[i+1]=p[i]else:cnt_n0[i+1]=cnt_n0[i]+1p[i+1]=(p[i]*10+d)%MOD ans=[]forl,rinqueries:n0=cnt_n0[r+1]-cnt_n0[l]sd=sum_d[r+1]-sum_d[l]x=(p[r+1]-(p[l]*pow10[n0])%MOD+MOD)%MOD ans.append((x*sd)%MOD)returnans

7/9 3532. 针对图的路径存在性查询 I

因为 nums 已经非递减排序，若两个相邻点 i-1 和 i 满足
nums[i] - nums[i-1] <= maxDiff，
则这两个点直接有边，可以连在同一连通块里。
进一步可知：同一连通块在下标上一定是连续的一段。
所以只需线性扫描一次 nums，给每个下标分配一个“连通块编号”：
从左到右遍历 i=1…n-1。
若 nums[i] - nums[i-1] > maxDiff，说明连通块断开，编号 +1。
comp[i] 记录当前编号。
回答查询 [u, v] 时，只要判断 comp[u] == comp[v] 即可。

defpathExistenceQueries(n,nums,maxDiff,queries):""" :type n: int :type nums: List[int] :type maxDiff: int :type queries: List[List[int]] :rtype: List[bool] """comp=[0]*n cid=0foriinrange(1,n):ifnums[i]-nums[i-1]>maxDiff:cid+=1comp[i]=cidreturn[comp[u]==comp[v]foru,vinqueries]

7/10 3534. 针对图的路径存在性查询 II

边的定义只和数值差有关，与原下标无关。
把点按 nums 值排序后，设排序后位置为 0…n-1。
若 i < j 且 val[j] - val[i] <= maxDiff，则 i 与 j 直接相连。
对固定 i，一步能到达的右侧点是一个连续区间，记其最远端为 reach[i]。
reach 可以用双指针在线性时间求出。
查询最短路时，先把原节点下标映射到排序后位置 s,t（设 s <= t）：
若 s == t，答案是 0。
问题变成：从 s 到 t，最少几步“每步最多跳到 reach[cur]”。
这是典型最小跳跃问题，可用倍增优化。
倍增定义：
up[k][i] 表示从 i 出发走 2^k 步后，最远能到达的位置。
转移：
up[0][i] = reach[i]
up[k][i] = up[k-1][ up[k-1][i] ]
对每个查询贪心地从大到小尝试 2^k：
若 up[k][cur] < t，就先跳这 2^k 步并累加答案。
最后再跳一步即可到达/越过 t。
如果从 s 出发任意步都到不了 t，返回 -1。

defpathExistenceQueries(n,nums,maxDiff,queries):""" :type n: int :type nums: List[int] :type maxDiff: int :type queries: List[List[int]] :rtype: List[int] """pairs=sorted((v,i)fori,vinenumerate(nums))vals=[vforv,_inpairs]pos=[0]*nforidx,(_,orig_i)inenumerate(pairs):pos[orig_i]=idx reach=[0]*n r=0foriinrange(n):ifr<i:r=iwhiler+1<nandvals[r+1]-vals[i]<=maxDiff:r+=1reach[i]=r comp=[0]*n cid=0foriinrange(1,n):ifvals[i]-vals[i-1]>maxDiff:cid+=1comp[i]=cid max_log=n.bit_length()up=[[0]*nfor_inrange(max_log)]up[0]=reach[:]forkinrange(1,max_log):prev=up[k-1]cur=up[k]foriinrange(n):cur[i]=prev[prev[i]]defmin_steps(a,b):s=pos[a]t=pos[b]ifs>t:s,t=t,sifs==t:return0ifcomp[s]!=comp[t]:return-1ans=0cur=sforkinrange(max_log-1,-1,-1):nxt=up[k][cur]ifnxt<t:ans+=1<<k cur=nxtreturnans+1return[min_steps(u,v)foru,vinqueries]

7/11 2685. 统计完全连通分量的数量

先把图建成邻接表，然后遍历每个未访问节点，用 DFS/BFS 找到一个连通分量。
设该分量有 k 个点。
一个包含 k 个点的完全图，边数应为 k*(k-1)/2。
因此在遍历分量时统计该分量所有点的度数之和 deg_sum，
则分量实际边数为 deg_sum/2（无向边被统计了两次）。
若 deg_sum/2 == k*(k-1)/2，说明该分量是完全连通分量，答案加一。

defcountCompleteComponents(n,edges):""" :type n: int :type edges: List[List[int]] :rtype: int """g=[[]for_inrange(n)]foru,vinedges:g[u].append(v)g[v].append(u)vis=[False]*n ans=0foriinrange(n):ifvis[i]:continuestack=[i]vis[i]=Truenodes=0deg_sum=0whilestack:u=stack.pop()nodes+=1deg_sum+=len(g[u])forving[u]:ifnotvis[v]:vis[v]=Truestack.append(v)ifdeg_sum//2==nodes*(nodes-1)//2:ans+=1returnans

7/12 1331. 数组序号转换

排序后用map存储各个数的序号

defarrayRankTransform(arr):""" :type arr: List[int] :rtype: List[int] """l=sorted(arr)m={}num=1print(l)fori,vinenumerate(l):ifi>0andl[i-1]<v:num+=1m[v]=num ans=[0]*len(arr)fori,vinenumerate(arr):ans[i]=m[v]returnans