leetcode
leetcode 951 ~ 1000
困于环中的机器人

困于环中的机器人

难度:

标签:

题目描述

代码结果

运行时间: 23 ms, 内存: 16.1 MB


/*
 * Problem: Determine if a robot stays in a circle after executing a set of instructions repeatedly.
 * Instructions:
 * - 'G': Go straight 1 unit
 * - 'L': Turn left 90 degrees
 * - 'R': Turn right 90 degrees
 * The robot initially faces north (positive y direction).
 * The robot's movement directions are represented as:
 * 0: North, 1: East, 2: South, 3: West
 * This solution uses Java Streams to process the instructions.
 */
import java.util.stream.IntStream;

public class RobotCircleStream {
    public boolean isRobotBounded(String instructions) {
        int[] position = {0, 0}; // Initial position (x, y)
        int[] direction = {0, 1}; // Initial direction (north)
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // N, E, S, W

        // Process instructions using streams
        IntStream.range(0, instructions.length()).forEach(i -> {
            char instruction = instructions.charAt(i);
            if (instruction == 'G') {
                position[0] += direction[0];
                position[1] += direction[1];
            } else if (instruction == 'L') {
                direction = directions[(directionIndex(direction) + 3) % 4];
            } else if (instruction == 'R') {
                direction = directions[(directionIndex(direction) + 1) % 4];
            }
        });

        // Check if the robot is back at the origin or not facing north
        return (position[0] == 0 && position[1] == 0) || directionIndex(direction) != 0;
    }

    // Helper method to determine direction index
    private int directionIndex(int[] direction) {
        if (direction[0] == 0 && direction[1] == 1) return 0; // North
        if (direction[0] == 1 && direction[1] == 0) return 1; // East
        if (direction[0] == 0 && direction[1] == -1) return 2; // South
        return 3; // West
    }
}

解释

方法:

本题解的关键思路是模拟机器人的移动和转向,并检查一遍指令后机器人的状态。机器人如果在执行一轮指令后返回到起点或者朝向非北方向(说明它的路径将会是闭环),则表示机器人的行动是有界的。在代码中,使用变量x, y来记录机器人在平面上的位置,d来记录当前的方向(用角度表示,北为0度,东90度,南180度,西270度或-90度)。根据指令'G', 'L', 'R'更新这些变量。最后,检查机器人是否回到原点(x = 0, y = 0)或方向不为北(d % 360 != 0),如果满足任一条件,则返回true,表示机器人的运动是有界的。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在算法中,为什么机器人返回到原点或方向改变后,可以确信机器人的运动是有界的?
在算法中,如果机器人在执行一轮指令后返回到原点,无论之后如何重复这些指令,机器人都会保持在原点,或者沿着一个循环路径行动。如果机器人方向改变(即不再朝北),这意味着在重复指令后,机器人将开始在一个闭环路径上移动,最终形成一个有限的循环区域。因此,这两种情况下机器人的运动都是有界的。
🦆
算法中使用了模360的操作来判断方向。这种处理方式是否适用于所有可能的方向变化,包括多次累积旋转?
模360的操作能有效处理方向,因为角度加减后可能超过360度或小于0度,模360可以将这些值规范化到[0, 360)的范围内。这样处理后,可以保证方向的计算始终有效,无论多少次旋转,方向总是被正确地处理。
🦆
代码中将方向用角度表示,并进行加减操作。这种表示法在处理方向时有什么优势或可能的缺点?
使用角度表示方向的优势在于直观和易于处理。通过简单的加减操作即可模拟实际的转向动作。然而,这种方法的缺点包括可能出现的额外计算(如模360操作)以及在某些情况下可能不如使用向量或矩阵运算直接,特别是在更复杂的空间运动模拟中。
🦆
如果输入指令非常长,算法是否还能有效地处理,或者可能会遇到什么性能瓶颈?
本算法在处理每个指令时进行一次循环,其时间复杂度为O(n),n是指令长度。对于非常长的指令序列,这种处理方法仍然有效,但性能瓶颈可能在于处理大量数据时的时间消耗。当输入极大时,执行时间会线性增长,这可能导致处理速度变慢,尤其在资源受限的环境下更为明显。

相关问题