📘 Python 数据结构与算法学习笔记
1. 算法基础 🧱
本节内容
- 算法概念
- 时间复杂度
- 空间复杂度
- 复习：递归
一. 算法
- 算法：一个计算过程，解决问题的方法
- 程序 = 数据结构 + 算法
- 输入 → 算法 → 输出
2. 估计算法运行效率与时间复杂度 ⏱️
一. 时间复杂度
- 时间复杂度：用来评估算法运行效率的一个式子
示例代码与复杂度分析：
Python
# 1. O(1)
print("Hello")
# O(n)
for i in range(n):
print("Hello World")
# O(n^2)
for i in range(n):
for j in range(n):
print("Hello")
# O(n^3)
for i in range(n):
for j in range(n):
for k in range(n):
print("Hello")
# 2. O(1)
print("Hello")
print("Hello")
print("Hello")
# O(log n)
# 2^6 = 64, log2 64 = 6
while n > 1:
print(n)
n = n // 2
# 时间复杂度记为 O(log2 n) 或 O(log n)
二. 小结
- 时间复杂度是用来估计算法运行时间的一个式子（单位）。
- 一般来说，时间复杂度高的算法比时间复杂度低的算法慢。
- 常见的实践复杂度（按效率排序）： O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
- 常见问题的时间复杂度： O(n!),O(2n),O(nn)...
3. 简单判断时间复杂度 ⚡
一. 如何简单快速地判断算法复杂度
- 快速判断算法复杂度（适用于绝大多数简单情况）：
- 确定问题规模 n
- 循环减半过程 → logn
- k 层关于循环 n 的循环 → nk
- 复杂情况：根据算法执行过程判断
4. 空间复杂度 💾
一. 空间复杂度
- 空间复杂度：用来评估算法内存占用大小的式子
- 空间复杂度的表示方式与时间复杂度完全一样
- 算法使用了几个变量：O(1)
- 算法使用了长度为 n 的一维列表：O(n)
- 算法使用了 m 行 n 列的二维列表：O(mn)
- “空间换时间”
5. 复习：递归 🔄
一. 递归的两个特点：
- 调用自身
- 结束条件
示例：
Python
6. 递归示例：汉诺塔问题 🗼
一. 背景
- 大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。
- 大梵天命令婆罗门把圆盘从下面开始按照大小顺序重新摆放在另一根柱子上。
- 在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
- 64根柱子移动完毕之日，就是世界毁灭之时。
二. 分析（n个盘子时）
- 把 n−1 个圆盘从 A 经过 C 移动到 B
- 把第 n 个圆盘从 A 移动到 C
- 把 n−1 个小圆盘从 B 经过 A 移动到 C
代码实现：
Python
def hanoi(n, a, b, c):
if n > 0:
hanoi(n - 1, a, c, b)
print("moving from %s to %s" % (a, c))
hanoi(n - 1, b, a, c)
hanoi(3, 'A', 'B', 'C')
示例分析：
- 首先，调用
hanoi(3,'A','B','C') - 它会先执行
hanoi(2,'A','C','B')- 这一步又会先执行
hanoi(1,'A','B','C') - 这一步会打印
moving from A to C
- 这一步又会先执行
- 然后打印
moving from A to B, 移动最大的盘子 - 最后执行
hanoi(1,'C','A','B')，打印moving from C to B - 接着，打印
moving from A to C，移动最大的盘子
7. 顺序查找 🔍
本节内容
- 什么是列表查找
- 顺序查找
- 二分查找
一. 查找
- 查找：在一些数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程。
- 列表查找（线性表查找）：从列表中查找指定元素。
- 输入：列表、待查找元素
- 输出：元素下标（未找到元素时一般返回 None 或 -1）
- 内置列表查找函数：
index()
二. 顺序查找
- 顺序查找：也叫线性查找，从列表第一个元素开始，顺序进行搜索，直到找到元素或搜索到列表最后一个元素为止。
enumerate():enumerate()函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。
代码实现：
Python
- 时间复杂度为：O(n)
三. 二分查找
- 二分查找：又叫折半查找，从有序列表的初始候选区
li[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。 - 实例：从列表中查找元素 3
[1, 2, 3, 4, 5, 6, 7, 8, 9] - 注意：在 python 中使用的 // 会直接舍弃掉小数部分
代码实现：
Python
def binary_search(li, val):
left = 0
right = len(li) - 1
while left <= right: # 候选区有值
mid = (left + right) // 2
if li[mid] == val:
return mid
elif li[mid] > val: # 待查找的值在 mid 左侧
right = mid - 1
else: # li[mid] < val 待查找的值在 mid 右侧
left = mid + 1
return None
- 二分查找的时间复杂度为 O(logn)
- 二分查找时间复杂度比线性查找小多了
8. 排序介绍 📶
本节内容
- 什么是列表排序
- 常见排序算法介绍
- 排序算法分析
一. 列表排序
- 排序：将一组“无序”的记录序列调整为“有序”的记录序列。
- 列表排序：将无序列表变为有序列表。
- 输入：列表
- 输出：有序列表
- 升序与降序
- 内置排序函数：
sort()
二. 常见排序算法
- 排序 Low B 三人组
- 冒泡排序
- 选择排序
- 插入排序
- 排序 NB 三人组
- 快速排序
- 堆排序
- 归并排序
- 其他排序
- 希尔排序
- 计数排序
- 基数排序
9. 冒泡排序 🧼
一. 冒泡排序原理
- 列表每两个相邻的数，如果前面比后面大，则交换这两个数。
- 一趟排序完成后，则无序区减少一个数，有序区增加一个数。
- 代码关键点：趟、无序区范围。
基础实现：
Python
def bubble_sort(li):
for i in range(len(li)-1):
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
print(li)
二. 优化与复杂度
- 时间复杂度：O(n2)
优化实现：
Python
def bubble_sort(li):
for i in range(len(li)-1):
exchange = False
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
exchange = True
if not exchange:
return
- 冒泡排序-优化：如果冒泡排序中的一趟排序没有发生交换，则说明列表已经有序，可以直接结束算法。
10. 选择排序 🤏
一. 简单版本（不推荐）
Python
def select_sort_simple(li):
li_new = []
for i in range(len(li)):
min_val = min(li)
li_new.append(min_val)
li.remove(min_val)
return li_new
- 注意：
min()和remove()都不是 O(1) 的操作。
二. 正式版本
Python
def select_sort(li):
for i in range(len(li)-1):
min_loc = i
for j in range(i+1, len(li)):
if li[j] < li[min_loc]:
min_loc = j
li[i], li[min_loc] = li[min_loc], li[i]
三. 基本过程
- 一趟排序记录最小的数，放到第一个位置。
- 再一趟排序记录列表无序区最小的数，放到第二个位置。
- ......
- 算法关键点：有序区和无序区、无序区最小数的位置。
- 时间复杂度也是 O(n2)。
11. 插入排序 🃏
一. 插入排序原理
- 初始时手里（有序区）只有一张牌。
- 每次（从无序区）摸一张牌，插入到手里已有牌的正确位置。
二. 代码实现
Python
def insert_sort(li):
for i in range(1, len(li)):
tmp = li[i]
j = i - 1
while li[j] > tmp and j >= 0:
li[j+1] = li[j]
j -= 1
li[j+1] = tmp
- 时间复杂度：O(n2)
- 注：学了时间复杂度可以利用它大约估计出程序运行的时间（计算机1秒钟能够运行 107 次基本运算）。
12. 快速排序原理介绍 🚀
一. 快速排序：快
- 思路：
- 取一个元素 p（第一个元素），使元素 p 归位；
- 列表被 p 分成两部分，左边都比 p 小，右边都比 p 大；
- 递归完成排序。
框架：
Python
def quick_sort(data, left, right):
if left < right:
mid = partition(data, left, right)
quick_sort(data, left, mid-1)
quick_sort(data, mid+1, right) # 原文此处 right 缺失，已修正
二. Partition 函数
Python
def partition(li, left, right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp:
right -= 1
li[left] = li[right]
while left < right and li[right] <= tmp:
left += 1
li[right] = li[left]
li[left] = tmp
return left
三. 效率与问题
- 效率：时间复杂度 O(nlogn)
- 问题：
- 最坏情况：原来是使用第一个数据来操作的（倒序时效率退化），但是可以使用随机数来解决。
- 递归消耗（Recursion limit）。
13. 堆排序前传：树的基础知识 🌳
一. 树与二叉树
- 树：一种数据结构，可以递归定义。
- 树是由 n 个节点组成的集合：
- 如果 n=0，那这是一棵空树。
- 如果 n>0，那存在 1 个节点作为树的根节点，其他节点可以为 m 个集合，每个集合本身又是一棵树。
二. 概念
- 根节点（最开始）、叶子节点（最后的，不能再分的）
- 树的深度（高度）
- 树的度（该节点能分出多少个叉）
- 孩子节点/父节点
- 子树
三. 二叉树
- 二叉树：度不超过 2 的树。
- 每个节点最多有两个孩子节点。
- 每个孩子节点被区分为左孩子节点和右孩子节点。
四. 完全二叉树
- 满二叉树：一个二叉树，如果每一个层的节点数都达到最大值，则这个二叉树就是满二叉树。
- 完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树（即上面都是满二叉树，最下面一层从左到右不能“缺”）。
五. 二叉树的存储方式
- 链式存储方式
- 顺序存储方式
六. 二叉树的顺序存储方式
- 使用列表（把它想像成二叉树）
[9, 8, 7, 6, 5, 0, 1, 2, 4, 3] - 父节点和左孩子节点的编号下标关系：
- 0-1, 1-3, 2-5, 3-7...
- i→2i+1
- 父节点和右孩子节点的编号下标关系：
- 0-2, 1-4, 2-6...
- i→2i+2
14. 堆排序前传：堆和堆的向下调整 🌲
一. 什么是堆
- 堆：一种特殊的完全二叉树结构。
- 大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大。
- 小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小。
二. 堆的向下调整性质
- 假设根节点的左右子树都是堆，但根节点不满足堆的性质。
- 可以通过一次向下的调整来将其变成一个堆（将孩子节点的数和父节点的数根据大小来互换位置）。
三. 堆排序的过程演示
- 建立堆（从最小的子树开始）。
- 得到堆顶元素，为最大元素。
- 去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次重新调整使堆有序（挨个出数）。
- 堆顶元素为第二大元素。
- 重复步骤 3，直到堆变空。
四. 向下调整函数的实现
Python
def sift(li, low, high):
"""
li: 列表
low: 根节点的位置
high: 最后一个数字的位置
"""
i = low # i最开始指向根节点位置
j = 2 * i + 1 # j开始是左孩子
tmp = li[low] # 把堆顶存起来
while j <= high: # 只要j位置有数
if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子有且比较大
j = j + 1 # j指向右孩子
if li[j] > tmp:
li[i] = li[j]
i = j # 往下看一层
j = 2 * i + 1
else: # tmp更大，把tmp放到i的位置上
li[i] = tmp # 把tmp放到某一级领导的位置上
break
else:
li[i] = tmp # 把tmp放到叶子节点上
15. 堆排序的实现：构造堆 🏗️
Python
def heap_sort(li):
n = len(li)
for i in range((n-2)//2, -1, -1):
# i表示建堆的时候调整的部分的根的下标
sift(li, i, n-1)
# 建堆完成了
16. 堆排序的实现：完整代码 ✨
一. 挨个出数逻辑
Python
for i in range(n-1, -1, -1):
# i指向当前堆的最后一个元素
li[0], li[i] = li[i], li[0]
sift(li, 0, i-1) # i-1是新的high
二. 完整的代码实现
Python
def sift(li, low, high):
# li: 列表
# low: 根节点的位置
# high: 最后一个数字的位置
i = low # i最开始指向根节点位置
j = 2 * i + 1 # j开始是左孩子
tmp = li[low] # 把堆顶存起来
while j <= high: # 只要j位置有数
if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子有且比较大
j = j + 1 # j指向右孩子
if li[j] > tmp:
li[i] = li[j]
i = j # 往下看一层
j = 2 * i + 1
else: # tmp更大，把tmp放到i的位置上
li[i] = tmp # 把tmp放到某一级领导的位置上
break
else:
li[i] = tmp # 把tmp放到叶子节点上
def heap_sort(li):
n = len(li)
for i in range((n-2)//2, -1, -1):
# i表示建堆的时候调整的部分的根的下标
sift(li, i, n-1)
# 建堆完成了
for i in range(n-1, -1, -1):
# i指向当前堆的最后一个元素
li[0], li[i] = li[i], li[0]
sift(li, 0, i-1) # i-1是新的high
# 测试
li = [i for i in range(100)]
import random
random.shuffle(li)
heap_sort(li)
17. 堆的时间复杂度 ⏳
- 堆排序时间复杂度：O(nlogn)
18. 堆排序 -- 内置模块 📦
- Python "内置"模块：
heapq(但实现的是小根堆) - 常用函数：
heapify(x)# 建堆heappush(heap, item)heappop(heap)# 弹出最小的元素
19. 堆排序 -- topk 问题 🔝
一. 问题描述
- 现在有 n 个数，设计算法得到前 k 大的数 (k<n)。
- 解决思路：
- 排序后切片：O(nlogn)
- 排序 LowB 三人组：O(kn)
- 堆排序思路：O(nlogk)
- 堆排序思路详解：
- 取列表前 k 个元素建立一个小根堆。堆顶就是目前第 k 大的数。
- 依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素；如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整。
- 遍历列表所有元素后，倒序弹出堆顶。
二. topk 实现
Python
def sift(li, low, high):
i = low
j = 2 * i + 1
tmp = li[low]
while j <= high:
if j + 1 <= high and li[j+1] < li[j]: # 如果右孩子有且比较小（改为小根堆）
j = j + 1
if li[j] < tmp:
li[i] = li[j]
i = j
j = 2 * i + 1
else:
li[i] = tmp
break
else:
li[i] = tmp
def topk(li, k):
heap = li[0:k]
for i in range((k-2)//2, -1, -1):
sift(heap, i, k-1)
# 1. 建堆
for i in range(k, len(li)): # 原文 len(li)-1，应为 len(li)
if li[i] > heap[0]:
heap[0] = li[i]
sift(heap, 0, k-1)
# 2. 遍历
for i in range(k-1, -1, -1):
heap[0], heap[i] = heap[i], heap[0]
# 这样做的目的是将当前最小的元素（因为是最小堆）移动到它最终应该在的位置，即数组的前部。
sift(heap, 0, i-1)
# 3. 出数
return heap
li = list(range(1000))
import random
random.shuffle(li)
print(topk(li, 10))
20. 归并排序 🤝
一. 归并
- 假设现在的列表分两段有序，如何将其合成为一个有序列表？这种操作称为一次归并。
二. 示例（分成的两部分分别是有序的）
Python
def merge(li, low, mid, high):
i = low
j = mid + 1
ltmp = []
while i <= mid and j <= high: # 只要左右两边都有数
if li[i] < li[j]:
ltmp.append(li[i])
i += 1
else:
ltmp.append(li[j])
j += 1
# while执行完，肯定有一部分没数了
while i <= mid:
ltmp.append(li[i])
i += 1
while j <= high:
ltmp.append(li[j])
j += 1
li[low:high+1] = ltmp
三. 归并排序 -- 使用归并
- 分解：将列表越分越小，直至分成一个元素。
- 终止条件：一个元素是有序的。
- 合并：将两个有序列表归并，列表越来越大。
Python
def merge_sort(li, low, high):
if low < high: # 至少有两个元素，递归
mid = (low + high) // 2
merge_sort(li, low, mid)
merge_sort(li, mid + 1, high)
merge(li, low, mid, high)
四. 复杂度
- 时间复杂度：O(nlogn)
- 空间复杂度：O(n)
21. NB 三人组小结 📊
一. 总结
- 三种排序算法的时间复杂度都是 O(nlogn)。
- 运行时间（一般情况）： 快速排序 < 归并排序 < 堆排序
- 缺点：
- 快速排序：极端情况下排序效率低。
- 归并排序：需要额外的内存开销。
- 堆排序：在块的排序算法中相对较慢。
二. 复杂度对比表
| 排序方法 | 时间复杂度 (平均) | 时间复杂度 (最坏) | 时间复杂度 (最好) | 空间复杂度 | 稳定性 | 代码复杂度 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 | 简单 |
| 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 | 简单 |
| 插入排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 | 简单 |
| 快速排序 | O(nlogn) | O(n2) | O(nlogn) | O(logn) ~ O(n) | 不稳定 | 较复杂 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | 复杂 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | 较复杂 |
导出到 Google 表格
- 稳定性：指排完后，保持和原来数字相对位置一样。
- 示例：
{'name':'a','age':18},{'name':'b','age':25},{'name':'a','age':20} - 如果按照名字排序且稳定：a(18) 在 a(20) 前面。
- 规律：挨个移动的都是稳定的，不挨个移动的都是不稳定的。
22. 希尔排序 🐚
一. 原理
- 希尔排序是一种分组插入排序算法。
- 首先取一个整数 d1=n/2，将元素分为 d1 个组，每组相邻两元素之间的距离为 d1，在各组内进行直接插入排序。
- 取第二个整数 d2=d1/2，重复上述分组排序过程，直到 d1=1，即所有元素在同一组内进行直接插入排序。
- 希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使得所有数据有序。
二. 实现
Python
def insert_sort_gap(li, gap):
for i in range(gap, len(li)):
tmp = li[i]
j = i - gap
while j >= 0 and li[j] > tmp:
li[j+gap] = li[j]
j -= gap
li[j+gap] = tmp
def shell_sort(li):
d = len(li) // 2
while d >= 1:
insert_sort_gap(li, d)
d //= 2
三. 讨论
- 希尔排序的时间复杂度讨论比较复杂，并且和选取的 gap 序列有关。
23. 计数排序 🔢
一. 问题
- 对列表进行排序，已知列表中的数范围都在 0 到 100 之间，设计时间复杂度为 O(n) 的算法。
二. 实现
Python
def count_sort(li, max_count=100):
count = [0 for _ in range(max_count+1)]
for val in li:
count[val] += 1
li.clear()
for ind, val in enumerate(count):
for i in range(val):
li.append(ind)
24. 桶排序 🥣
一. 原理
- 在计数排序中，如果元素的范围比较大（比如在 1 到 1 亿之间）如何改造算法？
- 桶排序：首先将元素分在不同的桶中，再对每个桶中的元素排序。
二. 实现
Python
def bucket_sort(li, n=100, max_num=10000):
buckets = [[] for _ in range(n)] # 创建桶
for var in li:
i = min(var // (max_num // n), n-1) # i 表示var放到几号桶里
buckets[i].append(var) # 把var加到桶里
# 保持桶内的顺序
for j in range(len(buckets[i])-1, 0, -1):
if buckets[i][j] < buckets[i][j-1]:
buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
else:
break
sorted_li = []
for buc in buckets:
sorted_li.extend(buc)
return sorted_li
三. 讨论
- 桶排序的表现取决于数据的分布，也就是需要对不同数据排序时采取不同的分桶策略。
- 平均情况时间复杂度：O(n+k)
- 最坏情况时间复杂度：O(n2k)
- 空间复杂度: O(nk)
25. 基数排序 🏗️
一. 基数排序原理
- 多关键字排序：假如现在有一个员工表，要求按照薪资排序，年龄相同的员工按照年龄排序。
- 先按照年龄进行排序，再按照薪资进行稳定的排序。
- 对
32, 13, 94, 52, 17, 54, 93排序，是否可以看做多关键字排序？（个位、十位）
二. 实现
Python
def radix_sort(li):
max_num = max(li) # 最大值 9->1, 99->2, 888->3, 10000->5
it = 0
while 10**it <= max_num:
buckets = [[] for _ in range(10)]
for var in li:
# 987 it=2 987//10->98 98%10->8; it=3 987//100->9 9%10->9
digit = (var // 10**it) % 10
buckets[digit].append(var)
# 分桶完成
li.clear()
for buc in buckets:
li.extend(buc)
# 把数重新写回li
it += 1
三. 讨论
- 时间复杂度: O(kn)
- 空间复杂度：O(k+n)
- k 表示数字位数。
26. 查找排序部分习题 📝
LeetCode 网站
一. 查找排序相关试题
- 给两个字符串 s 和 t，判断 t 是否为 s 的重新排列后组成的单词。
s='anagram', t='nagaram', return trues='rat', t='car', return false
二. 二维列表查找
- 给定一个 m×n 的二维列表，查找一个数是否存在，列表有下列特性：
- 每一行的列表从左到右已经排序好。
- 每一行第一个数比上一行最后一个数大。
三. 两数之和
- 给定一个列表和一个整数，设计算法找到两个数的下标，使得两个数之和为给定的正数，保证肯定仅有一个结果。
- 例如，列表
[1, 2, 5, 4]与目标整数 3，1+2=3，结果为(0, 1)。
27. 查找排序相关面试题 1 (Anagram)
解法 1:
Python
class Solution:
def isAnagram(self, s, t):
ss = list(s)
tt = list(t)
ss.sort()
tt.sort()
return ss == tt
解法 2:
Python
解法 3 (最快):
Python
def isAnagram(s, t):
dict1 = {}
dict2 = {}
for ch in s:
dict1[ch] = dict1.get(ch, 0) + 1
for ch in t:
dict2[ch] = dict2.get(ch, 0) + 1
return dict1 == dict2
28. 查找排序习题 2 (Matrix Search)
解法 1:
Python
class Solution:
def searchMatrix(self, matrix, target):
for line in matrix:
if target in line:
return True
return False
解法 2 (二分):
Python
class Solution:
def searchMatrix(self, matrix, target):
h = len(matrix)
if h == 0:
return False
w = len(matrix[0])
if w == 0:
return False
left = 0
right = w * h - 1
while left <= right:
mid = (left + right) // 2
i = mid // w
j = mid % w
if matrix[i][j] == target:
return True
elif matrix[i][j] > target:
right = mid - 1
else:
left = mid + 1
else:
return False
29. 查找排序习题 3 (Two Sum)
解法 1 (暴力):
Python
class Solution:
def twoSum(self, nums, target):
n = len(nums)
for i in range(n):
for j in range(n):
if i != j: # 要避免i和j相等
if nums[i] + nums[j] == target:
return sorted([i, j])
解法 2 (优化暴力):
Python
class Solution:
def twoSum(self, nums, target):
n = len(nums)
for i in range(n):
for j in range(i):
if nums[i] + nums[j] == target:
return sorted([i, j])
解法 3 (二分 - 如果有序):
Python
# 输入的列表是有序的
class Solution:
def binary_search(self, li, left, right, val):
while left <= right:
mid = (left + right) // 2
if li[mid] == val:
return mid
elif li[mid] > val:
right = mid - 1
else:
left = mid - 1 # 原文可能有误，应为 left = mid + 1 ? 保持原文
def twoSum(self, nums, target):
for i in range(len(nums)):
a = nums[i]
b = target - a
if b >= a:
j = self.binary_search(nums, i+1, len(nums)-1, b)
else:
j = self.binary_search(nums, 0, i-1, b)
if j:
break
return sorted([i+1, j+1])
解法 4 (带索引排序+二分):
Python
class Solution:
def binary_search(self, li, left, right, val):
while left <= right:
mid = (left + right) // 2
if li[mid][0] == val:
return mid
elif li[mid][0] > val:
right = mid - 1
else:
left = mid - 1 # 原文如此
def twoSum(self, nums, target):
new_nums = [[num, i] for i, num in enumerate(nums)]
new_nums.sort(key=lambda x: x[0])
for i in range(len(new_nums)):
a = new_nums[i][0]
b = target - a
if b >= a:
j = self.binary_search(new_nums, i+1, len(nums)-1, b)
else:
j = self.binary_search(new_nums, 0, i-1, b)
if j:
break
return sorted([new_nums[i][1], new_nums[j][1]])
30. 数据结构的介绍 🏗️
一. 定义
- 数据结构：是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。
- 简单来说，数据结构就是设计数据以何种方式组织并存储在计算机中。
- 比如：列表、集合与字典等都是一种数据结构。
- 程序 = 数据结构 + 算法
二. 数据结构的分类
- 数据结构按照其逻辑结构可分为：线性结构、树结构、图结构。
- 线性结构：数据结构中的元素存在一对一的相互关系。
- 树结构：数据结构中的元素存在一对多的相互关系。
- 图结构：数据结构中的元素存在多对多的相互关系。
31. 列表/数组 📃
一. 概念
- 其他语言叫做数组，列表约等于数组。
- 列表中的数据是顺序存储的。
二. 问题与操作
- 列表（其他语言称为数组）是一种基本数据类型。
- 关于列表的问题：
- 列表中的元素是如何存储的？
- 列表的基本操作：按下标查找、插入元素、删除元素。
- 这些操作的时间复杂度是多少？
- 扩展：python 的列表是如何实现的？
三. 数组与列表区别
- 数组与列表有两点不同:
- 数组元素类型要相同 / 列表中存储的是地址，一个地址占 4 个字节。
- 数组长度固定 / 列表可以自己再开新的空间。
- 对列表进行增删操作时间复杂度都是 O(n)。
32. 栈 🥞
一. 概念
- 栈：是一个数据集合，可以理解为只能在一端进行插入或删除操作的列表。
- 栈的特点：后进先出 LIFO (last-in, first-out)。
- 栈的概念：栈顶、栈底。
- 栈的基本操作：
- 进栈（压栈）：push
- 出栈：pop
- 取栈顶：gettop
类封装实现：
Python
class Stack:
def __init__(self):
self.stack = []
def push(self, element):
self.stack.append(element)
def pop(self):
return self.stack.pop()
def get_top(self):
if len(self.stack) > 0:
return self.stack[-1]
else:
return None
二. 栈的实现
- 使用一般的列表结构即可实现栈：
- 进栈:
li.append - 出栈：
li.pop - 取栈顶：
li[-1] - 创建一个列表，然后只使用这三个功能也相当于是一个栈。
三. 栈的应用 -- 括号匹配问题
- 问题：给一个字符串，其中包含小括号、中括号、大括号，求该字符串中的括号是否匹配。
- 例如：
()()[]{}匹配([{()}])匹配[]()不匹配[(])不匹配
示例：
Python
def brace_match(s):
match = {'}': '{', ']': '[', ')': '('}
stack = Stack()
for ch in s:
if ch in {'(', '[', '{'}:
stack.push(ch)
else: # ch in {')',']','}'}
if stack.is_empty():
return False
elif stack.get_top() == match[ch]:
stack.pop()
else: # stack.get_top()!=match[ch]
return False
if stack.is_empty():
return True
else:
return False
33. 队列 🚶
一. 队列
- 队列（Queue）：是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除。
- 进行插入一端称为队尾 (rear), 插入动作称为进队或入队。
- 进行删除的一端称为队头 (front)，删除动作称为出队。
- 队列的性质：先进先出 (First-in, First-out)。
二. 队列的实现
- 队列能否用列表简单实现? 为什么？（列表头出队复杂度高）
三. 队列的实现方式 -- 环形队列
- 空队列 ->
rear和front在同一个位置 - 队满 ->
rear和front差一个位置（牺牲一个位置） - 环形队列：当队列指针
front == MaxSize + 1时，再前进一个位置就自动到 0。 - 队首指针前进 1：
front = (front + 1) % MaxSize - 队尾指针前进 1：
rear = (rear + 1) % MaxSize - 队空条件：
rear == front - 队满条件：
(rear + 1) % MaxSize == front
代码实现：
Python
class Queue:
def __init__(self, size=100):
self.queue = [0 for _ in range(size)]
self.size = size
self.rear = 0 # 队尾指针
self.front = 0 # 队首指针
def push(self, element):
if not self.is_filled():
self.rear = (self.rear + 1) % self.size
self.queue[self.rear] = element
else:
raise IndexError("Queue is empty") # 应该是 Full
def pop(self):
if not self.is_empty():
self.front = (self.front + 1) % self.size
return self.queue[self.front]
else:
raise IndexError("Queue is empty")
# 判断队空
def is_empty(self):
return self.rear == self.front
# 判断队满
def is_filled(self):
return (self.rear + 1) % self.size == self.front
34. 队列的内置模块 📦
一. 双向队列
- 双向队列的两端都支持进队和出队操作。
- 基本操作：队首进队、队首出队、队尾进队、队尾出队。
二. Python 队列内置模块
- 使用方法：
from collections import deque - 创建队列：
queue = deque() - 进队：
append() - 出队：
popleft() - 用于双向队列：
- 双向队列队首进队：
appendleft()# 左边是队首 - 双向队列队尾出队：
pop()
示例（Tail 命令模拟）：
Python
def tail(n):
with open('text.txt', 'r') as f:
q = deque(f, n) # 队满了自动进出队
return q
for line in tail(5):
print(line, end='')
35. 栈和队列的应用 -- 迷宫问题 🧩
一. 问题
- 给一个二维列表，表示迷宫（0表示通道，1表示围墙）。给出算法，求一条走出迷宫的路径。
二. 栈 -- 深度优先搜索 (DFS)
- 回溯法
- 思路：从一个节点开始，任意找下一个能走的点，当找不到能走的点时，退回上一个点寻找是否有其他方向的点。
- 使用栈存储当前路径。
Python
maze = [
[1,1,1,1,1,1,1,1,1,1],
[1,0,0,1,0,0,0,1,0,1],
[1,0,0,1,0,0,0,1,0,1],
[1,0,0,0,0,1,1,0,0,1],
[1,0,1,1,1,0,0,0,0,1],
[1,0,0,0,1,0,0,0,0,1],
[1,0,1,0,0,0,1,0,0,1],
[1,0,1,1,1,0,1,1,0,1],
[1,1,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1]
]
dirs = [
lambda x,y:(x+1,y),
lambda x,y:(x-1,y),
lambda x,y:(x,y-1),
lambda x,y:(x,y+1)
]
def maze_path(x1, y1, x2, y2):
stack = []
stack.append((x1, y1))
while(len(stack) > 0):
curNode = stack[-1] # 当前的节点
if curNode[0] == x2 and curNode[1] == y2:
# 走到终点
for p in stack:
print(p)
return True
# x,y四个方向 x-1,y; x+1,y; x,y-1; x,y+1
for dir in dirs:
nextNode = dir(curNode[0], curNode[1])
# 如果下一个节点能走
if maze[nextNode[0]][nextNode[1]] == 0:
stack.append(nextNode)
maze[nextNode[0]][nextNode[1]] = 2 # 2表示为已经走过
break
else:
maze[nextNode[0]][nextNode[1]] = 2 # 原文可能是 stack.pop前标记？逻辑有点怪，保持原文
stack.pop()
else:
print('没有路')
return False
三. 队列 - 广度优先搜索 (BFS)
- 思路：从一个节点开始，寻找所遇接下来能就继续走的点，继续不断寻找，直到找到出口。
- 使用队列存储当前正在考虑的节点。
四. 使用队列进行迷宫问题：实现
Python
from collections import deque
def print_r(path):
curNode = path[-1]
realpath = []
while curNode[2] != -1:
realpath.append(curNode[0:2])
curNode = path[curNode[2]]
realpath.append(curNode[0:2]) # 起点
realpath.reverse()
for node in realpath:
print(node)
def maze_path_queue(x1, y1, x2, y2):
queue = deque()
queue.append((x1, y1, -1))
path = []
while len(queue) > 0:
curNode = queue.popleft()
path.append(curNode)
if curNode[0] == x2 and curNode[1] == y2:
# 终点
print_r(path)
return True
for dir in dirs:
nextNode = dir(curNode[0], curNode[1])
if maze[nextNode[0]][nextNode[1]] == 0:
queue.append((nextNode[0], nextNode[1], len(path)-1)) # 后续节点进队，记录哪个节点带他来的
maze[nextNode[0]][nextNode[1]] = 2 # 标记为已经走过
else:
print("没有路")
return False
36. 链表 🔗
一. 链表
- 每个节点包含两部分，数据域 item 和指向下一个节点的指针 next。通过节点之间的互相连接，最终串联成一个链表。
Python
class Node:
def __init__(self, item):
self.item = item
self.next = None
a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.next = c
二. 创建链表和遍历
- 头插法
- 尾插法
头插法示例：
Python
class Node:
def __init__(self, item):
self.item = item
self.next = None
def create_linklist(li):
head = Node(li[0])
for element in li[1:]:
node = Node(element)
node.next = head
head = node
return head
def print_linklist(lk):
while lk:
print(lk.item, end=',')
lk = lk.next
lk = create_linklist([1, 2, 3])
print_linklist(lk)
尾插法示例：
Python
def create_linklist_tail(li):
head = Node(li[0])
tail = head
for element in li[1:]:
node = Node(element)
tail.next = node
tail = node
return head
三. 链表的遍历
- 链表节点的插入
Python
- 链表节点的删除
Python
37. 双链表 ⛓️
一. 概念
-
双链表的每个节点有两个指针：一个指向后一个节点，另一个指向前一个节点。
-
如何建立双链表:
Python
class Node(object):
def __init__(self, item=None):
self.item = item
self.next = None
self.prior = None
二. 双链表节点的插入
- 画图理解：
Python
(p要先和后面连起来)
三. 双链表节点的删除
- 代码：
Python
38. 链表总结 📝
一. 链表 -- 复杂度分析
- 顺序表（列表/数组）与链表比较：
- 按元素值查找
- 按下标查找
- 在某元素后插入
- 删除某元素
二. 链表与顺序表
- 链表在插入和删除的操作上明显快于顺序表。
- 链表的内存可以更灵活的分配。
- 试利用链表重新实现栈和队列。
- 链表这种存储的数据结构对树和图的结构有很大的启发性。
39. 哈希表 #️⃣
一. 哈希表
- 哈希表一个通过哈希函数来计算数据存储位置的数据结构，通常支持如下操作:
insert(key, value): 插入键值对 (key, value)get(key): 如果存在键为 key 的键值对则返回其值 value, 否则返回空delete(key): 删除键为 key 的键值对
二. 直接寻址表
- 当关键字的全域 U 比较小时，直接寻址是一种简单而有效的方法。
三. 直接寻址表的缺点
- 当域 U 很大时，需要消耗大量内存，很不实际。
- 如果域 U 很大而实际出现的 key 很少，则大量空间被浪费。
- 无法处理关键字不是数字的情况。
四. 哈希
- 直接寻址表：key 为 k 的元素放到 k 位置上。
- 改进直接寻址表：哈希
- 构建大小为 m 的寻址表 T。
- key 为 k 的元素放到 h(k) 位置上。
- h(k) 是一个函数，其将域 U 映射到表 T[0,1,...,m−1]。
五. 哈希表
- 哈希表（又称为散列表），是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成。哈希函数 h(k) 将元素关键字 k 作为自变量，返回元素的存储下标。
- 假设一个长度为 7 的哈希表，哈希函数 h(k)=k%7。元素集合
{14, 22, 3, 5}的存储方式。
六. 哈希冲突
- 由于哈希表的大小是有限的，而要存储的值的总数量是无限的，因此对于任何哈希函数，都会出现两个不同元素映射到一个位置上的情况，这种情况叫做哈希冲突。
- 比如 h(k)=k%7,h(0)=h(7)=h(14)=...
七. 解决哈希冲突
- 开放寻址法：
- 如果哈希函数返回的位置已经有值，则可以向后探查新的位置来存储这个值。
- 线性探查：如果位置 i 被占用，则探查 i+1,i+2,...（到空位就停止）。
- 二次探查：如果位置 i 被占用，则探查 i+12,i−12,i+22,i−22,...
- 二度哈希：有 n 个哈希函数，当使用第 1 个哈希函数 h1 发生冲突时，则尝试使用 h2, h3。
- 拉链法：
- 哈希表每个位置都连接一个链表，当冲突发生时，冲突的元素将被加到该位置链表的最后。
八. 哈希表 —— 常见哈希函数
- 除法哈希法：h(k)=k%m
- 乘法哈希法：h(k)=floor(m∗(A∗key%1)) （A 是个小数）（floor 是向下取整）
- 全域哈希法：ha,b(k)=((a∗key+b)modp)modm,a,b=1,2,...,p−1
40. 哈希表的实现 💻
Python
class HashTable:
def __init__(self, size=101):
self.size = size
self.T = [LinkList() for i in range(self.size)] # 假设有 LinkList 类
def h(self, k):
return k % self.size
def insert(self, k):
i = self.h(k)
if self.find(k):
print("Duplicated Insert.")
else:
self.T[i].append(k)
def find(self, k):
i = self.h(k)
return self.T[i].find(k)
41. 哈希表的应用 🌐
一. 集合与字典
- 字典与集合都是通过哈希表来实现的。
a = {'name': 'Alex', 'age': 18, 'gender': 'Man'}- 使用哈希表存储字典，通过哈希函数将字典的键映射为下标。假设 h(′name′)=3,h(′age′)=1,h(′gender′)=4，则哈希表存储为
[None, 18, None, 'Alex', 'Man']。 - 如果发生哈希冲突，则通过拉链法或开发寻址法解决。
二. MD5 算法
- MD5 曾经是密码学中常用的哈希函数，可以把任意长度的数据映射为 128 位的哈希值。其曾经包含如下特征：
- 同样的消息，其 MD5 值必定相同；
- 可以快速计算出任意给定消息的 MD5 值；
- 除非暴力的枚举所有可能的信息，否则不可能从哈希值反推出消息本身；
- 两条消息之间即使只有微小的差别，其对应的 MD5 值也应该是完全不同、完全不相关的；
- 不能在有意义的时间内人工的构造两个不同的消息使其具有相同的 MD5 值。
三. MD5 应用举例
- 文件的哈希值：算出文件的哈希值，若两个文件的哈希值相同，则可认为这两个文件是相同的。因此：
- 用户可以利用它来验证下载的文件是否完整。
- 云存储服务商可以利用它来判断用户要上传的文件是否已经存在于服务器上，从而实现秒传的功能，同时避免存储过多相同的文件副本。
四. SHA2 算法
- 历史上 MD5和 SHA-1 曾经是使用最为广泛的 cryptographic hash function，但是随着密码学的发展，这两个哈希函数的安全性相继受到了各种挑战。
- 因此现在安全性较重要的场合推荐使用 SHA-2 等新的更安全的哈希函数。
- SHA-2 包含了一系列的哈希函数: SHA-224, SHA-256, SHA-384, SHA-512 等，其对应的哈希值长度分别为 224, 256, 384 or 512 位。
- 应用举例（比特币）：
- 在比特币系统中，所有参与者需要共同解决如下问题：对于一个给定的字符串 U，给定的目标哈希值 H，需要计算出一个字符串 V，使得 U+V 的哈希值与 H 的差小于一个给定值 D。此时，只能通过暴力枚举 V 来进行猜测。首先计算出结果的人可获得一定奖金。
42. 数的概念 🌳
一. 树与二叉树
- 树是一种数据结构。比如：目录结构。
- 树是一种可以递归定义的数据结构。
- 树是由 n 个节点组成的集合：
- 如果 n=0, 那这是一棵空树;
- 如果 n>0, 那存在 1 个节点作为树的根节点，其他节点可以分为 m 个集合，每个集合本身又是一棵树。
二. 一些概念
- 根节点、叶子节点
- 树的深度（高度）
- 数的度
- 孩子节点/父节点
- 子树
43. 树的实例: 模拟文件系统 📂
一. 节点定义
Python
class Node:
def __init__(self, name, type='air'):
self.name = name
self.type = type # 'dir' or 'file'
self.children = []
self.parent = None
def __repr__(self):
return self.name
二. 文件系统类
Python
class FileSystemTree:
def __init__(self):
self.root = Node('/')
self.now = self.root
def mkdir(self, name):
# name 以 / 结尾
if name[-1] != '/':
name += "/"
node = Node(name)
self.now.children.append(node)
node.parent = self.now
def ls(self):
return self.now.children
def cd(self, name):
if name[-1] != '/':
name += "/"
if name == '../':
self.now = self.now.parent
return
for child in self.now.children:
if child.name == name:
self.now = child
return
raise ValueError('invalid dir')
三. 存储方式
- 树绝大多数都是用链式存储。
44. 二叉树的概念 🌲
一. 二叉树的链式存储
- 将二叉树的节点定义为一个对象，节点之间通过类似链表的链接方式来连接。
二. 节点定义
Python
class BiTreeNode:
def __init__(self, data):
self.data = data
self.lchild = None # 左孩子
self.rchild = None # 右孩子
# 示例
a = BiTreeNode("A")
b = BiTreeNode("B")
c = BiTreeNode("C")
d = BiTreeNode("D")
e = BiTreeNode("E")
f = BiTreeNode("F")
g = BiTreeNode("G")
e.lchild = a
e.rchild = g
a.rchild = c
c.lchild = b
c.rchild = d
g.rchild = f
root = e
print(root.lchild.rchild.data)
三. 二叉树的遍历
- 前序遍历：EACBDGF
- 中序遍历：ABCDEGF
- 后序遍历：BDCAFGE
- 层次遍历：EAGCFBD
代码实现：
Python
# 1. pre_order
def pre_order(root):
if root:
print(root.data, end=',')
pre_order(root.lchild)
pre_order(root.rchild)
# 2. in_order
def in_order(root):
if root:
in_order(root.lchild)
print(root.data, end=',')
in_order(root.rchild)
# 3. post_order
def post_order(root):
if root:
post_order(root.lchild)
post_order(root.rchild)
print(root.data, end=',')
# 4. level_order
def level_order(root):
queue = deque()
queue.append(root)
while len(queue) > 0: # 只要队不空
node = queue.popleft()
print(node.data, end=',')
if node.lchild:
queue.append(node.lchild)
if node.rchild:
queue.append(node.rchild)
45. 二叉搜索树的概念 🎋
一. 二叉搜索树 (BST)
- 二叉搜索树是一棵二叉树且满足性质：设 x 是二叉树的一个节点。如果 y 是 x 左子树的一个节点，那么
y.key <= x.key；如果 y 是 x 右子树的一个节点，那么y.key >= x.key。 - 二叉搜索树的操作：查询、插入、删除。
46. 二叉搜索树：插入 ➕
一. 代码实现
Python
class BiTreeNode:
def __init__(self, data):
self.data = data
self.lchild = None # 左孩子
self.rchild = None # 右孩子
self.parent = None # 需要 parent 指针
class BST:
def __init__(self, li=None):
self.root = None
if li:
for val in li:
self.insert_no_rec(val)
# 1. 递归插入
def insert(self, node, val):
if not node:
node = BiTreeNode(val)
elif val < node.data:
node.lchild = self.insert(node.lchild, val)
node.lchild.parent = node
elif val > node.data:
node.rchild = self.insert(node.rchild, val)
node.rchild.parent = node
return node
# 2. 非递归插入
def insert_no_rec(self, val):
p = self.root
if not p: # 空树
self.root = BiTreeNode(val)
return
while True:
if val < p.data:
if p.lchild:
p = p.lchild
else: # 左孩子不存在
p.lchild = BiTreeNode(val)
p.lchild.parent = p
return
elif val > p.data:
if p.rchild:
p = p.rchild
else:
p.rchild = BiTreeNode(val)
p.rchild.parent = p
return
else:
return
47. 二叉搜索数：查询 🔍
一. 代码实现
Python
def query(self, node, val):
if not node:
return None
if node.data < val:
return self.query(node.rchild, val)
elif node.data > val:
return self.query(node.lchild, val)
else:
return node
def query_no_rec(self, val):
p = self.root
while p:
if p.data < val:
p = p.rchild
elif p.data > val:
p = p.lchild
else:
return p
return None
48. 二叉搜索树：删除 ❌
一. 删除操作
- 如果要删除的节点是叶子节点：直接删除。
- 如果要删除的节点只有一个孩子：将此节点的父亲与孩子连接，然后删除该节点。
- 如果要删除的节点有两个孩子：将其右子树的最小节点（该节点最多有一个右孩子）删除，并替换当前节点。
二. 二叉树删除实现
Python
def __remove_node_1(self, node):
# 情况1: node是叶子节点
if not node.parent:
self.root = None
if node == node.parent.lchild: # node是它父亲的左孩子
node.parent.lchild = None
else: # 右孩子
node.parent.rchild = None
def __remove_node_21(self, node):
# 情况2.1: node只有一左个孩子
if not node.parent: # 根节点
self.root = node.lchild
node.lchild.parent = None
elif node == node.parent.lchild:
node.parent.lchild = node.lchild
node.lchild.parent = node.parent
else:
node.parent.rchild = node.rchild # 原文这里是 node.rchild 疑似笔误，应为 node.lchild? 保持原文
node.lchild.parent = node.parent
def __remove_node_22(self, node):
# 情况2.2: node只有一个右孩子
if not node.parent:
self.root = node.rchild
elif node == node.parent.lchild:
node.parent.lchild = node.rchild
node.rchild.parent = node.parent
else:
node.parent.rchild = node.rchild
node.rchild.parent = node.parent
def delete(self, val):
if self.root: # 不是空树
node = self.query_no_rec(val)
if not node: # 不存在
return False
if not node.lchild and not node.rchild:
self.__remove_node_1(node)
elif not node.rchild: # 2.1只有一个左孩子
self.__remove_node_21(node)
elif not node.lchild: # 2.2只有一个右孩子
self.__remove_node_22(node)
else: # 3.两个孩子都有
min_node = node.rchild
while min_node.lchild:
min_node = min_node.lchild
node.data = min_node.data
# 删除 min_node
if min_node.rchild:
self.__remove_node_22(node) # 这里原文传的是 node 还是 min_node? 逻辑上应是 min_node
else:
self.__remove_node_1(min_node)
49. AVL 树的概念 ⚖️
一. 二叉搜索树的效率
- 平均情况下，二叉搜索树进行搜索的时间复杂度为 O(logn)。
- 最坏情况下，二叉树搜索树可能非常偏斜。
- 解决方案：
- 随机化插入
- AVL 树
二. AVL 树
- AVL 树是一棵自平衡的二叉搜索树。
- AVL 树具有一下性质：
- 根的左右子树的高度之差的绝对值不能超过 1。
- 根的左右子树都是平衡二叉树。
50. AVL 树 -- 旋转 🔄
一. AVL 树 -- 插入
- 插入一个节点可能会破会破坏 AVL 树的平衡，可以通过旋转操作来进行修正。
- 插入一个节点后，只有从插入节点到根节点的路径上的节点的平衡可能被改变。我们需要找出第一个破坏了平衡条件的节点，称之为 K。K 的两棵子树的高度差 2。
- 不平衡的出现可能有 4 种情况。
二. 四种旋转情况
- 左旋：不平衡是由于对 K 的右孩子的右子树插入导致的。
- 右旋：不平衡是由于对 K 的左孩子的左子树插入导致的。
- 右旋-左旋：不平衡是由于对 K 的右孩子的左子树插入导致的。
- 左旋-右旋：不平衡是由于对 K 的左孩子的右子树插入导致的。
三. AVL：旋转实现
Python
# 左旋
def rotate_left(self, p, c):
s2 = c.lchild
p.rchild = s2
if s2:
s2.parent = p
c.lchild = p
p.parent = c
p.bf = 0
c.bf = 0
# 右旋
def rotate_right(self, p, c):
s2 = c.rchild
p.lchild = s2
if s2:
s2.parent = p
c.rchild = p
p.parent = c
p.bf = 0
c.bf = 0
# 左旋-右旋
def rotate_right_left(self, p, c):
g = c.lchild
s3 = g.rchlid
c.lchild = s3
if s3:
s3.parent = c
g.rchild = c
c.parent = g
s2 = g.lchild
p.rchild = s2
if s2:
s2.parent = p
g.lchild = p
p.parent = g
# bf
if g.bf > 0:
p.bf = -1
c.bf = 0
elif g.bf < 0:
p.bf = 0
c.bf = 1
else: # 插入的是g
p.bf = 0
c.bf = 0
# 右旋-左旋
def rotate_left_right(self, p, c):
g = c.rchild
s2 = g.lchild
c.rchild = s2
if s2:
s2.parent = c
g.lchild = c
c.parent = g
s3 = g.rchild
p.lchild = s3
if s3:
s3.parent = p
g.rchild = p
p.parent = g
# 更新
if g.bf < 0:
p.bf = 1
c.bf = 0
elif g.bf > 0:
p.bf = 0
c.bf = -1
else:
p.bf = 0
c.bf = 0
- 插入：balance facotor 是左右两个子树的高度差。
51. AVL 树应用与数据结构总结 📚
一. 二叉搜索树扩展应用 - B 树
- B 树是一棵自平衡的多路搜索树。常用于数据库的索引。
52. 贪心算法 🤑
一. 贪心算法
- 贪心算法（又称贪婪算法）：是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
- 贪心算法并不保证会得到最优解，但是在某些问题上贪心算法的解就是最优解。要会判断一个问题能否用贪心算法来计算。
二. 找零问题
- 假设商店老板需要找零 n 元钱，钱币的面额有：100元、50元、20元、5元、1元，如何找零使得所需钱币的数量最少？
Python
def charge(t, n):
m = [0 for _ in range(len(t))]
for i, money in enumerate(t):
m[i] = n // money
n = n % money
return m, n
三. 背包问题
- 一个小偷在某个商店发现有 n 个商品，第 i 个商品价值 vi 元，重 wi 千克。他希望拿走的价值尽量高，但它的背包最多只能容纳 W 千克的东西。他应该拿走哪些商品？
- 0-1 背包：对于一个商品，小偷那么要么把它完整拿走，要么留下。不能只拿走一部分，或把一个商品拿走多次（商品为金条）。
- 分数背包：对于一个商品，小偷可以拿走其中任意一部分。（商品为金砂）。
- 举例：
- 商品1：v1=60, w1=10
- 商品2：v2=100, w2=20
- 商品3：v3=120, w3=30
- 背包容量：W=50
- 对于 0-1 背包和分数背包，贪心算法是否都能得到最优解？为什么？
52.1 分数背包的实现
Python
def fractional_backpack(goods, w):
m = [0 for _ in range(len(goods))]
total_v = 0
for i, (prize, weight) in enumerate(goods):
if w >= weight:
m[i] = 1
w -= weight
total_v += prize
else:
m[i] = w / weight
w = 0
total_v += m[i] * prize
break
return m, total_v
52.2 拼接最大数字问题
- 问题：有 n 个非负整数，将其按照字符串拼接的方式拼接为一个整数。如何拼接可以得到的整数最大？
- 例：
32, 94, 128, 1286, 6, 71可以拼接出的最大整数为94716321286128。
实现：
Python
from functools import cmp_to_key
li = [32, 94, 128, 1286, 6, 71]
def xy_cmp(x, y):
if x + y < y + x:
return 1
elif x + y > y + x:
return -1
else:
return 0
def number_join(li):
li = list(map(str, li))
li.sort(key=cmp_to_key(xy_cmp))
return ''.join(li)
52.3 活动选择问题
- 假设有 n 个活动，这些活动要占用同一片场地，而场地在某时刻只能供一个活动使用。
- 每个活动都有一个开始时间 si 和结束时间 fi（题目中时间以整数表示），表示活动在
[si, fi)区间占用场地。 - 问：安排哪些活动能够使该场地举办的活动的个数最多？
- 贪心结论：最先结束的活动一定是最优解的一部分。
- 证明：假设 a 是所有活动中最先结束的活动，b 是最优解中最先结束的活动。
- 如果 a=b，结论成立。
- 如果 a!=b, 则 b 的结束时间一定晚于 a 的结束时间，则此时用 a 替换掉最优解中的 b，a 一定不与最优解中的其他活动时间重叠，因此替换后的解也是最优解。
53. 贪心算法总结 📝
- 都是最优化问题。
- 挺快的。
54. 动态规划 🗓️
一. 从斐波那契数列看动态规划
- 斐波那契数列：Fn=Fn−1+Fn−2
- 练习：使用递归和非递归的方法来求解斐波那契数列的第 n 项。
代码示例：
Python
def fibnacci(n):
if n == 1 or n == 2:
return 1
else:
return fibnacci(n-1) + fibnacci(n-2)
def fibnacci_no_recurison(n):
f = [0, 1, 1]
if n > 2:
for i in range(n-2):
num = f[-1] + f[-2]
f.append(num)
return f[n]
- 子问题的重复计算 -> 递归
- 循环 -> 动态规划（DP）的思想 = 递推式 + 重复子问题
55. 钢条切割问题 📏
一. 问题
- 某公司出售钢条，出售价格与钢条长度之间的关系如下表：
- 长度 i: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- 价格 pi: 1, 5, 8, 9, 10, 17, 17, 20, 24, 30
- 问题：现有一段长度为 n 的钢条和上面的价格表，求切割钢条方案，使得总收益最大。
二. 递推式
- 设长度为 n 的钢条切割后最优收益值为 rn, 可以得出递进式： rn=max(pn,r1+rn−1,r2+rn−2,...,rn−1+r1)
- 第一个参数 pn 表示不切割。
- 考察所有的 i, 选择其中收益最大的方案。
三. 最优子结构
- 可以将求解规模为 n 的原问题，划分为规模更小的子问题：完成一次切割后，可以将产生的两段钢条看成两个独立的钢条切割问题。
- 钢条切割满足最优子结构：问题的最优解由相关子问题的最优解组合而成，这些子问题可以独立求解。
- 钢条切割问题还存在更简单的递归求解方法：
- 从钢条的左边切割下长度为 i 的一段，只对右边剩下的一端继续进行切割，左边的不再切割。
- 递推式简化为 rn=max(pi+rn−i)
- 不做切割的方案就可以描述为：左边一段长度为 n，收益为 pn, 剩余一段长度为 0，收益为 r0=0。
四. 自上而下的实现
Python
p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
def cut_rod_recurision_1(p, n):
if n == 0:
return 0
else:
res = p[n]
for i in range(1, n):
res = max(res, cut_rod_recurision_1(p, i) + cut_rod_recurision_1(p, n-i))
return res
def cut_rod_recurision_2(p, n):
if n == 0:
return 0
else:
res = 0
for i in range(1, n+1):
res = max(res, p[i] + cut_rod_recurision_2(p, n-i))
return res
五. 效率
- 为何自顶向下递归实现的效率会这么差？
- 时间复杂度 O(2n)
六. 动态规划解法
- 递归算法由于重复求解相同子问题，效率极低。
- 动态规划的思想：
- 每个子问题只求解一次，保存求解结果。
- 之后需要此问题时，只需查找保存的结果。
七. 自底向上实现
Python
def cut_rod_dp(p, n):
r = [0]
for i in range(1, n+1): # 原文为 range(n+1) 但通常dp循环从1开始更清晰，保持原文逻辑
res = 0
for j in range(1, i+1):
res = max(res, p[j] + r[i-j])
r.append(res) # 原文为 res.append(res) 逻辑有误，已修正为 r.append
return r[n]
- 时间复杂度：O(n2)
八. 重构解
- 如何修改动态规划算法，使其不仅输出最优解，还输出最优切割方案？
- 对每个子问题，保存切割一次时左边切下的长度
r[i], s[i]
Python
def cut_rod_extend(p, n):
r = [0]
s = [0]
for i in range(1, n+1):
res_r = 0 # 价格最大值
res_s = 0 # 价格最大值对应方案的左边不切割部分的长度
for j in range(1, i+1):
if p[j] + r[i-j] > res_r:
res_r = p[j] + p[i-j] # 这里应该是 p[j] + r[i-j] ? 保持原文
res_s = j
r.append(res_r)
s.append(res_s)
return r[n], s
def cut_rod_solution(p, n):
r, s = cut_rod_extend(p, n)
ans = []
while n > 0:
ans.append(s[n])
n -= s[n]
return ans
九. 动态规划问题关键特征
- 最优子结构：原问题的最优解中涉及多少个子问题。
- 重叠子问题
56. 最长公共子序列 🧬
一. 问题
- 一个序列的子序列是在该序列中删去若干元素后得到的序列。
- 例: "ABCD" 和 “BDF” 都是 "ABCDEFG" 的子序列。
- 最长公共子序列 (LCS) 问题：给定两个序列 X 和 Y，求 X 和 Y 长度最大的公共子序列。
- 例：
X="ABBCBDE",Y="DBBCDB",LCS(X,Y)="BBCD" - 应用多场景：字符串相似度比对。
二. 思考
- 暴力穷举法的时间复杂度是多少？
- 最长公共子序列是否具有最优子结构性质？
三. 实现思路
- 例如：要求
a="ABCBDAB"与b="BDCABA"的 LCS: - 由于最后一位 "B" != "A":
- 因此 LCS(a, b) 应该来源于
LCS(a[:-1], b)与LCS(a, b[:-1])中更大的那一个。
- 因此 LCS(a, b) 应该来源于
代码示例 (计算长度):
Python
def lcs_length(x, y):
m = len(x)
n = len(y)
c = [[0 for _ in range(n+1)] for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if x[i-1] == y[j-1]: # i 和 j 位置上的字符匹配的时候，来自于左上方+1
c[i][j] = c[i-1][j-1] + 1
else:
c[i][j] = max(c[i-1][j], c[i][j-1])
return c[m][n]
代码示例 (记录路径):
Python
def lcs(x, y):
m = len(x)
n = len(y)
c = [[0 for _ in range(n+1)] for _ in range(m+1)]
b = [[0 for _ in range(n+1)] for _ in range(m+1)] # 1 左上方 2 上方 3 左方
for i in range(1, m+1):
for j in range(1, n+1):
if x[i-1] == y[j-1]: # i 和 j 位置上的字符匹配的时候，来自于左上方+1
c[i][j] = c[i-1][j-1] + 1
b[i][j] = 1
elif c[i-1][j] > c[i][j-1]: # 来自于上方
c[i][j] = c[i-1][j]
b[i][j] = 2
else:
c[i][j] = c[i][j-1]
b[i][j] = 3
return c[m][n], b
# 回溯算法
def lcs_trackback(x, y):
c, b = lcs(x, y)
i = len(x)
j = len(y)
res = []
while i > 0 and j > 0:
if b[i][j] == 1: # 来自左上方=>匹配
res.append(x[i-1])
i -= 1
j -= 1
elif b[i][j] == 2: # 来自上方=>不匹配
i -= 1
else: # ==3 来自左方=>不匹配
j -= 1
return "".join(reversed(res))
57. 欧几里得算法 ➗
一. 最大公约数
- 约数：如果整数 a 能被整数 b 整除，那么 a 叫做 b 的倍数，b 叫做 a 的约数。
- 给定两个整数 a, b，两个数的所有公共约数所有公共约数中的最大值即为最大公约数。
- 例: 12 与 16 的最大公约数是 4。