主題

LeetCode - 874. Walking Robot Simulation 解題心得

Not In My Back Yard | 2021-02-01 00:00:06 | 巴幣 0 | 人氣 61

題目連結:


題目意譯:
有一個機器人於一個無限延展的標準座標 XY 平面上的原點 (0, 0) 並面朝北。機器人可以接受以下三種可能的指令種類中之一:
-2: 向左旋轉 90 度;
-1: 向右旋轉 90 度;
1 <= k <= 9: 向前移動 k 單位長。

有些座標格子為障礙物。第 i 個障礙物位於格子點 obstacles[i] = (xi, yi)。

如果機器人試圖移動到障礙物,機器人將會停留於原先的格子(但是會繼續執行接著的指令)

回傳機器人在執行指令時離原點的最遠歐幾里德距離之平方(即如果距離值為 5 ,則回傳 25)。

注:
北代表 +Y 方向。
東代表 +X 方向。
南代表 -Y 方向。
西代表 -X 方向。

限制:
1 ≦ commands.length ≦ 10 ^ 4
commands[i] 保證是列表 [-2,-1,1,2,3,4,5,6,7,8,9] 中的其中一個值。
0 ≦ obstacles.length ≦ 10 ^ 4
-3 * 10 ^ 4 ≦ xi 、 yi ≦ 3 * 10 ^ 4
答案保證小於 2 ^ 31 。



範例測資:
範例 1:
輸入: commands = [4,-1,3], obstacles = []
輸出: 25
解釋: The robot starts at (0, 0):
1. 向北移動 4 單位到 (0, 4)。
2. 向右轉。
3. 向東移動 3 單位到 (3, 4)。
其中離原點最遠的點為 (3, 4),其距離平方為 3 ^ 2 + 4 ^ 5 = 25 平方單位遠。

範例 2:
輸入: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
輸出: 65
解釋: The robot starts at (0, 0):
1. 向北移動 4 單位到 (0, 4)。
2. 向右轉。
3. 向東移動 1 單位後被障礙物阻擋而只能到 (1, 4)。所以機器人在 (1, 4)。
4. 向左轉。
5. 向北移動 4 單位 (1, 8)。
其中離原點最遠的點為 (1, 8),其距離平方為 1 ^ 2 + 8 ^ 5 = 65 平方單位遠。


解題思維:
模擬即可。

不過因為有障礙物的存在,所以每當機器人要向前移動 k 單位時,不要一次移動 k 格,要一格一格動。然後每次動之前,先計算機器人會抵達何處,然後看該處是否為障礙物。如果是就停止前進。

但是如果每次都直接線性搜尋一個座標 (x, y) 是否為障礙物會很費時。因此我們可以把 obstacles 裡所有座標值丟進雜湊表(Hash Table)裡方便搜尋,或是將 obstacles 裡所有點按照 X 座標大小排序,X 座標一樣的再按照 Y 座標排序,然後每次搜尋時用二分搜尋法(Binary Search)去找目標座標是否存在於 obstacles 裡。如此一來,搜尋的時長就會降低,就不至於花太久時間甚至超時。

每次移動完後,計算當前座標與原點之距離平方,取其中最大的即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作