【leetcode刷题】T177-模拟行走机器人

木又AI帮

发布于 2019-10-10 11:54:31

5190

发布于 2019-10-10 11:54:31

文章被收录于专栏：木又AI帮

木又连续日更第17天（17/100）

木又的第177篇7leetcode解题报告

贪心类型第6篇解题报告

leetcode第62题：模拟行走机器人

https://leetcode-cn.com/problems/walking-robot-simulation

【题目】

机器人在一个无限大小的网格上行走，从点 (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

【思路】

我们可以首先得到机器人前进的方向，再将可能前进的点进行判断是否有障碍物存在，如果有障碍物，则在障碍物前止步。

判断该点是否有障碍物，可将obstacles进行hash。

【代码】

python版本

class Solution(object):
    def robotSim(self, commands, obstacles):
        """
        :type commands: List[int]
        :type obstacles: List[List[int]]
        :rtype: int
        """
        # 每走一步前，查找该方向是否有障碍物
        obstacles = [tuple(oi) for oi in obstacles]
        ob = set(obstacles)
        print(ob)
        end = [0, 0]
        res = 0
        d = 90
        for c in commands:
            if c == -1:
                d = (d + 270) % 360
            elif c == -2:
                d = (d + 90) % 360
            else:
                 for i in range(1, c + 1):
                    if d == 0:
                        end[0] += 1
                    elif d == 90:
                        end[1] += 1
                    elif d == 180:
                        end[0] -= 1
                    else:
                        end[1] -= 1
                    # 判断当前值是否在obstacles中
                    if tuple(end) in ob:
                        if d == 0:
                            end[0] -= 1
                        elif d == 90:
                            end[1] -= 1
                        elif d == 180:
                            end[0] += 1
                        else:
                            end[1] += 1
                        break
                    res = max(res, end[0] ** 2 + end[1] ** 2)
        return res

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-10-04，如有侵权请联系 cloudcommunity@tencent.com 删除

机器人