python(牛客)试题解析1

python(牛客)试题解析1 - 简单

转载作者：我是一只小鸟更新时间：2022-11-20 21:32:09

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章python(牛客)试题解析1 - 简单由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

导航:

1、NC103 反转字符串。

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

3、NC151 最大公约数。

4、NC65 斐波那契数列。

5、字符按排序后查看第k个最小的字母。

6、数组内取出下标相同的元素求和从小到大排序，并取第k小的和值。

7、将探险队的坐标位置中挑选出相对总部的距离最远的坐标位置。

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

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

。

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

。

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

。

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

。

5、输入一个由n个大小写字母组成的字符，按Ascii码值从小到大排序，查找字符串中第k个最小Ascii码值的字母。

输入要求：第一行输入大小写组成的字符串第二行输入k, k必须大于0，k可以大于字符串长度输出要求：输出该字母所在字符串的位置索引，字符串第一个位置索引是为0, k如果大于字符串长度，则输出最大值的怎么所在字符串的位置索引，如果第k个最小Ascii码值的字母有重复，则输出该字母的最小位置索引。示例：输入： AbCdeFG 3 输出： 5 。

解析：字符串排序默认即使用Ascii码，所以直接使用sorted方法处理。

                          
                            l1 = input()
k = int(input())
if k > len(l1):
    k = len(l1)
l2 =sorted(l1)
letter = l2[k-1]
print(l1.index(letter))

。

6、数组内取出下标相同的元素求和从小到大排序，并取第k小的和值。

                        
                          给定两个整数数组，arr1、arr2，数组元素按升序排列；
                        
                        

                        
                          假设从arr1、arr2中分别取出一个元素，可构成一对元素；
                        
                        

                        
                          现在需要取出k对元素，并对取出的所有元素求和，计算和的最小值；
                        
                        

                        
                          注意：两对元素对应arr1、arr2的下标是相同的，视为同一对元素。
                        
                        

                        
                           描述： 
                        
                        

                        
                          输入两行数组arr1、arr2
                        
                        

                        
                          每行首个数字为数组大小size， 0 < size <= 100
                        
                        

                        
                          arr1，arr2中的每个元素e， 0< e <1000
                        
                        

                        
                          接下来一行，正整数k 0 < k <= arr1.size * arr2.size
                        
                        

                        
                          输出描述
                        
                        

                        
                          满足要求的最小值
                        
                        

                        
                           示例： 
                        
                        

                        
                          输入
                        
                        

                        
                          3 1 1 2
                        
                        

                        
                          3 1 2 3
                        
                        

                        
                          2
                        
                        

                        
                          输出
                        
                        

                        
                          4
                        
                        

                        
                           解析： 
                          推导式进行求和后从小到大排序，并取得第k小的和值

                          
                            a = list(map(
                             int 
                            ,input().split()))[
                             1 
                             :] b 
                            = list(map(
                             int 
                            ,input().split()))[
                             1 
                             :] k 
                            = 
                             int 
                             (input()) sum_ 
                            = [x+y 
                             for 
                             x 
                             in 
                             a 
                             for 
                             y 
                             in 
                             b] sum2 
                            =
                             sorted(sum_) print(sum(sum2[:k]))

。

7、将探险队的坐标位置中挑选出相对总部的距离最远的坐标位置。

描述：给出一个仅包含字母的字符串，不包含空格，统计字符串中各个字母（区分大小写）出现的次数，并按照字母出现次数从大到小的顺序输出各个字母及其出现次数。如果次数相同，按照自然顺序进行排序，且小写字母在大写字母之前。输入描述: 输入一行，为一个仅包含字母的字符串。输出描述: 按照字母出现次数从大到小的顺序输出各个字母和字母次数，用英文分号分隔，注意末尾的分号；字母和次数间用英文冒号分隔。示例1 输入 xyxyXX 输出 x:2;y:2;X:2; 说明每个字符出现的个数都是2，故x排在y之前，而小写字母x在X之前示例2 输入 abababb 输出 b:4;a:3,

描述：通过字典记录字符出现的次数，并进行排序输出。

                          
                            s =
                             input() d 
                            =
                             {} a 
                            =
                             [] 
                             for 
                             i 
                             in 
                             s: 
                             if 
                             i 
                             in 
                             d.keys(): d[i] 
                            += 
                             1 
                             else 
                             : d[i] 
                            = 
                             1 
                             l 
                            = sorted(d.items(),key=lambda x:x[
                             1 
                            ],reverse=
                             True) 
                             for 
                             i 
                             in 
                             l: a.append(f 
                             " 
                             {i[0]}:{i[1]} 
                             " 
                             ) print( 
                             " 
                             ; 
                             " 
                            .join(a)+
                             " 
                             ; 
                             " 
                            )