Leetcode 874 Walking Robot Simulation

发表于 |

A robot on an infinite grid starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands:
-2: turn left 90 degrees
-1: turn right 90 degrees
1 <= x <= 9: move forward x units
Some of the grid squares are obstacles.
The i-th obstacle is at grid point (obstacles[i][0], obstacles[i][1])
If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)
Return the square of the maximum Euclidean distance that the robot will be from the origin.

Example 1:
Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: robot will go to (3, 4)

Example 2:
Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)

Note:

  1. 0 <= commands.length <= 10000
  2. 0 <= obstacles.length <= 10000
  3. -30000 <= obstacle[i][0] <= 30000
  4. -30000 <= obstacle[i][1] <= 30000
  5. The answer is guaranteed to be less than 2 ^ 31.

分析：

  1. 首先应该确定目前行进的方向，我用(1,-1,-2,2)这四个值分别代表上下左右,dire = 1代表目前向上行进，故初始化dire = 1
  2. 当commands[i] = -2 or -1时，改变dire的值，这跟dire当前的值有关，具体方法于思路中说
  3. 因为每次行进的距离不超过10，那么最多也就走90000步，我们完全可以每一步都判断其是否被一个obstacles所阻挡，但是每次比较一个元祖是不是在集合中也太蠢了，所以稍微处理一下，我们用两个字典记录obstacles，例如，dx[x1]代表一个列表，列表里面记录所有横坐标为x1的点的纵坐标,dy[y1]同理
  4. 注意，这道题是要求整个过程中达到的最大的欧拉距离，并不是最后的距离，所有每移动一次就要比较一次，我就是没看到这一点，做了特别特别久，都不知道哪里错了！

思路：

  1. 我们用一个directions = {1:[-2,2], -1:[2,-2], -2:[-1,1], 2:[1,-1]}记录方向的变换，对于directions[x]，x代表当前方向，directions[x][0]表示向左转之后的方向，directions[x][1]代表向右转之后的方向
  2. 用position=[x,y]记录此时的位置，每进行一次移动就记录一次
  3. 别看代码这么长，其实后面的代码都是一样的（只跟方向有关），因为太恶心了我也懒得整合了
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
# O(n) time, O(n) space
class Solution(object):
    def robotSim(self, commands, obstacles):
        """
        :type commands: List[int]
        :type obstacles: List[List[int]]
        :rtype: int
        """
        dx = collections.defaultdict(set)
        dy = collections.defaultdict(set)
        for x,y in obstacles:
            dx[x].add(y)
            dy[y].add(x)

        position = [0, 0]
        directions = {1:[-2,2], -1:[2,-2], -2:[-1,1], 2:[1,-1]}
        dire = 1
        res = 0
        for i in range(len(commands)):
            # 左转
            if commands[i] == -2:
                dire = directions[dire][0]
            # 右转
            elif commands[i] == -1:
                dire = directions[dire][1]
            else:
                x = commands[i]
                # 若在向上or下走，固定x,判断每个y是否存在于dx[x]中
                if dire == 1:
                    for i in range(1,x+1):
                        if position[1] + i in dx[position[0]]:
                            position[1] = position[1] + i - 1
                            break
                    else:
                        position[1] = position[1] + i
                elif dire == -1:
                    for i in range(1,x+1):
                        if position[1] - i in dx[position[0]]:
                            position[1] = position[1] - i + 1
                            break
                    else:
                        position[1] = position[1] - i
                # 若在向左or右走，固定y，判断每个x是否存在于dy[y]中
                elif dire == -2:
                    for i in range(1,x+1):
                        if position[0] - i in dy[position[1]]:
                            position[0] = position[0] - i + 1
                            break
                    else:
                        position[0] = position[0] - i
                elif dire == 2:
                    for i in range(1,x+1):
                        if position[0] + i in dy[position[1]]:
                            position[0] = position[0] + i - 1
                            break
                    else:
                        position[0] = position[0] + i
            res = max(res, position[0]**2 + position[1]**2)
        return res

47 / 47 test cases passed.
diffculty: easy
Runtime: 144 ms