# 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)
- Introduction
- 第一章 - 算法专题
- 数据结构
- 基础算法
- 二叉树的遍历
- 动态规划
- 哈夫曼编码和游程编码
- 布隆过滤器
- 字符串问题
- 前缀树专题
- 《贪婪策略》专题
- 《深度优先遍历》专题
- 滑动窗口(思路 + 模板)
- 位运算
- 设计题
- 小岛问题
- 最大公约数
- 并查集
- 前缀和
- 平衡二叉树专题
- 第二章 - 91 天学算法
- 第一期讲义-二分法
- 第一期讲义-双指针
- 第二期
- 第三章 - 精选题解
- 《日程安排》专题
- 《构造二叉树》专题
- 字典序列删除
- 百度的算法面试题 * 祖玛游戏
- 西法的刷题秘籍】一次搞定前缀和
- 字节跳动的算法面试题是什么难度?
- 字节跳动的算法面试题是什么难度?(第二弹)
- 《我是你的妈妈呀》 * 第一期
- 一文带你看懂二叉树的序列化
- 穿上衣服我就不认识你了?来聊聊最长上升子序列
- 你的衣服我扒了 * 《最长公共子序列》
- 一文看懂《最大子序列和问题》
- 第四章 - 高频考题(简单)
- 面试题 17.12. BiNode
- 0001. 两数之和
- 0020. 有效的括号
- 0021. 合并两个有序链表
- 0026. 删除排序数组中的重复项
- 0053. 最大子序和
- 0088. 合并两个有序数组
- 0101. 对称二叉树
- 0104. 二叉树的最大深度
- 0108. 将有序数组转换为二叉搜索树
- 0121. 买卖股票的最佳时机
- 0122. 买卖股票的最佳时机 II
- 0125. 验证回文串
- 0136. 只出现一次的数字
- 0155. 最小栈
- 0167. 两数之和 II * 输入有序数组
- 0169. 多数元素
- 0172. 阶乘后的零
- 0190. 颠倒二进制位
- 0191. 位1的个数
- 0198. 打家劫舍
- 0203. 移除链表元素
- 0206. 反转链表
- 0219. 存在重复元素 II
- 0226. 翻转二叉树
- 0232. 用栈实现队列
- 0263. 丑数
- 0283. 移动零
- 0342. 4的幂
- 0349. 两个数组的交集
- 0371. 两整数之和
- 0437. 路径总和 III
- 0455. 分发饼干
- 0575. 分糖果
- 0874. 模拟行走机器人
- 1260. 二维网格迁移
- 1332. 删除回文子序列
- 第五章 - 高频考题(中等)
- 0002. 两数相加
- 0003. 无重复字符的最长子串
- 0005. 最长回文子串
- 0011. 盛最多水的容器
- 0015. 三数之和
- 0017. 电话号码的字母组合
- 0019. 删除链表的倒数第N个节点
- 0022. 括号生成
- 0024. 两两交换链表中的节点
- 0029. 两数相除
- 0031. 下一个排列
- 0033. 搜索旋转排序数组
- 0039. 组合总和
- 0040. 组合总和 II
- 0046. 全排列
- 0047. 全排列 II
- 0048. 旋转图像
- 0049. 字母异位词分组
- 0050. Pow(x, n)
- 0055. 跳跃游戏
- 0056. 合并区间
- 0060. 第k个排列
- 0062. 不同路径
- 0073. 矩阵置零
- 0075. 颜色分类
- 0078. 子集
- 0079. 单词搜索
- 0080. 删除排序数组中的重复项 II
- 0086. 分隔链表
- 0090. 子集 II
- 0091. 解码方法
- 0092. 反转链表 II
- 0094. 二叉树的中序遍历
- 0095. 不同的二叉搜索树 II
- 0096. 不同的二叉搜索树
- 0098. 验证二叉搜索树
- 0102. 二叉树的层序遍历
- 0103. 二叉树的锯齿形层次遍历
- 105. 从前序与中序遍历序列构造二叉树
- 0113. 路径总和 II
- 0129. 求根到叶子节点数字之和
- 0130. 被围绕的区域
- 0131. 分割回文串
- 0139. 单词拆分
- 0144. 二叉树的前序遍历
- 0150. 逆波兰表达式求值
- 0152. 乘积最大子数组
- 0199. 二叉树的右视图
- 0200. 岛屿数量
- 0201. 数字范围按位与
- 0208. 实现 Trie (前缀树)
- 0209. 长度最小的子数组
- 0211. 添加与搜索单词 * 数据结构设计
- 0215. 数组中的第K个最大元素
- 0221. 最大正方形
- 0229. 求众数 II
- 0230. 二叉搜索树中第K小的元素
- 0236. 二叉树的最近公共祖先
- 0238. 除自身以外数组的乘积
- 0240. 搜索二维矩阵 II
- 0279. 完全平方数
- 0309. 最佳买卖股票时机含冷冻期
- 0322. 零钱兑换
- 0328. 奇偶链表
- 0334. 递增的三元子序列
- 0337. 打家劫舍 III
- 0343. 整数拆分
- 0365. 水壶问题
- 0378. 有序矩阵中第K小的元素
- 0380. 常数时间插入、删除和获取随机元素
- 0416. 分割等和子集
- 0445. 两数相加 II
- 0454. 四数相加 II
- 0494. 目标和
- 0516. 最长回文子序列
- 0518. 零钱兑换 II
- 0547. 朋友圈
- 0560. 和为K的子数组
- 0609. 在系统中查找重复文件
- 0611. 有效三角形的个数
- 0718. 最长重复子数组
- 0754. 到达终点数字
- 0785. 判断二分图
- 0820. 单词的压缩编码
- 0875. 爱吃香蕉的珂珂
- 0877. 石子游戏
- 0886. 可能的二分法
- 0900. RLE 迭代器
- 0912. 排序数组
- 0935. 骑士拨号器
- 1011. 在 D 天内送达包裹的能力
- 1014. 最佳观光组合
- 1015. 可被 K 整除的最小整数
- 1019. 链表中的下一个更大节点
- 1020. 飞地的数量
- 1023. 驼峰式匹配
- 1031. 两个非重叠子数组的最大和
- 1104. 二叉树寻路
- 1131.绝对值表达式的最大值
- 1186. 删除一次得到子数组最大和
- 1218. 最长定差子序列
- 1227. 飞机座位分配概率
- 1261. 在受污染的二叉树中查找元素
- 1262. 可被三整除的最大和
- 1297. 子串的最大出现次数
- 1310. 子数组异或查询
- 1334. 阈值距离内邻居最少的城市
- 1371.每个元音包含偶数次的最长子字符串
- 第六章 - 高频考题(困难)
- 0004. 寻找两个正序数组的中位数
- 0023. 合并K个升序链表
- 0025. K 个一组翻转链表
- 0030. 串联所有单词的子串
- 0032. 最长有效括号
- 0042. 接雨水
- 0052. N皇后 II
- 0084. 柱状图中最大的矩形
- 0085. 最大矩形
- 0124. 二叉树中的最大路径和
- 0128. 最长连续序列
- 0145. 二叉树的后序遍历
- 0212. 单词搜索 II
- 0239. 滑动窗口最大值
- 0295. 数据流的中位数
- 0301. 删除无效的括号
- 0312. 戳气球
- 0335. 路径交叉
- 0460. LFU缓存
- 0472. 连接词
- 0488. 祖玛游戏
- 0493. 翻转对
- 0887. 鸡蛋掉落
- 0895. 最大频率栈
- 1032. 字符流
- 1168. 水资源分配优化
- 1449. 数位成本和为目标值的最大数字
- 后序