导航：
一、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]))
经验首页