【LeetCode日记】 335. 路径交叉

封谞
• 阅读 1023

题目地址(335. 路径交叉)

https://leetcode-cn.com/probl...

题目描述

给定一个含有 n 个正数的数组 x。从点 (0,0) 开始,先向北移动 x[0] 米,然后向西移动 x[1] 米,向南移动 x[2] 米,向东移动 x[3] 米,持续移动。也就是说,每次移动后你的方位会发生逆时针变化。

编写一个 O(1) 空间复杂度的一趟扫描算法,判断你所经过的路径是否相交。

 

示例 1:

┌───┐
│   │
└───┼──>
    │

输入: [2,1,1,2]
输出: true
示例 2:

┌──────┐
│      │
│
│
└────────────>

输入: [1,2,3,4]
输出: false
示例 3:

┌───┐
│   │
└───┼>

输入: [1,1,1,1]
输出: true

思路

符合直觉的做法是$O(N)$时间和空间复杂度的算法。这种算法非常简单,但是题目要求我们使用空间复杂度为$O(1)$的做法。

关于空间复杂度为$O(N)$的算法可以参考我之前的874.walking-robot-simulation。 思路基本是类似,只不过 obstacles(障碍物)不是固定的,而是我们不断遍历的时候动态生成的,我们每遇到一个点,就将其标记为 obstacle。随着算法的进行,我们的 obstacles 逐渐增大,最终和 N 一个量级。

我们考虑进行优化。我们仔细观察发现,如果想让其不相交,从大的范围来看只有两种情况:

  1. 我们画的圈不断增大。
  2. 我们画的圈不断减少。

【LeetCode日记】 335. 路径交叉
(有没有感觉像迷宫?)

这样我们会发现,其实我们画最新一笔的时候,并不是之前画的所有的都需要考虑,我们只需要最近的几个就可以了,实际上是最近的五个,不过不知道也没关系,我们稍后会讲解。

【LeetCode日记】 335. 路径交叉

红色部分指的是我们需要考虑的,而剩余没有被红色标注的部分则无需考虑。不是因为我们无法与之相交,而是我们一旦与之相交,则必然我们也一定会与红色标记部分相交

然而我们画的方向也是不用考虑的。比如我当前画的方向是从左到右,那和我画的方向是从上到下有区别么?在这里是没区别的,不信我帮你将上图顺时针旋转 90 度看一下:

【LeetCode日记】 335. 路径交叉

方向对于我们考虑是否相交没有差别。

当我们仔细思考的时候,会发现其实相交的情况只有以下几种:

【LeetCode日记】 335. 路径交叉

这个时候代码就呼之欲出了。

  • 我们只需要遍历数组 x,假设当前是第 i 个元素。
  • 如果 x[i] >= x[i - 2] and x[i - 1] <= x[i - 3],则相交(第一种情况)
  • 如果 x[i - 1] <= x[i - 3] and x[i - 2] <= x[i],则相交(第二种情况)
  • 如果 i > 3 and x[i - 1] == x[i - 3] and x[i] + x[i - 4] == x[i - 2],则相交(第三种情况)
  • 如果 i > 4 and x[i] + x[i - 4] >= x[i - 2] and x[i - 1] >= x[i - 3] - x[i - 5] \
    and x[i - 1] <= x[i - 3] and x[i - 2] >= x[i - 4] and x[i - 3] >= x[i - 5] ,则相交(第四种情况)
  • 否则不相交

关键点解析

  • 一定要画图辅助
  • 对于这种$O(1)$空间复杂度有固定的套路。常见的有:
  1. 直接修改原数组
  2. 滑动窗口(当前状态并不是和之前所有状态有关,而是仅和某几个有关)。

我们采用的是滑动窗口。但是难点就在于我们怎么知道当前状态和哪几个有关。对于这道题来说,画图或许可以帮助你打开思路。另外面试的时候说出$O(N)$的思路也不失为一个帮助你冷静分析问题的手段。

代码

代码支持:Python3

Python3 Code:

class Solution:
    def isSelfCrossing(self, x: List[int]) -> bool:
        n = len(x)
        if n < 4:
            return False
        for i in range(3, n):
            if x[i] >= x[i - 2] and x[i - 1] <= x[i - 3]:
                return True
            if x[i - 1] <= x[i - 3] and x[i - 2] <= x[i]:
                return True
            if i > 3 and x[i - 1] == x[i - 3] and x[i] + x[i - 4] == x[i - 2]:
                return True
            if i > 4 and x[i] + x[i - 4] >= x[i - 2] and x[i - 1] >= x[i - 3] - x[i - 5] \
                    and x[i - 1] <= x[i - 3] and x[i - 2] >= x[i - 4] and x[i - 3] >= x[i - 5]:
                return True
        return False


本篇文章由一文多发平台ArtiPub自动发布

点赞
收藏
评论区
推荐文章
blmius blmius
4年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
美凌格栋栋酱 美凌格栋栋酱
7个月前
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Stella981 Stella981
3年前
SpringBoot整合Redis乱码原因及解决方案
问题描述:springboot使用springdataredis存储数据时乱码rediskey/value出现\\xAC\\xED\\x00\\x05t\\x00\\x05问题分析:查看RedisTemplate类!(https://oscimg.oschina.net/oscnet/0a85565fa
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
3年前
PHP创建多级树型结构
<!lang:php<?php$areaarray(array('id'1,'pid'0,'name''中国'),array('id'5,'pid'0,'name''美国'),array('id'2,'pid'1,'name''吉林'),array('id'4,'pid'2,'n
Easter79 Easter79
3年前
SpringBoot整合Redis乱码原因及解决方案
问题描述:springboot使用springdataredis存储数据时乱码rediskey/value出现\\xAC\\xED\\x00\\x05t\\x00\\x05问题分析:查看RedisTemplate类!(https://oscimg.oschina.net/oscnet/0a85565fa
Wesley13 Wesley13
3年前
Java日期时间API系列36
  十二时辰,古代劳动人民把一昼夜划分成十二个时段,每一个时段叫一个时辰。二十四小时和十二时辰对照表:时辰时间24时制子时深夜11:00凌晨01:0023:0001:00丑时上午01:00上午03:0001:0003:00寅时上午03:00上午0
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Python进阶者 Python进阶者
1年前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这