1041. Robot Bounded In Circle 機器人在圈圈裏面?

 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.

 

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'.


Leetcode有很多機器人走路問題
起手式 要記住 左轉 右轉的寫法
機器人有四個state 位置 兩個，方向兩個，(x,y) 和 (dx,dy)

如果走回原點，則會固定。
這題最困難的事情是 如果最後走的方向是向北，那就會一路向北走 否則就一定會bound
證明不是很簡單
大家可以想一下:


class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        dirx, diry=0,1
        x,y=0,0
        
        for d in instructions:
            if d== "G":
                x,y=x+dirx, y+diry
            elif d=="L":
                dirx, diry=-1*diry, dirx
            else:
                dirx, diry=diry, -dirx
        return (x,y)==(0,0) or (dirx, diry)!=(0,1)

留言

張貼留言

這個網誌中的熱門文章

382. Linked List Random Node: 隨機選元素從list裡面

圖片
  Given a singly linked list, return a random node's value from the linked list. Each node must have the   same probability   of being chosen. Implement the  Solution  class: Solution(ListNode head)  Initializes the object with the integer array nums. int getRandom()  Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be choosen.   Example 1: Input ["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"] [[[1, 2, 3]], [], [], [], [], []] Output [null, 1, 3, 2, 2, 3] Explanation Solution solution = new Solution([1, 2, 3]); solution.getRandom(); // return 1 solution.getRandom(); // return 3 solution.getRandom(); // return 2 solution.getRandom(); // return 2 solution.getRandom(); // return 3 // getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.   Constraints: The number of nodes ...
閱讀完整內容

2134. Minimum Swaps to Group All 1's Together II 使得所有1連在一起

 2134. Minimum Swaps to Group All 1's Together II  使得所有1連在一起 A  swap  is defined as taking two  distinct  positions in an array and swapping the values in them. A  circular  array is defined as an array where we consider the  first  element and the  last  element to be  adjacent . Given a  binary   circular  array  nums , return  the minimum number of swaps required to group all  1 's present in the array together at  any location .   Example 1: Input: nums = [0,1,0,1,1,0,0] Output: 1 Explanation: Here are a few of the ways to group all the 1's together: [0, 0 , 1 ,1,1,0,0] using 1 swap. [0,1, 1 ,1, 0 ,0,0] using 1 swap. [1,1,0,0,0,0,1] using 2 swaps (using the circular property of the array). There is no way to group all 1's together with 0 swaps. Thus, the minimum number of swaps required is 1. Example 2: Input: nums = [0,1,1,1,0,0,1,1,0] Output: 2 Explanation: Here are a few...
閱讀完整內容