1041. Robot Bounded In Circle

Easy

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.

``````class Solution:
def isRobotBounded(self, instructions: str) -> bool:
x = 0
y = 0
dir = 0 #direction - N W S E
#offset for each direction
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
for c in instructions:
if c == 'G': #go ahead by dir
x += dx[dir]
y += dy[dir]
elif c == 'L': #turn left
dir = (dir + 3)%4
elif c == 'R': #turn right
dir = (dir + 1)%4
return (x == 0 and y == 0) or dir != 0 #if go back to origin or not facing north

``````

``````Success
[Details]
Runtime: 32 ms, faster than 86.36% of Python3 online submissions for Robot Bounded In Circle.
Memory Usage: 13.2 MB, less than 100.00% of Python3 online submissions for Robot Bounded In Circle.
``````

838. Push Dominoes

Medium

There are `N` dominoes in a line, and we place each domino vertically upright.

In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

image

After each second, each domino that is falling to the left pushes the adjacent domino on the left.

Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

Given a string "S" representing the initial state. `S[i] = 'L'`, if the i-th domino has been pushed to the left; `S[i] = 'R'`, if the i-th domino has been pushed to the right; `S[i] = '.'`, if the `i`-th domino has not been pushed.

Return a string representing the final state.

Example 1:

Input: ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

Example 2:

Input: "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.

``````class Solution(object):
def pushDominoes(self, D):
"""
:type dominoes: str
:rtype: str
"""
max_int = 9999999
#record the distance from current dominoe to nearest push down one(left and right)
left_steps = [max_int for x in range(len(D))]
right_steps = [max_int for x in range(len(D))]

for i in range(len(D)):
if D[i] == 'L':
#if occur one push down domine
left_steps[i] = 0
#for all following domine that influenced
for j in range(i-1, -1, -1):
if D[j] != '.': #only influence '.'
break
left_steps[j] = left_steps[j+1]+1
elif D[i] == 'R':
right_steps[i] = 0
for j in range(i+1, len(D)):
if D[j] != '.':
break
right_steps[j] = right_steps[j-1]+1

#simulate the push work
ND = ''
for i in range(len(D)):
if left_steps[i] < right_steps[i]:
ND += 'L'
elif left_steps[i] > right_steps[i]:
ND += 'R'
else:
ND += '.'

return ND
``````

``````Time Limit Exceeded
[Details]
``````

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

1041. Robot Bounded In Circle

Easy

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.

``````class Solution:
def isRobotBounded(self, instructions: str) -> bool:
x = 0
y = 0
dir = 0 #direction - N W S E
#offset for each direction
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
for c in instructions:
if c == 'G': #go ahead by dir
x += dx[dir]
y += dy[dir]
elif c == 'L': #turn left
dir = (dir + 3)%4
elif c == 'R': #turn right
dir = (dir + 1)%4
return (x == 0 and y == 0) or dir != 0 #if go back to origin or not facing north

``````

``````Success
[Details]
Runtime: 32 ms, faster than 86.36% of Python3 online submissions for Robot Bounded In Circle.
Memory Usage: 13.2 MB, less than 100.00% of Python3 online submissions for Robot Bounded In Circle.
``````

838. Push Dominoes

Medium

There are `N` dominoes in a line, and we place each domino vertically upright.

In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

image

After each second, each domino that is falling to the left pushes the adjacent domino on the left.

Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

Given a string "S" representing the initial state. `S[i] = 'L'`, if the i-th domino has been pushed to the left; `S[i] = 'R'`, if the i-th domino has been pushed to the right; `S[i] = '.'`, if the `i`-th domino has not been pushed.

Return a string representing the final state.

Example 1:

Input: ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

Example 2:

Input: "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.

``````class Solution(object):
def pushDominoes(self, D):
"""
:type dominoes: str
:rtype: str
"""
max_int = 9999999
#record the distance from current dominoe to nearest push down one(left and right)
left_steps = [max_int for x in range(len(D))]
right_steps = [max_int for x in range(len(D))]

for i in range(len(D)):
if D[i] == 'L':
#if occur one push down domine
left_steps[i] = 0
#for all following domine that influenced
for j in range(i-1, -1, -1):
if D[j] != '.': #only influence '.'
break
left_steps[j] = left_steps[j+1]+1
elif D[i] == 'R':
right_steps[i] = 0
for j in range(i+1, len(D)):
if D[j] != '.':
break
right_steps[j] = right_steps[j-1]+1

#simulate the push work
ND = ''
for i in range(len(D)):
if left_steps[i] < right_steps[i]:
ND += 'L'
elif left_steps[i] > right_steps[i]:
ND += 'R'
else:
ND += '.'

return ND
``````

``````Time Limit Exceeded
[Details]
``````