Daily classic

Thoughts in the Still Night — Li Bai (Tang)

In front of the bed there was moonlight, and I thought it was frost on the ground.

Looking up the bright moon, lower the head to think of home.

describe

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.
Copy the code

Example 2:

Input: instructions = "GG"
Output: false
Explanation: The robot moves north indefinitely.
Copy the code

Example 3:

Input: instructions = "GL"
Output: true
Explanation: The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...
Copy the code

Note:

1 <= instructions.length <= 100
instructions[i] is 'G', 'L' or, 'R'.
Copy the code

parsing

On the plane there is a robot initially standing at (0, 0) and facing north. A robot can receive one of three commands:

  • “G” : 1 unit straight;
  • “L” : turn left 90 degrees;
  • R: Turn 90 degrees to the right.

The robot executes the instructions sequentially and repeats them forever. Return True if and only if there is a cyclic path in the plane so that the robot can always return to the origin and still face north after performing the instructions for n times, otherwise return False. We can find by finding the rule that if we want to return True, we may return to the origin and face north after executing instructions for at most 4 times, such as example 3. However, it may return to the origin and face north after executing the instructions for at most 2 times, such as example 1. Therefore, we went through the instructions with 4 times the length and counted the number of instructions. The position cur changed when G was encountered, and the direction D changed when L or R was encountered. If count%len(Instructions)==0 and D %4==0 and cur==[0,0], return True; otherwise return False.

answer

class Solution(object): def isRobotBounded(self, instructions): """ :type instructions: str :rtype: Bool "" dirs = [(0, 1), (-1, 0), (0, -1), (1, 0)] cur = [0,0] d = 0 count = 0 for instructions*4: count += 1 if c == 'G': cur[0] += dirs[d%4][0] cur[1] += dirs[d%4][1] elif c == 'L': d += 1 else: D -= 1 if count%len(Instructions)==0 and D %4==0 and cur==[0,0]: return True return FalseCopy the code

The results

Given In Python online submissions for Robot Bounded In circles. Memory Usage: 13.5 MB, less than 28.85% of Python online submissions for Robot Bounded In Circle.Copy the code

Original link: leetcode.com/problems/ro…

Your support is my biggest motivation