LeetCode专题-模拟

栏目: 编程工具 · 发布时间: 3个月前

来源: studygolang.com

本文转载自:https://studygolang.com/articles/20672,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有。

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.

LeetCode专题-模拟

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

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

Time Limit Exceeded
[Details]

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

关注码农网公众号

关注我们,获取更多IT资讯^_^


为你推荐:

相关软件推荐:

查看所有标签

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

C专家编程

C专家编程

[美] Peter Vander Linde / 徐波 / 人民邮电出版社 / 2002-12 / 40.00元

《C专家编程》展示了最优秀的C程序员所使用的编码技巧,并专门开辟了一章对C++的基础知识进行了介绍。 书中对C的历史、语言特性、声明、数组、指针、链接、运行时、内存,以及如何进一步学习C++等问题作了细致的讲解和深入的分析。全书撷取几十几个实例进行讲解,对C程序员具有非常高的实用价值。 这本《C专家编程》可以帮助有一定经验的C程序员成为C编程方面的专家,对于具备相当的C语言基础的程序员......一起来看看 《C专家编程》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具