Python 常用数据结构

数值

Python 用 inf 来表示
在 Python 3.10 及更高版本中，int 类型新增了一个名为 bit_count() 的方法，用于计算整数的二进制表示中 1 的个数。

num = 5
num.bit_count()

数据结构

字符串

str.upper():将字符串中的所有字符转换为大写。
str.lower():将字符串中的所有字符转换为小写。
str.strip():移除字符串首尾的空白字符（包括空格、制表符、换行符等）。
str.lstrip():移除字符串开头的空白字符。
str.rstrip():移除字符串末尾的空白字符。
str.split(sep=None, maxsplit=-1):将字符串分割成子字符串列表，默认使用空白字符作为分隔符。可以通过 sep 参数指定其他分隔符，并通过 maxsplit 参数限制分割次数。
str.join(iterable):将可迭代对象中的元素连接成一个字符串，元素之间用当前字符串作为分隔符。
str.replace(old, new, count=-1):将字符串中的 old 子字符串替换为 new 子字符串。可以通过 count 参数限制替换次数。
str.find(sub, start=0, end=len(string)):返回子字符串 sub 在字符串中首次出现的位置。如果未找到，返回 -1。
str.index(sub, start=0, end=len(string)):返回子字符串 sub 在字符串中首次出现的位置。如果未找到，抛出 ValueError。
str.startswith(prefix, start=0, end=len(string)):检查字符串是否以指定的前缀 prefix 开头。
str.endswith(suffix, start=0, end=len(string)):检查字符串是否以指定的后缀 suffix 结尾。
str.format(*args, **kwargs):格式化字符串，可以插入变量或表达式的值。
str.isalpha():检查字符串是否只包含字母。
str.isdigit():检查字符串是否只包含数字。
str.isalnum():检查字符串是否只包含字母和数字。
str.count(sub, start=0, end=len(string)):返回子字符串 sub 在字符串中出现的次数。
str.capitalize():将字符串的第一个字符转换为大写，其余字符转换为小写。
str.title():将字符串中每个单词的首字母转换为大写。

操作符	实例
+	a + b 输出结果： HelloPython
*	a*2 输出结果：HelloHello
[]	a[1] 输出结果 e
[ : ]	a[1:4] 输出结果 ell
in	’H’ in a 输出结果 True
not in	’M’ not in a 输出结果 True
r/R	`print( r'\n' ) print( R'\n' )`
%	请看下一节内容。

其他资料：

列表

对 list 的切片进行 reverse 没有用
l 进行 reverse，再复制回去。否则就头尾对换。
list.reverse() 原地 reverse
判断回文，非原地 reverse 后比较，或者 list[:: -1] == list

map

defaultdict

from collections import defaultdict
dict1 = defaultdict(int)
dict2 = defaultdict(set)
dict3 = defaultdict(str)
dict4 = defaultdict(list)

dict 对象

dict.clear(): 移除字典中的所有元素。
dict.copy(): 返回字典的浅拷贝。
dict.fromkeys(seq[, value]): 创建一个新的字典，以序列 seq 中的元素作为键，可选参数 value 作为值。
dict.get(key[, default]): 返回指定键的值，如果键不存在，则返回 default 值（默认为 None）。
dict.items(): 返回字典的键值对视图对象，可以用于迭代。
dict.keys(): 返回字典的键视图对象，可以用于迭代。
dict.values(): 返回字典的值视图对象，可以用于迭代。
dict.pop(key[, default]): 移除并返回指定键的值。如果键不存在，则返回 default 值（如果提供了 default 参数），否则抛出 KeyError。
dict.popitem(): 移除并返回字典中的最后一对键值对。如果字典为空，则抛出 KeyError。
dict.setdefault(key[, default]): 如果键存在于字典中，则返回其值；如果不存在，则插入键并将 default 值设为其值（默认为 None），然后返回该值。
dict.update([other]): 使用另一个字典或键值对更新当前字典。
dict.__contains__(key): 检查字典是否包含指定的键。
dict.__getitem__(key): 获取指定键的值。
dict.__setitem__(key, value): 设置指定键的值。
dict.__delitem__(key): 删除指定键的键值对。
dict.__len__(): 返回字典中键值对的数量。

队列

	功能	线程安全
collections.deque()	双端队列	否
queue.Queue()	普通队列	是，`threading.Lock`
queue.PriorityQueue()	优先级队列	是
queue.LifoQueue()	LIFO 后进先出队列	是

