5

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

 1 year ago
source link: https://www.cnblogs.com/mrwhite2020/p/16905635.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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

一、NC103 反转字符串

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

三、NC151 最大公约数

四、NC65 斐波那契数列

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

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

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

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

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

五、输入一个由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))

六、数组内取出下标相同的元素求和从小到大排序，并取第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]))

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

描述：给出一个仅包含字母的字符串，不包含空格，统计字符串中各个字母（区分大小写）出现的次数，并按照字母出现次数从大到小的顺序输出各个字母及其出现次数。如果次数相同，按照自然顺序进行排序，且小写字母在大写字母之前。
输入描述:
输入一行，为一个仅包含字母的字符串。
输出描述:
按照字母出现次数从大到小的顺序输出各个字母和字母次数，用英文分号分隔，注意末尾的分号；字母和次数间用英文冒号分隔。
示例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)+";")

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK