python 切片

示例数组 a = [0, 1, 2, 3, 4, 5]

倒数索引

示例

• a[-1]： 倒数第1个数字，5，等同于正向的a[0]
• a[-2]： 倒数第2个数字，4
• a[-3]： 倒数第3个数字，3

含义

• 所有的负数索引，-n就是倒数第n个数；不像正向索引有0，a[1] 是顺数第2个数。
• -1 则为倒数第一个，不存在 倒数第0个。

前后普通切片

• a[:3]：前3个数字，不包括a[3]，[0, 1, 2]
• a[3:]：从a[3]开始到末尾的所有数字，包括a[3]，[3, 4, 5]
• a[-3:]：从倒数第3个数字开始到末尾 的所有数字，包括a[-3]，[3, 4, 5]
• a[:-3]：从开始到倒数第3个数字的所有数字，不包括a[-3]，[0, 1, 2]

带结束位置的切片

• a[-3:-1]：从倒数第3个数字到倒数第1个数字，不包括a[-1]，[3, 4]

带步长的切片

示例

• a[::-1]：步长为1，从尾向前走，省略了 start和end
  • 倒着走：5,4,3,2,1,0
• a[::1]：步长为1，从前向后走，省略了 start和end
  • 正着走：0,1,2,3,4,5
• a[::2]：步长为2，从前往后走
  • 正着走：0,2,4
• a[::-2]：步长为2，从后往前走
  • 倒着走：5,3,1

步数为负

• 步长-1：从尾向前走，步长为1
• 步长-2：从尾向前走，步长为2

步长为正

• 步长1：从前向后走，步长为1
• 步长2：从前向后走，步长为2

range 函数

提示

range函数

• start (默认为0), stop, step (默认为1)。
• 从start开始，不包含stop，步长为step。

range(n)

• 等价于 range(0,n)，[0, n)，不含n，步长为1

range(n, -1, -1)

• 逆序遍历，从n开始，到-1结束，不含-1，step=-1

统计计数

Counter类统计

from collections import Counter

# 字符计数, p为字符串
cnt_p = Counter(p)   
cnt_s = Counter()  
# 直接判断两个counter是否相似，自动忽视值为0的项
if cnt_p == cnt_s:    
    res.append(left)

defaultdict

from collections import defaultdict

# 前缀和计数
count = defaultdict(int)  
count[0] = 1
count[current_sum] += 1

堆

堆

堆特性

• 堆序性：任意节点的值必须大于等于（或小于等于）其子树中每个节点的值。
• 完全二叉树：除了最后一层，其他层的节点都是满的，最后一层的节点都紧靠左排列。

最大堆/大顶堆

• 根节点是整棵树中最大元素。任意节点的值都大于等于其子节点的值。

最小堆/小顶堆

• 根节点 是整棵树中最小元素。任意节点的值都小于等于其子节点的值。

常见应用场景

• 优先队列
• 堆排序：O(nlogn)
• topk 问题

python 堆用法

• 包：heapq

常用方法

• 列表 -> 堆，默认为最小堆：heapq.heapify(data)

• 入堆：heapq.heappush(data, 3)

  • 如果入堆元素是列表，如(cnt, num)，那么会先比较 第一个元素

• 出堆： val = heapq.heappop(data)

• 入堆并出堆：保证堆大小不变，新入旧出：heapq.heappushpop(data, 3)

• 只获取最小值：直接heap[0]

• 获取n个最大的/最小的：heapq.nlargest(3, data)

最大堆

• 默认为最小堆，把数值全变负数，则为最大堆

操作	时间复杂度	说明
构建堆 (Heapify)	$O(n)$	批量转换一个无序列表
插入 (Push)	$O(\log n)$	需要进行上浮调整
弹出最大值 (Pop)	$O(\log n)$	需要进行下沉调整
获取最大值 (Peek)	$O(1)$	直接访问 heap[0]

import heapq

def test_heap_construct():
    data = [5, 1, 9, 3, 7]
    heapq.heapify(data)  # 原地修改列表，变为堆结构
    print(data[0])       # 输出 1，最小值永远在首位
    print(data)


