Medium

题目描述

在无限的平面上，机器人最初位于 (0, 0) 处并面向北方。注意：

  • 北方向是 y 轴的正方向。
  • 南方向是 y 轴的负方向。
  • 东方向是 x 轴的正方向。
  • 西方向是 x 轴的负方向。

机器人可以接收以下三个指令之一：

  • “G”：直走 1 个单位。
  • “L”：向左转 90 度（即逆时针方向）。
  • “R”：向右转 90 度（即顺时针方向）。

机器人按顺序执行给定的指令，并永远重复它们。

当且仅当平面中存在一个圆，使得机器人永远不会离开该圆时，返回 true。

示例 1：

输入：instructions = "GGLLGG"
输出：true
解释：机器人最初在 (0, 0) 处面向北方。
"G": 移动一步。位置：(0, 1)。方向：北。
"G": 移动一步。位置：(0, 2)。方向：北。
"L": 逆时针转 90 度。位置：(0, 2)。方向：西。
"L": 逆时针转 90 度。位置：(0, 2)。方向：南。
"G": 移动一步。位置：(0, 1)。方向：南。
"G": 移动一步。位置：(0, 0)。方向：南。
重复指令，机器人进入循环：(0, 0) --> (0, 1) --> (0, 2) --> (0, 1) --> (0, 0)。
因此，我们返回 true。

示例 2：

输入：instructions = "GG"
输出：false
解释：机器人最初在 (0, 0) 处面向北方。
"G": 移动一步。位置：(0, 1)。方向：北。
"G": 移动一步。位置：(0, 2)。方向：北。
重复指令，继续向北前进而不会进入循环。
因此，我们返回 false。

示例 3：

输入：instructions = "GL"
输出：true

约束条件：

  • 1 <= instructions.length <= 100
  • instructions[i] 是 ‘G’、‘L’ 或 ‘R’。

解题思路

这道题的关键是理解什么情况下机器人会被限制在一个圆内。

机器人是否被困在圆中取决于执行一轮指令后的状态。我们需要分析两个关键信息：

  1. 位置变化：执行一轮指令后机器人相对于起始位置的偏移
  2. 方向变化：执行一轮指令后机器人的朝向

根据数学原理，机器人被困在圆中的充要条件是：执行一轮指令后，要么回到原点（位置偏移为0），要么方向发生了改变（不再朝向北方）。

证明思路：

  • 如果一轮后回到原点，显然会形成循环
  • 如果一轮后位置有偏移但方向改变了，那么经过有限轮后必定会回到原点。具体来说：
    • 如果方向转了90度，最多4轮后回到原点
    • 如果方向转了180度，最多2轮后回到原点
    • 如果方向转了270度，最多4轮后回到原点
  • 只有当一轮后既有位置偏移又保持朝北时，机器人才会无限远离原点

算法实现：模拟执行一轮指令，记录最终位置和方向，然后判断是否满足被困条件。

我们可以用数组 directions = [[0,1], [1,0], [0,-1], [-1,0]] 表示北、东、南、西四个方向，用索引0-3表示当前朝向。

代码实现

class Solution {
public:
    bool isRobotBounded(string instructions) {
        // 方向数组：北(0,1), 东(1,0), 南(0,-1), 西(-1,0)
        vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, y = 0;
        int dir = 0; // 初始朝向北方
        
        for (char instruction : instructions) {
            if (instruction == 'G') {
                x += directions[dir][0];
                y += directions[dir][1];
            } else if (instruction == 'L') {
                dir = (dir + 3) % 4; // 逆时针转90度
            } else if (instruction == 'R') {
                dir = (dir + 1) % 4; // 顺时针转90度
            }
        }
        
        // 如果回到原点或者方向改变了，则被困在圆中
        return (x == 0 && y == 0) || (dir != 0);
    }
};

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        # 方向数组：北(0,1), 东(1,0), 南(0,-1), 西(-1,0)
        directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        x = y = 0
        direction = 0  # 初始朝向北方
        
        for instruction in instructions:
            if instruction == 'G':
                x += directions[direction][0]
                y += directions[direction][1]
            elif instruction == 'L':
                direction = (direction + 3) % 4  # 逆时针转90度
            elif instruction == 'R':
                direction = (direction + 1) % 4  # 顺时针转90度
        
        # 如果回到原点或者方向改变了，则被困在圆中
        return (x == 0 and y == 0) or (direction != 0)

public class Solution {
    public bool IsRobotBounded(string instructions) {
        // 方向数组：北(0,1), 东(1,0), 南(0,-1), 西(-1,0)
        int[,] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, y = 0;
        int dir = 0; // 初始朝向北方
        
        foreach (char instruction in instructions) {
            if (instruction == 'G') {
                x += directions[dir, 0];
                y += directions[dir, 1];
            } else if (instruction == 'L') {
                dir = (dir + 3) % 4; // 逆时针转90度
            } else if (instruction == 'R') {
                dir = (dir + 1) % 4; // 顺时针转90度
            }
        }
        
        // 如果回到原点或者方向改变了，则被困在圆中
        return (x == 0 && y == 0) || (dir != 0);
    }
}

var isRobotBounded = function(instructions) {
    let x = 0, y = 0;
    let direction = 0; // 0: North, 1: East, 2: South, 3: West
    
    const dx = [0, 1, 0, -1];
    const dy = [1, 0, -1, 0];
    
    for (let char of instructions) {
        if (char === 'G') {
            x += dx[direction];
            y += dy[direction];
        } else if (char === 'L') {
            direction = (direction + 3) % 4;
        } else if (char === 'R') {
            direction = (direction + 1) % 4;
        }
    }
    
    return (x === 0 && y === 0) || direction !== 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

其中 n 是指令字符串的长度。我们只需要遍历一次指令序列，每个操作都是常数时间，空间复杂度为常数级别。