LeetCode 874. 模拟行走机器人

Categories:

题目描述
思路分析
1. 解法一：哈希集合 + 模拟（推荐）
相似题目

题目描述

✅ 874. 模拟行走机器人

思路分析

解法一：哈希集合 + 模拟（推荐）

核心思路：

用集合存储障碍物坐标，便于 O(1) 判断。

维护当前方向，按指令移动或转向。

每步更新最远距离平方。

复杂度分析：

时间复杂度：O(S)，其中 S 为总步数。

空间复杂度：O(m)，其中 m 表示障碍物数量。

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        Set<Long> block = new HashSet<>();
        for (int[] o : obstacles) {
            long key = (((long) o[0]) << 32) ^ (o[1] & 0xffffffffL);
            block.add(key);
        }

        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int dir = 0;
        int x = 0;
        int y = 0;
        int best = 0;

        for (int cmd : commands) {
            if (cmd == -2) {
                dir = (dir + 3) % 4;
            } else if (cmd == -1) {
                dir = (dir + 1) % 4;
            } else {
                for (int i = 0; i < cmd; i++) {
                    int nx = x + dirs[dir][0];
                    int ny = y + dirs[dir][1];
                    long key = (((long) nx) << 32) ^ (ny & 0xffffffffL);
                    if (block.contains(key)) {
                        break;
                    }
                    x = nx;
                    y = ny;
                    best = Math.max(best, x * x + y * y);
                }
            }
        }

        return best;
    }
}

func robotSim(commands []int, obstacles [][]int) int {
	block := make(map[int64]bool)
	for _, o := range obstacles {
		key := (int64(o[0]) << 32) ^ int64(uint32(o[1]))
		block[key] = true
	}

	dirs := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
	dir := 0
	x, y := 0, 0
	best := 0

	for _, cmd := range commands {
		if cmd == -2 {
			dir = (dir + 3) % 4
		} else if cmd == -1 {
			dir = (dir + 1) % 4
		} else {
			for step := 0; step < cmd; step++ {
				nx := x + dirs[dir][0]
				ny := y + dirs[dir][1]
				key := (int64(nx) << 32) ^ int64(uint32(ny))
				if block[key] {
					break
				}
				x, y = nx, ny
				dist := x*x + y*y
				if dist > best {
					best = dist
				}
			}
		}
	}

	return best
}

相似题目

题目	难度	考察点
1041. 困于环中的机器人	中等	模拟
1496. 判断路径是否相交	简单	模拟
59. 螺旋矩阵 II	中等	模拟
54. 螺旋矩阵	中等	模拟
657. 机器人能否返回原点	简单	模拟

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/37730531