Python刷題筆記

1、輸出格式化

第一種格式化的輸出：

name = "jack"
age = 17
salary = 20031.8752
print("你的名字是：%s,今年 %d 歲,工資 %7.2f" % (name,age,salary) )
---------------------------------------
你的名字是：jack,今年 17 歲,工資 20031.88
---------------------------------------

第二種格式化的輸出：

name = "jack"
age = 17
salary = 20031.8752
print(f"你的名字是：{name},今年 {age} 歲,工資:{salary}")
---------------------------------------
你的名字是：jack,今年 17 歲,工資:20031.8752
---------------------------------------

2、數值類型轉換

基本格式	解釋
int(x)	將x轉換為一個整數
float(x)	將x轉換為一個浮點數
str(x)	將x轉換為一個字符串
chr(x)	將x轉換為一個字符

3、字符串類題型

題型一：大小寫轉換

1、使用str.lower()方法，把所有大寫字母轉換成小寫字母。

n=input()
print(n.lower())
--------------------
輸入：HeLLo WORLD
輸出：hello world
--------------------

2、使用str.upper()方法，把所有小寫字母轉換成大寫字母

n=input()
print(n.upper())
--------------------
輸入：hello world
輸出：HELLO WORLD
--------------------

3、使用str.capitalize()方法，僅首字母轉化為大寫字母，其余小寫字母

n=input()
print(n.capitalize())
--------------------
輸入：hello world
輸出：Hello world
--------------------

4、使用str.title()方法，每個單詞的首字母大寫

n=input()
print(n.title())
--------------------
輸入：hello world
輸出：Hello World
--------------------

題型二：字母（a-z）之間的轉換

講解：ord()表示該字母的ASCII數值【配合ASCII表進行求解】

n = int(input())
a=input()
out = ''
for i in range(len(a)):m = ord(a[i]) + nwhile m > ord('z'):m = m - ord('z') + ord('a') - 1out += chr(m)
print(out)
-----------------
輸入：
1
qwez
輸出：rxfa
-----------------

題型三：反轉問題（數字，符號，字母…）

2.1: 全部進行反轉操作

a = "Love You"
b = a[::-1]
print(b)
--------------
uoY evoL
--------------

單詞倒序問題1

給定一堆用空格隔開的英文單詞，輸出這些英文單詞的倒序（單詞內部保持原序）。

比如，輸入：Hao Hao Xue Xi，輸出：Xi Xue Hao Hao

words = input().split()	# ['Hao', 'Hao', 'Xue', 'Xi']
words.reverse()
# 基本格式：'分隔符'.join(列表【list】)
result = ' '.join(words)print(result)

2.2: 局部進行反轉操作

單詞倒序問題2

給定一堆用空格隔開的英文單詞，將每個單詞內部逆序后輸出（單詞順序不變）。

比如，輸入：Hao Hao Xue Xi，輸出：oaH oaH euX iX

a = input().split() # ['Hao', 'Hao', 'Xue', 'Xi']
re_words = [word[::-1] for word in a]
result = ' '.join(re_words)print(result)

【補充】回文數題型

方式一：回文數的基本思路：
def f(n):temp = nans = 0while temp>0:ans = ans*10 + temp%10temp = int(temp/10)return ans
方式二：字符串特性
n=input()
n2=n[::-1]

4、判斷某字符是否包含于字符串內（STL+KMP）

n = input().strip()
if "No Information" in n:print("???")
elif "is greater than" in n:parts = n.split()a = int(parts[0])b = int(parts[-1])if a>b:print("Yes")else:print("No")
------------------------------------
輸入：10 is greater than 5
輸出：Yes
------------------------------------

5、公共前綴

給定n個字符串，求它們的公共前綴。

num = int(input())
#列表：其中for _ in range(num)表示循環num次，其中下劃線 _ 通常用來忽略不需要返回值的循環變量
strings = [input().strip() for _ in range(num)]  # 常規寫法 common = []
min_length = min(len(s) for s in strings)for i in range(min_length):temp = strings[0][i]if all(s[i]==temp for s in strings):common.append(temp)else:breakprint(''.join(common))
-------------------------------
輸入：3actrpgactfpsactarpg
輸出：act
-------------------------------

6、持續輸入（遇到0停）

輸入兩個正整數a和b，求a+b的值。當a和b同時為0時停止執行。

