Leetcode: Self Crossing

发布时间:2017-5-23 9:08:44 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Leetcode: Self Crossing ",主要涉及到Leetcode: Self Crossing 方面的内容,对于Leetcode: Self Crossing 感兴趣的同学可以参考一下。

Leetcode: 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.Example 1:Given x = [2, 1, 1, 2],┌───┐│   │└───┼──>    │Return true (self crossing)Example 2:Given x = [1, 2, 3, 4],┌──────┐│      │││└────────────>Return false (not self crossing)Example 3:Given x = [1, 1, 1, 1],┌───┐│   │└───┼>Return true (self crossing)

4th line may cross with 1st line, and so on: 5th with 2nd, ...etc

5th line may cross with 1st line, and so on: 6th with 2nd, ...etc

6th line also may cross with 1st line, and so on: 7th with 2nd, ...etc

However, if 7th line also cross with 1st line, the following definitely happens at the same time: 

  a. 7th line cross with 2nd line

  b. 6th line cross with 1st line

  we have covered these cases.

 1 public class Solution { 2     public boolean isSelfCrossing(int[] x) { 3         if (x.length <= 3) return false; 4         for (int i=3; i<x.length; i++) { 5             //check if 4th line cross with the first line and so on 6             if (x[i]>=x[i-2] && x[i-1]<=x[i-3]) return true; 7              8             //check if 5th line cross with the first line and so on 9             if (i >= 4) {10                 if (x[i-1]==x[i-3] && x[i]+x[i-4]>=x[i-2]) return true;11             }12             13             //check if 6th line cross with the first line and so on14             if (i >= 5) {15                 if (x[i-2]>=x[i-4] && x[i]>=x[i-2]-x[i-4] && x[i-1]<=x[i-3] && x[i-1]>=x[i-3]-x[i-5]) return true;16             }17         }18         return false;19     }20 }

上一篇:Android音频系统之AudioFlinger(四)
下一篇:JS区分移动端和PC

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

腹肌贴健身器材智能腹部训练健腹器肌