2022/01/09 - 1041. Robot Bounded In Circle
1041. Robot Bounded In Circle - Medium
Description
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 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.
Solution
这道题不难看出规律，机器人会一直重复这些指令，如果一组指令结束后，机器人是朝着北面的，那么机器人将会一路向北。嘿嘿...
如果一组指令结束后，机器人面向的不是北面，那么可以肯定，在两次或者四次重复后，一定会回到原始坐标，则一定会出现循环。
所以我们可以定义一个代表方向的变量数组（Python和Go中可以直接替换dx和dy），然后在向左或者向右的指令出现时，改变机器人下一步会走的方向，最后判断一组指令过后，机器人是否回到原点或者机器人是否朝向北方来返回true或者false。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution {
public boolean isRobotBounded(String instructions) {
int x = 0, y = 0, i = 0;
int[][] direction = new int[][] {{0,1},{1,0},{0,-1},{-1,0}};
char[] chArr = instructions.toCharArray();
for (char c: chArr) {
if (c == 'L') {
i = (i + 3) % 4;
} else if (c == 'R') {
i = (i + 1) % 4;
} else {
x += direction[i][0];
y += direction[i][1];
}
}
return x == 0 && y == 0 || i > 0;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution:
# {-1, 0} -> R -> {0, 1} dx, dy = dy, -dx
# {0, 1} -> R -> {1, 0} dx, dy = dy, -dx
# {-1, 0} -> L -> {0, -1} dx, dy = -dy, dx
# {0, -1} -> L -> {1, 0} dx, dy = -dy, dx
def isRobotBounded(self, instructions: str) -> bool:
x, y, dx, dy = 0, 0, 0, 1
for c in instructions:
if c == 'R': dx, dy = dy, -dx
elif c == 'L': dx, dy = -dy, dx
else:
x, y = x + dx, y + dy
return x == 0 and y == 0 or dy != 1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | func isRobotBounded(instructions string) bool {
x, y := 0, 0
dx, dy := 0, 1
for _, r := range instructions {
if r == 'R' {
dx, dy = dy, -dx
} else if r == 'L' {
dx, dy = -dy, dx
} else {
x, y = x + dx, y + dy
}
}
return x == 0 && y == 0 || dy != 1
}
|