【教3妹学算法-每日3题(3)】判断路径是否相交

插： 前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。 
坚持不懈，越努力越幸运，大家一起学习鸭~~~

3妹：“池塘边的榕树上, 知了在声声叫着夏天”
2哥：“操场边的秋千上,只有蝴蝶停在上面”
3妹：没想到2哥也会唱这类歌曲啊。
2哥：这首哥在我小时候已经很流行了。3妹怎么想起来唱这首歌了？
3妹：2哥在追忆青春，而我正值青春，不会去追忆，所以只能追忆一下童年了，哈哈哈哈。
2哥：“你的童年我的童年好像都一样？”
3妹：“小小肩膀大大书包，上呀上学堂？”，哈哈哈哈。
2哥：哈哈哈哈

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

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

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

示例 1：

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

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

提示：

1 <= path.length <= 10^4
path[i] 为 ‘N’、‘S’、‘E’ 或 ‘W’

#思路：
哈希表，记录已经走过的点

#java代码1：

class Solution {
    public boolean isPathCrossing(String path) {
        Set<Integer> vis = new HashSet<Integer>();

        int x = 0, y = 0;
        vis.add(getHash(x, y));

        int length = path.length();
        for (int i = 0; i < length; i++) {
            char dir = path.charAt(i);
            switch (dir) {
                case 'N': --x; break;
                case 'S': ++x; break;
                case 'W': --y; break;
                case 'E': ++y; break;
            }
            int hashValue = getHash(x, y);
            if (!vis.add(hashValue)) {
                return true;
            }
        }

        return false;
    }

    public int getHash(int x, int y) {
        return x * 20001 + 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
30
31