第 447 场周赛-20250427

https://leetcode.cn/contest/weekly-contest-447/

中国时间：2025-04-27 10:30, 1 小时 30 分

给你一个正整数数组 nums 和一个正整数 k。

当 nums 的一个排列中的所有数字，按照排列顺序 连接其十进制表示 后形成的数可以被 k 整除时，我们称该排列形成了一个 可整除连接 。

返回能够形成 可整除连接 且 字典序最小 的排列（按整数列表的形式表示）。如果不存在这样的排列，返回一个空列表。

排列是数组所有元素的一种重排。

如果在数组 a 和数组 b 第一个位置不同的地方，a 的元素小于对应位置上 b 的元素，那么数组 a 的 字典序小于数组 b 。如果前 min(a.length, b.length) 个元素均相同，则较短的数组字典序更小。

示例 1：

输入: nums = [3,12,45], k = 5

输出: [3,12,45]

解释:

排列	连接后的值	是否能被 5 整除
[3, 12, 45]	31245	是
[3, 45, 12]	34512	否
[12, 3, 45]	12345	是
[12, 45, 3]	12453	否
[45, 3, 12]	45312	否
[45, 12, 3]	45123	否

可以形成可整除连接且字典序最小的排列是 [3,12,45]。

示例 2：

输入: nums = [10,5], k = 10

输出: [5,10]

解释:

排列	连接后的值	是否能被 10 整除
[5, 10]	510	是
[10, 5]	105	否

可以形成可整除连接且字典序最小的排列是 [5,10]。

示例 3：

输入: nums = [1,2,3], k = 5

输出: []

解释:

由于不存在任何可以形成有效可整除连接的排列，因此返回空列表。

提示：

1 <= nums.length <= 13
1 <= nums[i] <= 10^5
1 <= k <= 100

python

class Solution:
    def concatenatedDivisibility(self, nums: List[int], k: int) -> List[int]:

T3534.针对图的路径存在性查询II

https://leetcode.cn/problems/path-existence-queries-in-a-graph-ii/

给你一个整数 n，表示图中的节点数量，这些节点按从 0 到 n - 1 编号。

同时给你一个长度为 n 的整数数组 nums，以及一个整数 maxDiff。

如果满足 |nums[i] - nums[j]| <= maxDiff（即 nums[i] 和 nums[j] 的 绝对差 至多为 maxDiff），则节点 i 和节点 j 之间存在一条 无向边 。

此外，给你一个二维整数数组 queries。对于每个 queries[i] = [ui, vi]，找到节点 ui 和节点 vi 之间的 最短距离 。如果两节点之间不存在路径，则返回 -1。

返回一个数组 answer，其中 answer[i] 是第 i 个查询的结果。

注意：节点之间的边是无权重（unweighted）的。

示例 1：

输入: n = 5, nums = [1,8,3,4,2], maxDiff = 3, queries = [[0,3],[2,4]]

输出: [1,1]

解释:

生成的图如下：

查询	最短路径	最短距离
[0, 3]	0 → 3	1
[2, 4]	2 → 4	1

因此，输出为 [1, 1]。

示例 2：

输入: n = 5, nums = [5,3,1,9,10], maxDiff = 2, queries = [[0,1],[0,2],[2,3],[4,3]]

输出: [1,2,-1,1]

解释:

生成的图如下：

查询	最短路径	最短距离
[0, 1]	0 → 1	1
[0, 2]	0 → 1 → 2	2
[2, 3]	无	-1
[4, 3]	3 → 4	1

因此，输出为 [1, 2, -1, 1]。

示例 3：

输入: n = 3, nums = [3,6,1], maxDiff = 1, queries = [[0,0],[0,1],[1,2]]

输出: [0,-1,-1]

解释:

由于以下原因，任意两个节点之间都不存在边：

节点 0 和节点 1：|nums[0] - nums[1]| = |3 - 6| = 3 > 1
节点 0 和节点 2：|nums[0] - nums[2]| = |3 - 1| = 2 > 1
节点 1 和节点 2：|nums[1] - nums[2]| = |6 - 1| = 5 > 1

因此，不存在任何可以到达其他节点的节点，输出为 [0, -1, -1]。

提示：

1 <= n == nums.length <= 10^5
0 <= nums[i] <= 10^5
0 <= maxDiff <= 10^5
1 <= queries.length <= 10^5
queries[i] == [ui, vi]
0 <= ui, vi < n

