尧图网站建设  方案)
LeetCode 1496 Path Crossing 题解哈希集合与坐标编码的两种 O(n) 方案【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南围绕 LeetCode 1496 Path Crossing路径交叉展开基于本仓库 articles/path-crossing.md 的讲解框架完整覆盖哈希集合记录已访问坐标与自定义哈希将坐标编码为整数两种解法并结合仓库内 Java 实现 与 Kotlin 实现 的源码细节进行纵深分析。读完本文你将掌握用方向字典 坐标集合判断路径是否自交的通用套路、不同语言下坐标唯一表示的工程取舍以及时间复杂度 O(n)、空间复杂度 O(n) 的推导依据。前置知识在动手解题之前需要先熟悉以下两个基础概念哈希集合Hash Set用于 O(1) 的成员查询是判断某个坐标是否曾经访问过的核心数据结构。不同语言对应HashSet、unordered_set、Set、map等容器。坐标系Coordinate Systems理解如何在二维平面上表示和追踪位置即用(x, y)二元组描述一个点其中N/S改变y、E/W改变x。这两个前置条件在仓库内都有对应的工程化体现例如 Kotlin 实现 用PairInt, Int表示坐标Java 实现 用int[]数组表示坐标。1. 解法一哈希集合记录访问坐标直觉Intuition我们从原点(0, 0)出发逐字符读取路径。每一步都按照方向指示移动一格。如果走到一个之前访问过的位置说明路径发生了自交crossing。哈希集合恰好提供 O(1) 的查找能力用来回答这个坐标是否出现过。算法流程初始化一个集合visit并加入起点(0, 0)。初始化坐标x 0y 0。遍历路径中的每个字符根据方向N、S、E、W更新x或y。如果新位置已经存在于visit中返回true。否则把新位置加入visit。如果走完整个路径都没有重复访问任何位置返回false。各语言实现Pythonclass Solution: def isPathCrossing(self, path: str) - bool: dir { N: [0, 1], S: [0, -1], E: [1, 0], W: [-1, 0] } visit set() x, y 0, 0 for c in path: visit.add((x, y)) dx, dy dir[c] x, y x dx, y dy if (x, y) in visit: return True return FalsePython 实现采用方向字典元组(x, y)。注意它的循环顺序与多数语言不同先把当前点加入集合再移动并检查新点效果等价——因为每一步移动前当前点必然已在集合中最终依然能捕获所有重复访问。Javapublic class Solution { public boolean isPathCrossing(String path) { SetString visit new HashSet(); int x 0, y 0; visit.add(x , y); for (char c : path.toCharArray()) { if (c N) y; else if (c S) y--; else if (c E) x; else if (c W) x--; String pos x , y; if (visit.contains(pos)) return true; visit.add(pos); } return false; } }Cclass Solution { public: bool isPathCrossing(string path) { unordered_setstring visit; int x 0, y 0; visit.insert(to_string(x) , to_string(y)); for (char c : path) { if (c N) y; else if (c S) y--; else if (c E) x; else if (c W) x--; string pos to_string(x) , to_string(y); if (visit.count(pos)) return true; visit.insert(pos); } return false; } };JavaScriptclass Solution { /** * param {string} path * return {boolean} */ isPathCrossing(path) { const visit new Set(); let x 0, y 0; visit.add(${x},${y}); for (const c of path) { if (c N) y; else if (c S) y--; else if (c E) x; else if (c W) x--; const pos ${x},${y}; if (visit.has(pos)) return true; visit.add(pos); } return false; } }C#public class Solution { public bool IsPathCrossing(string path) { var visit new HashSetstring(); int x 0, y 0; visit.Add(${x},{y}); foreach (char c in path) { if (c N) y; else if (c S) y--; else if (c E) x; else if (c W) x--; string pos ${x},{y}; if (visit.Contains(pos)) return true; visit.Add(pos); } return false; } }Gofunc isPathCrossing(path string) bool { visit : make(map[string]bool) x, y : 0, 0 visit[fmt.Sprintf(%d,%d, x, y)] true for _, c : range path { if c N { y } else if c S { y-- } else if c E { x } else if c W { x-- } pos : fmt.Sprintf(%d,%d, x, y) if visit[pos] { return true } visit[pos] true } return false }Kotlinclass Solution { fun isPathCrossing(path: String): Boolean { val visit HashSetString() var x 0 var y 0 visit.add($x,$y) for (c in path) { when (c) { N - y S - y-- E - x W - x-- } val pos $x,$y if (visit.contains(pos)) return true visit.add(pos) } return false } }Swiftclass Solution { func isPathCrossing(_ path: String) - Bool { var visit SetString() var x 0, y 0 visit.insert(\(x),\(y)) for c in path { if c N { y 1 } else if c S { y - 1 } else if c E { x 1 } else if c W { x - 1 } let pos \(x),\(y) if visit.contains(pos) { return true } visit.insert(pos) } return false } }Rustimpl Solution { pub fn is_path_crossing(path: String) - bool { let mut visit HashSet::new(); let (mut x, mut y) (0i32, 0i32); visit.insert((x, y)); for c in path.chars() { match c { N y 1, S y - 1, E x 1, W x - 1, _ {} } if !visit.insert((x, y)) { return true; } } false } }Rust 的实现非常简洁直接使用HashSet(i32, i32)元组坐标并借助insert的返回值——当insert返回false时说明该元素已存在即发生交叉立即返回true。仓库源码佐证两种坐标表示风格仓库中的两套解法恰好演示了坐标序列化的两种不同风格Java 实现 使用Arrays.toString(pos)将int[]数组转换为[0, 0]形式的字符串再存入HashSetString这与上述标准解法用x , y拼接的思路一致都通过带分隔符的字符串保证唯一性。Kotlin 实现 则直接使用PairInt, Intx to y作为集合元素无需任何序列化语言层面的值相等性即可完成去重判断同时用mapOf维护方向到位移的映射表与 Python 版本的方向字典风格呼应。可以看到字符串拼接、元组、Pair 是三种等价做法选型取决于语言习惯与对可读性/性能的偏好。时间与空间复杂度时间复杂度$O(n)$其中n为路径字符串长度只需单次遍历每次集合操作平均 O(1)。空间复杂度$O(n)$最坏情况下每个坐标都不同集合中最多存储n个位置含起点。2. 解法二哈希集合自定义哈希编码坐标直觉Intuition解法一的字符串/元组表示已经足够正确但在某些语言中字符串拼接存在额外开销。解法二将坐标直接编码成一个整数把其中一个坐标左移 32 位再与另一个坐标相加得到该位置的唯一哈希值。这样集合中只存整数避免了字符串拼接开销同时保持 O(1) 查询。算法流程定义哈希函数hash(x, y) (x 32) y。初始化集合并加入hash(0, 0)。用x 0、y 0追踪当前位置。遍历路径中的每个字符根据方向更新坐标。计算新位置的hash值。若该值已存在于集合中返回true。否则将哈希值加入集合。未发现交叉则返回false。各语言实现Pythonclass Solution: def isPathCrossing(self, path: str) - bool: visit set() x, y 0, 0 visit.add(self.hash(x, y)) for c in path: if c N: y 1 elif c S: y - 1 elif c E: x 1 elif c W: x - 1 pos self.hash(x, y) if pos in visit: return True visit.add(pos) return False def hash(self, x: int, y: int) - int: return (x 32) yJavapublic class Solution { public boolean isPathCrossing(String path) { SetLong visit new HashSet(); int x 0, y 0; visit.add(hash(x, y)); for (char c : path.toCharArray()) { if (c N) y; else if (c S) y--; else if (c E) x; else if (c W) x--; long pos hash(x, y); if (visit.contains(pos)) return true; visit.add(pos); } return false; } private long hash(long x, long y) { return (x 32) y; } }Java 版本使用long类型的集合SetLong因为(x 32) y的结果可能超出int范围。Cclass Solution { public: bool isPathCrossing(string path) { unordered_setpairint, int, pair_hash visit; int x 0, y 0; visit.insert({x, y}); for (char c : path) { if (c N) y; else if (c S) y--; else if (c E) x; else if (c W) x--; if (visit.count({x, y})) return true; visit.insert({x, y}); } return false; } private: struct pair_hash { template class T1, class T2 size_t operator()(const pairT1, T2 p) const { return (hashT1()(p.first) 32) hashT2()(p.second); } }; };C 版本的思路略有不同集合元素仍然是pairint, int但通过自定义仿函数pair_hash定义其哈希规则为(hash(first) 32) hash(second)把坐标编码为整数的思想下沉到了哈希函数层面。JavaScriptclass Solution { /** * param {string} path * return {boolean} */ isPathCrossing(path) { const visit new Set(); let x 0, y 0; visit.add(this.hash(x, y)); for (const c of path) { if (c N) y; else if (c S) y--; else if (c E) x; else if (c W) x--; const pos this.hash(x, y); if (visit.has(pos)) return true; visit.add(pos); } return false; } /** * param {number} x * param {number} x * return {number} */ hash(x, y) { return (x 16) y; } }C#public class Solution { public bool IsPathCrossing(string path) { var visit new HashSetlong(); int x 0, y 0; visit.Add(Hash(x, y)); foreach (char c in path) { if (c N) y; else if (c S) y--; else if (c E) x; else if (c W) x--; long pos Hash(x, y); if (visit.Contains(pos)) return true; visit.Add(pos); } return false; } private long Hash(long x, long y) { return (x 32) y; } }Gofunc isPathCrossing(path string) bool { visit : make(map[int64]bool) x, y : int64(0), int64(0) visit[hash(x, y)] true for _, c : range path { if c N { y } else if c S { y-- } else if c E { x } else if c W { x-- } pos : hash(x, y) if visit[pos] { return true } visit[pos] true } return false } func hash(x, y int64) int64 { return (x 32) y }Kotlinclass Solution { fun isPathCrossing(path: String): Boolean { val visit HashSetLong() var x 0L var y 0L visit.add(hash(x, y)) for (c in path) { when (c) { N - y S - y-- E - x W - x-- } val pos hash(x, y) if (visit.contains(pos)) return true visit.add(pos) } return false } private fun hash(x: Long, y: Long): Long { return (x shl 32) y } }Swiftclass Solution { func isPathCrossing(_ path: String) - Bool { var visit SetInt64() var x: Int64 0, y: Int64 0 visit.insert(hash(x, y)) for c in path { if c N { y 1 } else if c S { y - 1 } else if c E { x 1 } else if c W { x - 1 } let pos hash(x, y) if visit.contains(pos) { return true } visit.insert(pos) } return false } private func hash(_ x: Int64, _ y: Int64) - Int64 { return (x 32) y } }Rustimpl Solution { pub fn is_path_crossing(path: String) - bool { let mut visit HashSet::new(); let (mut x, mut y) (0i64, 0i64); visit.insert(Self::hash(x, y)); for c in path.chars() { match c { N y 1, S y - 1, E x 1, W x - 1, _ {} } let pos Self::hash(x, y); if !visit.insert(pos) { return true; } } false } fn hash(x: i64, y: i64) - i64 { (x 32) y } }关于自定义哈希的几个工程要点位移位数与溢出多数语言使用(x 32) y前提是坐标不会大到让左右两部分互相干扰。JavaScript 由于位运算限制在 32 位整数原文档改用(x 16) y16 位给 x、16 位给 y这是针对语言特性做的合理适配。整数类型选择Java/C#/Go/Kotlin/Swift/Rust 等版本一律使用 64 位整数long/int64/Long/i64承载编码结果避免(x 32) y溢出或截断。与解法一的取舍自定义哈希省去了字符串拼接理论上常数更小但其正确性依赖于编码唯一这一前提且在不同语言中需额外处理溢出与位移位数。解法一的字符串/元组表示更直观、更不容易出错。两种方案的渐进复杂度完全相同实战中可依据可读性与性能需求二选一。时间与空间复杂度时间复杂度$O(n)$遍历一次路径集合操作平均 O(1)。空间复杂度$O(n)$集合最多存储n个编码后的整数。常见陷阱陷阱一忘记加入起点最常见的错误是在处理路径之前忘记把原点(0, 0)加入已访问集合。路径完全可能回到起点造成交叉因此起点必须从一开始就被追踪。如果只在移动之后才加入位置就会漏掉路径返回原点这类用例。陷阱二坐标表示不当导致碰撞或漏判把坐标存入哈希集合时不合适的表示方式可能引发碰撞或漏判。例如用x y直接拼接数字而不是x , y带分隔符拼接会让不同坐标对产生相同字符串——(1, 23)和(12, 3)都会变成123从而误判交叉。因此必须使用分隔符或元组表示来保证唯一性。仓库内 Java 实现 采用Arrays.toString自动生成[x, y]格式天然规避了这类碰撞问题。小结Path Crossing 是一道经典的模拟 去重问题核心模型沿路径逐格移动用哈希集合记录所有访问过的坐标一旦移动到已访问位置即判定交叉。两种实现路线解法一以字符串/元组/Pair 直接表示坐标直观通用解法二用(x 32) y把坐标编码为整数规避字符串拼接开销但需注意语言位宽与溢出。复杂度两种解法均为时间 O(n)、空间 O(n)。工程细节起点必须预先入集合坐标序列化必须唯一带分隔符或使用元组。本仓库在 articles/path-crossing.md 之外还提供了可直接对照阅读的 Java 实现 与 Kotlin 实现两者分别示范了Arrays.toString数组序列化与PairInt, Int直接存储的工程风格可作为练习与代码审查的参考样例。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 1496 Path Crossing 题解：哈希集合与坐标编码的两种 O(n) 方案
LeetCode 1496 Path Crossing 题解哈希集合与坐标编码的两种 O(n) 方案【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南围绕 LeetCode 1496 Path Crossing路径交叉展开基于本仓库 articles/path-crossing.md 的讲解框架完整覆盖哈希集合记录已访问坐标与自定义哈希将坐标编码为整数两种解法并结合仓库内 Java 实现 与 Kotlin 实现 的源码细节进行纵深分析。读完本文你将掌握用方向字典 坐标集合判断路径是否自交的通用套路、不同语言下坐标唯一表示的工程取舍以及时间复杂度 O(n)、空间复杂度 O(n) 的推导依据。前置知识在动手解题之前需要先熟悉以下两个基础概念哈希集合Hash Set用于 O(1) 的成员查询是判断某个坐标是否曾经访问过的核心数据结构。不同语言对应HashSet、unordered_set、Set、map等容器。坐标系Coordinate Systems理解如何在二维平面上表示和追踪位置即用(x, y)二元组描述一个点其中N/S改变y、E/W改变x。这两个前置条件在仓库内都有对应的工程化体现例如 Kotlin 实现 用PairInt, Int表示坐标Java 实现 用int[]数组表示坐标。1. 解法一哈希集合记录访问坐标直觉Intuition我们从原点(0, 0)出发逐字符读取路径。每一步都按照方向指示移动一格。如果走到一个之前访问过的位置说明路径发生了自交crossing。哈希集合恰好提供 O(1) 的查找能力用来回答这个坐标是否出现过。算法流程初始化一个集合visit并加入起点(0, 0)。初始化坐标x 0y 0。遍历路径中的每个字符根据方向N、S、E、W更新x或y。如果新位置已经存在于visit中返回true。否则把新位置加入visit。如果走完整个路径都没有重复访问任何位置返回false。各语言实现Pythonclass Solution: def isPathCrossing(self, path: str) - bool: dir { N: [0, 1], S: [0, -1], E: [1, 0], W: [-1, 0] } visit set() x, y 0, 0 for c in path: visit.add((x, y)) dx, dy dir[c] x, y x dx, y dy if (x, y) in visit: return True return FalsePython 实现采用方向字典元组(x, y)。注意它的循环顺序与多数语言不同先把当前点加入集合再移动并检查新点效果等价——因为每一步移动前当前点必然已在集合中最终依然能捕获所有重复访问。Javapublic class Solution { public boolean isPathCrossing(String path) { SetString visit new HashSet(); int x 0, y 0; visit.add(x , y); for (char c : path.toCharArray()) { if (c N) y; else if (c S) y--; else if (c E) x; else if (c W) x--; String pos x , y; if (visit.contains(pos)) return true; visit.add(pos); } return false; } }Cclass Solution { public: bool isPathCrossing(string path) { unordered_setstring visit; int x 0, y 0; visit.insert(to_string(x) , to_string(y)); for (char c : path) { if (c N) y; else if (c S) y--; else if (c E) x; else if (c W) x--; string pos to_string(x) , to_string(y); if (visit.count(pos)) return true; visit.insert(pos); } return false; } };JavaScriptclass Solution { /** * param {string} path * return {boolean} */ isPathCrossing(path) { const visit new Set(); let x 0, y 0; visit.add(${x},${y}); for (const c of path) { if (c N) y; else if (c S) y--; else if (c E) x; else if (c W) x--; const pos ${x},${y}; if (visit.has(pos)) return true; visit.add(pos); } return false; } }C#public class Solution { public bool IsPathCrossing(string path) { var visit new HashSetstring(); int x 0, y 0; visit.Add(${x},{y}); foreach (char c in path) { if (c N) y; else if (c S) y--; else if (c E) x; else if (c W) x--; string pos ${x},{y}; if (visit.Contains(pos)) return true; visit.Add(pos); } return false; } }Gofunc isPathCrossing(path string) bool { visit : make(map[string]bool) x, y : 0, 0 visit[fmt.Sprintf(%d,%d, x, y)] true for _, c : range path { if c N { y } else if c S { y-- } else if c E { x } else if c W { x-- } pos : fmt.Sprintf(%d,%d, x, y) if visit[pos] { return true } visit[pos] true } return false }Kotlinclass Solution { fun isPathCrossing(path: String): Boolean { val visit HashSetString() var x 0 var y 0 visit.add($x,$y) for (c in path) { when (c) { N - y S - y-- E - x W - x-- } val pos $x,$y if (visit.contains(pos)) return true visit.add(pos) } return false } }Swiftclass Solution { func isPathCrossing(_ path: String) - Bool { var visit SetString() var x 0, y 0 visit.insert(\(x),\(y)) for c in path { if c N { y 1 } else if c S { y - 1 } else if c E { x 1 } else if c W { x - 1 } let pos \(x),\(y) if visit.contains(pos) { return true } visit.insert(pos) } return false } }Rustimpl Solution { pub fn is_path_crossing(path: String) - bool { let mut visit HashSet::new(); let (mut x, mut y) (0i32, 0i32); visit.insert((x, y)); for c in path.chars() { match c { N y 1, S y - 1, E x 1, W x - 1, _ {} } if !visit.insert((x, y)) { return true; } } false } }Rust 的实现非常简洁直接使用HashSet(i32, i32)元组坐标并借助insert的返回值——当insert返回false时说明该元素已存在即发生交叉立即返回true。仓库源码佐证两种坐标表示风格仓库中的两套解法恰好演示了坐标序列化的两种不同风格Java 实现 使用Arrays.toString(pos)将int[]数组转换为[0, 0]形式的字符串再存入HashSetString这与上述标准解法用x , y拼接的思路一致都通过带分隔符的字符串保证唯一性。Kotlin 实现 则直接使用PairInt, Intx to y作为集合元素无需任何序列化语言层面的值相等性即可完成去重判断同时用mapOf维护方向到位移的映射表与 Python 版本的方向字典风格呼应。可以看到字符串拼接、元组、Pair 是三种等价做法选型取决于语言习惯与对可读性/性能的偏好。时间与空间复杂度时间复杂度$O(n)$其中n为路径字符串长度只需单次遍历每次集合操作平均 O(1)。空间复杂度$O(n)$最坏情况下每个坐标都不同集合中最多存储n个位置含起点。2. 解法二哈希集合自定义哈希编码坐标直觉Intuition解法一的字符串/元组表示已经足够正确但在某些语言中字符串拼接存在额外开销。解法二将坐标直接编码成一个整数把其中一个坐标左移 32 位再与另一个坐标相加得到该位置的唯一哈希值。这样集合中只存整数避免了字符串拼接开销同时保持 O(1) 查询。算法流程定义哈希函数hash(x, y) (x 32) y。初始化集合并加入hash(0, 0)。用x 0、y 0追踪当前位置。遍历路径中的每个字符根据方向更新坐标。计算新位置的hash值。若该值已存在于集合中返回true。否则将哈希值加入集合。未发现交叉则返回false。各语言实现Pythonclass Solution: def isPathCrossing(self, path: str) - bool: visit set() x, y 0, 0 visit.add(self.hash(x, y)) for c in path: if c N: y 1 elif c S: y - 1 elif c E: x 1 elif c W: x - 1 pos self.hash(x, y) if pos in visit: return True visit.add(pos) return False def hash(self, x: int, y: int) - int: return (x 32) yJavapublic class Solution { public boolean isPathCrossing(String path) { SetLong visit new HashSet(); int x 0, y 0; visit.add(hash(x, y)); for (char c : path.toCharArray()) { if (c N) y; else if (c S) y--; else if (c E) x; else if (c W) x--; long pos hash(x, y); if (visit.contains(pos)) return true; visit.add(pos); } return false; } private long hash(long x, long y) { return (x 32) y; } }Java 版本使用long类型的集合SetLong因为(x 32) y的结果可能超出int范围。Cclass Solution { public: bool isPathCrossing(string path) { unordered_setpairint, int, pair_hash visit; int x 0, y 0; visit.insert({x, y}); for (char c : path) { if (c N) y; else if (c S) y--; else if (c E) x; else if (c W) x--; if (visit.count({x, y})) return true; visit.insert({x, y}); } return false; } private: struct pair_hash { template class T1, class T2 size_t operator()(const pairT1, T2 p) const { return (hashT1()(p.first) 32) hashT2()(p.second); } }; };C 版本的思路略有不同集合元素仍然是pairint, int但通过自定义仿函数pair_hash定义其哈希规则为(hash(first) 32) hash(second)把坐标编码为整数的思想下沉到了哈希函数层面。JavaScriptclass Solution { /** * param {string} path * return {boolean} */ isPathCrossing(path) { const visit new Set(); let x 0, y 0; visit.add(this.hash(x, y)); for (const c of path) { if (c N) y; else if (c S) y--; else if (c E) x; else if (c W) x--; const pos this.hash(x, y); if (visit.has(pos)) return true; visit.add(pos); } return false; } /** * param {number} x * param {number} x * return {number} */ hash(x, y) { return (x 16) y; } }C#public class Solution { public bool IsPathCrossing(string path) { var visit new HashSetlong(); int x 0, y 0; visit.Add(Hash(x, y)); foreach (char c in path) { if (c N) y; else if (c S) y--; else if (c E) x; else if (c W) x--; long pos Hash(x, y); if (visit.Contains(pos)) return true; visit.Add(pos); } return false; } private long Hash(long x, long y) { return (x 32) y; } }Gofunc isPathCrossing(path string) bool { visit : make(map[int64]bool) x, y : int64(0), int64(0) visit[hash(x, y)] true for _, c : range path { if c N { y } else if c S { y-- } else if c E { x } else if c W { x-- } pos : hash(x, y) if visit[pos] { return true } visit[pos] true } return false } func hash(x, y int64) int64 { return (x 32) y }Kotlinclass Solution { fun isPathCrossing(path: String): Boolean { val visit HashSetLong() var x 0L var y 0L visit.add(hash(x, y)) for (c in path) { when (c) { N - y S - y-- E - x W - x-- } val pos hash(x, y) if (visit.contains(pos)) return true visit.add(pos) } return false } private fun hash(x: Long, y: Long): Long { return (x shl 32) y } }Swiftclass Solution { func isPathCrossing(_ path: String) - Bool { var visit SetInt64() var x: Int64 0, y: Int64 0 visit.insert(hash(x, y)) for c in path { if c N { y 1 } else if c S { y - 1 } else if c E { x 1 } else if c W { x - 1 } let pos hash(x, y) if visit.contains(pos) { return true } visit.insert(pos) } return false } private func hash(_ x: Int64, _ y: Int64) - Int64 { return (x 32) y } }Rustimpl Solution { pub fn is_path_crossing(path: String) - bool { let mut visit HashSet::new(); let (mut x, mut y) (0i64, 0i64); visit.insert(Self::hash(x, y)); for c in path.chars() { match c { N y 1, S y - 1, E x 1, W x - 1, _ {} } let pos Self::hash(x, y); if !visit.insert(pos) { return true; } } false } fn hash(x: i64, y: i64) - i64 { (x 32) y } }关于自定义哈希的几个工程要点位移位数与溢出多数语言使用(x 32) y前提是坐标不会大到让左右两部分互相干扰。JavaScript 由于位运算限制在 32 位整数原文档改用(x 16) y16 位给 x、16 位给 y这是针对语言特性做的合理适配。整数类型选择Java/C#/Go/Kotlin/Swift/Rust 等版本一律使用 64 位整数long/int64/Long/i64承载编码结果避免(x 32) y溢出或截断。与解法一的取舍自定义哈希省去了字符串拼接理论上常数更小但其正确性依赖于编码唯一这一前提且在不同语言中需额外处理溢出与位移位数。解法一的字符串/元组表示更直观、更不容易出错。两种方案的渐进复杂度完全相同实战中可依据可读性与性能需求二选一。时间与空间复杂度时间复杂度$O(n)$遍历一次路径集合操作平均 O(1)。空间复杂度$O(n)$集合最多存储n个编码后的整数。常见陷阱陷阱一忘记加入起点最常见的错误是在处理路径之前忘记把原点(0, 0)加入已访问集合。路径完全可能回到起点造成交叉因此起点必须从一开始就被追踪。如果只在移动之后才加入位置就会漏掉路径返回原点这类用例。陷阱二坐标表示不当导致碰撞或漏判把坐标存入哈希集合时不合适的表示方式可能引发碰撞或漏判。例如用x y直接拼接数字而不是x , y带分隔符拼接会让不同坐标对产生相同字符串——(1, 23)和(12, 3)都会变成123从而误判交叉。因此必须使用分隔符或元组表示来保证唯一性。仓库内 Java 实现 采用Arrays.toString自动生成[x, y]格式天然规避了这类碰撞问题。小结Path Crossing 是一道经典的模拟 去重问题核心模型沿路径逐格移动用哈希集合记录所有访问过的坐标一旦移动到已访问位置即判定交叉。两种实现路线解法一以字符串/元组/Pair 直接表示坐标直观通用解法二用(x 32) y把坐标编码为整数规避字符串拼接开销但需注意语言位宽与溢出。复杂度两种解法均为时间 O(n)、空间 O(n)。工程细节起点必须预先入集合坐标序列化必须唯一带分隔符或使用元组。本仓库在 articles/path-crossing.md 之外还提供了可直接对照阅读的 Java 实现 与 Kotlin 实现两者分别示范了Arrays.toString数组序列化与PairInt, Int直接存储的工程风格可作为练习与代码审查的参考样例。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考