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'}
困于环中的机器人。题意是给一个用字符串表示的指令,指令包含G, L, R,分别表示直走一个单位,左转90度,右转90度。假设机器人一开始是在(0,0)处并且面朝北方,请判断机器人是否永远无法离开。
这道题没有什么算法,只要这背后的数学原理想清楚就行。什么叫做无法离开(false)?意思是给的指令如果跑了一次或者若干次,机器人能返回原点,就叫做无法离开。首先创建一个长度为4的dirs二维数组,分别表示上,右,下,左四个方向坐标的增量,然后开始遍历input字符串。如果遇到R,往右走,i = i + 1;遇到L,往左走,i = i + 3。但是对于上和下两个方向,则单纯地改变X和Y的增量。遍历结束的时候判断,如果机器人能回到原点(0,0)或者i > 0则说明可以回到原点,否则就不能。
判断机器人能否回到原点是一个很直接的方法,但是判断i是否大于0是什么意思呢?因为i记录的是左右方向上的增量。当i > 0的时候,则说明这一串操作的最后,机器人的横坐标一定不是0。只要横坐标不是0,就说明机器人有可能在原点的左边/西边或者右边/东边而且一定不面向北方(否则怎么会面向西边或东边呢对吧),把这一套指令再跑若干次,机器人就能绕圈了。但是对于南北两个方向的增量,如果不为0,则说明机器人在每一遍循环的时候纵坐标是不能返回原点的,这样就只能return false了。
时间O(n)
空间O(n) - 二维数组表示方向
Java实现
1 class Solution { 2 public boolean isRobotBounded(String instructions) { 3 int x = 0; 4 int y = 0; 5 int i = 0; 6 int[][] dirs = new int[][] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; 7 for (int j = 0; j < instructions.length(); j++) { 8 if (instructions.charAt(j) == 'R') { 9 i = (i + 1) % 4; 10 } else if (instructions.charAt(j) == 'L') { 11 i = (i + 3) % 4; 12 } else { 13 x += dirs[i][0]; 14 y += dirs[i][1]; 15 } 16 } 17 return x == 0 && y == 0 || i > 0; 18 } 19 }