<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 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">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">robotSim</span><span class="hljs-params">(self, commands: List[int], obstacles: List[List[int]])</span> -> int:</span> pos = [<span class="hljs-params">0</span>, <span class="hljs-params">0</span>] deg = <span class="hljs-params">90</span> ans = <span class="hljs-params">0</span> obstaclesSet = set(map(tuple, obstacles)) <span class="hljs-keyword">for</span> command <span class="hljs-keyword">in</span> commands: <span class="hljs-keyword">if</span> command == <span class="hljs-params">-1</span>: deg = (deg + <span class="hljs-params">270</span>) % <span class="hljs-params">360</span> <span class="hljs-keyword">elif</span> command == <span class="hljs-params">-2</span>: deg = (deg + <span class="hljs-params">90</span>) % <span class="hljs-params">360</span> <span class="hljs-keyword">else</span>: <span class="hljs-keyword">if</span> deg == <span class="hljs-params">0</span>: i = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> i < command <span class="hljs-keyword">and</span> <span class="hljs-keyword">not</span> (pos[<span class="hljs-params">0</span>] + <span class="hljs-params">1</span>, pos[<span class="hljs-params">1</span>]) <span class="hljs-keyword">in</span> obstaclesSet: pos[<span class="hljs-params">0</span>] += <span class="hljs-params">1</span> i += <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> deg == <span class="hljs-params">90</span>: i = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> i < command <span class="hljs-keyword">and</span> <span class="hljs-keyword">not</span> (pos[<span class="hljs-params">0</span>], pos[<span class="hljs-params">1</span>] + <span class="hljs-params">1</span>) <span class="hljs-keyword">in</span> obstaclesSet: pos[<span class="hljs-params">1</span>] += <span class="hljs-params">1</span> i += <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> deg == <span class="hljs-params">180</span>: i = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> i < command <span class="hljs-keyword">and</span> <span class="hljs-keyword">not</span> (pos[<span class="hljs-params">0</span>] - <span class="hljs-params">1</span>, pos[<span class="hljs-params">1</span>]) <span class="hljs-keyword">in</span> obstaclesSet: pos[<span class="hljs-params">0</span>] -= <span class="hljs-params">1</span> i += <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> deg == <span class="hljs-params">270</span>: i = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> i < command <span class="hljs-keyword">and</span> <span class="hljs-keyword">not</span> (pos[<span class="hljs-params">0</span>], pos[<span class="hljs-params">1</span>] - <span class="hljs-params">1</span>) <span class="hljs-keyword">in</span> obstaclesSet: pos[<span class="hljs-params">1</span>] -= <span class="hljs-params">1</span> i += <span class="hljs-params">1</span> ans = max(ans, pos[<span class="hljs-params">0</span>] ** <span class="hljs-params">2</span> + pos[<span class="hljs-params">1</span>] ** <span class="hljs-params">2</span>) <span class="hljs-keyword">return</span> 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)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看