算法leetcode

【分类讨论】力扣335-路径交叉

字数统计: 1.7k字   |   阅读时长: 8分
, ,

摘要: 本文详细拆解 力扣335-路径交叉，核心是分类讨论的思想

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文我们来看一个使用分类讨论思想解决的问题。此前我们解决过另一个分类讨论的问题，参考 【分类讨论】力扣29-两数相除。本文分类讨论的步数更多，每一步根据可能得不同取值，做不同处理。

$1 题目

题目描述

给定一个含有 n 个正数的数组 x。从点 (0,0) 开始，先向北移动 x[0] 米，然后向西移动 x[1] 米，向南移动 x[2] 米，向东移动 x[3] 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。

编写一个 O(1) 空间复杂度的一趟扫描算法，判断你所经过的路径是否相交。

样例

$2 题解

算法：分类讨论

前 4 步 a[0..3]

若 n < 4，无交点。

n >= 4，则需要边走边判定。

考察第 4 步 a[3]

此时已经经过的点 p[0..3]，当前点 p[3]，p[0] 点决定 a[3] 的前途，求出走过 a[3] 后的落脚点 p[4]，对比 p[4] 和 p[0]。

(1) p[4].x <= p[0].x && p[4].y >= p[0].y : 产生交点
(2) p[4].x < p[0].x: 外螺旋
(3) p[4].x == p[0].x: 预备内螺旋
(4) p[4].x > p[0].x: 内螺旋

外螺旋，预备内螺旋，内螺旋三种状态的走法和判定方法见第 5 步以后的分析。

第 5 步及以后 a[4..n-1]

从第 5 步 a[4] 开始，当前这一步为 a[i]，此时已经经过的点 p[0..i]，当前点 p[i]。

p[i] 经过 a[i] 得到 p[i + 1]。

(1) 预备内螺旋:

p[i - 4] 和 p[i - 5] 决定 a[i] 的前途，对于 a[4] 为预备内螺旋，需要找 p[0] 和 p[-1]，追溯不到，因此初始时候增加一步，视为往西走了 0 距离，此时就可以在 p 里追溯到决定 a[4] 前途的点了:

判断线段 (p[i], p[i + 1]) 与线段 (p[i-5], p[i-4]) 是否有交点：

  • 若有，则返回
  • 若没有，则进入内螺旋状态

(2) 内螺旋

p[i - 2] 和 p[i - 3] 决定 a[i] 的前途:

判断线段 (p[i], p[i + 1]) 与线段 (p[i-3], p[i-2]) 是否有交点。

  • 若有，则返回
  • 若没有，继续内螺旋状态

(3) 外螺旋

p[i - 2] 和 p[i - 3] 决定 a[i] 的前途:

判断两个点 (p[i], p[i + 1]) 与直线 (p[i-2], p[i-3]) 的位置关系：

  • 在同一侧: 进入内螺旋状态
  • 在两侧: 继续外螺旋状态
  • p[i+1] 落在直线上: 进入预备内螺旋状态

最终算法流程

  • 前 4 步 a[0..3]
1
2
3
4
5
6
7
8
9
若 n < 3，无交点

n >= 4:
考察第 4 步 a[3], 此时已经经过的点 p[0..3]，当前点 p[3]
p[0] 个点决定 a[3] 的前途，求出走过 a[3] 后的落脚点 p[4]，对比 p[4] 和 p[0]
(1) p[4].x <= p[0].x && p[4].y >= p[0].y : 产生交点
(2) p[4].x < p[0].x: 外螺旋
(3) p[4].x == p[0].x: 预备内螺旋
(4) p[4].x > p[0].x: 内螺旋

迭代过程中始终维护当前点 p (代表 p[i]) 前面的 5 个点, p5, p4, p3, p2, p1 (代表 p[i-5 ~ i-1])

