[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. 1 <= instructions.length <= 100
  2. 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 }

 

LeetCode 题目总结

上一篇:data race Comparing the performance of atomic, spinlock and mutex Spin-Locks vs. Atomic Instruction


下一篇:armv8的VMSA/MMU/Cache介绍学习视频