Leetcode: Self Crossing
2024-10-16 05:12:27
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;
}
}
最新文章
- supermap iobect .net 7.1.2 图例的拆分
- centos 7配置网络 更新yum源
- oracle中利用trigger,sequence自动生成ID
- GEOS库的学习之一:介绍和编译
- 在linux下使用百度ueditor编辑器上传图片
- CSS3滤镜(filter--CSS3技术
- 图解JQUERY尺寸及位置定义
- SpringMVC(十二):SpringMVC 处理输出模型数据之@ModelAttribute
- Java IO流对象、多线程
- 容器—stack
- android手机短信获取
- 详解JS设计模式
- [Codis] Codis3部署流程
- cetos7最小化安装设置网络启动和更新yum源
- Apple公司Darwin流式服务器源代码分析
- centos7 安装pip+python3.6
- C#单例和Unity单例
- 这可能是最全的禁用win10自动更新了
- poj1321 棋盘问题(深搜dfs)
- Linux命令的那些事(三)
热门文章
- javaWeb中struts开发——Logic标签
- visual studio 2005 编fortran程序,运行后dos窗口显示问题
- ubuntu12.04 安装 php5.4/php5.5
- iOS自定义控件开发详解
- php--http与https的区别
- php--memcahce安装
- shopping cart<;代码>;
- 1058 N的阶乘的长度
- 转:[ASP.NET]重構之路系列v4 – 簡單使用interface之『你也會IoC』
- Java实验五报告——TCP传输及加解密