力扣第 447 场周赛

718
Contest
LeetCode
本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。

3531. 统计被覆盖的建筑 - 力扣（LeetCode） ​

解题思路 ​

哈希表，二分查找，条件判断一下

示例代码 ​

python
class Solution:

    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
        rows = defaultdict(list)
        cols = defaultdict(list)
        for x, y in buildings:
            rows[y].append(x)
            cols[x].append(y)
        for k, v in cols.items():
            cols[k] = sorted(v)
        for k, v in rows.items():
            rows[k] = sorted(v)
        ans = 0
        for x, y in buildings:
            yidx = bisect_left(cols[x], y)
            xidx = bisect_left(rows[y], x)
            if 0 < yidx < len(cols[x]) - 1 and 0 < xidx < len(rows[y]) - 1:
                ans += 1
        return ans

3532. 针对图的路径存在性查询 I - 力扣（LeetCode） ​

解题思路 ​

数据结构，用并查集记录存在边的点集，判断两点是否存在路径

染色法，由于数据已经排序，记录可到达的最左边的点，判断两点是否存在路径

示例代码 ​

python
class Solution:
    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[bool]:
        l = list(range(n))
        for i in range(n - 1):
            if nums[i + 1] - nums[i] <= maxDiff:
                l[i + 1] = l[i]
        return [l[u] == l[v] for u, v in queries]

3533. 判断连接可整除性 - 力扣（LeetCode） ​

解题思路 ​

暴力搜索，对数组先进行排序，直接爆搜最小数组字典序的数组

位运算方面，拼接数的余数直接计算

参考：全排列暴搜（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def concatenatedDivisibility(self, nums: List[int], k: int) -> List[int]:
        nums.sort()
        pow10 = [pow(10, len(str(x))) for x in nums]
        ans = []

        @cache
        def dfs(mask: int, pre: int) -> None:
            if mask == 0:
                return pre == 0
            for i, (x, p10) in enumerate(zip(nums, pow10)):
                if mask >> i & 1 and dfs(mask ^ (1 << i), (pre * p10 + x) % k):
                    ans.append(x)
                    return True
            return False

        if not dfs((1 << len(nums)) - 1, 0):
            return []
        dfs.cache_clear()
        ans.reverse()
        return ans

3534. 针对图的路径存在性查询 II - 力扣（LeetCode） ​

解题思路 ​

参考：排序+双指针+倍增（Python/Java/C++/Go）

示例代码 ​

python
  class Solution:
    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[int]:
        idxs = sorted(range(n), key=lambda i: nums[i])

        rank = [0] * n
        for i, j in enumerate(idxs):
            rank[j] = i

        mx = n.bit_length()
        pa = [[0] * mx for _ in range(n)]
        left = 0
        for i, j in enumerate(idxs):
            while nums[j] - nums[idxs[left]] > maxDiff:
                left += 1
            pa[i][0] = left

        for i in range(mx - 1):
            for x in range(n):
                p = pa[x][i]
                pa[x][i + 1] = pa[p][i]

        ans = []
        for l, r in queries:
            if l == r:
                ans.append(0)
                continue
            l, r = rank[l], rank[r]
            if l > r:
                l, r = r, l
            res = 0
            for k in range(mx - 1, -1, -1):
                if pa[r][k] > l:
                    res |= 1 << k
                    r = pa[r][k]
            ans.append(-1 if pa[r][0] > l else res + 1)
        return ans
LeetCode Weekly Contest 448
LeetCode Weekly Contest 446