力扣第 163 场双周赛

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

3648. 覆盖网格的最少传感器数目 - 力扣（LeetCode） ​

题目类型 ​

#数学

解题思路 ​

参考：O(1) 数学公式（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def minSensors(self, n: int, m: int, k: int) -> int:
        return (n + 2 * k) // (2 * k + 1) * ((m + 2 * k) // (2 * k + 1))

3649. 完美对的数目 - 力扣（LeetCode） ​

题目类型 ​

#双指针

解题思路 ​

条件二恒成立，条件一等价于|OA - OB| <= min(|a|, |b|) = min(OA, OB)，如果|a| < |b|，即OB <= 2*OA，同理可证绝对值较大值不能超过较小值的两倍

参考：用绝对值的几何意义化简式子（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def perfectPairs(self, nums: List[int]) -> int:
        nums = [abs(x) for x in nums]
        nums.sort()
        ans = l = 0
        for r, x in enumerate(nums):
            while l < r and nums[l] < x - x // 2:
                l += 1
            ans += r - l
        return ans

3650. 边反转的最小路径总成本 - 力扣（LeetCode） ​

题目类型 ​

#最短路 #Dijkstra

解题思路 ​

加入反转边，权值为正向边的两倍，用 dijkstra 计算最短路即可

示例代码 ​

python
class Solution:
    def minCost(self, n: int, edges: List[List[int]]) -> int:
        g = [[] for _ in range(n)]
        for u, v, w in edges:
            g[u].append((v, w))
            g[v].append((u, 2 * w))

        h = [(0, 0)]
        dis = [inf] * n
        dis[0] = 0
        while h:
            d, x = heappop(h)
            if d > dis[x]:
                continue
            for y, w in g[x]:
                nd = d + w
                if nd < dis[y]:
                    dis[y] = nd
                    heappush(h, (nd, y))
        return dis[-1] if dis[-1] < inf else -1

3651. 带传送的最小路径成本 - 力扣（LeetCode） ​

题目类型 ​

#动态规划 #后缀最小值优化 #网格图DP #Dijkstra

解题思路 ​

由于原地传送不会增加成本，所以至多k 次等于恰好k 次。

后缀最小值优化，由于传送成本为 0，所以到达权值较小的元素所需成本可以覆盖权值较大元素的所需成本，更新所需成本时需要按权值从大到小遍历。

参考：DP| 网格图 DP + 后缀最小值优化（Python/Java/C++/Go）

示例代码 ​

python
fmin = lambda x, y: x if x < y else y
class Solution:
    def minCost(self, grid: List[List[int]], k: int) -> int:
        n, m = len(grid), len(grid[0])
        f = [[inf] * m for _ in range(n)]
        f[0][0] = 0
        d = defaultdict(list)
        for i in range(n):
            for j in range(m):
                if i + 1 < n:
                    f[i + 1][j] = fmin(f[i + 1][j], f[i][j] + grid[i + 1][j])
                if j + 1 < m:
                    f[i][j + 1] = fmin(f[i][j + 1], f[i][j] + grid[i][j + 1])
                d[grid[i][j]].append((i, j))

        # (0, 0) -> (x, y) -> (i, j)
        ans = f[-1][-1]
        keys = sorted(d.keys(), reverse=True)
        for t in range(1, k + 1):
            mn = inf
            nf = f
            for key in keys:
                for x, y in d[key]:
                    mn = fmin(mn, f[x][y])
                for x, y in d[key]:
                    nf[x][y] = mn

            for i in range(n):
                for j in range(m):
                    if i + 1 < n:
                        nf[i + 1][j] = fmin(nf[i + 1][j], nf[i][j] + grid[i + 1][j])
                    if j + 1 < m:
                        nf[i][j + 1] = fmin(nf[i][j + 1], nf[i][j] + grid[i][j + 1])
            f = nf[:]
            ans = fmin(ans, f[-1][-1])
        return ans
力扣第 464 场周赛
力扣第 463 场周赛