算法疑难杂症

力扣LCP03-机器人大冒险

字数统计: 1.2k字   |   阅读时长: 4分
,

摘要: LCP03，减治法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

今天看一个中等题吧，LCP 03，算法的思想还是非常主流的，就是经常跟分治法容易搞混的减治法，参考文章：减治法，注意细节处理。

$1 题目

力扣团队买了一个可编程机器人，机器人初始位置在原点(0, 0)。小伙伴事先给机器人输入一串指令command，机器人就会无限循环这条指令的步骤进行移动。指令有两种：

U: 向y轴正方向移动一格
R: 向x轴正方向移动一格。
不幸的是，在 xy 平面上还有一些障碍物，他们的坐标用obstacles表示。机器人一旦碰到障碍物就会被损毁。

给定终点坐标(x, y)，返回机器人能否完好地到达终点。如果能，返回true；否则返回false。

限制：

1
2
3
4
5
2 <= command的长度 <= 1000
command由U，R构成，且至少有一个U，至少有一个R
0 <= x <= 1e9, 0 <= y <= 1e9
0 <= obstacles的长度 <= 1000
obstacles[i]不为原点或者终点

示例 1：
输入：command = “URR”, obstacles = [], x = 3, y = 2
输出：true
解释：U(0, 1) -> R(1, 1) -> R(2, 1) -> U(2, 2) -> R(3, 2)。

示例 2：
输入：command = “URR”, obstacles = [[2, 2]], x = 3, y = 2
输出：false
解释：机器人在到达终点前会碰到(2, 2)的障碍物。

示例 3：
输入：command = “URR”, obstacles = [[4, 2]], x = 3, y = 2
输出：true
解释：到达终点后，再碰到障碍物也不影响返回结果。

$2 题解

算法：减治法

首先机器人按照指令串的行进路线要么是往右，要么是往上，不会是往下或往左。因此当终点是 (x, y)，障碍点坐标为 (x0, y0) 时，如果 x0 > x 或 y0 > y，则障碍点 (x0, y0) 对结果无影响。

障碍点 (x0, y0) 如果有 x0 <= x 且 y0 <= y，则带障碍点对结果可能有影响。对所有这些对结果可能有影响的障碍点去判断该点是否在行进路线上，如果在，则无法到达终点。

如果终点在行进道路上，同时所有对结果可能有影响的障碍点(x0 <= x 且 y0 <= y)都不在行进道路上，则可以到达终点。

因此要回答能否到达终点这个问题，只需要回答终点是否在行进道路上，以及在终点右下方向(含正右和正下)的障碍点是否在行进路线上。本质就是回答一个问题：给定一个点，问该点是否在行进路线上。

考察问题：对于给定一个点 (x, y)，是否在指令串 command 形成的行进路线上。其中 x 和 y 可以很大以及 command 可以无限循环。

减治法的思路

假设一个指令串含有 nU 个 U，nR 个 R，那么如果 x > nU, y > nR，则考察(x, y) 是否在行进路线上就等同于考察 (x - nR, y - nU) 是否在行进路线上。这样就等于是问了同一个问题，只是规模减小了，这正是减治法的思想。

通过对 y 取模的方式可以把这种减治一次性进行到底，同时 x 等比例变化，使得 y 的值为 0 到 nU 之间，考察此时等比例变化后的 x 在什么范围就可以得出结论，只是要注意细节处理。

代码 (C++)

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
class Solution {
public:
    bool robot(string command, vector<vector<int>>& obstacles, int x, int y) {
        nU = 0, nR = 0;
        for(const char& ch: command)
        {
            if(ch == 'U')
            {
                mapping.push_back(nR);
                ++nU;
            }
            else
                ++nR;
        }
        mapping.push_back(nR);
        if(!check(x, y))
            return false;
        for(vector<int> o: obstacles)
        {
            if(o[0] <= x && o[1] <= y && check(o[0], o[1]))
                return false;
        }
        return true;
    }

private:
    vector<int> mapping; // mapping[i] := command 前缀中第 i+1 个 U 之前最多有多少个 R
    int nU, nR; // command 中 U 的个数，R 的个数

    bool check(int x0, int y0)
    {
        int n_total = y0 / nU;
        int y = y0 - n_total * nU;
        int x = x0 - n_total * nR;
        if(y == 0 && x < 0)
            return base_check(x + nR, y + nU);
        return base_check(x, y);
    }

    bool base_check(int x0, int y0)
    {
        // 0 <= y0 <= nU
        int right = mapping[y0];
        int left = 0;
        if(y0 > 0)
            left = mapping[y0 - 1];
        if(left <= x0 && x0 <= right)
            return true;
        else
            return false;
    }
};
Share