力扣 874. 模拟行走机器人
机器人在一个无限大小的 XY 网格平面上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ：
- -2 ：向左转 90 度
- -1 ：向右转 90 度
- 1 <= x <= 9 ：向前移动 x 个单位长度
网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点 obstacles[i] = (xi, yi) 。
机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，但仍然可以继续尝试进行该路线的其余部分。
返回从原点到机器人所有经过的路径点（坐标为整数）的最大欧式距离的平方。（即，如果距离为 5 ，则返回 25 ）
注意：
- 北表示 +Y 方向。
- 东表示 +X 方向。
- 南表示 -Y 方向。
- 西表示 -X 方向。
方案一：先将所有障碍物坐标都哈希保存，然后通过方向数组控制方向移动，如果的过程中的坐标经过 hash map 中保存的值，则停止前进。
func robotSim(commands []int, obstacles [][]int) (ans int) {
// 遍历所有障碍物，将其哈希存储
mp := make(map[int]struct{})
for _, v := range obstacles {
mp[hash(v[0], v[1])] = struct{}{}
}
// 方向数组 dx[idx], dy[idx] 正好表示东南西北四个方向
dx := []int{0, 1, 0, -1}
dy := []int{1, 0, -1, 0}
// 当前方向
dir := 0
// 初始坐标
x, y := 0, 0
// 遍历指令
for _, cmd := range commands {
switch cmd {
case -2: // 左转90 度
dir = (dir - 1 + 4) % 4
case -1: // 右转 90 度
dir = (dir + 1) % 4
default: // 前进
for i := 0; i < cmd; i++ {
// 下一步的位置
nx, ny := x + dx[dir], y + dy[dir]
// 如果下一步是障碍物
if _, ok := mp[hash(nx, ny)]; ok {
break
}
// 更新位置
x, y = nx, ny
}
// 更新结果
ans = max(ans, x * x + y * y)
}
}
return
}
// hash 哈希函数。
func hash(x, y int) int {
// 因为坐标有负数的，通过对 x，y 坐标 +30000
// 使其整体向坐标轴右上方移动，保证坐标的位置都位于第一象限
return (x + 30000) * 600000 + y + 30000
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
- 时间复杂度：O(len(commands) + len(obstacles))，因为需要遍历所有 commands 和 obstacles，所以时间复杂度为 O(len(commands) + len(obstacles))。
- 空间复杂度：O(len(obstacles))，因为使用了长度不超过 len(obstacles) 的无序映射以及常数级别的变量，所以空间复杂度为 O(len(obstacles))。