导航:
六、数组内取出下标相同的元素求和从小到大排序,并取第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
描述:给定一个长度为 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
描述:如果有一个自然数 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
描述:要求输入一个正整数 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]))
标签:return,试题,python,self,牛客,int,str,字符串,输入 From: https://www.cnblogs.com/mrwhite2020/p/16905635.html