while 1:# 返回的是數字a,b=list(map(int,input().split()))if a==0 and b==0:breakprint(a+b)
-------------------------
輸入：2 31 87 90 0
輸出：5916
-------------------------

7、排序題型【sorted題型】

給定n個考生的姓名、語文分數、數學分數，按下面三種排序要求之一進行排序：

按語文分數從高到低排序，分數相同時按姓名字典序從小到大排序
按數學分數從高到低排序，分數相同時按姓名字典序從小到大排序
按總分（語文+數學）從高到低排序，分數相同時按姓名字典序從小到大排序

輸入描述：

第一行兩個整數n（1≤n≤1000）、k（1≤k≤3），分別表示考生個數、排序方式（k=1時表示按第一種方式排序，k=2時表示按第二種方式排序，k=3時表示按第三種方式排序）；

接下來n行，每行為一個考生的姓名name、語文分數score1、數學分數score2（name為僅由大小寫字母組成的不超過15個字符的字符串，0≤score≤100），用空格隔開。數據確保不會出現相同的姓名。

輸出描述：

輸出排序后的結果，共n行，每行為一個考生的姓名、語文分數、數學分數、總分，用空格隔開。

m,n = list(map(int,input().split()))
# tuple相當于struct結構體
students = [tuple(input().split()) for _ in range(m)]# 新添tuple元素：總分
for i in range(len(students)):n1,s1,s2 = students[i]new = int(s1)+int(s2)students[i] = (n1,s1,s2,new)if n == 1:sorted_students = sorted(students,key=lambda x:(-int(x[1]),x[0]))
elif n == 2:sorted_students = sorted(students,key=lambda x:(-int(x[2]),x[0]))
elif n == 3:sorted_students = sorted(students,key=lambda x:(-int(x[3]),x[0]))for name,score1,score2,total in sorted_students:print(name,score1,score2,total)
---------------------------------------------------------
輸入：5 1SunWuKong 92 88ShaWuJing 90 92TangSanZang 100 100BaiLongMa 90 88ZhuBaJie 87 91
輸出：TangSanZang 100 100 200SunWuKong 92 88 180BaiLongMa 90 88 178ShaWuJing 90 92 182ZhuBaJie 87 91 178
---------------------------------------------------------

sorted講解：

順序：sorted(序列)

倒序：sorted(序列,reverse=True)

對其中某個部分進行排序：sorted(序列,key=lambda x:(x[3],x[0],…))

8、Python中實現數據結構模型

1：String類型【STL】

字符串【拼接】

a,b=input().split()
print(a+b)
--------------------------
輸入：good bad
輸出：goodbad
--------------------------

字符串【比較】

a,b=input().split()if a==b:print(0)
elif a>b:print(1)
else:print(-1)
----------------------
輸入：good bad
輸出：1
----------------------

字符串【長度】和【清空】

# 讀取輸入字符串
s = input()# 輸出【字符串的長度】
print(len(s), end=" ")# 【清空】字符串
s = ""# 再次輸出字符串的長度
print(len(s))

字符串的【插入】與【刪除指定位置字符】

# 讀取輸入字符串
s = input().strip()
# 讀取插入操作的參數
k1, c = input().strip().split()
k1 = int(k1)
# 讀取刪除操作的參數
k2 = int(input().strip())# 【插入元素】
s = s[:k1] + c + s[k1:]
print(s)# 【刪除指定位置的元素】
s = s[:k2] + s[k2+1:]
print(s)
------------------------------------
輸入：good2 u3
輸出：gouodgoud
------------------------------------

判斷是否為【子串】

使用s1.find(s2)函數判斷s2是否是s1的子串，如果是的話，輸出s2第一次在s1中出現的起始位置；如果不是，那么輸出-1。

# 讀取輸入的兩個字符串
s1, s2 = input().split()# 使用find方法查找s2在s1中的位置
pos = s1.find(s2)# 輸出查找結果
print(pos)

字符串【替換】

# 輸入
s1=input()
a,lens=list(map(int,input().split()))
a=int(a)
lens=int(lens)
s2=input()# 將s1中下標從a開始，長度為lens的子串替換為s2
new=s1.replace(s1[a:a+lens],s2)
print(new)

【思想】：字符串刪除特定元素

a="abbcdd"
temp=[]
for i in range(len(a)):if a[i]=='b':continuetemp.append(a[i])
new_a=''.join(temp)
print(new_a)