from collections import deque
 
# 创建一个空的 deque
d = deque()
 
# 添加元素
d.append(1)         # 右端添加
d.appendleft(0)     # 左端添加
d.extend([2, 3, 4]) # 右端扩展
d.extendleft([-2, -1]) # 左端扩展，注意顺序
 
# 移除元素
right = d.pop()  # 移除并返回右端元素 4
left = d.popleft()  # 移除并返回左端元素 -1
 
# 获取左右元素
left_element = d[0]
right_element = d[-1]
 
# 旋转 deque
d.rotate(2)  # 向右旋转 2 步
d.rotate(-1)  # 向左旋转 1 步
 
# 其他操作
d.clear()  # 清空 deque
d.insert(2, 'a')  # 在索引 2 处插入 'a'
d.remove('a')  # 移除第一个 'a'
d.reverse()  # 反转 deque

堆

from queue import PriorityQueue 这个是线程安全的
put() 添加，get() 获取并删除(如果没有元素会阻塞住)

import heapq
# 线程不安全
 
# 创建一个空堆
heap = []
 
# heapq.heapify(heap) 在 heap 基础上建堆
 
# 添加元素到堆中
heapq.heappush(heap, (5, 1, 5))  # 根据元祖中元素顺序依次使用优先级
heapq.heappush(heap, (4, 2, 4)) 
heapq.heappush(heap, (3, 1, 5)) 
heapq.heappush(heap, (2, 1, 5)) 
heapq.heappush(heap, (2, 5, 5)) 
 
# 堆顶元素，就是第一个元素
stack_top = heap[0]
 
# 弹出元素
while heap:
    item, priority_a, priority_b = heapq.heappop(heap)
    print(f"Item: {item}, Priority A: {priority_a}, Priority B: {priority_b}")
 
Item: 2, Priority A: 1, Priority B: 5
Item: 2, Priority A: 5, Priority B: 5
Item: 3, Priority A: 1, Priority B: 5
Item: 4, Priority A: 2, Priority B: 4
Item: 5, Priority A: 1, Priority B: 5

如果自定义排序，一种方法是提供一个元素，

算法

排序

sorted 自定义排序函数

from functools import cmp_to_key
 
# 自定义比较函数
def custom_str_compare(x, y):
    if len(x) < len(y):
        return -1
    elif len(x) > len(y):
        return 1
    else:
        return (x > y) - (x < y)
 
strings = ["apple", "banana", "pear", "kiwi"]
sorted_strings = sorted(strings, key=cmp_to_key(custom_str_compare))
 
print(sorted_strings)

优先级队列 heapq 自定义排序函数，参考上面的“堆”部分。

bisect 模块

bisect.bisect_left(a, x, lo=0, hi=len(a)): 在有序列表 a 中找到 x 应该插入的位置，以保持列表的有序性。is the analog of std::lower_bound().
bisect.bisect_right(a, x, lo=0, hi=len(a)): 找到 x 应该插入的位置，以保持列表的有序性。或者，返回右侧第一个 x 的位置。
bisect.bisect(a, x, lo=0, hi=len(a)): 功能等于 bisect_right。
bisect.insort_left(a, x, lo=0, hi=len(a)): 在有序列表 a 中插入 x，以保持列表的有序性。如果 x 已经存在于列表中，则插入到左侧第一个 x 的位置。
bisect.insort_right(a, x, lo=0, hi=len(a)): 与 insort_left 类似，但在存在多个 x 时，插入到右侧第一个 x 的位置。
bisect.insort(a, x, lo=0, hi=len(a)): 功能等于 insort_right

实现 lower-upper-bound

def lower_bound(nums: list, target: int) -> int:
    '''
    return the target lower bound index in nums
    '''
    first, last = 0, len(nums)
    while first < last:
        mid = first + (last - first) // 2
        # 注意此处是小于号
        if nums[mid] < target:
            first = mid + 1
        else:
            last = mid
    return first
 
def upper_bound(nums: list, target: int) -> int:
    '''
    return the first idx in nums when nums[idx] > target
    '''
    first, last = 0, len(nums)
    while first < last:
        mid = first + (last - first) // 2
        # 注意直接把 < 改成 <=
        if nums[mid] <= target:
            first = mid + 1
        else:
            last = mid
    return first

Collections 模块

`namedtuple()`

