♟縱橫四海 模擬機器人的軌跡 Walking Robot Simulation_Leetcode #874

閱讀時間約 1 分鐘

題目敘述 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)


Reference

[1] Walking Robot Simulation - LeetCode

83會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
Leetcode #1945. Sum of Digits of String After Convert 給定一個由小寫字母組成的字串 s ,以及一個整數 k 。 首先,用英文字母順序的位置替換每個字母,將 s 轉換 為整數 並且計算digits sum,反覆迭代k次。
給定一個長度為 n,而且索引從 0 開始的整數陣列 chalk 和參數 k 。一開始粉筆盒裡總共有 k 支粉筆。 當編號為 i 的學生回答問題時,會消耗 chalk[i] 支粉筆。 如果剩餘粉筆數量小於 chalk[i] ,那麼學生 i 需要 補充 粉筆。 請找出需要補充粉筆的學生的學生編號。
Convert 1D Array Into 2D Array 給定一個一維輸入陣列,請轉換成高度為m*寬度為n的二維陣列, 以二維陣列的形式輸出。 如果無法轉換,請輸出空陣列。
題目敘述 624. Maximum Distance in Arrays 給定一個輸入二維陣列arrays。 請計算的陣列距離是多少? 陣列距離的定義 = max | a - b | 其中 a, b 來自不同的一維陣列
題目敘述 860. Lemonade Change 假想一個經營檸檬水小舖的情境。 一杯檸檬水都賣$5 顧客付錢時只有三種可能,$5, $10 或 $ 20 初始時,檸檬水小舖沒有零錢。 給定一個顧客買檸檬水的付錢陣列bills,請問能不能滿足每一筆交易,並且找開零錢。 如果可以
題目敘述 149. Max Points on a Line 給定一串2維平面的點座標,請問最多有幾個點落在同一條直線上? 落在同一條直線也就是數學上所謂的"共線" colinear
Leetcode #1945. Sum of Digits of String After Convert 給定一個由小寫字母組成的字串 s ,以及一個整數 k 。 首先,用英文字母順序的位置替換每個字母,將 s 轉換 為整數 並且計算digits sum,反覆迭代k次。
給定一個長度為 n,而且索引從 0 開始的整數陣列 chalk 和參數 k 。一開始粉筆盒裡總共有 k 支粉筆。 當編號為 i 的學生回答問題時,會消耗 chalk[i] 支粉筆。 如果剩餘粉筆數量小於 chalk[i] ,那麼學生 i 需要 補充 粉筆。 請找出需要補充粉筆的學生的學生編號。
Convert 1D Array Into 2D Array 給定一個一維輸入陣列,請轉換成高度為m*寬度為n的二維陣列, 以二維陣列的形式輸出。 如果無法轉換,請輸出空陣列。
題目敘述 624. Maximum Distance in Arrays 給定一個輸入二維陣列arrays。 請計算的陣列距離是多少? 陣列距離的定義 = max | a - b | 其中 a, b 來自不同的一維陣列
題目敘述 860. Lemonade Change 假想一個經營檸檬水小舖的情境。 一杯檸檬水都賣$5 顧客付錢時只有三種可能,$5, $10 或 $ 20 初始時,檸檬水小舖沒有零錢。 給定一個顧客買檸檬水的付錢陣列bills,請問能不能滿足每一筆交易,並且找開零錢。 如果可以
題目敘述 149. Max Points on a Line 給定一串2維平面的點座標,請問最多有幾個點落在同一條直線上? 落在同一條直線也就是數學上所謂的"共線" colinear
你可能也想看
Google News 追蹤
Thumbnail
本專欄將提供給您最新的市場資訊、產業研究、交易心法、精選公司介紹,以上內容並非個股分析,還請各位依據自身狀況作出交易決策。歡迎訂閱支持我,獲得相關內容,也祝您的投資之路順遂! 每年 $990 訂閱方案👉 https://reurl.cc/VNYVxZ 每月 $99 訂閱方案👉https://re
Thumbnail
如果穿越這個隧道 時光可以回溯 我想回到初識的那天
程式語言在特定環境下就是魔法 現實世界也應該要有非大眾可以理解的規則與金手指才對 #因為架構太完整,這篇噗浪有用匿名發過 #故事取用前請簡單告知
Thumbnail
每段關係都有最佳賞味期,誰也不知道期限。現實世界中的美好結局,早就不是童話故事的樣貌。
一些人到異世界,一些人在宇宙旅行,只為了賭一把。
威力賦予人工智能機器人T50自由意識,讓它自行決定存在的意義。
Thumbnail
從異世界逃難而來的軟Q轉學生,竟然是身經百戰的勇者!看似和平的校園生活,人類和異世界各個陣營卻各懷鬼胎,軟Q們一面在異鄉努力求生,一面要防範敵人偷襲,檯面下暗潮洶湧的諜對諜一波未平一波又起,大戰是否將一觸即發?
Thumbnail
宇宙,終極的邊疆。這是星艦企業號的旅程。
它的任務,就是要持續探索未知的新世界,
找尋新生命以及新文明,勇敢踏入前人未至之境。
Thumbnail
一位時間旅行者發明了一部能夠穿越時空的時間機器,並成功乘坐該機器去到了未來......
Thumbnail
本專欄將提供給您最新的市場資訊、產業研究、交易心法、精選公司介紹,以上內容並非個股分析,還請各位依據自身狀況作出交易決策。歡迎訂閱支持我,獲得相關內容,也祝您的投資之路順遂! 每年 $990 訂閱方案👉 https://reurl.cc/VNYVxZ 每月 $99 訂閱方案👉https://re
Thumbnail
如果穿越這個隧道 時光可以回溯 我想回到初識的那天
程式語言在特定環境下就是魔法 現實世界也應該要有非大眾可以理解的規則與金手指才對 #因為架構太完整,這篇噗浪有用匿名發過 #故事取用前請簡單告知
Thumbnail
每段關係都有最佳賞味期,誰也不知道期限。現實世界中的美好結局,早就不是童話故事的樣貌。
一些人到異世界,一些人在宇宙旅行,只為了賭一把。
威力賦予人工智能機器人T50自由意識,讓它自行決定存在的意義。
Thumbnail
從異世界逃難而來的軟Q轉學生,竟然是身經百戰的勇者!看似和平的校園生活,人類和異世界各個陣營卻各懷鬼胎,軟Q們一面在異鄉努力求生,一面要防範敵人偷襲,檯面下暗潮洶湧的諜對諜一波未平一波又起,大戰是否將一觸即發?
Thumbnail
宇宙,終極的邊疆。這是星艦企業號的旅程。
它的任務,就是要持續探索未知的新世界,
找尋新生命以及新文明,勇敢踏入前人未至之境。
Thumbnail
一位時間旅行者發明了一部能夠穿越時空的時間機器,並成功乘坐該機器去到了未來......