【延伸題】：ds的字符串

ds 給了 xf 一個字符串。ds 對字符串可以進行若干次（可能是 0 次）如下操作：選擇子串 “ds” 或者子串 “xf”，將其從字符串中刪去。求最后剩下字符串的最短長度。子串是指原字符串中下標連續的一段字符串。

n=int(input())
strings=input()temp=stringswhile ('xf' in temp) or ('ds' in temp):lens=len(temp)li=[]for i in range(lens):li.append(temp[i])if len(li)>=2:if ''.join(li[-2:])=='ds':li.pop()li.pop()if ''.join(li[-2:])=='xf':li.pop()li.pop()temp=''.join(li)print(len(temp))
-------------------------------------
輸入：10 # 長度xdsxffxacf # 字符串
輸出：4
-------------------------------------

2：棧類型【先進后出】

stack=[]# 添加新元素至棧中
stack.append(1)
stack.append(2)
stack.append(3)
print(f"添加元素：%s" % stack)
# 刪除棧頂【先進后出】?
stack.pop()
print(f"刪除棧頂元素：%s" % stack)
# 查詢棧頂
num=stack[len(stack)-1]
print(f"查詢棧頂元素：%s" % num)
# 判斷棧是否為空
print(stack == [])
# 判斷棧元素個數
print(f"判斷棧元素個數：%d" % len(stack))
------------------------------------
添加元素：[1, 2, 3]
刪除棧頂元素：[1, 2]
查詢棧頂元素：2
False
判斷棧元素個數：2
------------------------------------

3：雙端隊列

# 創建一個空的列表作為雙端隊列
deque_list = []# 在雙端隊列的右側添加元素
deque_list.append('a')
deque_list.append('b')
print(deque_list)  # 輸出: ['a', 'b']# 在雙端隊列的左側添加元素
deque_list.insert(0, 'c')
print(deque_list)  # 輸出: ['c', 'a', 'b']# 從雙端隊列的右側移除并返回元素
right_element = deque_list.pop()
print(right_element)  # 輸出: 'b'
print(deque_list)  # 輸出: ['c', 'a']# 從雙端隊列的左側移除并返回元素
left_element = deque_list.pop(0)
print(left_element)  # 輸出: 'c'
print(deque_list)  # 輸出: ['a']

4：隊列類型【先進先出】

queue=[]# 添加新元素至隊列中
queue.append(1)
queue.append(2)
queue.append(3)
print(f"添加元素：%s" % queue)
# 刪除隊列元素【先進先出】?
queue.pop(0)
print(f"刪除棧頂元素：%s" % queue)
# 查詢隊列首個元素
num=queue[0]
print(f"查詢棧頂元素：%s" % num)
# 判斷棧是否為空
print(queue == [])
# 判斷棧元素個數
print(f"判斷棧元素個數：%d" % len(queue))
------------------------------------
添加元素：[1, 2, 3]
刪除棧頂元素：[2, 3]
查詢棧頂元素：2
False
判斷棧元素個數：2
------------------------------------

5：Set集合

基本語法

# 定義
1、語法：變量名={元素1,元素2,元素3,...}
2、注意：內部無序，且去重【不支持重復元素】，允許被修改
3、案例：set1 = {1,2,3} # set集合定義set2 = set() # set空集合定義
4、【不支持下標索引訪問】

常用操作方法

my_set={"你好","china","beauty"}# 添加新元素add
my_set.add("三玖")
print(my_set)
------------------------------------
{'beauty', 'china', '你好', '三玖'}
------------------------------------# 移除元素remove
my_set.remove("你好")
print(my_set)
----------------------
{'beauty', 'china'}
----------------------# 隨機取出一個元素pop
element = my_set.pop()
print(f"集合被取出的元素：{element},去除元素后：{my_set}")
----------------------------------------------------
集合被取出的元素：china,去除元素后：{'你好', 'beauty'}
----------------------------------------------------# 清空set集合clear
my_set.clear()
print(my_set)
----------
set()
----------# 取兩個集合差集difference => 注意點：結果會得到一個新的集合，集合1和集合2不變【差集】
set1 = {1,2,3}
set2 = {1,5,6}
set3 = set1.difference(set2) # 取出set1和set2差集（set1有而set2沒有）
print(f"去除差集后的結果：{set3}")
-----------------------
去除差集后的結果：{2, 3}
-----------------------# 消除兩個集合差集difference_update => 注意點：集合1被修改，集合2不變【差集】
set1 = {1,2,3}
set2 = {1,5,6}
set1.difference_update(set2) # set1中，刪除和set2相同的元素
print(f"去除差集后,set1的結果：{set1}")
print(f"去除差集后,set2的結果：{set2}")
----------------------------
去除差集后,set1的結果：{2, 3}
去除差集后,set2的結果：{1, 5, 6}
----------------------------# 兩集合合并union【交集】
set1 = {1,2,3}
set2 = {1,5,6}
new_set = set1.union(set2)
print(new_set)
------------------
{1, 2, 3, 5, 6}
------------------# 統計集合元素數量len
set = {1,2,3}
cnt = len(set)
print(cnt)
-----------
3
-----------# 集合遍歷 => 只支持for循環

