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