[LeetCode]Self Crossing

题目要求O(n)时间，O(1)空间的解法。第一眼看上去并不是很直观，感觉可能要存之前所有的interval，然后看当前interval是否和相互垂直的那一组interval有交点。但是画一画图就大概可以知道，我们只需要check三种情况，如下图所示：

也就分别对应以下三种情况：

• x[i]和x[i - 3]相交
• x[i]和x[i - 4]相交
• x[i]和x[i - 5]相交

代码如下：

	class Solution {
	public:
	bool isSelfCrossing(vector<int>& x) {
	//total three cases:
	//1. x[i] intersect with x[i - 3]
	//2. x[i] intersect with x[i - 4]
	//3. x[i] intersect with x[i - 5]
	for(int i = 3; i < x.size(); ++i)
	{
	if(x[i] >= x[i - 2] && x[i - 1] <= x[i - 3])return true;
	if(i >= 4 && x[i - 1] == x[i - 3] && x[i] + x[i - 4] >= x[i - 2])return true;
	if(i >= 5 && x[i] + x[i - 4] >= x[i - 2] && x[i - 1] + x[i - 5] >= x[i - 3] && x[i - 2] > x[i - 4] && x[i - 3] > x[i - 1])return true;
	}
	return false;
	}
	};

view raw Self Crossing.cpp hosted with ❤ by GitHub