友情支持
如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜
有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi 。因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
1496. 判断路径是否相交
给你一个字符串 path
,其中 path[i]
的值可以是 N
、S
、E
或者 W
,分别表示向北、向南、向东、向西移动一个单位。
你从二维平面上的原点 (0, 0)
处开始出发,按 path
所指示的路径行走。
如果路径在任何位置上与自身相交,也就是走到之前已经走过的位置,请返回 true
;否则,返回 false
。
示例 1:

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

输入:path = "NESWW" 输出:true 解释:该路径经过原点两次。
提示:
-
1 <= path.length <= 104
-
path[i]
为N
、S
、E
或W
思路分析
想找个巧办法,结果失败!还是用记录轨迹的办法搞定了。
因为题目要求 1 <= path.length <= 104
,那么 x
和 y
的值,最大不会超过 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;
}