LeetCode 335. Self Crossing
2023-03-14 09:46:16 时间
挺有趣的一道题,看题解才勉强做出。。。
题意就是给n个长度,然后以上左下右的顺序走。比如 [2,1,1,2]就是先上走2 左走1 下走1 右走2 如果还有就继续向上,向左……
求路径中是否存在交叉。
如果在纸上画一画,就会发现,在保证不出现交叉的前提下,可画的类型无非几种
(实不相瞒,我用微信截图随便画的)
就是说如果出现交叉,并不需要考虑和相离较远的某条线段的交叉,因为肯定会和附近的某条线进行交叉。所以算法是 O(N) 而不是 O(N^2)
总结一下可能出现的交叉 不画了 copy from https://blog.csdn.net/zmq570235977/article/details/51705518
图中考虑的三种情况,实际要考虑多个方向。不过判断条件是一样的。
class Solution { public: bool isSelfCrossing(vector<int>& x) { int n = x.size(); // 小于4条边是不会出现交叉的 for (int i = 3; i < n; i++) { if ( x[i - 1] <= x[i - 3] && x[i] >= x[i - 2] || (i >= 4 && i <= 8 && x[i - 4] + x[i] >= x[i - 2] && x[i - 3] == x[i - 1]) || (i >= 5 && i <= 8 && x[i - 1] <= x[i - 3] && x[i - 5] + x[i - 1] >= x[i - 3] && x[i - 4] <= x[i - 2] && x[i - 4] + x[i] >= x[i - 2]) ) return true; } return false; } };
相关文章
- 【杂谈】聊聊我们关于网络拥塞与控制优化的一些技术方案
- 宝塔面板 Nginx 挂马事件剖析与安全建议
- ? Java NIO 基础
- 生信入门课DAY6--向逸一(R包)
- AirServer2023最新版软件的功能优势介绍
- 电脑版word最新版本怎么下载到桌面(含mac word)
- fl studio21版本如何更新,2023年怎么永久激活fl studio免费升级注册解锁
- crossover怎么使用 crossover22软件使用方法
- 吉他贝斯打谱Guitar Pro8激活许可证,2023年最新序列号是多少?
- Mac内存空间不足怎么办? 用CleanMyMac X轻松释放储存空间
- OCR文字识别软件ABBYY FineReader 15中文版免费下载
- 2023-02-11:给你两个整数 m 和 n 。构造一个 m x n 的网格,其中每个单元格最开始是白色, 请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有
- 数学建模常用模型02:插值与拟合
- geo(三)
- STL-常用算法总结
- 【Blender】如何使用Festivity方案一键三渲二 - PMX版本
- 河道治理漂浮物识别监测系统
- 在 WebAssembly 中使用 C/C++ 和 libbpf 编写 eBPF 程序
- 在 WebAssembly 中使用 Rust 编写 eBPF 程序并发布 OCI 镜像
- Shell 编程(一):Shell 变量的高级用法