哈希算法题目：模拟行走机器人

题目描述
机器人从原点 (0,0) 开始，在二维平面上移动。给定一个命令序列，其中每个命令可以是：

• 整数：表示向前移动的步数
• 字符：表示转向（-2 表示向左转 90 度，-1 表示向右转 90 度）

同时给定一个障碍物数组，每个障碍物用坐标 [x,y] 表示。机器人在移动过程中，如果下一个位置是障碍物，将停留在当前位置，并跳过该移动指令的剩余部分。

要求计算机器人从原点开始执行所有命令后，到达位置离原点的最大欧式距离的平方（即 max(x² + y²)）。

解题过程

步骤1：理解方向和移动

• 机器人有四个基本方向：北(0,1)、东(1,0)、南(0,-1)、西(-1,0)
• 用方向数组表示：dirs = [[0,1], [1,0], [0,-1], [-1,0]]
• 初始方向索引为0（向北）

步骤2：处理转向指令

• 当前方向索引为d
• 右转(-1)：d = (d + 1) % 4
• 左转(-2)：d = (d + 3) % 4 （相当于d-1模4）

步骤3：处理移动和障碍物检测

• 将障碍物存入哈希集合，用字符串"x,y"作为键
• 对于移动指令，一步一步移动：
  • 计算下一个位置：nx = x + dirs[d][0], ny = y + dirs[d][1]
  • 如果[nx,ny]在障碍物集合中，停止本次移动
  • 否则更新当前位置

步骤4：跟踪最大距离

• 在每次成功移动后，计算当前距离平方：x² + y²
• 更新最大值

详细实现示例

def robotSim(commands, obstacles):
    # 方向数组：北、东、南、西
    dirs = [[0,1], [1,0], [0,-1], [-1,0]]
    x = y = d = 0  # 初始位置和方向
    max_dist = 0
    
    # 将障碍物存入哈希集合
    obstacle_set = set()
    for ob in obstacles:
        obstacle_set.add((ob[0], ob[1]))
    
    for cmd in commands:
        if cmd == -1:  # 右转
            d = (d + 1) % 4
        elif cmd == -2:  # 左转
            d = (d + 3) % 4
        else:  # 移动指令
            for _ in range(cmd):
                nx = x + dirs[d][0]
                ny = y + dirs[d][1]
                # 检查是否遇到障碍物
                if (nx, ny) in obstacle_set:
                    break
                x, y = nx, ny
                # 更新最大距离平方
                max_dist = max(max_dist, x*x + y*y)
    
    return max_dist

关键点说明

1. 方向处理：使用模运算简化方向转换
2. 障碍物检测：哈希集合提供O(1)的查询效率
3. 移动方式：一步一步移动确保遇到障碍物时立即停止
4. 距离计算：只需计算平方避免开方运算，节省计算资源

这个解法的时间复杂度是O(N+K)，其中N是命令数量，K是移动总步数，空间复杂度是O(M)用于存储障碍物。