Python一些常用操作

February 18, 2025

intervals.sort(key=lambda p: p[0])

LC 189 [:]切片操作

dict

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
# 包含初始键值对的字典
filled_dict = {'key1': 'value1', 'key2': 'value2'}

# 使用 dict() 构造函数
constructed_dict = dict(key1='value1', key2='value2')

valueList=list(filled_dict.values())

my_dict = {'apple': 1, 'banana': 2, 'cherry': 3}
for key in my_dict.keys():
    print(f"Key: {key}")

LC 49

defaultdict

defaultdict(int) 更适合一般的需要“键不存在时给默认值”的场景，不一定都是计数。

1
2
3
dd = defaultdict(int)  # int 类型，缺省值为 0
dd = defaultdict(lambda: 'default_value')
defaultdict(lambda: [0, 0]) # key 为一个数组

Counter

Counter 更适合对可迭代对象做频次统计、出现次数分析等，它自带的计数方法可以让实现许多场景更为简洁。Counter(p)表示从一个iterable创建计数器。

Iterable: list, tuple, str, dict, set, range, enumerate, map

del cnt[x] 删除对于x的计数。len(cnt)获取一共给几个元素计数。

新建一个 Counter

1
collections.Counter(nums)

list

index()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
numbers = [1, 2, 3, 4, 5]

# 查找数字3的位置
position = numbers.index(3)
print(position)  # 输出: 2

# 在索引1到4之间查找数字3
position = numbers.index(3, 1, 4)
print(position)  # 输出: 2

# 尝试查找不存在的数字
try:
    position = numbers.index(7)
except ValueError as e:
    print("Not found")  # 输出: Not found

sort()

它直接在原列表上进行排序操作，不创建新的列表。只能应用于列表。

字符串比较大小

与长度无关

1
print("apple" < "apricot")  # False

iterable

Iterable: list, tuple, str, dict, set, range, enumerate, map sorted(iterable)返回一个新的已排序列表。原始的可迭代对象不会被修改。时间复杂度为O(nlogn)

deque = collections.deque()

ACM模式

知乎整理

zip

1
2
3
4
5
names = ['Alice', 'Bob', 'Charlie']
scores = [90, 85, 88]

zipped = zip(names, scores)
print(list(zipped))

输出: [(‘Alice’, 90), (‘Bob’, 85), (‘Charlie’, 88)]

heapq

1
2
3
4
5
6
7
import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heap)  # 输出: [1, 3, 2]

对于单个元素：如果元素是可比较的（例如整数、浮点数等），那么堆会根据元素的大小进行排序，最小的元素位于堆顶。
对于元组元素：当元素是元组时，堆会首先比较元组的第一个元素。如果第一个元素相等，再比较第二个元素，以此类推。在你给出的代码中，压入堆的元素是 (value, key) 元组，堆会根据 value（即元素出现的频率）进行排序，value 最小的元素位于堆顶。

heapify(pq) 的作用是将任意列表转换为合法的最小堆，时间复杂度为 O (n)。

转换后： pq[0] 是最小值。
其他元素的位置满足堆性质，但不保证整体有序。

除法

python3 的地板除 “//” 是整数除法， “-3 // 2 = -2” ；向下取整

python3 的除法 “/” 是浮点除法， “-3 / 2 = -1.5” ；

而其他语言的除法是向零取整。在 Python 中要这样写：

int(a/float(b))

这里的 int 取整，是向零取整

负数

isdigit()无法判断负数，应该这样判断：

x.lstrip(’-’).isdigit()

注意如果想改变 x, 需要用 x=x.lstrip(c)

sort

1
ListNode.__lt__ = lambda a, b: a.val < b.val  # 让堆可以比较节点大小

前K个高频单词

字典排序

通过投票对团队排名

sorted(dict) 会对字典的**键(keys)**进行排序,返回排序后的键列表

Complexity

heap

heapify: Time: O(k)
heapq.heappush: Time&Space: O(logK)

Recursion

merge sort: T(n)=2T(n/2)+T(n)=T(nLogn)
S(n)=S(logn)

LC 23: T(k)=2T(k/2)+O(n)=T(nLogK)

Sorted List

插入 / 删除操作：SortedList 的时间复杂度是 O (log n)
- sl.add(x)
- sl.remove(x) / sl.discard(x)：删除元素。
- sl.pop(index=-1)：根据索引删除元素。
SortedList 支持 O (1) 时间复杂度的随机访问
- sl[i] 是 $O(1)$ 的

SortedDict

二分搜索 Key：$O(\log N)$
- sd.bisect_left(key)：在有序的键上搜索索引。
- sd.peekitem(index)：以 $O(\log N)$ 时间返回 (key, value) 元组

1. 我的日程安排表 I

矩阵的深拷贝

result = [row[:] for row in matrix]

split

