Leetcode: Self Crossing

时间:2022-03-31 23:53:02
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, either of the following cases should definitely happens:

  a. 7th line cross with 2nd line

  b. 6th line cross with 1st line

  we have covered these cases.

 public class Solution {
public boolean isSelfCrossing(int[] x) {
if (x.length <= 3) return false;
for (int i=3; i<x.length; i++) {
//check if 4th line cross with the first line and so on
if (x[i]>=x[i-2] && x[i-1]<=x[i-3]) return true; //check if 5th line cross with the first line and so on
if (i >= 4) {
if (x[i-1]==x[i-3] && x[i]+x[i-4]>=x[i-2]) return true;
} //check if 6th line cross with the first line and so on
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-1]>=x[i-3]-x[i-5]) return true;
}
}
return false;
}
}

Leetcode: Self Crossing的更多相关文章

  1. &lbrack;LeetCode&rsqb; Self Crossing 自交

    You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to th ...

  2. 还记得高中的向量吗?leetcode 335&period; Self Crossing(判断线段相交)

    传统解法 题目来自 leetcode 335. Self Crossing. 题意非常简单,有一个点,一开始位于 (0, 0) 位置,然后有规律地往上,左,下,右方向移动一定的距离,判断是否会相交(s ...

  3. 【LeetCode】Self Crossing(335)

    1. Description You are given an array x of n positive numbers. You start at point (0,0) and moves x[ ...

  4. 【LeetCode】335&period; Self Crossing(python)

    Problem:You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metr ...

  5. &lbrack;leetcode&rsqb;335&period; Self Crossing

    You are given an array x of n positive numbers. You start at point (,) and moves x[] metres to the n ...

  6. LeetCode All in One 题目讲解汇总&lpar;持续更新中&period;&period;&period;&rpar;

    终于将LeetCode的免费题刷完了,真是漫长的第一遍啊,估计很多题都忘的差不多了,这次开个题目汇总贴,并附上每道题目的解题连接,方便之后查阅吧~ 477 Total Hamming Distance ...

  7. &lbrack;LeetCode&rsqb; Frog Jump 青蛙过河

    A frog is crossing a river. The river is divided into x units and at each unit there may or may not ...

  8. Leetcode&colon; Frog Jump

    A frog is crossing a river. The river is divided into x units and at each unit there may or may not ...

  9. Swift LeetCode 目录 &vert; Catalog

    请点击页面左上角 -> Fork me on Github 或直接访问本项目Github地址:LeetCode Solution by Swift    说明:题目中含有$符号则为付费题目. 如 ...

随机推荐

  1. &lbrack;JAVA&rsqb; java class 基本定义 Note

    java class 基本定义 Note 1 package abeen.note; 2 import java.util.*; 3 4 5 /* 6 java calss 基本 7 */ 8 pub ...

  2. RestoreDirectory 引起的BUG

    IIRC, in windows XP when you press Save on a SaveFileDialog (or Open on a OpenFileDialog) the direct ...

  3. c中的关键字、标识符、注释

    一. 学习语法之前的提醒 1) C语言属于一门高级语言,其实,所有高级语言的基本语法组成部分都是一样的,只是表现形式不太一样 2) 就好像亚洲人和非洲人,大家都有人类的结构:2只 手.2只脚.1个头, ...

  4. STL数组处理常用函数

    reverse(a,a+n)反转 sort(a,a+n,cmp)排序 unique(a,a+n,cmp)对于有序集合进行去重,返回新数组最后一个元素的指针 next_permutatoin(a,a+n ...

  5. python建立pip&period;ini

    pip 是python的包管理器工具,类似linux的apt-get.yum包管理器,主要是用来进行安装python库, pip默认从官方源pypi.python.org下载数据,国内速度相对比较慢, ...

  6. iOS-设计模式之通知

    通知设计模式简单好用,就是一个项目中如果用的太多,不利于代码维护,可读性太差. 实现过程: [[NSNotificationCenter defaultCenter]postNotificationN ...

  7. vue1&period;0配置路由

    1,//创建 router 实例 var router = new VueRouter() 2,//components下新建home.vue组件,并在app.vue中引入模块: import hom ...

  8. Apache-httpd&period;conf详解

    ## Apache服务器主配置文件.  包括服务器指令的目录设置.# 详见 <URL:http://www.apache.org/docs/> ## 请在理解用途的基础上阅读各指令.## ...

  9. java 导mysql数据为表格给浏览器接收

    jar 包准备 <dependency> <groupId>org.apache.poi</groupId> <artifactId>poi</a ...

  10. property(四十)

    一个静态属性property本质就是实现了get,set,delete三种方法 用法: class Foo: @property def AAA(self): print('get的时候运行我啊') ...