一个算法题--Self Crossing
2024-08-29 23:25:47
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.
Example1:
Example2:
Example3:
Answer:
public boolean isSelfCrossing(int[] x) {
if(x==null||x.length<=3){
return false;
}
for(int i=3;i<x.length;i++){
if(x[i]>=x[i-2]&&x[i-1]<=x[i-3]){ // case 1
return true;
}else if(i>=4&&x[i-1]==x[i-3]&&x[i]+x[i-4]>=x[i-2]){ // case 2
return true;
}else if(i>=5&&x[i-2]>x[i-4]&&x[i]+x[i-4]>=x[i-2]&&x[i-1]<x[i-3]&&x[i-1]+x[i-5]>=x[i-3]){ //case 3
return true;
}
}
return false;
}
最新文章
- 面试题:return和finally执行
- c# 传递Null的string值导致的调用C++的dll报错 Attempted to read or write protected memory.
- js代码实现下拉菜单
- fir.im Weekly - 除了写代码,还需要了解什么
- C语言 百炼成钢2
- FDR
- jquery插件dataTables添加序号列
- Redis - 环境的安装配置
- Linux中的文件特殊权限
- 第四章 Web表单
- winform Label与DataGridView右对齐 分类: WinForm 2014-05-19 20:51 446人阅读 评论(0) 收藏
- Delphi内存操作API函数(备查,并一一学习)
- javaEE jdbc编程步骤
- 我的iOS-App
- java中的位操作
- vue2 vue-router 组装
- Struts2(三) 配置struts.xml的提示(在不联网的情况下)
- 转 InnoDB Error Handling
- Kylin引入Spark引擎
- IIS相关
热门文章
- C++连接sqlite数据库的增删查改操作
- 使用delphi TThread类创建线程备忘录
- 吴裕雄 Bootstrap 前端框架开发——Bootstrap 字体图标(Glyphicons):glyphicon glyphicon-music
- Web基础之日志
- 文本编辑器vim/vi——命令模式
- xargs详细
- SpringBoot 上传文件突然报错 Failed to parse multipart servlet request; nested exception is java.io.IOException: The temporary upload location [/tmp/tomcat.1428942566812653608
- TensorFlow中的L2正则化函数:tf.nn.l2_loss()与tf.contrib.layers.l2_regularizerd()的用法与异同
- 六十三、SAP中的逻辑运算符
- XTU 1205 Range