上岸算法 l Amazon OA 1月面经题 Amazon OA 开发岗

卖大米 2021-2-1 1343


题目描述: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 degress 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: "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: "GG"

Output: false

Explanation: 

The robot moves north indefinitely.

题解:

这题可能出现闭环的条件比较难考虑,其实我们知道不管机器人如何转向,在若干遍指令序列的执行过程中,一定可以回到初始的方向,而唯一会被环困住的情形是:当且仅当在重复若干次指令序列并且机器人面向北时,机器人的坐标为原点坐标。

参考代码

最新回复 (0)
返回