绝大多数算法题 / 数据处理：优先使用 .split()。它能帮你自动清洗掉多余的换行符、缩进和连续空格，直接拿到干净的单词或数字列表。

只有在特定格式解析（如 CSV / 定长文本）：当"空列/空字段"有明确业务含义，需要精确按列对齐时，才使用 .split(' ') 或 .split(',')。

map

字符串相乘
map(str, res)把int数组转换为str数组

二进制

n&1==1, 代表最低位是1。 n&2=2, 代表倒数第二位是1

运算符优先级陷阱：`<<` 与 `-`

在 Python 中，减法 - 的优先级高于左移 <<。因此：

1
return 1 << rh - 1  # 错误在这里！

会被解析成 1 << (rh - 1)，即 $2^{rh - 1}$。

但满二叉树节点数量的公式是 $2^{rh} - 1$，正确写法应加括号：

1
return (1 << rh) - 1

MOD

分裂二叉树的最大乘积
这个取模不能在取最大值的时候就取，要先取最大值，最后再取模

Master Theorem

$T(N) = aT(N/b) + O(N^d)$

三种情况及结论（简化版 $f(N) = O(N^d)$）

关系	主导方	时间复杂度 $T(N)$	经典算法代表
$\log_b a > d$	叶子节点主导（底层的子问题太多了）	$O(N^{\log_b a})$	矩阵乘法 Strassen 算法
$\log_b a = d$	每一层均匀分布（工作量平摊在每层）	$O(N^d \log N)$	归并排序、二分查找
$\log_b a < d$	根节点主导（顶层的额外花费 $f(N)$ 太大）	$O(f(N))$ 即 $O(N^d)$	比较少见的非均衡划分

① 二分查找 (Binary Search)

递推式：$T(N) = T(N/2) + O(1)$

参数：$a=1, b=2, d=0$

比较：$\log_2 1 = 0$，与 $d=0$ 相等（情况 2）

结论：$O(N^0 \log N) = O(\log N)$

② 归并排序 / 树的层序分治

递推式：$T(N) = 2T(N/2) + O(N)$

参数：$a=2, b=2, d=1$

比较：$\log_2 2 = 1$，与 $d=1$ 相等（情况 2）

结论：$O(N^1 \log N) = O(N \log N)$

③ 汉诺塔 / 满二叉树遍历

递推式：$T(N) = 2T(N/2) + O(1)$

参数：$a=2, b=2, d=0$

比较：$\log_2 2 = 1 > d=0$（情况 1）

结论：$O(N^{\log_2 2}) = O(N)$

sorted 和字典：排序依据与返回元素

字典的 key 是键；sorted 的 key= 参数是计算排序依据的函数，两者不是同一个概念。

sorted(iterable, key=...) 返回一个新列表，不修改原对象。key= 只决定如何比较元素，不会把元素变成它返回的排序依据。

对字典排序，默认得到键列表

1
2
3
4
outgoing = {"alice": 30, "bob": 50, "carol": 30}

sorted(outgoing)
sorted(outgoing.keys())

两种写法都返回 ["alice", "bob", "carol"]。直接遍历字典，拿到的是键。

按金额降序、账户名升序排序：

1
2
3
4
ranked_accounts = sorted(
    outgoing,
    key=lambda account_id: (-outgoing[account_id], account_id),
)

结果是 ["bob", "alice", "carol"]，仍然是账户名列表。

排序依据分别为 (-30, "alice")、(-50, "bob")、(-30, "carol")。Python 按元组从左到右比较：金额取负使大金额排在前面，金额相同再按账户名字典序升序排列。

遍历时只接收账户名，再查金额：

1
2
3
4
result = []
for account_id in ranked_accounts[:2]:
    amount = outgoing[account_id]
    result.append(f"{account_id} ({amount})")

结果是 ["bob (50)", "alice (30)"]。

对 items() 排序，得到键值对列表

outgoing.items() 中每个元素是 (account_id, amount)，因此排序函数接收的也是这个二元组。

1
2
3
4
5
6
7
8
ranked_items = sorted(
    outgoing.items(),
    key=lambda item: (-item[1], item[0]),
)

result = []
for account_id, amount in ranked_items[:2]:
    result.append(f"{account_id} ({amount})")

ranked_items 是 [("bob", 50), ("alice", 30), ("carol", 30)]。此时循环可以解包，顺序是键在前、值在后。

两个容易混用的地方

对字典直接排序后，不能用 for amount, account_id in ranked_accounts：每个元素是字符串，Python 会尝试把字符串的字符解包给两个变量。加括号也不会改变元素类型。

改为 .items() 后，不能继续写 key=lambda item: (-outgoing[item], item)：此时 item 是 ("alice", 30) 这样的元组，而字典的键是 "alice"，用整个元组查字典会产生 KeyError。应直接读取 item[1] 作为金额、item[0] 作为账户名。

记住：排序输入决定结果元素的类型；key= 只决定这些元素的排列顺序。