題目敘述 Walking Robot Simulation
機器人在一個無限大小的 X-Y 2D平面上行走，從點 (0, 0) 開始出發，一開始面向北方。
機器人可以接收以下三種類型的命令-2 ：向左轉 90 度
-1 ：向右轉 90 度
1 <= x <= 9 ：向前移動 x 個單位長度
在網格上有一些格子被視為障礙物 obstacles 。
第 i 個障礙物位於網格點 obstacles[i] = (xi, yi) 。 機器人無法走到障礙物上，它將會停留在障礙物的前一個網格方塊上，並繼續執行下一個命令。
請計算並且返回機器人距離原點的 最大距離 的 平方 。 （也就是說，如果距離為 5 ，則回傳 25 ）
測試範例
Example 1:
Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation:
機器人開始位於 (0, 0)：
1. 向北移動 4 個單位，到達 (0, 4)
2. 右轉
3. 向東移動 3 個單位，到達 (3, 4)
距離原點最遠的是 (3, 4) ，距離為 3^2 + 4^2 = 25
Example 2:
Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation:
機器人開始位於 (0, 0)：
1. 向北移動 4 個單位，到達 (0, 4)
2. 右轉
3. 向東移動 1 個單位，然後被位於 (2, 4) 的障礙物阻擋，機器人停在 (1, 4)
4. 左轉
5. 往北走 4 個單位，到達 (1, 8)
距離原點最遠的是 (1, 8) ，距離為 1^2 + 8^2 = 65
Example 3:
Input: commands = [6,-1,-1,6], obstacles = []
Output: 36
Explanation:
機器人開始位於 (0, 0):
1. 向北移動 6 個單位，到達 (0, 6).
2. 右轉
3. 右轉
4. 向南移動 6 個單位，到達 (0, 0).
機器人距離原點最遠的點是 (0, 6)，其距離的平方是 6^2 = 36 個單位。
約束條件
Constraints:
1 <= commands.length <= 10^4
指令的長度介於1~一萬。
commands[i]is either-2,-1, or an integer in the range[1, 9].
指令內容是-2(左轉), -1(右轉) 或者1~9之間的整數。
0 <= obstacles.length <= 10^4
障礙物陣列的長度介於0~一萬之間。
-3 * 10^4 <= xi, yi<= 3 * 10^4
x, y 座標都介於 負三萬~正三萬。
- The answer is guaranteed to be less than
2^31.
答案一定在4Byte整數範圍內。
演算法 根據指令模擬行進過程
指令內容是-2(左轉), -1(右轉) 或者1~9之間的整數(直接往前走k步)。
根據指令格式，判斷左轉、右轉、還是直接往前走k步。
每回合移動完之後，計算和原點的距離。
最後，回傳和原點的距離最大值的平方。
程式碼 根據指令模擬行進過程
class Solution:
def robotSim(self, commands, obstacles):
x, y = 0, 0
max_dist_square, direction = 0, 0
# North West South East
move, obstacles = [(0, 1), (-1, 0), (0, -1), (1, 0), ], set(map(tuple, obstacles))
for command in commands:
# Turn left
if command == -2: direction = (direction + 1) % 4
# Turn right
elif command == -1: direction = (direction - 1) % 4
else:
# Keep moving k times
delta_x, delta_y = move[direction]
while command and (x + delta_x, y + delta_y) not in obstacles:
x += delta_x
y += delta_y
command -= 1
max_dist_square = max(max_dist_square, x ** 2 + y ** 2)
return max_dist_square
複雜度分析
時間複雜度: O(n)
掃描每個指令一次，根據指令做出對應的行動。
空間複雜度: O(obstacle)
需要建立一個障礙物集合，所需空間為O(obstacle)
