题目描述
在无限的平面上,机器人最初位于 (0, 0) 处,面朝北方。机器人可以接受下列三条指令之一:
“G”:直走 1 个单位
“L”:左转 90 度
“R”:右转 90 度
机器人按顺序执行指令 instructions,并一直重复它们。
只有在平面中存在环使得机器人永远无法离开时,返回 true。否则,返回 false。
样例
输入:"GGLLGG"
输出:true
解释:
机器人从 (0,0) 移动到 (0,2),转 180 度,然后回到 (0,0)。
算法1
(模拟) $O(N)$
Starting at the origin and face north (0,1),
after one sequence of instructions,
执行一次后的两种情况
- if chopper return to the origin, he is obvious in an circle.
- if chopper finishes with face not towards north, it will get back to the initial status in another one or three sequences.
Explanation
(x,y) is the location of chopper.
d[i] is the direction he is facing. 注意这里指的是他朝的方向而不是坐标
i = (i + 1) % 4 will turn right
i = (i + 3) % 4 will turn left
Check the final status after instructions.
Python 代码
class Solution:
def isRobotBounded(self, instructions: str) -> bool:
x, y, dx, dy = 0, 0, 0, 1
for i in instructions:
if i == 'R': dx, dy = dy, -dx
if i == 'L': dx, dy = -dy, dx
if i == 'G': x, y = x + dx, y + dy
return (x, y) == (0, 0) or (dx, dy) != (0,1)
算法2
C++ 代码
bool isRobotBounded(string instructions) {
int x = 0, y = 0, i = 0;
vector<vector<int>> d = {{0, 1}, {1, 0}, {0, -1}, { -1, 0}};
for (char & ins : instructions)
if (ins == 'R')
i = (i + 1) % 4;
else if (ins == 'L')
i = (i + 3) % 4;
else
x += d[i][0], y += d[i][1];
return x == 0 && y == 0 || i > 0;
}
I found that solution very popular and helpful: https://www.youtube.com/watch?v=wUmJVRKXZCQ&ab_channel=EricProgramming
Well didn’t expect an English audience. to be honest, this solution is from leetcode comments section. (In 2020, I still not quite understood how algorithms work.)
anyway, Thx for the suggestion. <3. (if not robot)