<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>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 0335. 路徑交叉 ## 題目地址(335. 路徑交叉) <https://leetcode-cn.com/problems/self-crossing/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個含有 n 個正數的數組 x。從點 (0,0) 開始,先向北移動 x[0] 米,然后向西移動 x[1] 米,向南移動 x[2] 米,向東移動 x[3] 米,持續移動。也就是說,每次移動后你的方位會發生逆時針變化。 編寫一個 O(1) 空間復雜度的一趟掃描算法,判斷你所經過的路徑是否相交。 示例 1: ┌───┐ │ │ └───┼──> │ 輸入: [2,1,1,2] 輸出: true 示例 2: ┌──────┐ │ │ │ │ └────────────> 輸入: [1,2,3,4] 輸出: false 示例 3: ┌───┐ │ │ └───┼> 輸入: [1,1,1,1] 輸出: true ``` ``` ## 前置知識 - 滑動窗口 ## 公司 - 暫無 ## 思路 符合直覺的做法是O(N)O(N)O(N)時間和空間復雜度的算法。這種算法非常簡單,但是題目要求我們使用空間復雜度為O(1)O(1)O(1)的做法。 關于空間復雜度為O(N)O(N)O(N)的算法可以參考我之前的[874.walking-robot-simulation](https://github.com/azl397985856/leetcode/blob/be15d243a3b93d7efa731d0589a54a63cbff61ae/problems/874.walking-robot-simulation.md)。 思路基本是類似,只不過 obstacles(障礙物)不是固定的,而是我們不斷遍歷的時候動態生成的,我們每遇到一個點,就將其標記為 obstacle。隨著算法的進行,我們的 obstacles 逐漸增大,最終和 N 一個量級。 我們考慮進行優化。我們仔細觀察發現,如果想讓其不相交,從大的范圍來看只有兩種情況: 1. 我們畫的圈不斷增大。 2. 我們畫的圈不斷減少。 ![](https://img.kancloud.cn/cb/14/cb14e51b00059ee2cc7fdd5acb09efdf_707x1186.jpg)(有沒有感覺像迷宮?) 這樣我們會發現,其實我們畫最新一筆的時候,并不是之前畫的所有的都需要考慮,我們只需要最近的幾個就可以了,實際上是最近的五個,不過不知道也沒關系,我們稍后會講解。 ![](https://img.kancloud.cn/2e/e1/2ee14fb3c4b1aeee79011a994aa5f6eb_1068x766.jpg) 紅色部分指的是我們需要考慮的,而剩余沒有被紅色標注的部分則無需考慮。不是因為我們無法與之相交,而是我們`一旦與之相交,則必然我們也一定會與紅色標記部分相交`。 然而我們畫的方向也是不用考慮的。比如我當前畫的方向是從左到右,那和我畫的方向是從上到下有區別么?在這里是沒區別的,不信我幫你將上圖順時針旋轉 90 度看一下: ![](https://img.kancloud.cn/69/cb/69cbc88f0b7007f52bbd53ca3112e7f0_547x1186.jpg) 方向對于我們考慮是否相交沒有差別。 當我們仔細思考的時候,會發現其實相交的情況只有以下幾種: ![](https://img.kancloud.cn/5d/a0/5da031a54addc89759acb6e603ee5ea9_996x870.jpg) 這個時候代碼就呼之欲出了。 - 我們只需要遍歷數組 x,假設當前是第 i 個元素。 - 如果 x\[i\] >= x\[i - 2\] and x\[i - 1\] <= x\[i - 3\],則相交(第一種情況) - 如果 x\[i - 1\] <= x\[i - 3\] and x\[i - 2\] <= x\[i\],則相交(第二種情況) - 如果 i > 3 and x\[i - 1\] == x\[i - 3\] and x\[i\] + x\[i - 4\] == x\[i - 2\],則相交(第三種情況) - 如果 i > 4 and x\[i\] + x\[i - 4\] >= x\[i - 2\] and x\[i - 1\] >= x\[i - 3\] - x\[i - 5\] \\ and x\[i - 1\] <= x\[i - 3\] and x\[i - 2\] >= x\[i - 4\] and x\[i - 3\] >= x\[i - 5\] ,則相交(第四種情況) - 否則不相交 ## 關鍵點解析 - 一定要畫圖輔助 - 對于這種O(1)O(1)O(1)空間復雜度有固定的套路。常見的有: - 直接修改原數組 - 滑動窗口(當前狀態并不是和之前所有狀態有關,而是僅和某幾個有關)。 我們采用的是滑動窗口。但是難點就在于我們怎么知道當前狀態和哪幾個有關。對于這道題來說,畫圖或許可以幫助你打開思路。另外面試的時候說出O(N)O(N)O(N)的思路也不失為一個幫助你冷靜分析問題的手段。 ## 代碼 代碼支持: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">isSelfCrossing</span><span class="hljs-params">(self, x: List[int])</span> -> bool:</span> n = len(x) <span class="hljs-keyword">if</span> n < <span class="hljs-params">4</span>: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">3</span>, n): <span class="hljs-keyword">if</span> x[i] >= x[i - <span class="hljs-params">2</span>] <span class="hljs-keyword">and</span> x[i - <span class="hljs-params">1</span>] <= x[i - <span class="hljs-params">3</span>]: <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> <span class="hljs-keyword">if</span> x[i - <span class="hljs-params">1</span>] <= x[i - <span class="hljs-params">3</span>] <span class="hljs-keyword">and</span> x[i - <span class="hljs-params">2</span>] <= x[i]: <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> <span class="hljs-keyword">if</span> i > <span class="hljs-params">3</span> <span class="hljs-keyword">and</span> x[i - <span class="hljs-params">1</span>] == x[i - <span class="hljs-params">3</span>] <span class="hljs-keyword">and</span> x[i] + x[i - <span class="hljs-params">4</span>] == x[i - <span class="hljs-params">2</span>]: <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> <span class="hljs-keyword">if</span> i > <span class="hljs-params">4</span> <span class="hljs-keyword">and</span> x[i] + x[i - <span class="hljs-params">4</span>] >= x[i - <span class="hljs-params">2</span>] <span class="hljs-keyword">and</span> x[i - <span class="hljs-params">1</span>] >= x[i - <span class="hljs-params">3</span>] - x[i - <span class="hljs-params">5</span>] \ <span class="hljs-keyword">and</span> x[i - <span class="hljs-params">1</span>] <= x[i - <span class="hljs-params">3</span>] <span class="hljs-keyword">and</span> x[i - <span class="hljs-params">2</span>] >= x[i - <span class="hljs-params">4</span>] <span class="hljs-keyword">and</span> x[i - <span class="hljs-params">3</span>] >= x[i - <span class="hljs-params">5</span>]: <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> ``` ``` **復雜度分析** 其中 N 為數組長度。 - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(1)O(1)O(1) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 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>

                              哎呀哎呀视频在线观看