第六章 - 高频考题(困难)
0335. 路径交叉

题目地址(335. 路径交叉)

https://leetcode-cn.com/problems/self-crossing/

题目描述

1
给定一个含有 n 个正数的数组 x。从点 (0,0) 开始,先向北移动 x[0] 米,然后向西移动 x[1] 米,向南移动 x[2] 米,向东移动 x[3] 米,持续移动。也就是说,每次移动后你的方位会发生逆时针变化。
2
3
编写一个 O(1) 空间复杂度的一趟扫描算法,判断你所经过的路径是否相交。
4
5
6
7
示例 1:
8
9
┌───┐
10
│ │
11
└───┼──>
12
13
14
输入: [2,1,1,2]
15
输出: true
16
示例 2:
17
18
┌──────┐
19
│ │
20
21
22
└────────────>
23
24
输入: [1,2,3,4]
25
输出: false
26
示例 3:
27
28
┌───┐
29
│ │
30
└───┼>
31
32
输入: [1,1,1,1]
33
输出: true
Copied!

前置知识

  • 滚动数组

公司

  • 暂无

思路

符合直觉的做法是$O(N)$时间和$O(B)$空间复杂度的算法,其中 B 为障碍物的个数,也就是行走过程中经过的坐标点的个数。这种算法非常简单,关于空间复杂度为$O(B)$的算法可以参考我之前的874.walking-robot-simulation。 思路基本是类似,只不过 obstacles(障碍物)不是固定的,而是我们不断遍历的时候动态生成的,我们每遇到一个点,就将其标记为 obstacle。随着算法的进行,我们的 obstacles 逐渐增大,最终会增加到 $O(B)$。
但是题目要求我们使用空间复杂度为$O(1)$的做法。我们考虑进行优化。我们仔细观察发现,如果想让其不相交,从大的范围来看只有两种情况:
  1. 1.
    我们画的圈不断增大。
  2. 2.
    我们画的圈不断减少。
(有没有感觉像迷宫?)
这样我们会发现,其实我们画最新一笔的时候,并不是之前画的所有的都需要考虑,我们只需要最近的几个就可以了,实际上是最近的五个,不过不知道也没关系,我们稍后会讲解。
红色部分指的是我们需要考虑的,而剩余没有被红色标注的部分则无需考虑。不是因为我们无法与之相交,而是我们一旦与之相交,则必然我们也一定会与红色标记部分相交
然而我们画的方向也是不用考虑的。比如我当前画的方向是从左到右,那和我画的方向是从上到下有区别么?在这里是没区别的,不信我帮你将上图顺时针旋转 90 度看一下:
方向对于我们考虑是否相交没有差别。
当我们仔细思考的时候,会发现其实相交的情况只有以下几种:
图有误,第一种和第二种是同一种情况,换个角度看一样了。文字解释和代码已经更正
这个时候代码就呼之欲出了。
  • 我们只需要遍历数组 x,假设当前是第 i 个元素。
  • 如果 x[i] >= x[i - 2] and x[i - 1] <= x[i - 3],则相交(第一种情况)
  • 如果 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)$空间复杂度有固定的套路。常见的有:
  1. 1.
    直接修改原数组
  2. 2.
    滚动数组(当前状态并不是和之前所有状态有关,而是仅和某几个有关)。
我们采用的是滚动数组。如果你了解动态规划的滚动数组优化的话应该理解我的意思 。但是难点就在于我们怎么知道当前状态和哪几个有关。对于这道题来说,画图或许可以帮助你打开思路。另外面试的时候说出$O(B)$的思路也不失为一个帮助你冷静分析问题的手段。
感谢 @saberjiang-b 指出的代码重复判断问题

代码

代码支持:Python3
Python3 Code:
1
class Solution:
2
def isSelfCrossing(self, x: List[int]) -> bool:
3
n = len(x)
4
if n < 4:
5
return False
6
for i in range(3, n):
7
if x[i] >= x[i - 2] and x[i - 1] <= x[i - 3]:
8
return True
9
if i > 3 and x[i - 1] == x[i - 3] and x[i] + x[i - 4] == x[i - 2]:
10
return True
11
if i > 4 and x[i] + x[i - 4] >= x[i - 2] and x[i - 1] >= x[i - 3] - x[i - 5] \
12
and x[i - 1] <= x[i - 3] and x[i - 2] >= x[i - 4] and x[i - 3] >= x[i - 5]:
13
return True
14
return False
Copied!
复杂度分析
其中 N 为数组长度。
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(1)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 45K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。