友情支持

如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜

支付宝

微信

有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

1496. 判断路径是否相交

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

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

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= path.length <= 104

  • path[i]NSEW

思路分析

想找个巧办法,结果失败!还是用记录轨迹的办法搞定了。

因为题目要求 1 <= path.length <= 104,那么 xy 的值,最大不会超过 104,直接讲 (x, y) 转换成 x * 10000 + y 一个数字来作为坐标即可。

  • 一刷

 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
27
28
29
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-05-27 20:32:05
 */
public boolean isPathCrossing(String path) {
  int x = 0, y = 0;
  Set<Integer> visited = new HashSet<>();
  visited.add(0);
  for (int i = 0; i < path.length(); i++) {
    char c = path.charAt(i);
    if (c == 'N') {
      y++;
    } else if (c == 'S') {
      y--;
    } else if (c == 'E') {
      x++;
    } else if (c == 'W') {
      x--;
    }
    int point = x * 10000 + y;
    if (visited.contains(point)) {
      return true;
    } else {
      visited.add(point);
    }
  }
  return false;
}