用途：创建具有命名字段的元组子类。

from collections import namedtuple
 
Point = namedtuple('Point', ['x', 'y'])
p = Point(1, 2)
print(p.x)  # 输出: 1
print(p.y)  # 输出: 2

`deque`

用途：双端队列，支持从两端高效地插入和删除元素。
代码见“队列”部分。

`Counter`

用途：计数器，用于统计元素出现的次数。
常用方法：
- elements()：返回一个迭代器，其中每个元素重复其计数值。
- most_common(n)：返回最常见的 n 个元素及其计数。
- subtract(iterable_or_mapping)：从当前计数器中减去另一个计数器或映射中的值。

from collections import Counter
 
c = Counter('abracadabra')
print(c)  # 输出: Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
print(c.most_common(2))  # 输出: [('a', 5), ('b', 2)]

`OrderedDict`

用途：有序字典，保持元素插入的顺序。
常用方法：
- popitem(last=True)：移除并返回一个 (key, value) 对。如果 last 为 True，则返回最后插入的项；否则返回第一个插入的项。
- move_to_end(key, last=True)：将指定的键移动到有序字典的末尾或开头。

from collections import OrderedDict
 
od = OrderedDict()
od['a'] = 1
od['b'] = 2
od['c'] = 3
print(od)  # 输出: OrderedDict([('a', 1), ('b', 2), ('c', 3)])
od.move_to_end('b')
print(od)  # 输出: OrderedDict([('a', 1), ('c', 3), ('b', 2)])

`defaultdict`

用途：默认字典，当访问不存在的键时，会自动提供一个默认值。

from collections import defaultdict
 
dd = defaultdict(int)
dd['a'] += 1
dd['b'] += 1
print(dd)  # 输出: defaultdict(<class 'int'>, {'a': 1, 'b': 1})

`ChainMap`

用途：将多个映射组合成一个单一的视图。

from collections import ChainMap
 
dict1 = {'a': 1, 'b': 2}
dict2 = {'b': 3, 'c': 4}
cm = ChainMap(dict1, dict2)
print(cm['a'])  # 输出: 1
print(cm['b'])  # 输出: 2
print(cm['c'])  # 输出: 4

`UserDict`, `UserList`, `UserString`

用途：这些类提供了自定义字典、列表和字符串的基类，可以方便地扩展和修改这些数据类型的行为。

from collections import UserDict
 
class MyDict(UserDict):
	def __setitem__(self, key, value):
		super().__setitem__(key, value * 2)
 
d = MyDict()
d['a'] = 1
print(d)  # 输出: {'a': 2}

math 模块

