LeetCode题练习与总结：路径交叉--335

一、题目描述

给你一个整数数组 distance 。

从 X-Y 平面上的点 (0,0) 开始，先向北移动 distance[0] 米，然后向西移动 distance[1] 米，向南移动 distance[2] 米，向东移动 distance[3] 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。

判断你所经过的路径是否相交。如果相交，返回 true ；否则，返回 false 。

示例 1：

输入：distance = [2,1,1,2]
输出：true

示例 2：

输入：distance = [1,2,3,4]
输出：false

示例 3：

输入：distance = [1,1,1,1]
输出：true

提示：

1 <= distance.length <= 10^5
1 <= distance[i] <= 10^5

二、解题思路

我们需要判断路径是否会相交。对于每一步移动，我们可以记录当前的位置和移动的方向。由于移动是逆时针的，我们可以用一个变量来记录当前的移动方向。

路径相交的情况有以下几种：

第四步开始会与第一步相交。
第五步开始会与第一步相交。
第六步开始会与第二步相交。

基于上述情况，我们可以得到以下规律：

当 i >= 3 时，如果 distance[i] >= distance[i - 2] 并且 distance[i - 1] <= distance[i - 3]，则第四步会与第一步相交。
当 i >= 4 时，如果 distance[i] + distance[i - 4] >= distance[i - 2] 并且 distance[i - 1] == distance[i - 3]，则第五步会与第一步相交。
当 i >= 5 时，如果 distance[i] + distance[i - 4] >= distance[i - 2] 并且 distance[i - 1] + distance[i - 5] >= distance[i - 3] 并且 distance[i - 1] < distance[i - 3]，则第六步会与第二步相交。

三、具体代码

class Solution {public boolean isSelfCrossing(int[] distance) {int n = distance.length;if (n < 4) return false;for (int i = 3; i < n; i++) {// 第四步开始会与第一步相交if (distance[i] >= distance[i - 2] && distance[i - 1] <= distance[i - 3]) {return true;}// 第五步开始会与第一步相交if (i >= 4 && distance[i] + distance[i - 4] >= distance[i - 2] && distance[i - 1] == distance[i - 3]) {return true;}// 第六步开始会与第二步相交if (i >= 5 && distance[i] + distance[i - 4] >= distance[i - 2] && distance[i - 1] + distance[i - 5] >= distance[i - 3] && distance[i - 1] < distance[i - 3]) {return true;}}return false;}
}

上述代码实现了对路径是否相交的判断，通过循环遍历 distance 数组，并按照上述规律判断路径是否相交。如果相交，则返回 true；否则，返回 false。

四、时间复杂度和空间复杂度

1. 时间复杂度

该算法包含一个主循环，该循环遍历整个 distance 数组。数组的大小为 n，所以循环会执行 n 次。在循环内部，我们执行了常数时间的操作，即比较和简单的算术运算。

因此，算法的时间复杂度是 O(n)，其中 n 是 distance 数组的长度。

2. 空间复杂度

该算法使用了固定数量的额外空间。它只使用了几个整型变量（n 和循环变量 i），这些变量占用的空间不随输入数组 distance 的大小而变化。

因此，算法的空间复杂度是 O(1)，即常数空间。

五、总结知识点

类定义 (class Solution):
- 定义了一个名为 Solution 的公共类，这是 Java 中定义类的标准方式。
方法定义 (public boolean isSelfCrossing(int[] distance)):
- 定义了一个公共方法 isSelfCrossing，它接受一个整数数组 distance 作为参数，并返回一个布尔值。
- public 关键字表示该方法可以被类外部访问。
- boolean 表示返回类型是布尔值，即 true 或 false。
数组长度获取 (int[] distance 的 length 属性):
- 使用 distance.length 来获取数组的长度，这是访问 Java 数组长度的标准方式。
循环结构 (for 循环):
- 使用 for 循环来遍历数组 distance，从索引 3 开始，因为前三个元素不足以形成交叉。
条件判断 (if 语句):
- 使用 if 语句来检查路径是否交叉的条件，这是控制流语句的一部分。
数组索引访问 (distance[i]):
- 使用数组索引 i 来访问数组 distance 中的元素。
比较操作符 (>=, <=, ==):
- 使用比较操作符来比较数组元素的大小，以确定路径是否交叉。
逻辑操作符 (&&, ||):
- 使用逻辑与 (&&) 和逻辑或 (||) 操作符来组合多个条件判断。
返回语句 (return true;, return false;):
- 使用 return 语句来结束方法的执行并返回一个值。
边界检查 (i >= 4, i >= 5):
- 在循环中添加了边界检查，以确保不会访问数组索引外的元素，这可以防止 ArrayIndexOutOfBoundsException。