No alive nodes found in your cluster LeetCode专题-模拟 | 码农网


栏目: 编程工具 · 发布时间: 2周前



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


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


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


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.



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:



Example 2:



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 '.'
                    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] != '.':
                    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'
                ND += '.'

        return ND

测试一下,算法应该是对的,但是用 python 实现会超时,用golang或者cpp可以通过所有测试用例。

Time Limit Exceeded

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网



Mastering JavaServer Faces

Mastering JavaServer Faces

Bill Dudney、Jonathan Lehr、Bill Willis、LeRoy Mattingly / Wiley / 2004-6-7 / USD 40.00

Harness the power of JavaServer Faces to create your own server-side user interfaces for the Web This innovative book arms you with the tools to utilize JavaServer Faces (JSF), a new standard that wi......一起来看看 《Mastering JavaServer Faces》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码


RGB HEX 互转工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具