python經典題型

一：雙指針

1、序列合并【典型寫法】

給定兩個升序的正整數序列A和B，將它們合并成一個新的升序序列并輸出。

n,m=list(map(int,input().split())) # 兩行的長度
a=list(map(int,input().split()))
b=list(map(int,input().split()))# 合并兩個升序序列
i,j=0,0
merged = []while i<n and j<m:if a[i]<=b[j]:merged.append(a[i])i+=1else:merged.append(b[j])j+=1# 將剩余的元素加入到結果中去
while i<n:merged.append(a[i])i+=1
while j<m:merged.append(b[j])j+=1for i in range(len(merged)):if i<len(merged)-1:print(merged[i],end=' ')else:print(merged[i],end='')
------------------------------------------
輸入：4 31 5 6 82 6 9
輸出：1 2 5 6 6 8 9
------------------------------------------

2、2-SUM-雙指針【典型寫法】

給定一個嚴格遞增序列A和一個正整數k，在序列A中尋找不同的下標i、j，使得Ai+Aj=k。問有多少對(i,j)同時i<j滿足條件。

size,target=list(map(int,input().split()))
array=list(map(int,input().split()))# 存放結果數
result=0
# 定義指針
i=0
j=size-1# 雙指針遍歷求解
while i<j:if array[i]+array[j]==target:result+=1i+=1j-=1elif array[i]+array[j]<target:i+=1else:j-=1print(result)
--------------------------------
輸入：5 61 2 4 5 6
輸出：2
--------------------------------

解釋：1 + 5 = 6、2 + 4 = 6，因此有兩對

3、集合交集

給定一個包含n個正整數的集合S1，再給定一個包含m個正整數的集合S2，求兩個集合的交集。

n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
b=list(map(int,input().split()))# 排序
a=sorted(a)
b=sorted(b)# 定義指針 與 結果集
i=0
j=0
result=[]# 雙指針遍歷求解
while i<n and j<m:if a[i]==b[j]:result.append(a[i])i+=1j+=1elif a[i]<b[j]:i+=1else:j+=1for i in range(len(result)):if i<len(result)-1:print(result[i],end=' ')else:print(result[i],end='')
----------------------------------------
輸入：5 41 2 5 6 82 4 6 7
輸出：2 6
----------------------------------------

4、集合并集

給定一個包含n個正整數的集合S1，再給定一個包含m個正整數的集合S2，求兩個集合的并集。

n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
b=list(map(int,input().split()))# 排序
a=sorted(a)
b=sorted(b)# 定義指針 與 結果集
i=0
j=0
result=[]# 雙指針遍歷求解
while i<n and j<m:if a[i]==b[j]:result.append(a[i])i+=1j+=1elif a[i]<b[j]:result.append(a[i])i+=1else:result.append(b[j])j+=1
# 將剩余的元素加入到結果中去
while i<n:result.append(a[i])i+=1
while j<m:result.append(b[j])j+=1for i in range(len(result)):if i<len(result)-1:print(result[i],end=' ')else:print(result[i],end='')
----------------------------------------
輸入：5 41 2 5 6 82 4 6 7
輸出：1 2 4 5 6 7 8
----------------------------------------

5、集合差集

給定一個包含n個正整數的集合S1，再給定一個包含m個正整數的集合S2，求兩個集合的差集，即S1?S2。

注：使用雙指針法完成。

