模拟行走机器人 II

给你一个在 XY 平面上的 width x height 的网格图，左下角 的格子为 (0, 0) ，右上角 的格子为 (width - 1, height - 1) 。网格图中相邻格子为四个基本方向之一（"North"，"East"，"South" 和 "West"）。一个机器人 初始 在格子 (0, 0) ，方向为 "East" 。

机器人可以根据指令移动指定的 步数 。每一步，它可以执行以下操作。

1. 沿着当前方向尝试 往前一步 。
2. 如果机器人下一步将到达的格子 超出了边界 ，机器人会 逆时针 转 90 度，然后再尝试往前一步。

如果机器人完成了指令要求的移动步数，它将停止移动并等待下一个指令。

请你实现 Robot 类：

• Robot(int width, int height) 初始化一个 width x height 的网格图，机器人初始在 (0, 0) ，方向朝 "East" 。
• void step(int num) 给机器人下达前进 num 步的指令。
• int[] getPos() 返回机器人当前所处的格子位置，用一个长度为 2 的数组 [x, y] 表示。
• String getDir() 返回当前机器人的朝向，为 "North" ，"East" ，"South" 或者 "West" 。

 

示例 1：

输入：
["Robot", "step", "step", "getPos", "getDir", "step", "step", "step", "getPos", "getDir"]
[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]
输出：
[null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]

解释：
Robot robot = new Robot(6, 3); // 初始化网格图，机器人在 (0, 0) ，朝东。
robot.step(2);  // 机器人朝东移动 2 步，到达 (2, 0) ，并朝东。
robot.step(2);  // 机器人朝东移动 2 步，到达 (4, 0) ，并朝东。
robot.getPos(); // 返回 [4, 0]
robot.getDir(); // 返回 "East"
robot.step(2);  // 朝东移动 1 步到达 (5, 0) ，并朝东。
                // 下一步继续往东移动将出界，所以逆时针转变方向朝北。
                // 然后，往北移动 1 步到达 (5, 1) ，并朝北。
robot.step(1);  // 朝北移动 1 步到达 (5, 2) ，并朝 北 （不是朝西）。
robot.step(4);  // 下一步继续往北移动将出界，所以逆时针转变方向朝西。
                // 然后，移动 4 步到 (1, 2) ，并朝西。
robot.getPos(); // 返回 [1, 2]
robot.getDir(); // 返回 "West"

 

提示：

• 2 <= width, height <= 100
• 1 <= num <= 105
• step ，getPos 和 getDir 总共 调用次数不超过 104 次。

/*
 * 思路：
 * 1. 使用 Java Stream 的迭代功能来处理步数移动。
 * 2. 通过迭代每一步，计算是否需要转向，更新坐标。
 * 3. 在完成所有移动后返回最终位置和方向。
 */

import java.util.stream.IntStream;

public class RobotStream {
    private int width, height;
    private int x, y;
    private int directionIndex;
    private String[] directions = {"East", "North", "West", "South"};
    
    public RobotStream(int width, int height) {
        this.width = width;
        this.height = height;
        this.x = 0;
        this.y = 0;
        this.directionIndex = 0; // East
    }
    
    public void step(int num) {
        IntStream.range(0, num).forEach(i -> {
            int nextX = x, nextY = y;
            switch (directions[directionIndex]) {
                case "East": nextX++; break;
                case "North": nextY++; break;
                case "West": nextX--; break;
                case "South": nextY--; break;
            }
            if (nextX < 0 || nextX >= width || nextY < 0 || nextY >= height) {
                directionIndex = (directionIndex + 1) % 4;
            } else {
                x = nextX;
                y = nextY;
            }
        });
    }
    
    public int[] getPos() {
        return new int[]{x, y};
    }
    
    public String getDir() {
        return directions[directionIndex];
    }
}

此题解采用了预计算的方法，通过预先存储机器人可能的所有位置和方向，以优化查询性能。在初始化时，Robot 类构建了一个沿着网格边界顺时针旋转的路径。这包括机器人从起始点开始，向东行进至最右边，然后向北至最顶部，接着向西至最左边，最后向南回到起始点上方的位置，形成一个封闭环路。此后，机器人的每一步都通过简单地索引更新来模拟，这使得移动操作非常高效。step 方法通过更新索引来模拟机器人的移动，getPos 和 getDir 方法则提供了查询当前位置和方向的功能。

O(1)

O(width + height)