python算法常用技巧與內置庫

python算法常用技巧與內置庫

近些年隨着python的越來越火，python也漸漸成為了很多程序員的喜愛。許多程序員已經開始使用python作為第一語言來刷題。

最近我在用python刷題的時候想去找點python的刷題常用庫api和刷題技巧來看看。類似於C++的STL庫文檔一樣，但是很可惜並沒有找到，於是決定結合自己的刷題經驗和上網搜索做一份文檔出來，供自己和大家觀看查閱。

1.輸入輸出:

1.1 第一行給定兩個值n,m，用空格分割，第一個n決定接下來有n行的輸入，m決定每一行有多少個數字，m個數字均用空格分隔.

解決辦法：python的input函數接收到的輸入默認都是字符串，所以我們使用 字符串切割、強制類型轉換、列表生成器就可以完美解決輸入問題。代碼如下:

# 接收兩個值，使用n,m分別接收列表中的兩個值
n, m  = [int(x) for x in input().split()]

# 構造輸入列表的列表
num_list = []

for i in range(n):
	# python可以不用在意m的值，將所有數值接收進來然後使用len判斷長度
	tmp_list = [int(x) for x in input().split()]
	num_list.append(tmp_list)

同理，若是用逗號(,)分隔的話，split函數中傳入相同的值就行。

1.2 輸出一行數字

由於python的print函數默認利用換行作為結束符，所以我們需要將它修改成我們需要的間隔，代碼如下:

for i in range(10):
	print(i, end=' ')

end是print函數中的一個參數，決定輸出的結束字符，這裡修改成空格代表輸出一行數字，用空格間隔，其它字符可以自行修改。

2.空列表生成，字符串修改，列表遍歷

2.1 代碼編寫過程中，有時候會需要一個帶有長度的，有初始值的空列表，生成方式如下:

# 1. 用乘法生成一個初始值為False的長度為100的一維列表
visited = [False] * 100

# 2. 利用列表生成器生成一個n*m的二維的初始值為0的列表
visited = [[0 for i in range(m)] for j in range(n)]

2.2 在python當中字符串是無法原地修改的，如果每次修改都生成一個新字符串，那麼對修改次數很多且字符串很當的情況，開銷是很大的。所以一般是把字符串轉為列表進行修改最後再轉回來。

string = 'I love to eat chicken'
# 將字符串轉換成列表
string_list = list(string)

# .......對字符串列表進行修改
# Code

# 將字符串列表重新拼接成字符串
#string = ''.join(string_list)

2.3 python中列表遍歷有許多種不同的方式，最直接的辦法是直接對列表進行迭代遍歷，但是因為我們往往是基於索引對數組進行操作且需要修改數組的值，所以更推薦用以下代碼中的第二三中辦法:

num_list = [i for i in range(10)]

# 1. 直接迭代列表
for item in num_list:
	# Code
	pass

# 2. 通過索引進行迭代
for i in range(len(num_list)):
	print(num_list[i])

# 3. 通過enumerate函數進行迭代
for index, value in enumerate(num_list):
	# index為當前元素的索引，value為當前元素的值
	print(index, value)

3. collections庫的使用

3.1 deque隊列

deque 是python中的隊列（FIFO先進先出），隊列在進行隊首彈出的時候會比list要快。

尤其在使用BFS（深度優先搜索）的時候，隊列是必須要使用到的。部分deque使用代碼如下:

from collections import deque

# 初始化一個最大長度為3的隊列
d = deque([1,2,3], maxlen=3)

# 因為初始化隊列最大長度為3，再添加元素會把隊頭元素擠出
d.append(4)

# 初始化一個不限制長度的隊列
d = deque()

# 添加元素到隊尾部
d.append(1)
d.append(2)
d.append(3)

# 將隊首的元素彈出返回
print(d.popleft())

# 彈出隊尾元素並返回值
print(d.pop())

# 在隊首插入元素
d.appendleft(0)

3.2 Counter計數器

Counter 是一個計數器，可以對一個序列計數，計算序列中某個元素出現的數量。

以下是示例代碼:

import collections

# 一共有三種初始方法
# 1. 傳入一個序列
print(collections.Counter(['a', 'b', 'c', 'a', 'b', 'b']))
# 2.傳入一個字典
print(collections.Counter({'a':2, 'b':3, 'c':1}))
# 3.直接利用=傳參
print(collections.Counter(a=2, b=3, c=1))

# 也可以無參數構造，利用update函數更新
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對象
for letter in 'abcde':
    print('%s : %d' % (letter, c[letter]))

# elements()方法可以返回一個包含所有Counter數據的迭代器
c = collections.Counter('extremely')
c['z'] = 0
print(list(c.elements()))
# ['e', 'e', 'e', 'm', 'l', 'r', 't', 'y', 'x']

# most_common()返回前n個最多的數據
c=collections.Counter('aassdddffff')
for letter, count in c.most_common(2):
    print('%s: %d' % (letter, count))
