0874. 模拟行走机器人 · ttttt

# 0874. 模拟行走机器人 ## 题目地址（874. 模拟行走机器人） <https://leetcode-cn.com/problems/walking-robot-simulation/submissions/> ## 题目描述 ``` <pre class="calibre18">``` 机器人在一个无限大小的网格上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令： -2：向左转 90 度 -1：向右转 90 度 1 <= x <= 9：向前移动 x 个单位长度在网格上有一些格子被视为障碍物。第 i 个障碍物位于网格点 (obstacles[i][0], obstacles[i][1]) 如果机器人试图走到障碍物上方，那么它将停留在障碍物的前一个网格方块上，但仍然可以继续该路线的其余部分。返回从原点到机器人的最大欧式距离的平方。示例 1：输入: commands = [4,-1,3], obstacles = [] 输出: 25 解释: 机器人将会到达 (3, 4) 示例 2：输入: commands = [4,-1,4,-2,4], obstacles = [[2,4]] 输出: 65 解释: 机器人在左转走到 (1, 8) 之前将被困在 (1, 4) 处提示： 0 <= commands.length <= 10000 0 <= obstacles.length <= 10000 -30000 <= obstacle[i][0] <= 30000 -30000 <= obstacle[i][1] <= 30000 答案保证小于 2 ^ 31 ``` ``` ## 前置知识 - hashtable ## 公司 - 暂无 ## 思路这道题之所以是简单难度，是因为其没有什么技巧。你只需要看懂题目描述，然后把题目描述转化为代码即可。唯一需要注意的是查找障碍物的时候如果你采用的是`线形查找`会很慢，很可能会超时。 > 我实际测试了一下，确实会超时 - 一种方式是使用排序，然后二分查找，如果采用基于比较的排序算法，那么这种算法的瓶颈在于排序本身，也就是O(NlogN)O(NlogN)O(NlogN)。 - 另一种方式是使用集合，将 obstacles 放入集合，然后需要的时候进行查询，查询的时候的时间复杂度为O(1)O(1)O(1)。这里我们采用第二种方式。接下来我们来“翻译”一下题目。 - 由于机器人只能往前走。因此机器人往东西南北哪个方向走取决于它的`朝向`。 - 我们使用枚举来表示当前机器人的`朝向`。 - 题目只有两种方式改变`朝向`，一种是左转（-2），另一种是右转（-1）。 - 题目要求的是机器人在`运动过程中距离原点的最大值`，而不是最终位置距离原点的距离。为了代码书写简单，我建立了一个直角坐标系。用`机器人的朝向和 x 轴正方向的夹角度数`来作为枚举值，并且这个度数是 `0 <= deg < 360`。我们不难知道，其实这个取值就是`0`, `90`,`180`,`270` 四个值。那么当 0 度的时候，我们只需要不断地 x+1，90 度的时候我们不断地 y + 1 等等。 ![](https://img.kancloud.cn/6e/95/6e956186bcad9f56db40911e569bbd65_1298x980.jpg) ## 关键点解析 - 理解题意，这道题容易理解错题意，求解为`最终位置距离原点的距离` - 建立坐标系 - 空间换时间 ## 代码代码支持： Python3 Python3 Code: ``` <pre class="calibre18">``` class Solution: def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int: pos = [0, 0] deg = 90 ans = 0 obstaclesSet = set(map(tuple, obstacles)) for command in commands: if command == -1: deg = (deg + 270) % 360 elif command == -2: deg = (deg + 90) % 360 else: if deg == 0: i = 0 while i < command and not (pos[0] + 1, pos[1]) in obstaclesSet: pos[0] += 1 i += 1 if deg == 90: i = 0 while i < command and not (pos[0], pos[1] + 1) in obstaclesSet: pos[1] += 1 i += 1 if deg == 180: i = 0 while i < command and not (pos[0] - 1, pos[1]) in obstaclesSet: pos[0] -= 1 i += 1 if deg == 270: i = 0 while i < command and not (pos[0], pos[1] - 1) in obstaclesSet: pos[1] -= 1 i += 1 ans = max(ans, pos[0] ** 2 + pos[1] ** 2) return ans ``` ``` **复杂度分析** - 时间复杂度：O(N∗M)O(N \* M)O(N∗M), 其中 N 为 commands 的长度， M 为 commands 数组的平均值。 - 空间复杂度：O(obstacles)O(obstacles)O(obstacles) 更多题解可以访问我的LeetCode题解仓库：<https://github.com/azl397985856/leetcode> 。目前已经37K star啦。关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)