路径交叉

Posted on Edited on In Views: Waline: Views: Symbols count in article: 845 Reading time ≈ 1 mins.

题解方法

  • 数学归纳

数学归纳

第一种情况

cross_1

  • 第 i 次移动和第 i−3 次移动（包含端点）交叉的情况
  • 第 i−1 次移动距离小于等于第 i−3 次移动距离
  • 第 i 次移动距离大于等于第 i−2 次移动距离

第二种情况

cross_2

  • 第 4 次移动距离等于第 2 次移动距离。
  • 第 5 次移动距离大于等于第 3 次移动距离减第 1 次移动距离的差

第三种情况

cross_3

  • 第 i−1 次移动距离大于等于第 i−3 次移动距离

  • 第 i−2 次移动距离大于等于第 i−4 次移动距离

  • 第 i 次移动距离大于等于第 i−2 次移动距离减第 i−4 次移动距离的差

  • 第 i−1 次移动距离大于等于第 i−3 次移动距离减第 i−5 次移动距离的差

核心代码

数学归纳

第一种情况

1
2
3
4
5
// 第一类情况
if (distance[i - 1] <= distance[i - 3]
        && distance[i] >= distance[i - 2]) {
    return true;
}

第二种情况

1
2
3
4
5
6
7
// 第二类情况
else if (i == 4
        && distance[i - 2] >= distance[i - 4]
        && distance[i - 1] == distance[i - 3]
        && distance[i] >= distance[i - 2] - distance[i - 4]) {
    return true;
}

第三种情况

1
2
3
4
5
6
7
8
// 第三类情况
else if (i > 4
        && distance[i - 1] <= distance[i - 3]
        && distance[i - 2] >= distance[i - 4]
        && distance[i] >= distance[i - 2] - distance[i - 4]
        && distance[i - 1] >= distance[i - 3] - distance[i - 5]) {
    return true;
}

题目来源

335. 路径交叉 - 力扣（LeetCode） (leetcode-cn.com)