[转]Python编程知识点

Python常见数据结构

• list（列表）
• tuple（元组）
• set（集合）
• dict（字典）
• collections.deque（类似列表的容器，实现了在两端快速添加和弹出）
• collections.Counter（字典的子类，提供了可哈希对象的计数功能）
• collections.defaultdict（字典的子类，提供了一个工厂函数，为字典查询提供一个默认值）
• heapq（堆）
• ...

基本数据结构

列表

test_list = []
test_list.append(2)
test_list.extend([3, 4]) #等价于：test_list += [3, 4]
test_list.insert(0, 1)
test_list.remove(4) #移除列表中某个值的第一个匹配项
test_list.pop(2)
test_list.count(1) #计数
test_list.index(3) #返回列表中第一个匹配项的索引
test_list.sort() #排序(改变自身)
sorted_test_list = sorted(test_list) #不改变原列表，返回排序后的序列
test_list.reverse() #反向列表中元素
test_list_extra = [1, 2]
test_list_final = test_list + test_list_extra #"+"只能用来连接列表，在不改变原有列表的前提下返回一个新列表
#列表直接就可以实现堆栈，（栈是许多表达式计算题的通用解法）
stack = [3, 4, 5]
stack.append(6)
stack.pop()
#列表推导式
squares = [x**2 for x in range(10)]
vec1 = [num for elem in [[1, 2, 3], [4, 5, 6]] for num in elem]

集合

a, b = set('abcbad'), set('ac')
a.add('e')
a.remove('e')
print(a - b, a | b, a & b, a ^ b) #a - b: 差集; a | b: 并集; a & b: 交集; a ^ b: 对称差集(异或)

字典

test_dict = {'zbn': 1, 'sxt': 2}
test_dict['zbn'] = 3 #修改字典元素
del test_dict['zbn'] #删除字典元素
print(test_dict['zbn']) #获取字典元素
test_dict.get('zbn', 0) #获取key为'zbn'的value，如果没有这个key，返回默认值0
test_dict.items() #以列表返回可遍历的(键, 值)元组数组
test_dict.keys() #以列表返回一个字典所有的键
test_dict.values() #以列表返回字典中的所有值
test_dict.pop('zbn') #删除字典给定key所对应的值，返回值为被删除的值
test_dict.popitem() #返回并删除字典中的最后一对键和值。
test_dict.fromkeys(seq, val) #创建一个新字典，以序列seq中元素做字典的键，val为字典所有键对应的初始值
sorted(test_dict) #按key排序。
sorted(test_dict.items(), key = lambda kv:(kv[1], kv[0])) #按value排序

字符串

name = 'hello world'
print('hello' in name) #判断内容是否存在字符串中
print(name.endswith('d')) #判断是否以d结尾,执行结果为布尔值
print(name.startswith('h')) #判断是否以h开头,执行结果为布尔值
print('ab123'.isalnum()) #判断输入的字符串是否包含数字和字母，返回结果为布尔值
print('abcdA'.isalpha()) #判断输入的字符串是否是英文字母，返回结果为布尔值
print('123'.isdigit()) #判断输入的字符串是否是数字，返回结果为布尔值
print('  hello '.lstrip()) #默认去掉字符串左边的空格和换行，可以指定其他字符
print(' hello  '.rstrip()) #默认去掉字符串右边的空格和换行，可以指定其他字符
print('\n hello '.strip()) #默认去掉两边的空格和换行，可以指定其他字符
print(name.replace('hello', 'hi')) #将字符串中的hello替换为hi（字符串的值不可以直接赋值修改）
print(name.find('world')) #查找字符串的索引
print(name.find('world', 3, 10)) #可以指定查找字符串的范围, 3、10是开始、结束的下标值,下标值顾头不顾尾
print(name.index('o')) #按值查找，执行结果：4
name1 = 'zbn,sxt' #将字符串切割成list
name1_list = name1.split(',') #按照逗号分割字符串，返回结果为list，name1的值未改变
print(name.count('h')) #统计h在字符串中出现的次数，执行结果：1
name = ['a', 'b', 'c']
print('*'.join(name)) #将字符串中的每个元素都使用*号连接，执行结果：a*b*c，返回一个新的变量值
print(ord('A')) # 获取字符ASCII码
name1.upper() # 转大写
name1.lower() # 转小写

# 可以利用正则表达式来帮助抽取或匹配信息
import re
string = ''
re.findall(r'', string) #找到所匹配的所有子串，并返回一个列表，如果没有找到匹配的，则返回空列表
re.match(r'', string) #尝试从字符串的起始位置匹配一个模式
re.search(r'', string) #扫描整个字符串并返回第一个成功的匹配
re.split(r'', string) #按照能够匹配的子串将字符串分割后返回列表, 自带的split函数只能指定一个分割符，需要使用多个分割符时，可以使用re.split()。
re.sub(r'', '', string) #替换字符串中的匹配项

