编程打卡第二天之路径交叉

62 阅读 0 评论 41 点赞

我是靠谱客的博主超帅项链，最近开发中收集的这篇文章主要介绍编程打卡第二天之路径交叉，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述：

给你一个整数数组 distance 。

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

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

示例 1：

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

数据要求：

1 <= distance.length <= 105
1 <= distance[i] <= 105

解题思路：

plan A：枚举所有相交的类型：

plan B：枚举不相交的情况：

#include<iostream>
#include<vector>
using namespace std;

class Solustion {
public:
    bool isSelfCrossing(vector<int>& distance) {
        int n = distance.size();
        int i = 0;
        while (i < n && (i<2 || distance[i]>distance[i - 2])) {
            i++;
        }

        if (i == n) return false;
        //外卷变内卷
        if ((i == 3 && distance[i] == distance[i - 2]) || (i >= 4 && distance[i] >= distance[i - 2] - distance[i - 4])) {
            distance[i - 1] -= distance[i - 3];
           
        }
         i++;
        while (i < n && distance[i] < distance[i - 2]) {
            i++;

           //内卷
        }
        return i != n;
    }
};

    int main() {
        Solustion solustion;
        vector<int> dis;
        int i;
        while (1) {
            cin >> i;   
            dis.push_back(i);
             if (cin.get() == 'n') 
                 break;
        }
 
        cout<<solustion.isSelfCrossing(dis)<<endl;
        for (i = 0; i < dis.size(); i++) {
            cout << dis[i] << endl;
        }
        return 0;
    }