题目
在无限的平面上，机器人最初位于 (0, 0) 处，面朝北方。注意:
- 北方向 是y轴的正方向。
- 南方向 是y轴的负方向。
- 东方向 是x轴的正方向。
- 西方向 是x轴的负方向。
机器人可以接受下列三条指令之一：
"G"：直走 1 个单位"L"：左转 90 度"R"：右转 90 度
机器人按顺序执行指令 instructions，并一直重复它们。
只有在平面中存在环使得机器人永远无法离开时，返回 true。否则，返回 false。
示例 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
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“L”:逆时针旋转90度。位置:(0,1).方向:西。
“G”:移动一步。位置:(- 1,1)方向:西。
“L”:逆时针旋转90度。位置:(- 1,1)方向:南。
“G”:移动一步。位置:(- 1,0)方向:南。
“L”:逆时针旋转90度。位置:(- 1,0)方向:东方。
“G”:移动一步。位置:(0,0)方向:东方。
“L”:逆时针旋转90度。位置:(0,0)方向:北。
重复指令，机器人进入循环:(0,0)——>(0,1)——>(- 1,1)——>(- 1,0)——>(0,0)。
在此基础上，我们返回true。
提示：
1 <= instructions.length <= 100instructions[i]仅包含'G', 'L', 'R'
思路
- 进入循环说明机器人在执行步骤一定次数后会回到原点，那么我们就需要考虑什么情况下机器人可以回到原点。
- 一般情况下，只要不是朝着一个方向一直走，肯定就能回到原点，因为每次发生的方位变化，总共也就最多是发生90-270度的变化，所以当步骤数达到1-4的最小公倍数的时候，必然是会恢复到原来的状态的。
- 基于此，我们可以考虑循环的情况了：
- 如果发生方向变化，那么总是能回来的。
- 如果循环完后没有移动，总是能回来的。
- 那么我们可以定义一个在0-3变化的指针表示方向，另外定义一个规模为4的数组表示各方向上的移动。
- 最后我们就可以根据指针方向和数组相对方向的相等情况判断是否可以产生循环了。
代码实现
class Solution {
public:
bool isRobotBounded(string instructions) {
int ptr = 0, directions[4];
for(int i = 0; i < 4; ++i) directions[i] = 0;
for(int i = 0; i < instructions.size(); ++i) {
if(instructions[i] == 'G') ++directions[ptr];
else if(instructions[i] == 'L') ptr = (ptr+3) % 4;
else if(instructions[i] == 'R') ptr = (ptr+1) % 4;
}
if(ptr != 0) return true;
if(directions[0]==directions[2] && directions[1]==directions[3]) return true;
return false;
}
};复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。