n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
b=list(map(int,input().split()))# 排序
a=sorted(a)
b=sorted(b)# 定義指針 與 結果集
i=0
j=0
result=[]# 雙指針遍歷求解
while i<n and j<m:if a[i]==b[j]:i+=1j+=1elif a[i]<b[j]:result.append(a[i])i+=1else:j+=1
# 將剩余的元素加入到結果中去
while i<n:result.append(a[i])i+=1for i in range(len(result)):if i<len(result)-1:print(result[i],end=' ')else:print(result[i],end='')
----------------------------------------
輸入：5 41 2 5 6 82 4 6 7
輸出：1 5 8
----------------------------------------

6、美麗的區間【區間和】

題目大意：求序列里區間和大于或等于常數s的最小區間長度

給定一個長度為 n 的序列 a1,a2,?,an 和一個常數 S。對于一個連續區間如果它的區間和大于或等于 S，則稱它為美麗的區間。對于一個美麗的區間，如果其區間長度越短，它就越美麗。請你從序列中找出最美麗的區間。

n,s=list(map(int,input().split()))
a=list(map(int,input().split()))i,j=0,0 # 雙指針
sum = 0 # 記錄【區間和】
lens=10000000000000while i < len(a):if sum < s:sum+=a[i]i+=1else:if lens > i-j:lens = i-jsum -= a[j]j+=1
if lens==10000000000000:print(0)
else:print(lens)
----------------------------------
輸入：5 6 # n=5，s=61 2 3 4 5
輸出：2
----------------------------------

二：二分查找

基本題型

在一個嚴格遞增序列A中尋找一個指定元素x，如果能找到，那么輸出它的下標；如果不能找到，那么輸出?1。

注：使用二分法實現。

size,target=list(map(int,input().split())) # 元素的個數、需要尋找的元素
a=list(map(int,input().split()))def f(a,size,target):left=0right=size-1while left <= right:mid=left+(right-left)//2if a[mid]==target:return midelif a[mid]<target:left=mid+1else:right=mid-1return -1print(f(a,size,target))
-------------------------------
輸入：5 31 2 3 5 8
輸出：2
-------------------------------

【延伸】單峰序列?

單峰序列是指，在這個序列中存在一個位置，滿足這個位置的左側（含該位置）是嚴格遞增的、右側（含該位置）是嚴格遞減的，這個位置被稱作峰頂位置。現在給定一個單峰序列，求峰頂位置的下標。

n=int(input())
a=list(map(int,input().split()))def f(n,a):left=0right=n-1while left<right:mid = int((left+right)/2)if a[mid]<a[mid-1]:right=midelse:left=mid+1return left-1print(f(n,a))
-------------------------------------
輸入：51 3 5 2 1
輸出：2
-------------------------------------

【延伸】木棒切割問題

給出n根木棒的長度，現在希望通過切割它們來得到至少k段長度相等的木棒（長度必須是整數），問這些長度相等的木棒的最大長度。

n,k=map(int,input().split())
a = list(map(int,input().split()))def f(n,k,a):l=0r=10**5while l<r:mid = (l + r + 1) // 2  # 計算中間值stick_count=sum(x//mid for x in a)if stick_count<k:r=mid-1else:l=midreturn lprint(f(n,k,a))
--------------------------------------
輸入：3 710 24 15
輸出：6
--------------------------------------

解釋：

對三根長度分別為10、24、15的木棒來說，k=7，即需要至少7段長度相等的木棒，此時可以得到最大長度為6，因為在這種情況下，第一根木棒可以提供10/6=1段、第二根木棒可以提供24/6=4段、第三根木棒可以提供15/6=2段，達到了7段的要求。

【延伸】分巧克力

兒童節那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友們。

小明一共有 N 塊巧克力，其中第 i 塊是 Hi×Wi 的方格組成的長方形。為了公平起見，

小明需要從這 N 塊巧克力中切出 K 塊巧克力分給小朋友們。切出的巧克力需要滿足：

形狀是正方形，邊長是整數;
大小相同;

例如一塊 6×5 的巧克力可以切出 6 塊 2×2 的巧克力或者 2 塊 3×3 的巧克力。

當然小朋友們都希望得到的巧克力盡可能大，你能幫小明計算出最大的邊長是多少么？