# f: 4
# d: 3

# Counter對象可以進行加減交並，直接使用運算符 +、-、&、|
# +會將兩個字典中相同字符的出現次數相加，-會給出第一個Counter相對於第二個的差集。交集給出兩個計數器當中都有的元素，且計數被賦值為較小的那個，並集為兩個計數器的元素出現最多的那個。

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——帶有默認值的字典

一般情況下創建的字典dict是不含有默認值的，即若是字典中不包含a這個key，調用dct{a}的話就會報錯。

在進行算法設計和數據結構設計的時候我們希望任意給定一個key都能從字典中取出值來，哪怕只是一個默認值，這個時候我們就需要用到defaultdict。

例如在用字典表示圖中一個節點的相連節點的時候，我們希望將這個節點作為一個key，然後與它相連的節點組成一個列表作為它的value，這個時候我們就可以使用defaultdict(list)來創建一個默認值為列表的字典。

# list的默認值為空列表
list_dict = collections.defaultdict(list)
# int的默認值為0
int_dict = collections.defaultdict(int)

print(list_dict['a'])
print(int_dict['a'])

# 輸出：[]
# 輸出：0

3.4 小結

collection中常被用來寫算法和數據結構的就是這幾個，其它比如排序字典和命名元組很少會用上。

4.排序

4.1 對列表排序

對列表排序有兩種方法，一種是使用列表內置的sort函數，sort函數直接在列表原地修改，無返回值，可以通過參數key自定義比較的key和比較函數。

第二種就是使用python的sorted函數，這個函數自由度比較高，可以自己設定比較函數和比較的key，返回一個新的列表。

如果需要自定義比較的函數，需要從庫functools導入函數cmp_to_key函數，將比較函數轉為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 對字典/元組列表排序

若是需要對字典（將字典利用item函數轉化成元組列表）或者元組列表這種每一個item有兩個值的序列進行排序，這個時候就需要利用sorted函數中的key來決定取哪個值排序。代碼如下:

# 利用字符串創建計數器字典
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內置的模塊itertools中集成了一些與迭代有關的函數，其中就有排列組合函數。

5.1 排列

排列函數permutations接收一個列表，返回這個列表內所有元素的全排列列表。

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 組合

組合函數combinations接收兩個參數，第一個為一個需要進行組合的列表，第二個參數為一個正整數，代表從列表中抽取多少個元素進行組合，返回一個組合列表。

from itertools import combinations
print(list(combinations([1,2,3],2)))

# 輸出如下：
# [(1, 2), (1, 3), (2, 3)]

6.小技巧

6.1 在python中分了可變類型和不可變類型，當函數傳參的時候：

  • 若是不可變類型如字符串，則傳遞參數的時候會深拷貝一份，在新的數據上修改並不改變原數據
  • 若是可變類型如列表，則傳遞參數的時候傳遞的是引用，屬於淺拷貝，在函數中對新列表進行操作會影響到原來的列表。

若是確實需要傳遞可變類型進入函數，則可以在函數內部第一行進行一次深拷貝如：

def test(num_list:list):
	# 進行深拷貝
	num_list = num_list[:]

6.2 當刪除列表中的元素的時候，列表後面的元素會自動往前移動，導致出錯

例如，列表為[1,2,3,4,5,6]，想要刪除列表中的偶數，如果直接找到一個偶數然後利用其索引刪除，如下代碼所示（錯誤示範），那麼很抱歉，出問題了。

# 此處為錯誤示範！！！！！！！！
lst = [1, 2, 3, 4, 5, 6]
for i in range(len(lst)):
    if lst[i] % 2 == 0:
        lst.pop(i)

print(lst)

# 上面這段代碼沒有輸出，因為報索引越界錯誤了。

下面的代碼才是正確示範：

lst = [1, 2, 3, 4, 5, 6]
lst = [i for i in lst if i % 2 != 0]

print(lst)

# 輸出如下：
# [1, 3, 5]

若是需要更複雜的篩選手段，可以在if i%2 !=0那裡更改成一個函數判斷，函數內部就實現篩選方法。

6.3 訪問字典元素要使用get方法

前文說過，普通的dict字典是沒有默認值的，所以這個時候如果直接利用中括號放置key來查找value的話是有可能會報錯的。

那麼為了避免這種情況，在利用字典的key來取value的時候，需要利用字典的get函數。

get函數的第一個參數為key，第二個參數為可選（默認為None），當字典中找不到傳入的key的時候，會返回第二個參數所賦的值。

7.小結

以上是本人在使用python刷題的時候作的一些總結，若有不到位的地方請指出。

本文旨在為自己做一個文檔，同時也為大家提供一些便利。

關注我的公眾號【程序小員】，收貨一大波福利知識。

我是落陽，謝謝你的到訪。

Tags:

VirMach 便宜 VPS

QNews

QNews