【使用Python實現算法】02 原生類型與內置函數

【使用 Python 實現算法】目錄

• 01 語言特性

• 02 原生類型與內置函數

本期話題是 Python 的原生類型和內置函數在算法實現中的一些技巧，首先從最常見的 Python 原生類型開始。

int

int類型有兩個內置的方法bit_count與bit_length，分別用來獲取整數二進制表達的1的個數和二進制位數，在很多場景下都很實用。
n = 9
assert n.bit_count() == 2
assert n.bit_length() == 4


float

float的as_integer_ratio方法可以獲得浮點數的最簡分數表達。
f = 6.125
assert f.as_integer_ratio() == (49, 8)

利用f-string可以輕松獲得浮點數的指定小數位數的字符串表達。
assert f"{1/3:.4f}" == "0.3333"


list

list的pop方法接收整數參數 n， 返回並刪除列表中的第 n 個元素（O(n)的時間復雜度，效率不高）。
arr = [1, 2, 3]
assert arr.pop(1) == 2
assert arr == [1, 3]

算法實現中經常需要用到棧結構，Python 的 list 類型原生擁有棧的所有功能，也可以簡單的封裝一下，定義自己的 Stack 類型。
class Stack(list):
 push = list.append
 top = lambda l: l[-1]
 empty = lambda l: not l


tuple

tuple類型在算法實現中的使用頻率不是很高，不過list類型是不可哈希的（不能作為字典的鍵），這類場景下可以將list轉換為tuple後進行使用。

dict

dict的fromkeys方法可以用於初始化擁有同一個默認值的字典。
counter = dict.fromkeys("abc", 0)

for ch in "abccaaa":
 counter[ch] += 1

assert counter == {"a": 4, "b": 1, "c": 2}

初始化dict的另一個常用方法是使用字典推導式。
counter = {ch: count for ch, count in [("a", 1), ("b", 2), ("c", 3)]}
assert counter == {"a": 1, "b": 2, "c": 3}


set

Python 的set類型原生支持使用常見的運算符進行集合運算。
a, b = set([1, 2, 3]), set([2, 3, 4])
assert a & b == {2, 3} # 交集
assert a | b == {1, 2, 3, 4} # 並集
assert a - b == {1} # 差集
assert {2, 3} < a # 子集判斷
assert a > {1} # 超集判斷


str

有大量的算法題目涉及到字符串及其處理，Python 的str類型擁有大量的用途多樣的內置方法，主要分為三個類型。

檢查字符串類型

str.isalnum # 是否為字母或數字
str.isalpha # 是否為字母
str.isascii # 是否屬於ASCII字符集
str.isdecimal # 是否為十進制值數字
str.isdigit # 是否為數字，支持其他Unicode數字，例如"①"
str.isidentifier # 是否為Python關鍵字
str.islower # 是否為小寫字母
str.isnumeric # 是否為數字，包括一些Unicode數字，例如"½"
str.isprintable # 是否為可打印字符
str.isspace # 是否為空格
str.istitle # 是否為標題（一個大寫字母後面跟0個及以上的小寫字母）
str.isupper # 是否為大寫字母


根據內容返回新的字符串

str.translate # 使用一個映射關系轉換字符串
assert "acbbc".translate(str.maketrans("abc", "xyz")) == "xzyyz"

str.replace # 替換子串
str.upper # 轉大寫
str.lower # 轉小寫

str.zfill # 左側填0
assert "abc".zfill(5) == "00abc"

str.capitalize # 首字母大寫，其他字母小寫
assert "aBC cAA".capitalize() == "Abc caa"

str.titie # 每個單詞首字母大寫，其他字母小寫
assert "aBC cAA".title() == "Abc Caa"

str.swapcase # 大寫變小寫，小寫變大寫
assert "aBC cAb".swapcase() == "Abc CaB"


拆分為多個子串

str.split # 使用指定分隔符拆分字符串
str.splitline # 按換行符拆分字符串

str.partition # 使用指定分隔符將字符串拆分為三段
assert "A B C".partition(" ") == ("A", " ", "B C")

此外還有str.join方法，可以用指定分隔符將多個字符串合並為一個。

complex

Python 原生提供復數類型complex，並支持常見的算術運算。
c = complex(1, -1)
assert c.real == 1
assert c.imag == -1

assert complex(1, 1) * complex(1, -1) == 2



本期的第二部分的主題是 Python 的內置函數，並根據函數的參數類型和返回類型將內置函數分為對象類和容器（迭代器）類。

對象類

對象類的內置函數主要涉及具體類型的對象的處理。

abs

計算絕對值。

max, min

返回多個值（或一個可迭代對象）的最大值或最小值。

chr, ord

數字和 ASCII 字符的相互轉換。
chr(ord("a") + 1) == "b"


divmod

同時獲取整數除法運算的商和余數。
assert divmod(5, 2) == (2, 1)


hex

獲取整數的十六進制表達。
assert hex(255) == "0xff"


pow

求冪。
assert pow(2, 3) == 8


round

浮點數取整（四捨六入五成雙）。
assert round(1.2) == 1
assert round(1.6) == 2
assert round(1.5) == 2
assert round(2.5) == 2


容器、迭代器類

容器、迭代器類的內置函數用於處理和生成各類容器對象和迭代器對象。

all

所有元素為真值時返回True
assert all(x < 10 for x in [1, 2, 3])
assert not all(x < 10 for x in [1, 2, 3, 11])


any

任一元素為真值時返回True
assert any(x < 10 for x in [11, 9, 12])
assert not any(x < 10 for x in [11, 12, 13])


next

獲取可迭代對象的下一個元素，常用於獲取收個滿足條件的元素(為防止不存在符合條件的元素，可以跟一個兜底的值)。
assert next(x for x in range(1, 10) if x % 3 == 0) == 3
assert next(itertools.chain((x for x in [1, 2, 4, 7] if x % 3 == 0), iter([-1]))) == -1


enumerate

遍歷容器，返回一個迭代索引和值的生成器（一般用在 for 循環中）。
assert dict(enumerate("abc")) == {0: "a", 1: "b", 2: "c"}

for index, ch in enumerate("abc"):
 pass


map

將指定函數應用到容器的每一個值，返回一個生成器（而不是列表）。一般使用列表推導式替代map函數，效率更高。

filter

使用指定函數測試容器的每一個值，過濾出函數值為真值的元素，返回一個生成器（而不是列表）。

range

獲取可迭代的整數區間。

sum

獲取容器或可迭代對象所有元素的和

sorted

對可迭代對象的值進行排序，返回一個列表，可指定排序方式，可返回倒序列表。
assert sorted(range(10), key=lambda x: x % 3) == [0, 3, 6, 9, 1, 4, 7, 2, 5, 8]
assert sorted([1, 3, 5, 2, 4], reverse=True) == [5, 4, 3, 2, 1]


zip

傳入多個可迭代對象，按順序將每個參數的相同索引的元素組合為一個tuple對象迭代生成。
assert list(zip(range(4), "abcd")) == [(0, "a"), (1, "b"), (2, "c"), (3, "d")]

可以使用 zip 方法進行矩陣轉置。
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
assert [list(row) for row in zip(*matrix)] == [[1, 4, 7], [2, 5, 8], [3, 6, 9]]


總結

Python 的原生類型和內置函數是很強大，值得深入研究一下。