n,k = list(map(int,input().split()))
a=[]
for _ in range(n):x=list(map(int,input().split()))a.append(x)def f(x):count=0for j in range(len(a)):x1=a[j][0]y1=a[j][1]count+=(x1//x)*(y1//x) # 數量return countleft=1
right=10000000
while left<=right:mid=(left+right)//2sums=f(mid)if sums<k:right=mid-1elif sums>=k:left=mid+1print(right)
------------------------------------------
輸入：2 106 55 6
輸出：2
------------------------------------------

三：并查集

并查集的基本寫法：初始化，查詢，合并。

1、合根植物

w 星球的一個種植園，被分成 m×n個小格子（東西方向 m 行，南北方向 n 列）。每個格子里種了一株合根植物。

這種植物有個特點，它的根可能會沿著南北或東西方向伸展，從而與另一個格子的植物合成為一體。

如果我們告訴你哪些小格子間出現了連根現象，你能說出這個園中一共有多少株合根植物嗎？

m,n=map(int,input().split())ans=m*n # 單獨集合數量# 【初始化】
nums=[i for i in range(m*n+1)]
#尋找父節點【尋找】
def find_root(x):if x==nums[x]:return xnums[x]=find_root(nums[x])return nums[x]
# 【合并】
def merge(x,y):global ans# 找到 l 和 r 的根節點x_root=find_root(x)y_root=find_root(y)# 如果 l 和 r 的根節點不同，說明它們原本不屬于同一個集合if x_root!=y_root:nums[x_root] = nums[y_root] ans-=1 # 每次合并操作后，獨立集合的數量減少 1k=int(input())
# 對于每組數據，讀取兩個整數 l 和 r，表示要將 l 和 r 所在的集合合并。
for i in range(k):# 找到 l 和 r 的根節點l,r=map(int,input().split())merge(l,r)
print(ans)
---------------------------------------------
輸入：5 4 # m行 n列16 # k為162 31 55 94 87 89 1010 1111 1210 1412 1614 1817 1815 1919 209 1313 17
輸出：5
---------------------------------------------

2、藍橋幼兒園

藍橋幼兒園的學生是如此的天真無邪，以至于對他們來說，朋友的朋友就是自己的朋友。小明是藍橋幼兒園的老師，這天他決定為學生們舉辦一個交友活動，活動規則如下：

小明會用紅繩連接兩名學生，被連中的兩個學生將成為朋友。

小明想讓所有學生都互相成為朋友，但是藍橋幼兒園的學生實在太多了，他無法用肉眼判斷某兩個學生是否為朋友。于是他起來了作為編程大師的你，請你幫忙寫程序判斷某兩個學生是否為朋友（默認自己和自己也是朋友）。

輸入描述：
第 1 行包含兩個正整數 N,M，其中 N 表示藍橋幼兒園的學生數量，學生的編號分別為 1～N。

之后的第 2～M+1 行每行輸入三個整數，op,x,y：

如果 op=1，表示小明用紅繩連接了學生 x 和學生 y 。
如果 op=2，請你回答小明學生 x 和學生 y 是否為朋友。

輸出描述：
對于每個 op=2 的輸入，如果 x 和 y 是朋友，則輸出一行 YES，否則輸出一行 NO。

n,m=list(map(int,input().split()))# 【初始化】
a=[i for i in range(n+1)]#尋找父節點【尋找】
def find_root(x):if x==a[x]:return xa[x]=find_root(a[x])return a[x]# 【合并】
def merge(x,y):x_root=find_root(x)y_root=find_root(y)if x_root!=y_root:a[x_root]=a[y_root]for i in range(m):op,x,y=list(map(int,input().split()))if op==1:merge(x,y)elif op==2:x_root=find_root(x)y_root=find_root(y)if x_root==y_root:print("YES")else:print("NO")
---------------------------------------------
輸入：5 5 2 1 21 1 32 1 31 2 3 2 1 2
輸出：NOYESYES
---------------------------------------------

四：STL + KMP

KMP算法是一種用于解決字符串匹配問題的經典算法，它的核心思想是利用已經匹配過的信息，避免不必要的匹配嘗試，從而提高匹配效率。

5.1、理論篇

5.2、實戰篇

Next數組【前綴表】

next數組是KMP算法中的一個關鍵概念，它記錄了模式串中每個位置的最長相同前后綴的長度。

在字符串匹配的KMP算法中有一個重要的概念是next數組，next數組的直接語義是：使“長度為L的前綴”與“長度為L的后綴”相同的最大L，且滿足條件的前后綴不能是原字符串本身。

例如對字符串ababa來說，長度為1的前綴與后綴都是a，它們相同；長度為2的前綴與后綴分別是ab和ba，它們不相同；長度為3的前綴與后綴都是aba，它們相同；長度為4的前綴與后綴分別是abab和baba，它們不相同。因此對字符串ababa來說，使“長度為L的前綴”與“長度為L的后綴”相同的最大L是3。

我們把這個最大的L值稱為原字符串S的next值。在此概念的基礎上，對給定的字符串S，下標為從1到n，那么next[i]就是指子串S[1...i]的next值。

現在給定一個字符串，求next數組每一項的值。

# next數組，用于填充這個數組
# s為模式串
def get_next(next,s):# 初始化j=0 # 前綴末尾位next[0]=0# i為后綴末尾位for i in range(1,len(s)):# 前后位不匹配,j邊界就是0【循環過程】while j>0 and s[i] != s[j]:# j回退到前一位對應的next表中的值j=next[j-1]# 前后綴相同情況if s[i]==s[j]:j+=1# 更新next數組next[i]=jreturn nexts=input()
next1=[0]*len(s) # 初始化next長度
next=get_next(next1,s)
for i in range(0,len(s)):if i<len(s)-1:print(next[i],end=' ')else:print(next[i],end='')
-----------------------------------------
輸入：ababaa
輸出：0 0 1 2 3 1
-----------------------------------------

解釋：

子串a的最長相等前后綴不存在（因為不能等于本身），因此L=0；

子串ab的最長相等前后綴不存在，因此L=0；

子串aba的最長相等前后綴是a，因此L=1；

子串abab的最長相等前后綴是ab，因此L=2；

子串ababa的最長相等前后綴是aba，因此L=3；

子串ababaa的最長相等前后綴是a，因此L=1。

子串判定

現有兩個字符串s1和s2，使用KMP算法判斷s2是否s1的子串。

s1=input() # 文本串
s2=input() # 模式串# next數組
def get_next(next,s):# 初始化j=0 # 前綴末尾位next[0]=0# i為后綴末尾位for i in range(1,len(s)):# 前后位不匹配,j邊界就是0【循環過程】while j>0 and s[i] != s[j]:# j回退到前一位對應的next表中的值j=next[j-1]# 前后綴相同情況if s[i]==s[j]:j+=1# 更新next數組next[i]=jreturn nextdef KMP(s1,s2):n=len(s1) # 文本串m=len(s2) # 模擬串next=[0]*len(s2) # 初始化next長度if m==0:return Truenext=get_next(next,s2)j=0for i in range(0,len(s1)):# s1對應元素 與 s2對應元素 不匹配while j>0 and s1[i] != s2[j]:j=next[j-1]# s1對應元素 與 s2對應元素 匹配if s1[i]==s2[j]:j+=1if j==len(s2):return Truereturn Falseresult=KMP(s1,s2)
print("Yes" if result else "No")
----------------------------------------
輸入：abadcbac
輸出：No
----------------------------------------

偷懶技巧：

s1=input() # 文本串
s2=input() # 模式串if s2 in s1:print("Yes")
else:print("No")

五：遞歸和遞推

【回溯法】，一般可以解決如下幾種問題：

組合問題：N個數里面按一定規則找出k個數的集合
切割問題：一個字符串按一定規則有幾種切割方式
子集問題：一個N個數的集合里有多少符合條件的子集
排列問題：N個數按一定規則全排列，有幾種排列方式
棋盤問題：N皇后，解數獨等等

基本框架：
void backtracking(參數) {if (終止條件) {存放結果;return;}for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）) {處理節點;backtracking(路徑，選擇列表); // 遞歸回溯，撤銷處理結果}
}

1、數的計算

輸入一個自然數 n (n≤1000)，我們對此自然數按照如下方法進行處理:

不作任何處理;
在它的左邊加上一個自然數,但該自然數不能超過原數的一半;
加上數后,繼續按此規則進行處理,直到不能再加自然數為止。

問總共可以產生多少個數。

def f(n):if n==1:return 1num=1for i in range(1,n//2+1):num=num+f(i)return numn=int(input())
print(f(n))
-----------------------------
輸入：6
輸出：6
-----------------------------

2、漢諾塔題型

漢諾塔（又稱河內塔）問題源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

抽象成模型就是說：

有三根相鄰的柱子，標號分別為A、B、C，A柱子按金字塔狀疊放著n個不同大小的圓盤，現在要把所有盤子一個一個移動到柱子C上，并且任何時候同一根柱子上都不能出現大盤子在小盤子上方，請問至少需要多少次移動，并給出具體的移動方案。

輸入：一個正整數n（1≤n≤16），表示圓盤的個數。

輸出：

? 第一行輸出一個整數，表示至少需要的移動次數。

? 接下來每行輸出一次移動，格式為X->Y，表示從柱子X移動最上方的圓盤到柱子Y最上方。

def f(n,from_rod,to_rod,mid_rod):if n==0:return# 將前n-1個盤子從from_rod到mid_rod,借助to_rod作為輔助f(n-1,from_rod,mid_rod,to_rod)# 將第n個盤子直接從from_rod移到to_rodprint(f"{from_rod}->{to_rod}")# 將前n-1個盤子從mid_rod到to_rod,借助from_rod作為輔助f(n-1,mid_rod,to_rod,from_rod)n = int(input())
print(2**n-1)
f(n,'A','C','B')

3、數字螺旋矩陣

給定一個正整數n，生成一個大小為n?n的方陣，其中按順時針的順序給出從1到n?n的每一個整數。

如下圖是n=5的螺旋矩陣。

def f(n):# 初始化n * n的矩陣：[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]matrix=[[0]*n for _ in range(n)]index=1def fill_matrix(x,y,size):nonlocal indexif size == 0:returnif size == 1:matrix[x][y] = indexindex+=1return# 填充最上邊的行for i in range(y,y+size-1):matrix[x][i]=indexindex+=1# 填充最右邊的列for i in range(x,y+size-1):matrix[i][y+size-1]=indexindex+=1# 填充最下邊的行for i in range(y+size-1,y,-1):matrix[x+size-1][i] = indexindex+=1# 填充最左邊的行for i in range(x+size-1,x,-1):matrix[i][y]=indexindex+=1# 遞歸填充內圈fill_matrix(x+1,y+1,size-2)fill_matrix(0,0,n)return matrixn=int(input())# [[1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7], [14, 23, 22, 21, 8], [13, 12, 11, 10, 9]]
result=f(n) for row in result:for i in range(len(row)):if i<len(row)-1:print(row[i],end=' ')else:print(row[i])
-------------------------------
輸入：5
輸出：1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9
-------------------------------

六、基礎題

1、卡片

小藍有 k 種卡片, 一個班有 n 位同學, 小藍給每位同學發了兩張卡片, 一位同學的兩張卡片可能是同一種, 也可能是不同種, 兩張卡片沒有順序。沒有兩位同學的卡片都是一樣的。

給定 n , 請問小藍的卡片至少有多少種?

注意：C計算兩種不同的卡片【比如(1,2)(1,3)(2,3)】，題目中還可以相同的卡片【比如(1,1)(2,2)(3,3)】，因此需要加k。

n=int(input())k=1
while 1:if k*(k+1)/2 >= n:print(k)breakelse:k+=1
----------------------------
輸入：6
輸出：3
----------------------------

2、水仙花數

如果一個三位數 n 的各位數字的立方和等于 n ，那么稱 n 為水仙花數。例如 153=1³⁺⁵3+3^3，因此 153 是水仙花數。

給定一個正整數，判斷這個數是否是水仙花數。

n = int(input())temp = nbai = temp // 100
shi = (temp // 10) % 10
ge = temp%10if ge**3+bai**3+shi**3 == n:print("YES")
else:print("NO")
---------------------------------
輸入：153
輸出：YES
---------------------------------

七、Hash法【補充】

給定一個嚴格遞增序列A和一個正整數k，在序列A中尋找不同的下標i、j，使得Ai+Aj=k。問有多少對(i,j)同時i<j滿足條件。

注：使用hash法實現

def find(n, k, A):# 初始化hash表，大小為10^6+1hashTable = [False] * (10 ** 6 + 1)# 填充hash表for num in A:hashTable[num] = Truecount = 0# 查找數對for num in A:if k - num >= 0 and hashTable[k - num]:count += 1# 每個數對被找到兩次，所以結果需要除以 2return count // 2n, m = map(int, input().split())
A = list(map(int, input().split()))print(find(n, m, A))
------------------------
輸入：5 61 2 4 5 6
輸出：2
------------------------