Last Updated on 2022-01-09 by Clay
題目
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 degrees 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: instructions = "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: instructions = "GG" Output: false Explanation: The robot moves north indefinitely.
Example 3:
Input: instructions = "GL" Output: true Explanation: The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...
Constraints:
1 <= instructions.length <= 100instructions[i]is'G','L'or,'R'.
一個機器人位於 (0, 0) 的位置並朝向北方，它可以接受三種指令：G、L、R。
G: 往前走一個單位的距離
L: 向左轉九十度
R: 向右轉九十度
而題目給定一組給機器人的指令，讓我們判斷機器人是否按照一個特定的迴圈在走，並不會偏移這個設定好的路徑。
解題思路
一開始我把解題的方法想得非常複雜，經過幾次試錯之後才想通：
- 一組指令走完後機器人只要在起點，不論面向哪個方向都仍在環圈之中
- 一組指令走完後機器人只要不在起點且面向北方，無論如何都不會形成迴圈
- 除此之外所有的指令，最終都會讓機器人在規律的迴圈中運行
只要按照上述原則去判斷機器人的方向與位置，最終就能很簡單地得到結論。
複雜度
| Time Complexity | O(n) |
| Space Complexity | O(1) |
C++ 範例程式碼
class Solution {
public:
bool isRobotBounded(string instructions) {
// Init
int _x = 0;
int _y = 1;
int pos_x = 0;
int pos_y = 0;
// The first loop
for (auto s: instructions) {
if (s == 'G') {
pos_x += _x;
pos_y += _y;
}
else if (s == 'L') {
if (_x == 0 && _y == 1) {
_x = -1;
_y = 0;
}
else if (_x == -1 && _y == 0) {
_x = 0;
_y = -1;
}
else if (_x == 0 && _y == -1) {
_x = 1;
_y = 0;
}
else if (_x == 1 && _y == 0) {
_x = 0;
_y = 1;
}
}
else if (s == 'R') {
if (_x == 0 && _y == 1) {
_x = 1;
_y = 0;
}
else if (_x == 1 && _y == 0) {
_x = 0;
_y = -1;
}
else if (_x == 0 && _y == -1) {
_x = -1;
_y = 0;
}
else if (_x == -1 && _y == 0) {
_x = 0;
_y = 1;
}
}
}
// Results
if (pos_x == 0 && pos_y == 0) return true;
else if (_x == 0 && _y == 1) return false;
return true;
}
};Python 範例程式碼
class Solution:
def isRobotBounded(self, instructions: str) -> bool:
# Init
_x = 0
_y = 1
pos_x = 0
pos_y = 0
# The first loop
for s in instructions:
if s == 'G':
pos_x += _x
pos_y += _y
elif s == 'L':
if _x == 0 and _y == 1:
_x = -1
_y = 0
elif _x == -1 and _y == 0:
_x = 0
_y = -1
elif _x == 0 and _y == -1:
_x = 1
_y = 0
elif _x == 1 and _y == 0:
_x = 0
_y = 1
elif s == 'R':
if _x == 0 and _y == 1:
_x = 1
_y = 0
elif _x == 1 and _y == 0:
_x = 0
_y = -1
elif _x == 0 and _y == -1:
_x = -1
_y = 0
elif _x == -1 and _y == 0:
_x = 0
_y = 1
# Results
if pos_x == 0 and pos_y == 0: return True
elif _x == 0 and _y == 1: return False
return True