# 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. 我們畫的圈不斷減少。 （有沒有感覺像迷宮？） 這樣我們會發現，其實我們畫最新一筆的時候，并不是之前畫的所有的都需要考慮，我們只需要最近的幾個就可以了，實際上是最近的五個，不過不知道也沒關系，我們稍后會講解。  紅色部分指的是我們需要考慮的，而剩余沒有被紅色標注的部分則無需考慮。不是因為我們無法與之相交，而是我們`一旦與之相交，則必然我們也一定會與紅色標記部分相交`。 然而我們畫的方向也是不用考慮的。比如我當前畫的方向是從左到右，那和我畫的方向是從上到下有區別么？在這里是沒區別的，不信我幫你將上圖順時針旋轉 90 度看一下：  方向對于我們考慮是否相交沒有差別。 當我們仔細思考的時候，會發現其實相交的情況只有以下幾種：  這個時候代碼就呼之欲出了。 - 我們只需要遍歷數組 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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。