神刀安全网

C++ Coding Exercise – Self Crossing

You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south, x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.

Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.

Submit your solution at: https://leetcode.com/problems/self-crossing/

C++ Coding Exercise – Self Crossing

leetcode-self-crossing

When n is less than 3

We can easily figure out that if n is smaller than 3 and the answer is false because all input are positive numbers (not zero) so three edges will not cross.

When n is 4

It will cross like this:

┌───┐ │   │ └───┼──>
┌───┐ │   │ └───┼──>     │

So the condition is to check the fourth edge with the second and the first with the third.

(x[3] >= x[1] && (x2]) <= x[0])
(x[3] >= x[1] && (x2]) <= x[0])

When n is 5

There is another special case with n=5.

┌──────┐ │      │ │      │ │      │ └──────/ <--this is a square corner  
┌──────┐ │      │ │      │ │      │ └──────/ <--this is a square corner

5 edges form a rectangle where the last edge plus the first edge equal or bigger than the third edge.

(x[3] == x[1] && x[4] + x[0] >= x[2])
(x[3] == x[1] && x[4] + x[0] >= x[2])

When n is 6

This is a special case that requires at least 6 edges:

┌──────┐ │      │<_____ │      │     │ │            │ └────────────/  <--this is a square corner  
┌──────┐ │      │<_____ │      │     │ │            │ └────────────/  <--this is a square corner

The last edge crosses the first edge. In order for this happen:

  1. Edge 4 is bigger than Edge 2
  2. Edge 6 is bigger than (Edge 4 – Edge 2)
  3. Edge 5 is bigger than (Edge 3 – Edge 1)
  4. Edge 5 is smaller than Edge 3

Using code:

(x[3] >= x[2] && x[5] >= x[3] - x[1] && x[4] >= x[2] - x[0] && x[4] <= x[2])
(x[3] >= x[2] && x[5] >= x[3] - x[1] && x[4] >= x[2] - x[0] && x[4] <= x[2])

Generalization

So the idea is to check for every possibilities of self-crossing, return true if found any. When all checks are performed and no crossings are found, the function returns false.

The O(n)algorithm does the one-scan pass. Checking for last-4 edges, last-5 edges and last-6 edges at each iteration turns the shape 90 degree. The non-self-crossing edges are checked and can be disregarded immediately.

class Solution { public:     bool isSelfCrossing(vector<int>& x) {         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) {                 if (x[i - 1] == x[i - 3] && x[i] + x[i - 4] >= x[i - 2]) {                     return true;                 }             }             if (i >= 5) {                 if (x[i - 2] >= x[i - 4] && x[i] >= x[i - 2] - x[i - 4] && x[i - 1] >= x[i - 3] - x[i - 5] && x[i - 1] <= x[i - 3]) {                     return true;                 }             }         }         return false;     } };
class Solution { public:     bool isSelfCrossing(vector<int>& x) {         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) {                 if (x[i - 1] == x[i - 3] && x[i] + x[i - 4] >= x[i - 2]) {                     return true;                 }             }             if (i >= 5) {                 if (x[i - 2] >= x[i - 4] && x[i] >= x[i - 2] - x[i - 4] && x[i - 1] >= x[i - 3] - x[i - 5] && x[i - 1] <= x[i - 3]) {                     return true;                 }             }         }         return false;     } };

–EOF–

GD Star Rating

loading…

648 words

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » C++ Coding Exercise – Self Crossing

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