困于环中的机器人
难度:
标签:
题目描述
代码结果
运行时间: 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的操作来判断方向。这种处理方式是否适用于所有可能的方向变化,包括多次累积旋转?
▷🦆
代码中将方向用角度表示,并进行加减操作。这种表示法在处理方向时有什么优势或可能的缺点?
▷🦆
如果输入指令非常长,算法是否还能有效地处理,或者可能会遇到什么性能瓶颈?
▷