【面试高频题】难度 1/5，小常规的脑筋急转弯类模拟题
【面试高频题】难度 1/5，小常规的脑筋急转弯类模拟题
题目描述
这是 LeetCode 上的「1041. 困于环中的机器人」，难度为「中等」。
Tag : 「模拟」、「脑筋急转弯」
在无限的平面上，机器人最初位于
处，面朝北方。注意:
- 北方向 是
y轴的正方向。 - 南方向 是
y轴的负方向。 - 东方向 是
x轴的正方向。 - 西方向 是
x轴的负方向。
机器人可以接受下列三条指令之一：
"G"：直走
个单位
"L"：左转
度
"R"：右转
度
机器人按顺序执行指令 instructions，并一直重复它们。
只有在平面中存在环使得机器人永远无法离开时，返回 true。否则，返回 false。
示例 1：
输入：instructions = "GGLLGG"
输出：true
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“G”:移动一步。位置:(0,2).方向:北。
“L”:逆时针旋转90度。位置:(0,2).方向:西。
“L”:逆时针旋转90度。位置:(0,2)方向:南。
“G”:移动一步。位置:(0,1)方向:南。
“G”:移动一步。位置:(0,0)方向:南。
重复指令，机器人进入循环:(0,0)——>(0,1)——>(0,2)——>(0,1)——>(0,0)。
在此基础上，我们返回true。
示例 2：
输入：instructions = "GG"
输出：false
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“G”:移动一步。位置:(0,2).方向:北。
重复这些指示，继续朝北前进，不会进入循环。
在此基础上，返回false。
示例 3：
输入：instructions = "GL"
输出：true
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“L”:逆时针旋转90度。位置:(0,1).方向:西。
“G”:移动一步。位置:(- 1,1)方向:西。
“L”:逆时针旋转90度。位置:(- 1,1)方向:南。
“G”:移动一步。位置:(- 1,0)方向:南。
“L”:逆时针旋转90度。位置:(- 1,0)方向:东方。
“G”:移动一步。位置:(0,0)方向:东方。
“L”:逆时针旋转90度。位置:(0,0)方向:北。
重复指令，机器人进入循环:(0,0)——>(0,1)——>(- 1,1)——>(- 1,0)——>(0,0)。
在此基础上，我们返回true。
提示：
instructions[i]仅包含'G','L','R'
模拟
为了方便，将 instructions 记为 s，“北西南东”四个方向分别记为“上左下右”四个逆时针方向。
起始位置在
，方向为上，我们可以将「位置 + 方向」统称为「状态」。
所谓“循环”，则是指执行若干次的 s 后，会回到相同的状态。
我们可以按 s 执行一遍，假设执行完所在位置为
，所在位置为
，先根据 「位置」 分情况讨论：
为
，此时无论执行一遍后的方向为何值，必然能在若干次执行后回到起始状态。
即只需要确保 (n * k) % 4 为
即可，机器人会陷入循环；
不为
，再根据 「方向」 进一步分情况讨论：
- 方向为上：每执行一遍
s指令，位置变化为
，方向不变。 那么执行
遍后位置为
，其中
为正整数，并且
和
不同时为
，因此随着执行次数增加，位置会离
越来越远，机器人不会陷入循环；
- 方向为下：每执行一遍
s指令，位置变化为
，方向翻转。 如果再执行一遍，由于再次执行时的方向与起始方向相反，因此位置变化为
，同时方向再次翻转（与起始方向一致）。即执行偶数次后，会回到起始状态，机器人会陷入循环；
- 方向为左：每执行一遍
s指令，位置变化为
，方向为逆时针
度。 如果执行第二次，位置变化为
，方向再逆时针
度（与起始方向相反）；执行第三次，位置变化为
，方向再逆时针
度（与起始方向呈顺时针
度），该次变化会和首次执行相互抵消；执行第四次，位置变化为
，方向再逆时针
度（与起始方向相同），该次变化与第二次执行相互抵消。总的位置变化为
，同时方向与起始方向一致，机器人会陷入循环；
- 方向为右：与「方向为左」同理，机器人会陷入循环。
综上，只要执行一遍 s 后所在位置为
或方向不为上，均可确保循环发生。
Java 代码：
class Solution {
public boolean isRobotBounded(String s) {
int x = 0, y = 0, d = 0;
int[][] dirs = new int[][]{{0,1}, {-1,0}, {0,-1}, {1,0}};
for (char c : s.toCharArray()) {
if (c == 'G') {
x += dirs[d][0]; y += dirs[d][1];
} else if (c == 'L') {
d = (d + 1) % 4;
} else {
d = ((d - 1) % 4 + 4) % 4;
}
}
return (x == 0 && y == 0) || d != 0;
}
}
C++ 代码：
class Solution {
public:
bool isRobotBounded(string s) {
int x = 0, y = 0, d = 0;
int dirs[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
for (char c : s) {
if (c == 'G') {
x += dirs[d][0]; y += dirs[d][1];
} else if (c == 'L') {
d = (d + 1) % 4;
} else {
d = ((d - 1) % 4 + 4) % 4;
}
}
return (x == 0 && y == 0) || d != 0;
}
};
Python 代码：
class Solution:
def isRobotBounded(self, s: str) -> bool:
x, y, d = 0, 0, 0
dirs = [[0, 1], [-1, 0], [0, -1], [1, 0]]
for c in s:
if c == 'G':
x += dirs[d][0]
y += dirs[d][1]
elif c == 'L':
d = (d + 1) % 4
else:
d = ((d - 1) % 4 + 4) % 4
return (x == 0 and y == 0) or d != 0
Go 代码：
func isRobotBounded(s string) bool {
x, y, d := 0, 0, 0
dirs := [][]int{{0, 1}, {-1, 0}, {0, -1}, {1, 0}}
for _, c := range s {
if c == 'G' {
x += dirs[d][0]
y += dirs[d][1]
} else if c == 'L' {
d = (d + 1) % 4
} else {
d = ((d - 1) % 4 + 4) % 4
}
}
return (x == 0 && y == 0) || d != 0
}
TypeScript 代码：
function isRobotBounded(s: string): boolean {
let x = 0, y = 0, d = 0;
const dirs: number[][] = [[0, 1], [-1, 0], [0, -1], [1, 0]];
for (const c of s) {
if (c === 'G') {
x += dirs[d][0];
y += dirs[d][1];
} else if (c === 'L') {
d = (d + 1) % 4;
} else {
d = ((d - 1) % 4 + 4) % 4;
}
}
return (x === 0 && y === 0) || d !== 0;
};
- 时间复杂度：
- 空间复杂度：
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1041 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
腾讯云开发者