def test_heap_push_pop():
    heap = []
    heapq.heappush(heap, 3)  
    print(heap)
    heapq.heappush(heap, 1)
    heapq.heappush(heap, 2)
    print(heap)

    val = heapq.heappop(heap)  
    print(val, heap)

def test_heap_getlargest():
    heap = [11, 4, 5, 6, 7]
    heapq.heapify(heap)
    print(heap)
    print(heapq.nlargest(3, heap))  
    print(heapq.nsmallest(3, heap))  
     
def test_maxheap():
    data = [3, 1, 4, 1, 5, 9, 2]
    # 1. 将所有数值取反
    max_heap = [-x for x in data]
    # 2. 让列表具备堆结构 (原地操作，时间复杂度 O(n))
    heapq.heapify(max_heap)
    # 3. 插入元素
    heapq.heappush(max_heap, -6)
    # 4. 获取并弹出最大值
    max_val = -heapq.heappop(max_heap)
    print(f"最大值: {max_val}") # 输出: 9


def run_test_heap():
    # test_heap_construct()
    # test_heap_push_pop()
    # test_heap_getlargest()
    test_maxheap()

队列

队列和栈

栈

• 先进 后出

队列

• 先进 先出

双端队列

• 两边 皆可出

from collections import deque

def demo_deque_basics():
    # 1. 初始化
    # 可以从列表、字符串或其他可迭代对象创建
    dq = deque([1, 2, 3])
    print(f"初始化 deque: {dq}")

    # 2. 右侧操作 (类似 list)
    dq.append(4)           # 添加到末尾
    last = dq.pop()        # 弹出末尾
    print(f"右侧操作后: {dq}, 弹出的值: {last}")

    # 3. 左侧操作 (deque 的杀手锏)
    dq.appendleft(0)       # 添加到开头
    first = dq.popleft()   # 弹出开头
    print(f"左侧操作后: {dq}, 弹出的值: {first}")

    # 4. 访问与长度
    print(f"队首元素: {dq[0]}, 队尾元素: {dq[-1]}, 长度: {len(dq)}")

def demo_deque_advanced():
    dq = deque([1, 2, 3, 4, 5])
    
    # 1. 旋转 (Rotate)
    # 正数：向右旋转；负数：向左旋转
    dq.rotate(1)  # [5, 1, 2, 3, 4]
    print(f"向右旋转 1 位: {dq}")
    dq.rotate(-2) # [2, 3, 4, 5, 1]
    print(f"向左旋转 2 位: {dq}")

    # 2. 限制最大长度 (常用作滑动窗口)
    # 当超过 maxlen 时，新元素加入会导致另一端元素自动弹出
    window = deque(maxlen=3)
    for i in range(5):
        window.append(i)
        print(f"添加 {i} 后的窗口: {list(window)}")

    # 3. 清空
    window.clear()
    print(f"清空后长度: {len(window)}")

if __name__ == "__main__":
    print("--- 基础功能测试 ---")
    demo_deque_basics()
    print("\n--- 进阶功能测试 ---")
    demo_deque_advanced()

栈

# 1. 初始化
stack = []

# 2. 入栈 (Push) - 向栈顶添加元素
# 时间复杂度: O(1)
stack.append(val)

# 3. 出栈 (Pop) - 弹出并返回栈顶元素
# 时间复杂度: O(1)
# 注意：如果栈为空，调用 pop() 会抛出 IndexError 错误
top = stack.pop()

# 4. 查看栈顶 (Peek / Top) - 仅获取值，不弹出
# 时间复杂度: O(1)
# 利用 Python 的负数索引，-1 代表序列的最后一个元素
if stack:
    top_val = stack[-1]

# 5. 判空 (IsEmpty) - 检查栈中是否有元素
# Python 中直接利用空列表的布尔值为 False 的特性
if not stack:
    print("栈为空")
    
# 6. 获取栈的大小 (Size)
# 时间复杂度: O(1)
size = len(stack)

# 7. 清空栈 (Clear)
stack.clear()

数组初始化

代码避坑

一维数组初始化

• 存储数字、字符串、布尔值等不可变对象：
• 用乘法是安全的，比如 indegrees = [0] * n。

多维数组初始化

• 内部元素是列表、字典等可变对象
• 绝不能用乘法，必须用列表推导式 [[0] * m for _ in range(n)] 或 [[] for _ in range(n)]。