打地鼠

标签: 数组 动态规划 矩阵 排序

难度: Hard

欢迎各位勇者来到力扣城，本次试炼主题为「打地鼠」。 ![middle_img_v2_d5d09656-0616-4a80-845e-ece461c5ba9g.png](https://pic.leetcode-cn.com/1650273183-nZIijm-middle_img_v2_d5d09656-0616-4a80-845e-ece461c5ba9g.png){:height="200px"} 勇者面前有一个大小为 `3*3` 的打地鼠游戏机，地鼠将随机出现在各个位置，`moles[i] = [t,x,y]` 表示在第 `t` 秒会有地鼠出现在 `(x,y)` 位置上，并于第 `t+1` 秒该地鼠消失。 勇者有一把可敲打地鼠的锤子，初始时刻（即第 `0` 秒）锤子位于正中间的格子 `(1,1)`，锤子的使用规则如下： - 锤子每经过 `1` 秒可以往上、下、左、右中的一个方向移动一格，也可以不移动 - 锤子只可敲击所在格子的地鼠，**敲击不耗时** 请返回勇者**最多**能够敲击多少只地鼠。 **注意：** - 输入用例保证在相同时间相同位置最多仅有一只地鼠 **示例 1：** >输入： `moles = [[1,1,0],[2,0,1],[4,2,2]]` > >输出： `2` > >解释： >第 0 秒，锤子位于 (1,1) >第 1 秒，锤子移动至 (1,0) 并敲击地鼠 >第 2 秒，锤子移动至 (2,0) >第 3 秒，锤子移动至 (2,1) >第 4 秒，锤子移动至 (2,2) 并敲击地鼠 >因此勇者最多可敲击 2 只地鼠 **示例 2：** >输入：`moles = [[2,0,2],[5,2,0],[4,1,0],[1,2,1],[3,0,2]]` > >输出：`3` > >解释： >第 0 秒，锤子位于 (1,1) >第 1 秒，锤子移动至 (2,1) 并敲击地鼠 >第 2 秒，锤子移动至 (1,1) >第 3 秒，锤子移动至 (1,0) >第 4 秒，锤子在 (1,0) 不移动并敲击地鼠 >第 5 秒，锤子移动至 (2,0) 并敲击地鼠 >因此勇者最多可敲击 3 只地鼠 **示例 3：** >输入：`moles = [[0,1,0],[0,0,1]]` > >输出：`0` > >解释： >第 0 秒，锤子初始位于 (1,1)，此时并不能敲击 (1,0)、(0,1) 位置处的地鼠 **提示：** + `1 <= moles.length <= 10^5` + `moles[i].length == 3` + `0 <= moles[i][0] <= 10^9` + `0 <= moles[i][1], moles[i][2] < 3`

Submission

运行时间: 458 ms

内存: 38.2 MB

class Solution:
    def getMaximumNumber(self, moles: List[List[int]]) -> int:
        moles1 = []
        f0 = 0
        for i in range(len(moles)):
            if moles[i][0] == 0:
                if moles[i][1] == 1 and moles[i][2] == 1:
                    f0 = 1
            else:
                moles1.append(moles[i])
        moles1.append([0, 1, 1])
        moles1.sort(key=lambda x: x[0])
        n = len(moles1)
        f = [0] * n
        p_max = [0] * n
        f[0] = f0
        p_max[0] = f0
        for i in range(1, n):
            t1, x1, y1 = moles1[i]
            for j in range(i - 1, -1, -1):
                t2, x2, y2 = moles1[j]
                if t1 - t2 >= 4:
                    f[i] = max(f[i], p_max[j] + 1)
                    break
                elif t1 - t2 >= abs(x1 - x2) + abs(y1 - y2):
                    f[i] = max(f[i], f[j] + 1)
            p_max[i] = max(f[i], p_max[i - 1])
        return p_max[n - 1]

Explain

该题解采用了动态规划的方法。首先，对特殊情况，即锤子在第0秒就能敲击到的地鼠进行处理，特别是当地鼠位于中心点(1,1)时。接着，将所有地鼠事件按时间顺序排序，并用一个动态规划数组f[i]来记录在达到第i个事件时，最多能敲击的地鼠数量。数组p_max用于快速获取前j个事件中最大的敲击数，以优化性能。在转移方程中，如果两个事件之间的时间差足够锤子从一个事件的位置移动到另一个位置，则尝试更新f[i]。这个方法综合考虑了时间和位置的约束，以达到最优解。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def getMaximumNumber(self, moles: List[List[int]]) -> int:
        moles1 = []
        f0 = 0
        # 处理t=0时刻特殊情况
        for i in range(len(moles)):
            if moles[i][0] == 0:
                if moles[i][1] == 1 and moles[i][2] == 1:
                    f0 = 1
            else:
                moles1.append(moles[i])
        moles1.append([0, 1, 1])
        # 按时间排序所有地鼠事件
        moles1.sort(key=lambda x: x[0])
        n = len(moles1)
        f = [0] * n
        p_max = [0] * n
        f[0] = f0
        p_max[0] = f0
        # 动态规划计算每个事件的最大敲击数
        for i in range(1, n):
            t1, x1, y1 = moles1[i]
            for j in range(i - 1, -1, -1):
                t2, x2, y2 = moles1[j]
                if t1 - t2 >= 4:
                    f[i] = max(f[i], p_max[j] + 1)
                    break
                elif t1 - t2 >= abs(x1 - x2) + abs(y1 - y2):
                    f[i] = max(f[i], f[j] + 1)
            p_max[i] = max(f[i], p_max[i - 1])
        return p_max[n - 1]

Explore

在给定的题解中，特别处理了t=0时刻地鼠出现在(1,1)位置的情况，因为(1,1)是中心点，从任何其他位置移动到中心点的距离都相等，这使得中心点成为一个战略位置。当有多只地鼠同时在t=0时刻出现在不同位置时，根据题解的逻辑，会优先选择(1,1)位置的地鼠敲击，因为它提供了最佳的起始位置优势。如果(1,1)位置没有地鼠，题解没有明确指定选择策略，这可能是一个题解的不足之处。理论上，应该选择一个位置，使得接下来能够最大化敲击数量的策略，但具体策略会依赖于后续地鼠的出现时间和位置。

在题解中添加一个[0, 1, 1]的元素到moles1数组是为了确保动态规划的过程中始终包含一个在时刻0、位置(1,1)的地鼠事件，即使在原始数据中没有地鼠在t=0时刻出现在(1,1)位置。这样做的目的是为了简化代码逻辑，使得动态规划的起点明确，始终从中心点开始计算。这个操作保证了动态规划数组f在计算每个事件的最大敲击数时，能够统一地从中心点开始考虑，不需要在代码中另外处理从边缘或其他位置开始的情况。这样的处理通过减少边界条件的复杂性，可以使代码更简洁且易于维护。