[LeetCode] 1041. Robot Bounded In Circle

On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:

"G": go straight 1 unit;
"L": turn 90 degrees to the left;
"R": turn 90 degress to the right.

The robot performs the instructions given in order, and repeats them forever.

Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

Example 1:

Input: "GGLLGG"
Output: true
Explanation: 
The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0).
When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.

Example 2:

Input: "GG"
Output: false
Explanation: 
The robot moves north indefinitely.

Example 3:

Input: "GL"
Output: true
Explanation: 
The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...

Note:

1 <= instructions.length <= 100
instructions[i] is in {'G', 'L', 'R'}

困于环中的机器人。

在无限的平面上，机器人最初位于 (0, 0) 处，面朝北方。机器人可以接受下列三条指令之一：

"G"：直走 1 个单位
"L"：左转 90 度
"R"：右转 90 度
机器人按顺序执行指令 instructions，并一直重复它们。

只有在平面中存在环使得机器人永远无法离开时，返回 true。否则，返回 false。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/robot-bounded-in-circle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题意是给一个用字符串表示的指令，指令包含G, L, R，分别表示直走一个单位，左转90度，右转90度。假设机器人一开始是在（0，0）处并且面朝北方，请判断机器人是否永远无法离开。

这道题没有什么算法，只要这背后的数学原理想清楚就行。什么叫做无法离开（false）？意思是给的指令如果跑了一次或者若干次，机器人能返回原点，就叫做无法离开。首先创建一个长度为4的dirs二维数组，分别表示上，右，下，左四个方向坐标的增量，然后开始遍历input字符串。如果遇到R，往右走，i = i + 1；遇到L，往左走，i = i + 3。但是对于上和下两个方向，则单纯地改变X和Y的增量。遍历结束的时候判断，如果机器人能直接回到原点（0，0）或者dir > 0则说明可以回到原点，否则就不能。dir表示机器人的方向，0，1，2，3分别表示朝向北，东，南，西四个方向。dir > 0表示是朝向除了北方的其他三个方向。

判断机器人能否回到原点是一个很直接的方法，但是判断i是否大于0是什么意思呢？因为 i 记录的是左右方向上的增量。当dir > 0的时候，则说明这一串操作的最后，机器人的横坐标一定不是0。只要横坐标不是0，就说明机器人有可能在原点的左边/西边或者右边/东边而且一定不面向北方（否则怎么会面向西边或东边呢对吧），把这一套指令再跑若干次，机器人就能绕圈了。但是对于南北两个方向的增量，如果不为0，则说明机器人在每一遍循环的时候纵坐标是不能返回原点的，这样就只能 return false 了。

时间O(n)

空间O(n) - 二维数组表示方向

Java实现

 1 class Solution {
 2     public boolean isRobotBounded(String instructions) {
 3         int dir = 0;
 4         int x = 0;
 5         int y = 0;
 6         // up, right, down, left
 7         int[][] dirs = new int[][] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
 8         for (int j = 0; j < instructions.length(); j++) {
 9             char c = instructions.charAt(j);
10             if (c == 'R') {
11                 dir = (dir + 1) % 4;
12             } else if (c == 'L') {
13                 dir = (dir + 3) % 4;
14             } else {
15                 x += dirs[dir][0];
16                 y += dirs[dir][1];
17             }
18         }
19         return x == 0 && y == 0 || dir > 0;
20     }
21 }

LeetCode 题目总结