# 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 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。