LeetCode LCP 57. 打地鼠 -- 动态规划+二分查询过滤无效数据

LCP 57. 打地鼠
困难
11
相关企业
欢迎各位勇者来到力扣城，本次试炼主题为「打地鼠」。

勇者面前有一个大小为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

题解

这个题目很有意思，数据量也比较大，因为可以在时间维度上去和历史时间维度比较，所以很自然想到应该是动态规划，如何动态规划呢？

注意输入的数据不是严格按时间大小输入的，所以一开始需要先按时间大小对数据排个序。

定义dp[maxn]，dp[i]表示锤子停在第i个节点moles[i]对应的位置(moles[i][1], moles[i][2])时的最大收益，那么锤子需要停留在这个位置，就需要从[0,i-1]中去找哪些moles的位置和出现时间能够保证在时间(moles[i][0]-moles[j][0])内从位置(moles[j][1],moles[j][2])到位置(moles[i][1],moles[i][2])。

所以我们的动态规划方程式就列出来如下：

class Solution {
public:
    int dp[100010];
    int getMaximumNumber(vector<vector<int>>& moles) 
    {
        sort(moles.begin(), moles.end());
        for(int i=0;i<moles.size();i++)
        {
            int dis = abs(moles[i][1]-1) + abs(moles[i][2]-1);
            if(dis<=moles[i][0])
            dp[i] = 1;
            else
            dp[i] = -1e9;
        }
        for(int i=1;i<moles.size();i++)
        {
            for(int j=i-1;j>=0;j--)
            {
                if(moles[i][0]==moles[j][0])continue;
                int dis = abs(moles[i][1]-moles[j][1]) + abs(moles[i][2]-moles[j][2]);
                if(dis<=(moles[i][0]-moles[j][0]))
                {
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
        }
        int res = 0;
        for(int i=0;i<moles.size();i++)
        {
            res = max(res, dp[i]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

很显然这样有个问题，会超时，因为数据量为1e5，而且我们这里跑了两层循环。
这里的问题是我们要在[0,i-1]中可以到达第i个节点的节点来做比较，于是我们考虑了一个有趣的问题，在3x3的网格中，只要两个节点出现的时间距离超过3秒，任意两个位置都是可以相互到达的，所以这里我们可以快速去寻找在[0,i-1]中时间与第i个节点时间距离超过3秒的节点fin，然后直接与[0,fin]内最大的那个结果比较即可，然后在[fin,i]之间跑循环比较，因为这里每个时间节点最多有9个位置，时间距离在3秒内，所以最坏的情况就是需要训练3x9=27次，远远不会超时，问题顺利解决。

class Solution 
{
public:
    int dp[100010], dp_mx[100010];
    int getMaximumNumber(vector<vector<int>>& moles) 
    {
        sort(moles.begin(), moles.end());
        for(int i=0;i<moles.size();i++)
        {
            int dis = abs(moles[i][1]-1) + abs(moles[i][2]-1);
            if(dis<=moles[i][0])
            dp[i] = 1;
            else
            dp[i] = -1e9;
        }
        dp_mx[0] = dp[0];
        for(int i=1;i<moles.size();i++)
        {
            int l=0,r=i-1;
            int fin = -1;
            while(l<=r)
            {
                int mid = (l+r)/2;
                if(moles[i][0]-moles[mid][0]<=3)
                {
                    r = mid-1;
                    fin = mid;
                }
                else l = mid + 1;
            }
            //cout<<"fin="<
            //没有找到时间距离在0-3的，因为时间距离超过3的任何位置都可以到达另外一个位置。
            if(fin==-1)
            {
                dp[i] = dp_mx[i-1] + 1;
            }
            else
            {
                //说明[0,fin-1]这个区间的节点都是随便可以到第i个节点的位置，所以这里比较一下
                if(fin>0)
                dp[i] = max(dp[i], dp_mx[fin-1]+1);
                //因为这几个节点和第i个节点的时间距离为3，需要判断下距离是否能够达到
                for(int j=i-1;j>=fin;j--)
                {
                    if(moles[i][0]==moles[j][0])continue;
                    int dis = abs(moles[i][1]-moles[j][1]) + abs(moles[i][2]-moles[j][2]);
                    if(dis<=(moles[i][0]-moles[j][0]))
                    {
                        if(dp[j]+1>dp[i])
                        {
                            dp[i] = dp[j]+1;
                        }
                    }
                }
            }
            dp_mx[i] = max(dp_mx[i-1], dp[i]);
        }
        int res = 0;
        for(int i=0;i<moles.size();i++)
        {
            res = max(res, dp[i]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65