判断路径是否相交

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

问题描述

给你一个字符串 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'

思路分析

首先我们应该要先理解一下题目意思，题目会给我们一个字符串path，path[i] 为 'N'、'S'、'E' 或 'W'，分别表示向北、向南、向东、向西移动一个单位。我们从二维平面上的原点 (0, 0) 处开始出发，按 path 所指示的路径行走。我们需要判断在移动的过程中路线会不会相交，也就是走到之前已经走过的位置，如果存在相交的情况，返回 true ；否则，返回 false 。

知道了题目的意思之后，我们便可以开始编写代码解题了：

• 1、遍历 path，计算移动的坐标

根据 path[i]来对应修改坐标值即可：

N 表示向北移动一个单位，x 坐标不变，y 坐标加一；

S 表示向南移动一个单位，x 坐标不变，y 坐标减一；

E 表示向东移动一个单位，y 坐标不变，x 坐标加一；

W 表示向西移动一个单位，y 坐标不变，x 坐标减一；

for (let i = 0; i < path.length; i++) {
  if (path[i] === "N") y++;
  else if (path[i] === "S") y--;
  else if (path[i] === "W") x--;
  else if (path[i] === "E") x++;
}

• 2、使用Set记录走过的坐标点

我们需要将走过的坐标点记录起来，用于判断当前经过的坐标点是否已经走过，我们可以使用Map或Set来记录，这里我是用 Set 来记录，添加坐标前判断 set 中是否已经存在当前坐标即可。

const set = new Set(["0-0"]);
let x = 0,
  y = 0;
for (let i = 0; i < path.length; i++) {
  if (path[i] === "N") y++;
  else if (path[i] === "S") y--;
  else if (path[i] === "W") x--;
  else if (path[i] === "E") x++;
  if (set.has(x + "-" + y)) return true;
  set.add(x + "-" + y);
}

AC 代码

完整 AC 代码如下：

/**
 * @param {string} path
 * @return {boolean}
 */
var isPathCrossing = function (path) {
  const set = new Set(["0-0"]);
  let x = 0,
    y = 0;
  for (let i = 0; i < path.length; i++) {
    if (path[i] === "N") y++;
    else if (path[i] === "S") y--;
    else if (path[i] === "W") x--;
    else if (path[i] === "E") x++;
    if (set.has(x + "-" + y)) return true;
    set.add(x + "-" + y);
  }
  return false;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。