| comments | difficulty | edit_url | rating | source | tags | |||
|---|---|---|---|---|---|---|---|---|
true |
中等 |
1521 |
第 136 场周赛 Q1 |
|
在无限的平面上，机器人最初位于 (0, 0) 处，面朝北方。注意:
- 北方向 是y轴的正方向。
- 南方向 是y轴的负方向。
- 东方向 是x轴的正方向。
- 西方向 是x轴的负方向。
机器人可以接受下列三条指令之一：
"G"：直走 1 个单位"L"：左转 90 度"R"：右转 90 度
机器人按顺序执行指令 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。
提示：
1 <= instructions.length <= 100instructions[i]仅包含'G', 'L', 'R'
我们可以模拟机器人的行走过程，用一个变量
遍历指令字符串 instructions，如果当前指令为 'L'，那么机器人转向西方，即 'R'，那么机器人转向东方，即
如果给定的指令字符串 instructions 执行一遍后，使得机器人最终回到原点，即
如果给定的指令字符串 instructions 执行一遍后，机器人没回到原点，不妨假设此时机器人位于
- 若
$k=0$ ，即机器人面向北方，那么执行第二遍指令后，坐标变化量是$(x, y)$ ；继续执行第三遍指令后，坐标变化量还是$(x, y)$ ...累加这些变化量，机器人最终会到$(n \times x, n \times y)$ ，其中$n$ 是一个正整数。由于机器人最终没有回到原点，即$x \neq 0$ 或$y \neq 0$ ，所以$n \times x \neq 0$ 或$n \times y \neq 0$ ，因此机器人不会进入循环； - 若
$k=1$ ，即机器人面向西方，那么机器人执行第二遍指令后，坐标变化量是$(-y, x)$ ；继续执行第三遍执行后，坐标变化量是$(-x, -y)$ ；继续执行第四遍指令后，坐标变化量是$(y, -x)$ 。累加这些坐标变化量，我们可以发现，机器人最终会回到原点$(0, 0)$ ； - 若
$k=2$ ，即机器人面向南方，那么执行第二遍指令后，坐标变化量是$(-x, -y)$ ，累加这两次坐标变化量，我们可以发现，机器人最终会回到原点$(0, 0)$ ； - 若
$k=3$ ，即机器人面向东方，那么执行第二遍指令后，坐标变化量是$(y, -x)$ ；继续执行第三遍指令后，坐标变化量是$(-x, -y)$ ；继续执行第四遍指令后，坐标变化量是$(-y, x)$ 。累加这些坐标变化量，我们可以发现，机器人最终会回到原点$(0, 0)$ 。
综上所述，如果给定的指令字符串 instructions 执行一遍后，机器人回到了原点，或者机器人的方向与初始方向不同，那么机器人一定会进入循环。
时间复杂度 instructions 的长度。
class Solution:
def isRobotBounded(self, instructions: str) -> bool:
k = 0
dist = [0] * 4
for c in instructions:
if c == 'L':
k = (k + 1) % 4
elif c == 'R':
k = (k + 3) % 4
else:
dist[k] += 1
return (dist[0] == dist[2] and dist[1] == dist[3]) or k != 0class Solution {
public boolean isRobotBounded(String instructions) {
int k = 0;
int[] dist = new int[4];
for (int i = 0; i < instructions.length(); ++i) {
char c = instructions.charAt(i);
if (c == 'L') {
k = (k + 1) % 4;
} else if (c == 'R') {
k = (k + 3) % 4;
} else {
++dist[k];
}
}
return (dist[0] == dist[2] && dist[1] == dist[3]) || (k != 0);
}
}class Solution {
public:
bool isRobotBounded(string instructions) {
int dist[4]{};
int k = 0;
for (char& c : instructions) {
if (c == 'L') {
k = (k + 1) % 4;
} else if (c == 'R') {
k = (k + 3) % 4;
} else {
++dist[k];
}
}
return (dist[0] == dist[2] && dist[1] == dist[3]) || k;
}
};func isRobotBounded(instructions string) bool {
dist := [4]int{}
k := 0
for _, c := range instructions {
if c == 'L' {
k = (k + 1) % 4
} else if c == 'R' {
k = (k + 3) % 4
} else {
dist[k]++
}
}
return (dist[0] == dist[2] && dist[1] == dist[3]) || k != 0
}function isRobotBounded(instructions: string): boolean {
const dist: number[] = new Array(4).fill(0);
let k = 0;
for (const c of instructions) {
if (c === 'L') {
k = (k + 1) % 4;
} else if (c === 'R') {
k = (k + 3) % 4;
} else {
++dist[k];
}
}
return (dist[0] === dist[2] && dist[1] === dist[3]) || k !== 0;
}