chr() 数字转字符
ord() 字符转数字
math.gcd(a,b) # 最大公约数
abs()、pow()、sum()、max()、min()
divmod(a, b)，获得商和余数(a // b, a % b)
int()、str()、bool()、 float()、long()
hex() 十进制转十六进制
bin() 整数转二进制字符串
oct() 整数转八进制字符串
unichr() 数字转 unicode 字符，仅 Python2
cmp(a,b) 小于、等于、大于=-1, 0, 1
round()

其他常用

排序
- sorted(iterable, cmp=None, key=None, reverse=False) 利用 key 或者 cmp 进行排序。cmp 就相当于 Java 中的判断表达式，key 就是比较的对象。
解压缩
- zip([iterable, ...])
- a,b = [1,2,3],[5,6,7] zip(a,b) ->[(1,5),(2,6),(3,7)]
迭代器
- filter(func, iterable) 使用 func 来筛选 iterable 对象
- filter(lambda x: x%2==0, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
- map(func, iterable) # 将迭代对象依次通过 func 函数
- reduce(lambda x, y: x+y, [1,2,3,4,5]) 使用迭代器 func 进行计算，两个输入参数
- enumerate(sequence, [start=0]) idx 和 item 的迭代对象
逻辑判断
- all(iterable) 所有为 True，则为 True
- any(iterable) 任意为 True，则为 True

lru-cache

@cache #不需移除旧值
def factorial(n):
    return n * factorial(n-1) if n else 1
 
# 不能直接在类的方法上用 lru cache，必须是函数才行
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        import functools
        @functools.lru_cache(None)
        def back_track(s):
            if(not s):
                return True
            res=False
            for i in range(1,len(s)+1):
                if(s[:i] in wordDict):
                    res=back_track(s[i:]) or res
            return res
        return back_track(s)

itertools.combinations

cur = [0]*n # 快捷创建一维数组
 
for c in itertools.combinations(range(len(req)), k):  # 从0-len随机选择k个组合在一起
	for i in c:
        pass

Python 输入

input() print() eval()
raw_input() 将输入数据均看成字符串
有多组输入数据，但没有具体的告诉你有多少组，只是让你对应每组输入，应该怎样输出？

while True: 
	a,b=map(int,input().strip().split())

输入一个整数，告诉我们接下来有多少组数据，然后在输入每组数据的具体值

tcase=int(input().strip())
for case in range(tcase):
	a,b=map(int,input().strip().split())

有多组输入数据，没有具体的告诉你有多少组，但是题目却告诉你遇见什么结束

while True:
	a,b=map(aint,input().strip().split())
	if a==0 and b==0:
		break

输入有多组，并却题目告诉你每组输入遇见什么结束，与第三种不同之处在于，每组输入都有相应的细化。

tcase = int(input().strip())
for case in range(tcase):
    a, b = map(int, input().strip().split())
    if a == 0 and b == 0:
        break

这次的输入实现输入一个整数，告诉我们有多少行，在输入每一行。对于每一行的输入，有划分为第一个数和其他的数，第一个数代表那一组数据一共有多少输入。

tcase = int(input().strip())
for case in range(tcase):
    data = map(int, input().strip().split())
    n, array = data[0], data[1:]    
    sum = 0
    for i in range(n):
        sum += array[i]

列表

class Solution:
    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
        points = set() # set 可以使用元组的方式判断是否存在某个点
        row, col, diagonal, antiDiagonal = Counter(), Counter(), Counter(), Counter() 
		# 使用Counter代替字典，可以直接进行+1操作，不用判断是否存在
		# 同样直接 if row[x] 就可以判断是否存在并且是否不等于0，代码更舒畅
        for r, c in lamps:
            if (r, c) in points:
                continue
            points.add((r, c))
            row[r] += 1
            col[c] += 1
            diagonal[r - c] += 1
            antiDiagonal[r + c] += 1
 
        ans = [0] * len(queries)
        for i, (r, c) in enumerate(queries):
            if row[r] or col[c] or diagonal[r - c] or antiDiagonal[r + c]:
                ans[i] = 1
            for x in range(r - 1, r + 2):
                for y in range(c - 1, c + 2):
                    if x < 0 or y < 0 or x >= n or y >= n or (x, y) not in points:
                        continue
                    points.remove((x, y))
                    row[x] -= 1
                    col[y] -= 1
                    diagonal[x - y] -= 1
                    antiDiagonal[x + y] -= 1
        return ans

s.isssubset(s2)

用不到的内置函数

Python 内置函数 | 菜鸟教程
用不到的
isinstance() basestring() execfile() issubclass() staticmethod()
file()
type()
reload()重新加载模块/包
vars(object)查看所有属性
locals()查看当前局部变量
dir()模块的属性列表
id()对象的内存地址
iter()创建迭代器对象
frozenset(iterable)冻结集合，不可变
next(iterable[, default])迭代器的下个对象，没有，使用默认值
open()
bytearray()
callable()
property()
format()
super()
classmethod()
getattr()
repr()
globals()
compile()
hasattr()
memoryview()
import()
complex()
hash()
delattr()
help()
setattr()
object()

🪴 Obsidian Publish

探索

Python 常用数据结构

数值

数据结构

字符串

列表

map

队列

堆

算法

排序

bisect 模块

实现 lower-upper-bound

Collections 模块

`namedtuple()`

`deque`

`Counter`

`OrderedDict`

`defaultdict`

`ChainMap`

`UserDict`, `UserList`, `UserString`

math 模块

其他常用

itertools.combinations

Python 输入

列表

用不到的内置函数

目录

反向链接

🪴 Obsidian Publish

探索

Python 常用数据结构

数值

数据结构

字符串

列表

map

队列

堆

算法

排序

bisect 模块

实现 lower-upper-bound

Collections 模块

namedtuple()

deque

Counter

OrderedDict

defaultdict

ChainMap

UserDict, UserList, UserString

math 模块

其他常用

itertools.combinations

Python 输入

列表

用不到的内置函数

目录

反向链接

`namedtuple()`

`deque`

`Counter`

`OrderedDict`

`defaultdict`

`ChainMap`

`UserDict`, `UserList`, `UserString`