詳解python算法常用技巧與內(nèi)置庫(kù)
近些年隨著python的越來(lái)越火,python也漸漸成為了很多程序員的喜愛。許多程序員已經(jīng)開始使用python作為第一語(yǔ)言來(lái)刷題。
最近我在用python刷題的時(shí)候想去找點(diǎn)python的刷題常用庫(kù)api和刷題技巧來(lái)看看。類似于C++的STL庫(kù)文檔一樣,但是很可惜并沒有找到,于是決定結(jié)合自己的刷題經(jīng)驗(yàn)和上網(wǎng)搜索做一份文檔出來(lái),供自己和大家觀看查閱。
1.輸入輸出:
1.1 第一行給定兩個(gè)值n,m,用空格分割,第一個(gè)n決定接下來(lái)有n行的輸入,m決定每一行有多少個(gè)數(shù)字,m個(gè)數(shù)字均用空格分隔.
解決辦法:python的input函數(shù)接收到的輸入默認(rèn)都是字符串,所以我們使用 字符串切割、強(qiáng)制類型轉(zhuǎn)換、列表生成器就可以完美解決輸入問題。代碼如下:
# 接收兩個(gè)值,使用n,m分別接收列表中的兩個(gè)值 n, m = [int(x) for x in input().split()] # 構(gòu)造輸入列表的列表 num_list = [] for i in range(n): # python可以不用在意m的值,將所有數(shù)值接收進(jìn)來(lái)然后使用len判斷長(zhǎng)度 tmp_list = [int(x) for x in input().split()] num_list.append(tmp_list)
同理,若是用逗號(hào)(,)分隔的話,split函數(shù)中傳入相同的值就行。
1.2 輸出一行數(shù)字
由于python的print函數(shù)默認(rèn)利用換行作為結(jié)束符,所以我們需要將它修改成我們需要的間隔,代碼如下:
for i in range(10): print(i, end=' ')
end是print函數(shù)中的一個(gè)參數(shù),決定輸出的結(jié)束字符,這里修改成空格代表輸出一行數(shù)字,用空格間隔,其它字符可以自行修改。
2.空列表生成,字符串修改,列表遍歷
2.1 代碼編寫過程中,有時(shí)候會(huì)需要一個(gè)帶有長(zhǎng)度的,有初始值的空列表,生成方式如下:
# 1. 用乘法生成一個(gè)初始值為False的長(zhǎng)度為100的一維列表 visited = [False] * 100 # 2. 利用列表生成器生成一個(gè)n*m的二維的初始值為0的列表 visited = [[0 for i in range(m)] for j in range(n)]
2.2 在python當(dāng)中字符串是無(wú)法原地修改的,如果每次修改都生成一個(gè)新字符串,那么對(duì)修改次數(shù)很多且字符串很當(dāng)?shù)那闆r,開銷是很大的。所以一般是把字符串轉(zhuǎn)為列表進(jìn)行修改最后再轉(zhuǎn)回來(lái)。
string = 'I love to eat chicken' # 將字符串轉(zhuǎn)換成列表 string_list = list(string) # .......對(duì)字符串列表進(jìn)行修改 # Code # 將字符串列表重新拼接成字符串 #string = ''.join(string_list)
2.3 python中列表遍歷有許多種不同的方式,最直接的辦法是直接對(duì)列表進(jìn)行迭代遍歷,但是因?yàn)槲覀兺腔谒饕龑?duì)數(shù)組進(jìn)行操作且需要修改數(shù)組的值,所以更推薦用以下代碼中的第二三中辦法:
num_list = [i for i in range(10)] # 1. 直接迭代列表 for item in num_list: # Code pass # 2. 通過索引進(jìn)行迭代 for i in range(len(num_list)): print(num_list[i]) # 3. 通過enumerate函數(shù)進(jìn)行迭代 for index, value in enumerate(num_list): # index為當(dāng)前元素的索引,value為當(dāng)前元素的值 print(index, value)
3. collections庫(kù)的使用
3.1 deque隊(duì)列
deque 是python中的隊(duì)列(FIFO先進(jìn)先出),隊(duì)列在進(jìn)行隊(duì)首彈出的時(shí)候會(huì)比list要快。
尤其在使用BFS(深度優(yōu)先搜索)的時(shí)候,隊(duì)列是必須要使用到的。部分deque使用代碼如下:
from collections import deque # 初始化一個(gè)最大長(zhǎng)度為3的隊(duì)列 d = deque([1,2,3], maxlen=3) # 因?yàn)槌跏蓟?duì)列最大長(zhǎng)度為3,再添加元素會(huì)把隊(duì)頭元素?cái)D出 d.append(4) # 初始化一個(gè)不限制長(zhǎng)度的隊(duì)列 d = deque() # 添加元素到隊(duì)尾部 d.append(1) d.append(2) d.append(3) # 將隊(duì)首的元素彈出返回 print(d.popleft()) # 彈出隊(duì)尾元素并返回值 print(d.pop()) # 在隊(duì)首插入元素 d.appendleft(0)
3.2 Counter計(jì)數(shù)器
Counter
是一個(gè)計(jì)數(shù)器,可以對(duì)一個(gè)序列計(jì)數(shù),計(jì)算序列中某個(gè)元素出現(xiàn)的數(shù)量。
以下是示例代碼:
import collections # 一共有三種初始方法 # 1. 傳入一個(gè)序列 print(collections.Counter(['a', 'b', 'c', 'a', 'b', 'b'])) # 2.傳入一個(gè)字典 print(collections.Counter({'a':2, 'b':3, 'c':1})) # 3.直接利用=傳參 print(collections.Counter(a=2, b=3, c=1)) # 也可以無(wú)參數(shù)構(gòu)造,利用update函數(shù)更新 c = collections.Counter() print('Initial :', c) # Initial: Counter() c.update('abcdaab') print('Sequence:', c) # Sequence: Counter({'a': 3, 'b': 2, 'c': 1, 'd': 1}) c.update({'a':1, 'd':5}) print('Dict:', c) # Dict: Counter({'d': 6, 'a': 4, 'b': 2, 'c': 1}) # 可以通過訪問字典的訪問方式訪問Counter對(duì)象 for letter in 'abcde': print('%s : %d' % (letter, c[letter])) # elements()方法可以返回一個(gè)包含所有Counter數(shù)據(jù)的迭代器 c = collections.Counter('extremely') c['z'] = 0 print(list(c.elements())) # ['e', 'e', 'e', 'm', 'l', 'r', 't', 'y', 'x'] # most_common()返回前n個(gè)最多的數(shù)據(jù) c=collections.Counter('aassdddffff') for letter, count in c.most_common(2): print('%s: %d' % (letter, count)) # f: 4 # d: 3 # Counter對(duì)象可以進(jìn)行加減交并,直接使用運(yùn)算符 +、-、&、| # +會(huì)將兩個(gè)字典中相同字符的出現(xiàn)次數(shù)相加,-會(huì)給出第一個(gè)Counter相對(duì)于第二個(gè)的差集。交集給出兩個(gè)計(jì)數(shù)器當(dāng)中都有的元素,且計(jì)數(shù)被賦值為較小的那個(gè),并集為兩個(gè)計(jì)數(shù)器的元素出現(xiàn)最多的那個(gè)。 c1 = collections.Counter(['a', 'b', 'c', 'a', 'b', 'b']) c2 = collections.Counter('alphabet') print ('C1:', c1) print ('C2:', c2) print ('\nCombined counts:') print (c1 + c2) print ('\nSubtraction:') print (c1 - c2) print ('\nIntersection (taking positive minimums):') print (c1 & c2) print ('\nUnion (taking maximums):') print (c1 | c2) # 以下為輸出: C1: Counter({'b': 3, 'a': 2, 'c': 1}) C2: Counter({'a': 2, 'l': 1, 'p': 1, 'h': 1, 'b': 1, 'e': 1, 't': 1}) Combined counts: Counter({'a': 4, 'b': 4, 'c': 1, 'l': 1, 'p': 1, 'h': 1, 'e': 1, 't': 1}) Subtraction: Counter({'b': 2, 'c': 1}) Intersection (taking positive minimums): Counter({'a': 2, 'b': 1}) Union (taking maximums): Counter({'b': 3, 'a': 2, 'c': 1, 'l': 1, 'p': 1, 'h': 1, 'e': 1, 't': 1})
3.3 defaultdict——帶有默認(rèn)值的字典
一般情況下創(chuàng)建的字典dict是不含有默認(rèn)值的,即若是字典中不包含a這個(gè)key,調(diào)用dct{a}的話就會(huì)報(bào)錯(cuò)。
在進(jìn)行算法設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的時(shí)候我們希望任意給定一個(gè)key都能從字典中取出值來(lái),哪怕只是一個(gè)默認(rèn)值,這個(gè)時(shí)候我們就需要用到defaultdict
。
例如在用字典表示圖中一個(gè)節(jié)點(diǎn)的相連節(jié)點(diǎn)的時(shí)候,我們希望將這個(gè)節(jié)點(diǎn)作為一個(gè)key,然后與它相連的節(jié)點(diǎn)組成一個(gè)列表作為它的value,這個(gè)時(shí)候我們就可以使用defaultdict(list)來(lái)創(chuàng)建一個(gè)默認(rèn)值為列表的字典。
# list的默認(rèn)值為空列表 list_dict = collections.defaultdict(list) # int的默認(rèn)值為0 int_dict = collections.defaultdict(int) print(list_dict['a']) print(int_dict['a']) # 輸出:[] # 輸出:0
3.4 小結(jié)
collection中常被用來(lái)寫算法和數(shù)據(jù)結(jié)構(gòu)的就是這幾個(gè),其它比如排序字典和命名元組很少會(huì)用上。
4.排序
4.1 對(duì)列表排序
對(duì)列表排序有兩種方法,一種是使用列表內(nèi)置的sort函數(shù),sort函數(shù)直接在列表原地修改,無(wú)返回值,可以通過參數(shù)key自定義比較的key和比較函數(shù)。
第二種就是使用python的sorted函數(shù),這個(gè)函數(shù)自由度比較高,可以自己設(shè)定比較函數(shù)和比較的key,返回一個(gè)新的列表。
如果需要自定義比較的函數(shù),需要從庫(kù)functools
導(dǎo)入函數(shù)cmp_to_key
函數(shù),將比較函數(shù)轉(zhuǎn)為key,使用代碼如下:
def custom_sort(x,y): if x>y: # 返回-1代表需要排在前面 return -1 if x<y: # 返回1代表需要排在后面 return 1 return 0 lst = [i for i in range(10, -1, -1)] print(lst) lst.sort() print(lst) print(sorted(lst, key=cmp_to_key(custom_sort))) # 輸出如下: # [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
4.2 對(duì)字典/元組列表排序
若是需要對(duì)字典(將字典利用item
函數(shù)轉(zhuǎn)化成元組列表)或者元組列表這種每一個(gè)item有兩個(gè)值的序列進(jìn)行排序,這個(gè)時(shí)候就需要利用sorted函數(shù)中的key來(lái)決定取哪個(gè)值排序。代碼如下:
# 利用字符串創(chuàng)建計(jì)數(shù)器字典 d = dict(collections.Counter('Hello World')) print(d) # 排序 print(sorted(d.items(), key=lambda x: x[1], reverse=True)) # 輸出如下: # {'H': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'W': 1, 'r': 1, 'd': 1} # [('l', 3), ('o', 2), ('H', 1), ('e', 1), (' ', 1), ('W', 1), ('r', 1), ('d', 1)]
5.排列組合
python內(nèi)置的模塊itertools中集成了一些與迭代有關(guān)的函數(shù),其中就有排列組合函數(shù)。
5.1 排列
排列函數(shù)permutations
接收一個(gè)列表,返回這個(gè)列表內(nèi)所有元素的全排列列表。
from itertools import permutations print(list(permutations([1,2,3]))) # 輸出如下: # [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
5.2 組合
組合函數(shù)combinations
接收兩個(gè)參數(shù),第一個(gè)為一個(gè)需要進(jìn)行組合的列表,第二個(gè)參數(shù)為一個(gè)正整數(shù),代表從列表中抽取多少個(gè)元素進(jìn)行組合,返回一個(gè)組合列表。
from itertools import combinations print(list(combinations([1,2,3],2))) # 輸出如下: # [(1, 2), (1, 3), (2, 3)]
6.小技巧
6.1 在python中分了可變類型和不可變類型,當(dāng)函數(shù)傳參的時(shí)候:
- 若是不可變類型如字符串,則傳遞參數(shù)的時(shí)候會(huì)深拷貝一份,在新的數(shù)據(jù)上修改并不改變?cè)瓟?shù)據(jù)若是可變類型如列表,則傳遞參數(shù)的時(shí)候傳遞的是引用,屬于淺拷貝,在函數(shù)中對(duì)新列表進(jìn)行操作會(huì)影響到原來(lái)的列表。
- 若是確實(shí)需要傳遞可變類型進(jìn)入函數(shù),則可以在函數(shù)內(nèi)部第一行進(jìn)行一次深拷貝如:
def test(num_list:list): # 進(jìn)行深拷貝 num_list = num_list[:]
6.2 當(dāng)刪除列表中的元素的時(shí)候,列表后面的元素會(huì)自動(dòng)往前移動(dòng),導(dǎo)致出錯(cuò)
例如,列表為[1,2,3,4,5,6]
,想要?jiǎng)h除列表中的偶數(shù),如果直接找到一個(gè)偶數(shù)然后利用其索引刪除,如下代碼所示(錯(cuò)誤示范),那么很抱歉,出問題了。
# 此處為錯(cuò)誤示范?。。。。。。?! lst = [1, 2, 3, 4, 5, 6] for i in range(len(lst)): if lst[i] % 2 == 0: lst.pop(i) print(lst) # 上面這段代碼沒有輸出,因?yàn)閳?bào)索引越界錯(cuò)誤了。
下面的代碼才是正確示范:
lst = [1, 2, 3, 4, 5, 6] lst = [i for i in lst if i % 2 != 0] print(lst) # 輸出如下: # [1, 3, 5]
若是需要更復(fù)雜的篩選手段,可以在if i%2 !=0
那里更改成一個(gè)函數(shù)判斷,函數(shù)內(nèi)部就實(shí)現(xiàn)篩選方法。
6.3 訪問字典元素要使用get方法
前文說過,普通的dict字典是沒有默認(rèn)值的,所以這個(gè)時(shí)候如果直接利用中括號(hào)放置key來(lái)查找value的話是有可能會(huì)報(bào)錯(cuò)的。
那么為了避免這種情況,在利用字典的key來(lái)取value的時(shí)候,需要利用字典的get
函數(shù)。
get
函數(shù)的第一個(gè)參數(shù)為key,第二個(gè)參數(shù)為可選(默認(rèn)為None),當(dāng)字典中找不到傳入的key的時(shí)候,會(huì)返回第二個(gè)參數(shù)所賦的值。
7.小結(jié)
以上是本人在使用python刷題的時(shí)候作的一些總結(jié),若有不到位的地方請(qǐng)指出。
到此這篇關(guān)于詳解python算法常用技巧與內(nèi)置庫(kù)的文章就介紹到這了,更多相關(guān)python算法技巧與內(nèi)置庫(kù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Python實(shí)現(xiàn)自動(dòng)上京東搶手機(jī)
這篇文章主要為大家詳細(xì)介紹了Python實(shí)現(xiàn)自動(dòng)上京東搶手機(jī)的方法,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-02-02快速解決pymongo操作mongodb的時(shí)區(qū)問題
這篇文章主要介紹了快速解決pymongo操作mongodb的時(shí)區(qū)問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來(lái)看看吧2020-12-12python實(shí)現(xiàn)csv格式文件轉(zhuǎn)為asc格式文件的方法
下面小編就為大家分享一篇python實(shí)現(xiàn)csv格式文件轉(zhuǎn)為asc格式文件的方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來(lái)看看吧2018-03-03Django Rest framework權(quán)限的詳細(xì)用法
這篇文章主要介紹了Django Rest framework權(quán)限的詳細(xì)用法,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-07-07Python使用窮舉法求兩個(gè)數(shù)的最大公約數(shù)問題
這篇文章主要介紹了Python使用窮舉法求兩個(gè)數(shù)的最大公約數(shù)問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-12-12