复杂数据结构

1.有序列表(SortedList)

#保持列表始终升序
from sortedcontainers import SortedList
sl = SortedList([3, 1, 5, 6, 2])
sl.add(9)

2.小根堆(heap)

#并不一定有序，但第一个元素始终是最小的
import heapq
heap = [1, 2]
heapq.heapify(heap)
heapq.heappush(heap, 3)
heapq.heappop(heap)
heapq.nlargest(2, heap)
heapq.nsmallest(2, heap)

3.有序字典(OrderedDict)

#有字典特性，插入有顺序（后插入的在末尾）
from collections import OrderedDict
od = OrderedDict()
od.popitem(last=True) #删除最后加入的
od.move_to_end(key, last=True) #将指定key的key-value移到最后

4.双端队列(deque)

#可以理解为左右两端都可以操作的列表
from collections import deque
queue = deque(["a", "b", "c"])
queue.append("d")
queue.appendleft("e")
queue.extend(["d", "e"])
queue.extendleft(["d", "e"])
queue.pop()
queue.popleft()
#只使用append()和popleft()的话就是普通队列(queue)

5.优先队列

from queue import PriorityQueue
Q = PriorityQueue()
Q.put((priority_number, element)) #priority_number为优先级，越小则优先级越高，element为元素本身
_, element = Q.get() # 弹出优先级最高的元素

6.嵌套型数据结构

a = [{'k1': 'v1'}, {'k2': 'v2'}]
b = {'k1': [1, 2, 3], 'k2': [1, 2, 3]}
c = {{'k1': 'v1'}, {'k2': 'v2'}}

7.默认字典

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

8.Counter计数

from collections import Counter
c = Counter(['c', 'h', 'e', 'n', 'k', 'c'])  # Counter({'c': 2, 'h': 1,
# 'e': 1, 'n': 1, 'k': 1})
c.most_common() #返回排序后的结果列表

编程小技巧

二分查找

# Python的二分查找库：bisect
import bisect
a = [5, 6, 8, 8, 9] #前提是列表有序
# 目标元素单次出现：
idx1 = bisect.bisect(a, 6)      #返回大于6的第一个下标 idx1 = 2
idx2 = bisect.bisect_left(a, 6) #返回6的下标 idx2 = 1 
# 目标多次出现：
idx3 = bisect.bisect(a, 8)      #最右边的8的下标+1 idx3 = 4 
idx4 = bisect.bisect_left(a, 8) #最左边的8的下标 idx4 = 2
# 目标没出现过：
idx5 = bisect.bisect(a, 7)      #返回插入后使列表有序的下标 idx5 = 2 
idx6 = bisect.bisect_left(a, 7) #此时和bisect一样 idx6 = 2 

利用lambda表达式实现对某个变量或多个变量进行排序

test_list = [[1, 3, 0], [2, 2, 1], [1, 2, 5], [2, 4, 7]]
sorted_test_list_1 = sorted(test_list, key=lambda x : (x[1]))
sorted_test_list_2 = sorted(test_list, key=lambda x : (x[1], x[2], -x[0])) #先以第二个列表升序排列，再以第三个列表升序排列，最后以第一个列表降序排列
test_dict = {'b': 3, 'c': 1, 'a': 2}
sorted_test_dict = sorted(test_dict.items(), key=lambda x: x[0])

列表按字符串长度排序

str_list = ['abc', 'home', 'apple', 'banana']
print(sorted(str_list, key=len))

any() 与 all()

any(iterable) #若给定的可迭代参数iterable全部为False，则返回False，如果有一个为True，则返回True。元素除了0、空、FALSE外都算True。
all(iterable) #...全部为True，则返回True，有一个为False，则返回False。元素除了是 0、空、False外都算True。

zip的使用

questions = ['name', 'quest', 'favorite color']
answers = ['lancelot', 'the holy grail', 'blue']
for q, a in zip(questions, answers):
    print('What is your {0}? It is {1}.'.format(q, a))

负数的补码形式表示(32位)

if num < 0:
    num = 2 ** 32 + num

转进制函数

#base代表转换前的进制数
int(strOrNum, base) #任意转10进制
bin(int(strOrNum, base)) #任意转2进制
oct(int(strOrNum, base)) #任意转8进制
hex(int(strOrNum, base)) #任意转16进制

zfill(n)可用于二进制字符串补全0

txt = '50'
x = txt.zfill(10)
print(x) #输出0000000050

itertools模块

