LeetCode 1041 Robot Bounded In Circle

LeetCode

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.

Example 1:

Input: instructions = “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: instructions = “GG”
Output: false
Explanation: The robot moves north indefinitely.

Example 3:

Input: instructions = “GL”
Output: true
Explanation: The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> …

Constraints: 1 <= instructions.length <= 100
* instructions[i] is 'G', 'L' or, 'R'.

题目大意：

循环按模式走是否回到原点

解题思路：

数学题，很难证明。定理是，只要按照给定模式走完，若回到原点或最后方向不是向北，都能回到原点

解题步骤：

N/A

注意事项：

Python代码：

def isRobotBounded(self, instructions: str) -> bool:
	DIRECTION_CONVERT_LEFT = {
		(0, 1): (-1, 0),
		(-1, 0): (0, -1),
		(0, -1): (1, 0),
		(1, 0): (0, 1),
	}
	DIRECTION_CONVERT_RIGHT = {
		(0, 1): (1, 0),
		(1, 0): (0, -1),
		(0, -1): (-1, 0),
		(-1, 0): (0, 1),
	}
	path, direction, position = instructions, (0, 1), (0, 0)
	for char in path:
		if char == 'L':
			direction = DIRECTION_CONVERT_LEFT[direction]
		elif char == 'R':
			direction = DIRECTION_CONVERT_RIGHT[direction]
		else:
			position = (position[0] + direction[0], position[1] + direction[1])
	return True if position == (0, 0) or direction != (0, 1) else False

算法分析：

时间复杂度为O(n)，空间复杂度O(1)