当前位置:   article > 正文

【Leetcode刷题Python】1496.判断路径是否相交_安卓判断两个path是否相交

安卓判断两个path是否相交

1 题目

给你一个字符串 path,其中 path[i] 的值可以是 ‘N’、‘S’、‘E’ 或者 ‘W’,分别表示向北、向南、向东、向西移动一个单位。

你从二维平面上的原点 (0, 0) 处开始出发,按 path 所指示的路径行走。

如果路径在任何位置上与自身相交,也就是走到之前已经走过的位置,请返回 true ;否则,返回 false 。
示例1

输入:path = “NES”
输出:false
解释:该路径没有在任何位置相交。

示例2

输入:path = “NESWW”
输出:true
解释:该路径经过原点两次。

2 解析

这是有一个字典的应用,将每个坐标存储起来,(x,y)作为关键字。如果重复出现坐标,就输出True

3 python实现

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        direction = {
            'N':(0,1),
            'S':(0,-1),
            'E':(-1,0),
            'W':(1,0)

        }
        x,y= 0,0
        visit = set([(0,0)])
        for p in path:
            dx,dy = direction[p]
            x,y = x+dx,y+dy
            if (x,y) in visit:
                return True

            visit.add((x,y))
        return False
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/790380
推荐阅读
相关标签
  

闽ICP备14008679号