LeetCode 中的 Python
Python in LeetCode
在这里不写特别基础的语法，主要是写 LeetCode 遇到的一些可用的 api
自己是 cpp 学起的，难免有点 cpp 的代码思维，这里放一点地道的 python 写法指南
1 语法
1.1 for
在 py 中有一个坑，for 语法内部改变的 i 是不会影响外层的迭代的
for i in range(9):
...
i = 9 # 实际上没有作用，仍然是循环 9 次1.2 while
while 有一个 else 的用法，表示没有经过 break 的正常语法结束
i = 0
while i < 3:
print(i)
i += 1
else:
print("loop finished normally") # 会被答打印，因为不是由于 break 退出的1.3 lambda 表达式
实现临时函数的功能
lambda 参数列表: 表达式
# 等价于
def f(参数列表):
return 表达式lambda 的返回值永远是那个表达式，没法更细化的自定义，例如用三元表达式实现条件判断逻辑
lambda x: x if x > 0 else -x1.4 数值
python 中的 int 是无限精度的，所以没有最小值，一般这么指定最小值
ret = float("-inf")1.5 位运算
python 中的位运算和 c++ 的差异不是特别大
| 运算 | 符号 | 含义 | 示例 | ||
|---|---|---|---|---|---|
| 按位与 | & | 两位都为 1 才为 1 | 5 & 3 = 1 | ||
| 按位或 | \ | 有一位为 1 即为 1 | 5 \ | 3 = 7 | |
| 按位异或 | ^ | 两位不同为 1 | 5 ^ 3 = 6 | ||
| 按位取反 | ~ | 逐位取反 | ~5 = -6 | ||
| 左移 | << | 左移并补 0 | 5 << 1 = 10 | ||
| 右移 | >> | 算术右移 | 5 >> 1 = 2 |
位运算有一些神奇的用法
例如 XOR（异或）可以在 LeetCode 136 中使用
1.6 深拷贝与浅拷贝
python 中的 copy 库可以对对象进行拷贝
copy 只复制容器本身，子对象仍共享； deepcopy 递归复制整个对象结构，完全独立
list 的 copy 方法就是 浅拷贝
import copy
b = [2, 3]
a = [1, b]
a1 = copy.copy(a) # a1 = a.copy() 也是同样的效果
a2 = copy.deepcopy(a)
b.append(4)
print(a) # [1, [2, 3, 4]]
print(a1) # [1, [2, 3, 4]] ← 被一起改了
print(a2) # [1, [2, 3]] ← 不受影响2 常规数据结构
2.1 list
2.1.1 增删改查
增加：支持末尾和中间
l.insert(k, x) 表示的是把 x 插入到当前的 k 下标的左侧，原来的从 k 开始的元素全部向后移动一位
如果插入的位置 k > len(l) 则会直接 append 到队伍尾部
lst = [1, 2]
lst.append(3) # [1,2,3] # 在末尾增加一个元素
lst.extend([4, 5]) # [1,2,3,4,5] # 在末尾增添一组元素
lst.insert(1, 99) # [1,99,2,3,4,5] 在索引 1 之前加一个元素删除：
lst = [1, 2, 3, 2]
lst.remove(2) # [1,3,2] # 删除第一个等于 2 的元素，找不到会报错
x = lst.pop() # x=2, lst=[1,3] # 删除最后一个元素
del lst[0] # lst=[3] # 按照索引删除2.1.2 数组分配内存
这里有个坑就是对于二维以上的分配，是不同的写法
n = 10
lst = [0] * n # 这是分配一个 size 的 10 的 list
dp = [[0] * n for _ in range(m)] # 这是二维的分配方法这个的含义是创建 1 个长度为 n 的 list，然后让 m 个元素都指向它，是引用复制
dp = [[0] * n] * m # 错误用法那为什么一维不会出错呢？ 因为一维是 int 元素而不是 list的引用，不是指向同一个容器
2.1.3 访问数组下标
对于 cpp 中用索引访问的方式，使用 enumerate：
当然用 range也行（我更习惯这个）
nums = [10, 20, 30]
for i, num in enumerate(nums):
print(i ,num)2.1.4 list 排序
（默认升序）排序用 nums.sort()，也有更加通用的自定义算法，结合 lambda 表达式使用参数 key=
# 初等用法
arr = [(1, 3), (2, 1), (4, 2)]
arr.sort(key=lambda x: x[1])
# [(2, 1), (4, 2), (1, 3)]也有多关键字排序算法，如果第一个比较相同，就去执行第二个的比较
arr.sort(key=lambda x: (key1, key2, key3)) # 对 tuple 进行字典序排序
# 首先按起点排序，如果起点相同按终点排序
intervals = [[1, 3], [2, 6], [1, 2]]
intervals.sort(key=lambda x: (x[0], x[1]))
# [[1, 2], [1, 3], [2, 6]]
arr.sort(key=lambda x: (x[0], -x[1])) # 起点升序，终点降序
# [(1, 3), (1, 1), (2, 2)]2.1.5 二分查找
import bisect
a = [1, 2, 2, 2, 4, 5]
bisect.bisect_left(a, 2) # 1
bisect.bisect_right(a, 2) # 4
# 判断元素是否存在
i = bisect.bisect_left(a, x)
exists = i < len(a) and a[i] == x
# 查找给定数字的一个区间
l = bisect.bisect_left(a, x)
r = bisect.bisect_right(a, x) - 1
# 自定义比较法
a = [(x.val, x) for x in arr] # 重新构建为字典
bisect.bisect_left(a, (target, -inf)) # 根据 (target, -inf) 依次比较， -inf 为了不影响左边界2.1.6 数组求和
sum(lst) # 直接求
sum(x for x in lst if x > 0) # 条件遍历求和2.1.7 模拟栈
栈使用的是 list 并且有以下几种 api 来执行相似的操作
同时需要注意一下几点：
- 用
-1来访问top - 巨大的语言差异：
python中的pop是会返回被弹出的数据的
stk = []
stk.append(x) # push
top = stk[-1] # top
top = stk.pop() # pop, 注意这个值是会被返回的2.2 dict
2.2.1 增删改查
添加元素一般有两种方式
a = {}
a['a'] = 1 # 直接赋值
a.setdefault('a', 1) # 如果不存在，就赋值为1删除元素使用 del 但是需要保证 key 存在
等价于在 cpp 中使用 mp.erase(key); 但是 cpp 不存在的时候不会报错
d = {"a": 1, "b": 2}
del d["a"]
d.pop("a") # 返回被删的 value
d.pop("x", None) # key 不存在时不报错
d.clear() # 清空2.2.2 排序
字典排序实际上不是对字典本身排序，而是通过排序创建一个新的 list 或者一个新的 dict
mp = {'b': 2, 'a': 3, 'c': 1}
sorted(mp.items())
# 按照键排序 [('a', 3), ('b', 2), ('c', 1)]
sorted(mp.items(), key=lambda kv: kv[1])
# 按照值排序 [('c', 1), ('b', 2), ('a', 3)]
sorted(mp.items(), key=lambda kv: (-kv[1], kv[0]))
# 频率高在前面，次数相同用字典序2.2.3 defaultdict
这是一个 dict 的子类型，增加了默认构建值的功能
这个功能只会在读取的时候生效，写入的时候和普通字典完全一致
from collections import defaultdict
d = defaultdict(int)
x = d['a']
# 如果不存在 'a' 这个键,类似于这个步骤
if 'a' not in d:
d['a'] = int() # 这里才调用
x = d['a']这里的初始化参数的意义是，如果访问一个不存在的值，就调用 int()，所以参数必须是一个可以调用的函数类似的东西
2.3 str
str 是不可修改的，这是最大最主要的和 cpp 的区别
下面都使用 s = "hello world" 的字符串作为演示
2.3.1 ASCII 码转化
python 中没有 char 类型，直接进行 str 转化就可以拿到 unicode 的编码（包含 ASCII 码在其中）
ord('A') # 65
ord('a') # 97
ord('0') # 48
ord('\n') # 10
chr(65) # 'A'
chr(97) # 'a'
chr(48) # '0'2.3.2 求子串
用切片（切片是左闭右开的）
s[start:end:step]
s[0:5] # 'hello'
s[:5] # 'hello'
s[6:] # 'world'
s[::-1] # 'dlrow olleh'（反转）2.3.3 大小写转化
s.upper() # 'HELLO WORLD'
s.lower() # 'hello world'
s.capitalize() # 'Hello world'
s.title() # 'Hello World'
s.swapcase() # 'HELLO WORLD' -> 'hello world'2.3.4 查找
s.find("world") # 6，找不到返回 -1
# 是否存在于
"world" in s # True2.3.5 替换，修改
s.replace("world", "python") # 'hello python'2.3.6 去除字符
"xxhelloxx".strip("x") # 'hello'2.3.7 分割与拼接
s = "a,b,c"
s.split(",") # ['a', 'b', 'c']
lst = ["a", "b", "c"]
",".join(lst) # 'a,b,c'2.3.8 多次修改
因为 python 中没有办法原地修改某一个字符，所以这里特地写一下怎么等价实现这种方式
- 使用切片，一次修改
O(n)
s = "abcd"
i = 3
s = s[:i] + 'X' + s[i+1:]- 转化
list，在频繁修改的时候比较好用，单次修改O(1), 合并O(n)
s = "abcd"
lst = list(s)
lst[3] = 'X'
s = "".join(lst)2.4 set
就是哈希，只有 key，没有 value
下面是常用的创建，增删，查找操作
s = set() # 空集合
s = {1, 2, 3} # 字面量
s = set([1, 2, 2, 3]) # 自动去重
s = set("abc") # {'a', 'b', 'c'}
s.add(x) # 添加单个元素
s.update([a, b, c]) # 批量添加（可迭代对象）
s.discard(x) # x 不存在不会报错 remove 会报错
s.pop() # 随机弹出一个元素
s.clear() # 清空
x in s # O(1)，最常用
x not in s
len(s)2.5 tuple
tuple 在 python 中类似于一个不可以修改的list，但是如果要让 hash 的 key 是类似于 list 的方式就只能使用 tuple
一般来说我们会先写一个 list 随后 tuple 化
a = [1, 2, 3]
a[1] = 3
t = tuple(a)3 API 数据结构
collections中一般来说， 数据类型会被写成首字母大写，但是deque,defaultdict这种除外，这种属于历史遗留问题
3.1 deque
这是一个双端队列，默认的话是左进右出的，访问数据方式也等同于 list
from collections import deque
q = deque()
q.append(x) # 右入
q.appendleft(x) # 左入
q.pop() # 右出
q.popleft() # 左出
# 访问
left = q[0] # 左端
right = q[-1] # 右端3.2 OrderedDict
这个主要用于 LRU 的内部数据结构，是 hash + 双向链表
from collections import OrderedDict
od = OrderedDict()
od[key] = val # 插入（默认在末尾）
od.move_to_end(key) # 刷新为最近使用
od.pop(key) # 删除任意 key
od.popitem(last=True) # 默认，删末尾
od.popitem(last=False) # 删头部
od.popitem(last=False) # 弹出最久未使用（LRU）3.3 heapq
这个 api 的操作方式不是创建一个类，而是对已有的 list 进行建堆以及执行其他操作
Top - K 常用数据结构，这个是小顶堆，一般建议要会写这个底层实现的
heap = []
heapq.heappush(heap, x) # 入堆
x = heapq.heappop(heap) # 弹出最小值
x = heap[0] # 查看最小值（不弹）
# 替换堆顶
heapq.heapreplace(heap, x)对于大顶堆我们一般用这种构造负 key 的方式，注意 heapq 是按照 tuple 字典序（即相同就比较下一个）
heapq.heappush(heap, (-key, value))
key, value = heapq.heappop(heap)
key = -key3.4 Counter
用来统计一个 list 中出现的次数
from collections import Counter
nums = [1, 1, 2, 2, 2, 3]
cnt = Counter(nums)
cnt[2] # 3
cnt[99] # 0 不存在时返回 0，而不是 KeyError
for num, freq in cnt.items():
pass # 访问方式如同字典4 自定义数据结构
4.1 链表
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
dummy = ListNode(0)
dummy.next = head
...