python(牛客)试题解析1 - 入门级

乎语百科 115 0

导航:

一、NC103 反转字符串

二、NC141 判断是否为回文字符串

三、NC151 最大公约数

四、NC65 斐波那契数列

- - - - - - - - - - 分-割-线 - - - - - - - - - - -

一、NC103 反转字符串描述:写出一个程序,接受一个字符串,然后输出该字符串反转后的字符串。(字符串长度不超过1000)示例:输入:"abcd",输出返回值:"dcba"

解析1:转出字符串中的元素组成列表,并反转列表,再次输出为字符串

class Solution:
    def solve(self , str: str) -> str:
        # write code here
        list1 = []
        for i in str:
            list1.append(i)
        list1.reverse()
        s =""
        for i in list1:
            s = s+i
        return s

解析2:利用字符串的切片倒序输出

class Solution:
    def solve(self , str: str) -> str:
        str1 = str[::-1]
        return str1

二、NC141 判断是否为回文字符串

描述:给定一个长度为 n 的字符串,请编写一个函数判断该字符串是否回文。如果是回文请返回true,否则返回false。字符串回文指该字符串正序与其逆序逐字符一致。

示例:输入:"absba",返回值:true;输入:"ranko",返回值:false

解析1:反转字符串,并增加判断

class Solution:
    def judge(self , str: str) -> bool:
        str1 = str[::-1]
        if str1 == str:
            return True
        else:
            return False

解析2:使用三母表达式简化输出

class Solution:
    def judge(self , str: str) -> bool:
        return True if str[::-1]==str[:] else False

三、NC151 最大公约数

描述:如果有一个自然数 a 能被自然数 b 整除,则称 a 为 b 的倍数, b 为 a 的约数。几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个自然数的最大公约数。输入 a 和 b , 请返回 a 和 b 的最大公约数。

示例:输入3,6,返回3;输入8,12,返回4

解析1:通过因式分解取出每个数字的质因数,然后遍历找到两组质因数里面相同的质因数,最后通过相乘得到最大公约数

class Solution:
    def gcd(self , a: int, b: int) -> int:
        #a = 30
        #b = 40
        res1 = []
        res2 = []
        res3 = []
        # 因式分解
        while a > 1:
            for i in range(a - 1):
                k = i + 2
                if a % k == 0:
                    res1.append(k)
                    a = int(a / k)
                    break
        #print(res1)
        while b > 1:
            for i in range(2, b + 1):
                if b % i == 0:
                    res2.append(i)
                    b = int(b / i)
                    break
        #print(res2)
        for i in range(0, len(res1)):
            if res1[i] in res2:
                res3.append(res1[i])
                res2.remove(res1[i])
        res = 1
        for i in res3:
            res = res * i
        #print(res)
        return res

解析2:辗转相减法,运算起来很简洁:出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合,以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数

class Solution:
    def gcd(self , a: int, b: int) -> int:
        t=0
        m=0
        n=0
        # 辗转相减减法
        if a == b:
            t = a
        else:
            m = max(a, b)
            n = min(a, b)
            t = m - n
            while n != t:
                m, n = max(n, t), min(n, t)
                t = m - n
        return t

四、NC65 斐波那契数列

描述:要求输入一个正整数 n ,请你输出斐波那契数列的第 n 项,且第一个和第二个数字均为1

示例:输入4,根据斐波那契数列的定义可知,fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3,所以答案为3。

解析1:使用递归的方式,但是由于算法复杂度较高,当数据较大的,运行的时间较长

class Solution:
    def Fibonacci(self , n: int) -> int:
        if n == 1 or n == 2:
            return 1
        elif n == 3:
            return 2
        else:
            return self.Fibonacci(n-1) + self.Fibonacci(n-2)

解析2:使用for循环的方式,利用记录中间变量temp避免了重复计算

class Solution:
    def Fibonacci(self , n: int) -> int:
        a, b = 1, 1
        if n <= 1:
            return 1
        else:
            for i in range(2, n):
                tmp = a + b
                a = b
                b = tmp
            return b

标签:

留言评论

  • 这篇文章还没有收到评论,赶紧来抢沙发吧~