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)