python(牛客)試題解析1 – 簡單
- 2022 年 11 月 19 日
- 筆記
- Python, python常見面試題
導航：
六、數組內取出下標相同的元素求和從小到大排序，並取第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]))
