记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步目录7/6 1288. 删除被覆盖区间7/7 3754. 连接非零数字并乘以其数字和 I7/8 3756. 连接非零数字并乘以其数字和 II7/9 3532. 针对图的路径存在性查询 I7/10 3534. 针对图的路径存在性查询 II7/11 2685. 统计完全连通分量的数量7/12 1331. 数组序号转换7/6 1288. 删除被覆盖区间先按区间左端点升序排序如果左端点相同按右端点降序排序。遍历排序后的区间维护当前看到的最大右端点 max_r若当前区间右端点 r max_r说明它被前面的某个区间覆盖跳过。否则它没有被覆盖答案加 1并更新 max_r r。defremoveCoveredIntervals(intervals): :type intervals: List[List[int]] :rtype: int intervals.sort(keylambdax:(x[0],-x[1]))ans0max_r-1for_,rinintervals:ifrmax_r:continueans1max_rrreturnans7/7 3754. 连接非零数字并乘以其数字和 I遍历数字的每一位将非零数字连接起来并乘以其数字和defsumAndMultiply(n): :type n: int :rtype: int s0num0d0whilen:digitn%10sdigitifdigit0:numnumdigit*(10**d)d1nn//10returnnum*s7/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[r1] - cnt_n0[l]即子串非零位个数sd sum_d[r1] - sum_d[l]即子串非零位的数字和由p[r1] p[l] * 10^n0 xx p[r1] - p[l] * 10^n0取模后即为子串拼接值返回 x * sd % MODdefsumAndMultiply(s,queries): :type s: str :type queries: List[List[int]] :rtype: List[int] MOD10**97nlen(s)sum_d[0]*(n1)cnt_n0[0]*(n1)p[0]*(n1)pow10[1]*(n1)fori,chinenumerate(s):dord(ch)-ord(0)sum_d[i1]sum_d[i]d pow10[i1](pow10[i]*10)%MODifd0:cnt_n0[i1]cnt_n0[i]p[i1]p[i]else:cnt_n0[i1]cnt_n0[i]1p[i1](p[i]*10d)%MOD ans[]forl,rinqueries:n0cnt_n0[r1]-cnt_n0[l]sdsum_d[r1]-sum_d[l]x(p[r1]-(p[l]*pow10[n0])%MODMOD)%MOD ans.append((x*sd)%MOD)returnans7/9 3532. 针对图的路径存在性查询 I因为 nums 已经非递减排序若两个相邻点 i-1 和 i 满足nums[i] - nums[i-1] maxDiff则这两个点直接有边可以连在同一连通块里。进一步可知同一连通块在下标上一定是连续的一段。所以只需线性扫描一次 nums给每个下标分配一个“连通块编号”从左到右遍历 i1…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 cid0foriinrange(1,n):ifnums[i]-nums[i-1]maxDiff:cid1comp[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] pairssorted((v,i)fori,vinenumerate(nums))vals[vforv,_inpairs]pos[0]*nforidx,(_,orig_i)inenumerate(pairs):pos[orig_i]idx reach[0]*n r0foriinrange(n):ifri:riwhiler1nandvals[r1]-vals[i]maxDiff:r1reach[i]r comp[0]*n cid0foriinrange(1,n):ifvals[i]-vals[i-1]maxDiff:cid1comp[i]cid max_logn.bit_length()up[[0]*nfor_inrange(max_log)]up[0]reach[:]forkinrange(1,max_log):prevup[k-1]curup[k]foriinrange(n):cur[i]prev[prev[i]]defmin_steps(a,b):spos[a]tpos[b]ifst:s,tt,sifst:return0ifcomp[s]!comp[t]:return-1ans0cursforkinrange(max_log-1,-1,-1):nxtup[k][cur]ifnxtt:ans1k curnxtreturnans1return[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 ans0foriinrange(n):ifvis[i]:continuestack[i]vis[i]Truenodes0deg_sum0whilestack:ustack.pop()nodes1deg_sumlen(g[u])forving[u]:ifnotvis[v]:vis[v]Truestack.append(v)ifdeg_sum//2nodes*(nodes-1)//2:ans1returnans7/12 1331. 数组序号转换排序后用map存储各个数的序号defarrayRankTransform(arr): :type arr: List[int] :rtype: List[int] lsorted(arr)m{}num1print(l)fori,vinenumerate(l):ifi0andl[i-1]v:num1m[v]num ans[0]*len(arr)fori,vinenumerate(arr):ans[i]m[v]returnans