超出时间限制 664 / 682 个通过的测试用例

按「并查集 + 动态 BFS」思路修正

连通性剪枝
- 排序后只对相邻对做并查，快速判断两点若不在同一块，直接 -1。
真正的 BFS
- 不再预先把所有边都存到邻接表（那会是 O(n²)），而是在 BFS 扩展时动态找“滑动窗口”内的所有未访问节点：
  1. 先把所有节点按 nums 升序，记为数组 A，并维护一个平衡集合（Python 用 bisect + list 或第三方的 sortedcontainers）存放「还没被 BFS 访问过」的所有 排序下标。
  2. 从起点 u 出发，把它在排序中的位置 ru 弹出集合并入队，dist[ru]=0。
  3. 每次取出当前排位 x，用二分在 A 上找左右界
    python
```
lo = bisect_left(A, A[x] - maxDiff)
hi = bisect_right(A, A[x] + maxDiff) - 1
```
  4. 在平衡集合里快速定位所有 ∈ [lo..hi] 的排位 y，它们都是直接邻居：
    - 将它们从集合里一并删掉
    - dist[y] = dist[x] + 1，加入队列
  5. 直到你把目标 rv 弹出，返回它的 dist。

这样一来，每个节点 只会被访问一次，查找窗口又是 O(log n) 去定位边界，摊销下来 O((n + q)·log n)。

python

from collections import deque
from bisect import bisect_left, bisect_right
from sortedcontainers import SortedList  # pip install sortedcontainers

class Solution:
    def pathExistenceQueries(self, n, nums, maxDiff, queries):
        # 1) 并查集只对相邻排序对做 union，用于快速连通性剪枝
        parent = list(range(n))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        def union(a, b):
            pa, pb = find(a), find(b)
            if pa != pb:
                parent[pb] = pa

        nodes = list(range(n))
        nodes.sort(key=lambda i: nums[i])
        for i in range(n-1):
            u, v = nodes[i], nodes[i+1]
            if nums[v] - nums[u] <= maxDiff:
                union(u, v)

        # 2) 排序数组 & 反向映射
        A   = [nums[i] for i in nodes]
        pos = [0]*n
        for sorted_idx, orig in enumerate(nodes):
            pos[orig] = sorted_idx

        answers = []
        for u, v in queries:
            if u == v:
                answers.append(0)
                continue
            # 剪枝：不连通就 -1
            if find(u) != find(v):
                answers.append(-1)
                continue

            # 真正 BFS：在排序下标空间里跑
            ru, rv = pos[u], pos[v]
            # ensure we know when we hit rv
            sl = SortedList(range(n))      # 当前所有未访问的排位
            dist = [-1]*n

            dq = deque()
            dq.append(ru)
            dist[ru] = 0
            sl.remove(ru)

            while dq:
                x = dq.popleft()
                if x == rv:
                    break

                # 找到所有 A[y] 与 A[x] 差值 ≤ maxDiff 的 y ∈ sl
                lo = bisect_left(A, A[x] - maxDiff)
                hi = bisect_right(A, A[x] + maxDiff) - 1

                # sl.irange 直接取出所有 in [lo, hi]
                for y in list(sl.irange(lo, hi)):
                    sl.remove(y)
                    dist[y] = dist[x] + 1
                    dq.append(y)

            answers.append(dist[rv])

        return answers

关键点

不要只连“相邻对”，否则只构建了生成树，漏掉大量直接边，导致最短路被拉长。
在线 BFS 时用「滑动窗口 + 平衡集合」动态枚举所有 |nums[i]−nums[j]|≤maxDiff 的邻居。
并查集只负责把明显不连通的查询剪掉，避免 BFS 白跑。

这样既修正了建图的错误，也能在 $n, q \leq 10^{5}$ 的规模下通过所有测试。

第 447 场周赛-20250427 ​

M3531.统计被覆盖的建筑 ​

M3532.针对图的路径存在性查询I ​

T3533.判断连接可整除性 ​

T3534.针对图的路径存在性查询II ​

第 447 场周赛-20250427

M3531.统计被覆盖的建筑

M3532.针对图的路径存在性查询I

T3533.判断连接可整除性

T3534.针对图的路径存在性查询II