import itertools as it
#可迭代对象的笛卡儿积
print(list(it.product('12', '34'))) #[('1', '3'), ('1', '4'), ('2', '3'), ('2', '4')]
#全排列
print(list(it.permutations('123'))) #[('1', '2', '3'), ('1', '3', '2'), ('2', '1', '3'), ('2', '3', '1'), ('3', '1', '2'), ('3', '2', '1')]
#可迭代对象所有的长度为r的子序列
print(list(it.combinations(range(4), 2))) #[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

算法相关知识

1.单调栈

在栈的「先进后出」规则基础上，要求「从栈顶到栈底的元素是单调递增（或者单调递减）。
重要性质：使用单调栈可以找到元素向左遍历第一个比他小的元素，也可以找到元素向左遍历第一个比他大的元素。
涉及到“寻找下一个更大更小”必选单调栈。

# 单调递增栈模板（递减只需将>改为<）
def monotoneIncreasingStack(nums):
    stack = []
    for num in nums:
        while stack and num > stack[-1]:
            stack.pop()
        stack.append(num)

2.DFS

DFS是“先走到尽头，再回溯继续”的遍历方式。

1. 尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

一般会使用visited数组或新加状态值来标记搜索过程的探寻状态，保证代码不会死循环。

# 模板
def dfs(graph: GraphAdjList, visited: set[Vertex], res: list[Vertex], vet: Vertex):
    """深度优先遍历辅助函数"""
    res.append(vet)  # 记录访问顶点
    visited.add(vet)  # 标记该顶点已被访问
    # 遍历该顶点的所有邻接顶点
    for adjVet in graph.adj_list[vet]:
        if adjVet in visited:
            continue  # 跳过已被访问的顶点
        # 递归访问邻接顶点
        dfs(graph, visited, res, adjVet)
 
def graph_dfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]:
    """深度优先遍历"""
    # 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
    # 顶点遍历序列
    res = []
    # 哈希表，用于记录已被访问过的顶点
    visited = set()
    dfs(graph, visited, res, start_vet)
    return res

3.二分查找

一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。

# 模板
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1  # 定义target在左闭右闭的区间里，[left, right]
 
        while left <= right:
            middle = left + (right - left) // 2
            if nums[middle] > target:
                right = middle - 1  # target在左区间，所以[left, middle - 1]
            elif nums[middle] < target:
                left = middle + 1  # target在右区间，所以[middle + 1, right]
            else:
                return middle  # 数组中找到目标值，直接返回下标
        return -1  # 未找到目标值

4.滑动窗口

滑动窗口算法在一个特定大小的字符串或数组上进行操作，而不在整个字符串和数组上操作，这样就降低了问题的复杂度，从而也达到降低了循环的嵌套深度。

# 模板
def sliding_window(nums, target):
    # 1. 初始化：
    # left左指针，right右指针，ans结果变量，初始化值根据实际需要调整，本处都为0
    # indicator为[left, right]窗口的指标，用于与题目target做比较
    left, right = 0, 0
    ans = 0
    indicator = 0
    # 2. 右指针滑动：indicator指标记得改变值
    while right < len(nums):
        indicator += nums[right]
        # 3. 左指针滑动：当indicator不满足要求时，滑动左指针，直至indicator满足题目要求
        while [left, right]窗口的indicator 不满足 target:
            indicator -= nums[left]
            left += 1
        # 4. 记录结果：走到这里表名indicator符合题意，记录结果，一般跟左右指针有关
        ans = func(ans, left, right)
        # 5. 右指针+1：不要忘记
        right += 1
    return ans

5.前缀和

基础技巧

求连续子区间和

• • 若使用0<i<=j<n的遍历，复杂度O(n2)。
  • 若使用前缀和，先遍历一次数组，求与数组元素对应的前缀和数组P。再遍历一次前缀和数据，使用P[j+1] - P[i]求A[i]+...+A[j]
    的连续和，复杂度为O(n)

# 进阶：边求前缀和边计算模板
ans = 0
# 前缀和初始化为0
pre = 0
# 存储结果的字典,明确key:value的含义，需要初始化为{0:1}或{0:-1}
dic = collections.defaultdict(int)
for num in nums:
    # 先计算前缀和
    pre += num
    # 利用dic和pre，以及题目条件k，更新ans结果
    ans += dic[pre - k]
    # 基于pre更新dic
    dic[pre] += 1
return ans

6.并查集

一般用于解决对于给定的多个集合之间的合并和查询问题。

class UnionFind:
    def __init__(self, size):
        self.size = size
        self.parent = [i for i in range(size)]
 
    def find(self, item):
        if self.parent[item] != item:
            self.parent[item] = self.find(self.parent[item])
        return self.parent[item]
 
    def union(self, item1, item2):
        root1, root2 = self.find(item1), self.find(item2)
        if root1 != root2:
            self.parent[root1] = root2
 
    def is_connected(self, item1, item2):
        return self.find(item1) == self.find(item2)