进入第 5 步 a[4] 时，前五个点分别为: p5, p4 为原点，p3, p2, p1 为利用 a[0~3] 推出来的

  • 第 5 步及以后 a[4..n-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
查看当前状态

(1) 预备内螺旋: 
判断线段 (p[i], p[i + 1]) 与线段 (p[i-5], p[i-4]) 是否有交点
- 若有，则返回
- 若没有，则进入内螺旋状态
    
(2) 内螺旋
判断线段 (p[i], p[i + 1]) 与线段 (p[i-3], p[i-2]) 是否有交点
- 若有，则返回
- 若没有，继续内螺旋状态

(3) 外螺旋
判断两个点 (p[i], p[i + 1]) 与直线 (p[i-2], p[i-3]) 的位置关系
- 在同一侧: 进入内螺旋状态
- 在两侧: 继续外螺旋状态
- p[i+1] 落在直线上: 进入预备内螺旋状态

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
struct Point
{
    int x, y;
    Point():x(0),y(0){}
    Point(int x, int y):x(x),y(y){}
};

class Solution {
public:
    bool isSelfCrossing(vector<int>& x) {
        int n = x.size();
        if(n < 4) return false;
        vector<Point> p_prev(5);
        Point p;
        int ori = 0;
        for(int i = 0; i < 3; ++i)
        {
            Point p_next = step(ori, p, x[i]);
            p_prev[2 - i] = p_next;
            p = p_next;
            ori = (ori + 1) % 4;
        }
        // 第四步 a[3]
        Point p0 = p_prev[3];
        Point p4 = step(ori, p, x[3]);
        ori = (ori + 1) % 4;
        int state = -1;
        // 对比 p4 和 p_prev[3]
        if(p4.x <= p0.x && p4.y >= p0.y)
            return true;
        else if(p4.x < p0.x)
            state = 2; // 外螺旋
        else if(p4.x == p0.x)
            state = 1; // 预备内螺旋
        else
            state = 0; // 内螺旋
        p = p4; // 当前点
        // 第五步及以后
        for(int i = 4; i < n; ++i)
        {
            Point p_next = step(ori, p, x[i]);
            if(state == 1) // 预备内螺旋
            {
                // 判断线段 (p[i], p[i + 1]) 与线段 (p[i-5], p[i-4]) 是否有交点
                if(segment_cross(p_next, p_prev[3], ori))
                    return true;
                else
                    state = 0;
            }
            else if(state == 0) // 内螺旋
            {
                if(segment_cross(p_next, p_prev[1], ori))
                    return true;
            }
            else // 外螺旋
            {
                int s = line_2p(p_next, p_prev[2], p_prev[3], ori);
                if(s == 0) // 同一侧
                    state = 0;
                else if(s == 1) // p_next 落在直线上
                    state = 1;
            }
            for(int i = 4; i > 0; --i)
                p_prev[i] = p_prev[i - 1];
            p_prev[0] = p;
            p = p_next;
            ori = (ori + 1) % 4;
        }
        return false;
    }

private:
    // 上，右，下，左
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};

    bool segment_cross(const Point& p1, const Point& p2, int ori)
    {
        if(ori == 0) // 上
            return p1.y >= p2.y;
        if(ori == 1) // 右
            return p1.x >= p2.x;
        if(ori == 2) // 下
            return p1.y <= p2.y;
        // 左
        return p1.x <= p2.x;
    }

    int line_2p(const Point& p1, const Point& p2, const Point& p3, int ori)
    {
        if(ori == 0) // 上
        {
            if(p1.y > p2.y)
                return 2;
            else if(p1.y <= p2.y && p1.y >= p3.y)
                return 1;
            else
                return 0;
        }
        if(ori == 1) // 右
        {
            if(p1.x > p2.x)
                return 2;
            else if(p1.x <= p2.x && p1.x >= p3.x)
                return 1;
            else
                return 0;
        }
        if(ori == 2) // 下
        {
            if(p1.y < p2.y)
                return 2;
            else if(p1.y >= p2.y && p1.y <= p3.y)
                return 1;
            else
                return 0;
        }
        // 左
        if(p1.x < p2.x)
            return 2;
        else if(p1.x >= p2.x && p1.x <= p3.x)
            return 1;
        else
            return 0;
    }

    Point step(int ori, Point p, int l)
    {
        Point t;
        t.x = p.x + dx[ori] * l;
        t.y = p.y + dy[ori] * l;
        return t;
    }
};
Share