JavaInterview JavaInterview
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)

『Java面试+Java学习』
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)
  • 指南
  • 简历

  • Java

  • 面试

  • 算法

  • algorithm
  • leetcode
JavaInterview.cn
2025-05-06
目录

判断路径是否相交Java

文章发布较早,内容可能过时,阅读注意甄别。

# 题目

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

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

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

示例 1: screen-shot-2020-06-10-at-123843-pm.png

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

示例 2: screen-shot-2020-06-10-at-123929-pm.png

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

提示:

  • 1 <= path.length <= 104

# 思路

HashSet

# 解法

class Solution {
public boolean isPathCrossing(String path) {
    int[] compass = new int[2];
    Set<Integer> set = new HashSet<>();
    set.add(0);
    for(int i =0 ; i < path.length(); i++){
        char c = path.charAt(i);
        if(c == 'N'){
            compass[1]++;
        } else if (c == 'S') {
            compass[1]--;
        }else if(c == 'E'){
            compass[0]+=20001;
        }else if (c == 'W'){
            compass[0]-=20001;
        }

        if(!set.add(compass[0]+compass[1])){
           return true;
        }
    }

    return false;
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 总结

  • 分析出几种情况,然后分别对各个情况实现
微信 支付宝
#Java
最近更新
01
1686. 石子游戏VI Java
09-07
02
1687. 从仓库到码头运输箱子 Java
09-07
03
1688. 比赛中的配对次数 Java
09-07
更多文章>
Theme by Vdoing | Copyright © 2019-2025 JavaInterview.cn
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式