目录

算法	内容	实现
数据结构	表	单链表
		双向链表
		哈希表
		最小栈
	树	二叉树
		字典树
		红黑树
		二叉平衡树
		堆
	图	并查集
		无向图
经典算法	排序算法	冒泡排序
		选择排序
		插入排序
		普通 / 3向切分 快速排序
		递归 / 非递归 归并排序
		计数 / 桶排序
		堆排序
		希尔排序
		基数排序
	搜索算法	二分查找
		二分查找左右边界
	回溯算法	子集
		组合
		全排列
	位运算	二进制中1的数量
		翻转二进制表示
LeetCode
数据结构思维导图
各排序算法时间复杂度

---

数据结构

参考

• 《算法4》代码：https://algs4.cs.princeton.edu/code/

写在前面

数据结构是计算机的基础课。其底层存储只有2种类型，顺序存储和链式存储。

因此，我这里实现的数据结构，没有用到第三方包的实现，完全利用最原始的方法来实现常用的数据结构，以及基于其上的一些算法。

虽然整个项目是用python实现的，但中间未使用”奇技淫巧“，只要方法正确，可以很快速地扩展到其他语言。

缺失之处

参数校验：这是一个非常麻烦的工作，用户可能输入的情况千奇百怪，因此参数校验只做了最基础的部分。

可扩展性：每个文件内都有各自类的测试。并没有去实现一个模板支持各种情况。例如：堆中实现的是大根堆。若构造时传入比较函数，则可扩展为小根堆。

表

• 单链表

  • 从传入的列表中构造单链表
  • 头插一个元素
  • 尾插一个元素
  • 向中间指定位置插入元素
  • 删除头部元素
  • 删除尾部元素
  • 删除指定中间位置的元素
  • 查找某个元素是否存在
  • 递归反转整个链表

• 双向链表

  • 从传入的列表中构造双向链表
  • 头插一个元素
  • 尾插一个元素
  • 向中间指定位置插入元素
  • 删除头部元素
  • 删除尾部元素
  • 删除指定中间位置的元素
  • 查找某个元素是否存在

• 哈希表

  • 通过一个列表构造哈希表
  • 向哈希表中插入一个值
  • 从哈希表中删除一个值
  • 哈希表中查找一个值
  • 哈希函数，通过给定的值，计算出一个位置

• 最小栈

  • 从传入的列表中构造最小栈
  • 插入一个元素
  • 弹出一个元素
  • 取得最小元素
  • 清空所有元素

树

• 二叉树

  • 从先序列表和中序列表构造二叉树
  • 二叉树的先序递归遍历
  • 二叉树的中序递归遍历
  • 二叉树的后序递归遍历
  • 二叉树的先序非递归遍历
  • 二叉树的中序非递归遍历
  • 二叉树的后序非递归遍历
  • 二叉树的层序遍历

• 字典树

  • 通过strings_list构造一颗字典树
  • 增加一个串
  • 查找字典树中是否存在对应串
  • 查找与prefix具有相同前缀的串
  • 删除字典树中的串
  • 获取字典树中的串的数量
  • 清空所有元素
  • 遍历以node为结点的整个字典树

• 红黑树

  • 从一个值列表构造一颗红黑树
  • 递归向红黑树中插入一个结点
  • 删除红黑树中的最小值
  • 删除红黑树中的最大值
  • 删除红黑树中具体的key
  • 取得树中的最小结点
  • 取得树中的最大结点
  • 在红黑树中查询子节点
  • 将一个红色右链接的结点 旋转 成为一个红色左链接的结点
  • 将一个红色左链接的结点 旋转 成为一个红色右链接的结点
  • 将右、左子树的红色链接转上来
  • 将左、左子树的红色链接转上来
  • 删除以node为根的红黑树的最小结点
  • 删除以node为根的红黑树的最大结点
  • 删除以node为根的红黑树下键为key的结点
  • 获取以node为根的树下最小结点
  • 获取以node为根的树下最大结点
  • 对node结点进行平衡操作

• 二叉平衡树

  • TODO

• 堆

  • 通过数组构造一个堆
  • 向堆中插入一个元素
  • 取出堆顶元素
  • 判断堆是否是空的
  • 清空所有元素
  • 将数组变成一个堆
  • 堆中index结点上浮
  • 堆中index结点下沉

图

• 并查集

  • 初始化结点
  • 采用quick-find方式实现union find
  • 采用quick-union方式实现union find
  • 采用加权quick-union方式实现union find
  • 判断两个结点是否连通
  • 连通结点组成的不同的连通分量数量

• 无向图

  • 通过传入边的列表来构造图
  • 向图中插入一条边
  • 从图中删除一条边
  • 取得结点的度
  • 取得对应边的权重
  • 取得边的数量
  • 判断是否是连通图
  • 用prim算法寻找最小生成树
  • 清空图

经典算法

排序算法

• 冒泡排序
• 选择排序
• 插入排序
• 快速排序
• 归并排序
• （计数）/ 桶排序
• 堆排序
• 希尔排序
• 基数排序

搜索算法

• 二分查找
• 二分查找左右边界

回溯算法

• 子集
• 组合
• 全排列

位运算

• 二进制中1的数量
• 翻转二进制表示

LeetCode

题目	链接
1.两数之和.py	1.两数之和.py
2.两数相加.py	2.两数相加.py
3.无重复字符的最长子串.py	3.无重复字符的最长子串.py
4.寻找两个正序数组的中位数.py	4.寻找两个正序数组的中位数.py
5.最长回文子串.py	5.最长回文子串.py
19.删除链表的倒数第-n-个结点.py	19.删除链表的倒数第-n-个结点.py
22.括号生成.py	22.括号生成.py
25.k-个一组翻转链表.py	25.k-个一组翻转链表.py
26.删除有序数组中的重复项.py	26.删除有序数组中的重复项.py
27.移除元素.py	27.移除元素.py
34.在排序数组中查找元素的第一个和最后一个位置.py	34.在排序数组中查找元素的第一个和最后一个位置.py
40.组合总和-ii.py	40.组合总和-ii.py
42.接雨水.py	42.接雨水.py
45.跳跃游戏-ii.py	45.跳跃游戏-ii.py
46.全排列.py	46.全排列.py
47.全排列-ii.py	47.全排列-ii.py
51.n-皇后.py	51.n-皇后.py
52.n皇后-ii.py	52.n皇后-ii.py
53.最大子序和.py	53.最大子序和.py
55.跳跃游戏.py	55.跳跃游戏.py
64.最小路径和.py	64.最小路径和.py
67.二进制求和.py	67.二进制求和.py
69.x-的平方根.py	69.x-的平方根.py
70.爬楼梯.py	70.爬楼梯.py
72.编辑距离.py	72.编辑距离.py
74.搜索二维矩阵.py	74.搜索二维矩阵.py
75.颜色分类.py	75.颜色分类.py
76.最小覆盖子串.py	76.最小覆盖子串.py
77.组合.py	77.组合.py
78.子集.py	78.子集.py
79.单词搜索.py	79.单词搜索.py
81.搜索旋转排序数组-ii.py	81.搜索旋转排序数组-ii.py
88.合并两个有序数组.py	88.合并两个有序数组.py
91.解码方法.py	91.解码方法.py
92.反转链表-ii.py	92.反转链表-ii.py
95.不同的二叉搜索树-ii.py	95.不同的二叉搜索树-ii.py
96.不同的二叉搜索树.py	96.不同的二叉搜索树.py
98.验证二叉搜索树.py	98.验证二叉搜索树.py
101.对称二叉树.py	101.对称二叉树.py
102.二叉树的层序遍历.py	102.二叉树的层序遍历.py
103.二叉树的锯齿形层序遍历.py	103.二叉树的锯齿形层序遍历.py
104.二叉树的最大深度.py	104.二叉树的最大深度.py
105.从前序与中序遍历序列构造二叉树.py	105.从前序与中序遍历序列构造二叉树.py
106.从中序与后序遍历序列构造二叉树.py	106.从中序与后序遍历序列构造二叉树.py
107.二叉树的层序遍历-ii.py	107.二叉树的层序遍历-ii.py
108.将有序数组转换为二叉搜索树.py	108.将有序数组转换为二叉搜索树.py
110.平衡二叉树.py	110.平衡二叉树.py
111.二叉树的最小深度.py	111.二叉树的最小深度.py
114.二叉树展开为链表.py	114.二叉树展开为链表.py
116.填充每个节点的下一个右侧节点指针.py	116.填充每个节点的下一个右侧节点指针.py
121.买卖股票的最佳时机.py	121.买卖股票的最佳时机.py
122.买卖股票的最佳时机-ii.py	122.买卖股票的最佳时机-ii.py
123.买卖股票的最佳时机-iii.py	123.买卖股票的最佳时机-iii.py
130.被围绕的区域.py	130.被围绕的区域.py
135.分发糖果.py	135.分发糖果.py
136.只出现一次的数字.py	136.只出现一次的数字.py
139.单词拆分.py	139.单词拆分.py
141.环形链表.py	141.环形链表.py
142.环形链表-ii.py	142.环形链表-ii.py
154.寻找旋转排序数组中的最小值-ii.py	154.寻找旋转排序数组中的最小值-ii.py
167.两数之和-ii-输入有序数组.py	167.两数之和-ii-输入有序数组.py
172.阶乘后的零.py	172.阶乘后的零.py
188.买卖股票的最佳时机-iv.py	188.买卖股票的最佳时机-iv.py
190.颠倒二进制位.py	190.颠倒二进制位.py
191.位-1-的个数.py	191.位-1-的个数.py
198.打家劫舍.py	198.打家劫舍.py
204.计数质数.py	204.计数质数.py
213.打家劫舍-ii.py	213.打家劫舍-ii.py
215.数组中的第k个最大元素.py	215.数组中的第k个最大元素.py
221.最大正方形.py	221.最大正方形.py
226.翻转二叉树.py	226.翻转二叉树.py
230.二叉搜索树中第k小的元素.py	230.二叉搜索树中第k小的元素.py
231.2-的幂.py	231.2-的幂.py
234.回文链表.py	234.回文链表.py
236.二叉树的最近公共祖先.py	236.二叉树的最近公共祖先.py
257.二叉树的所有路径.py	257.二叉树的所有路径.py
279.完全平方数.py	279.完全平方数.py
283.移动零.py	283.移动零.py
297.二叉树的序列化与反序列化.py	297.二叉树的序列化与反序列化.py
300.最长递增子序列.py	300.最长递增子序列.py
309.最佳买卖股票时机含冷冻期.py	309.最佳买卖股票时机含冷冻期.py
310.最小高度树.py	310.最小高度树.py
316.去除重复字母.py	316.去除重复字母.py
322.零钱兑换.py	322.零钱兑换.py
326.3-的幂.py	326.3-的幂.py
341.扁平化嵌套列表迭代器.py	341.扁平化嵌套列表迭代器.py
343.整数拆分.py	343.整数拆分.py
344.反转字符串.py	344.反转字符串.py
347.前-k-个高频元素.py	347.前-k-个高频元素.py
376.摆动序列.py	376.摆动序列.py
406.根据身高重建队列.py	406.根据身高重建队列.py
413.等差数列划分.py	413.等差数列划分.py
416.分割等和子集.py	416.分割等和子集.py
417.太平洋大西洋水流问题.py	417.太平洋大西洋水流问题.py
435.无重叠区间.py	435.无重叠区间.py
437.路径总和-iii.py	437.路径总和-iii.py
450.删除二叉搜索树中的节点.py	450.删除二叉搜索树中的节点.py
451.根据字符出现频率排序.py	451.根据字符出现频率排序.py
452.用最少数量的箭引爆气球.py	452.用最少数量的箭引爆气球.py
455.分发饼干.py	455.分发饼干.py
474.一和零.py	474.一和零.py
494.目标和.py	494.目标和.py
496.下一个更大元素-i.py	496.下一个更大元素-i.py
504.七进制数.py	504.七进制数.py
516.最长回文子序列.py	516.最长回文子序列.py
518.零钱兑换-ii.py	518.零钱兑换-ii.py
524.通过删除字母匹配到字典里最长单词.py	524.通过删除字母匹配到字典里最长单词.py
538.把二叉搜索树转换为累加树.py	538.把二叉搜索树转换为累加树.py
540.有序数组中的单一元素.py	540.有序数组中的单一元素.py
542.01-矩阵.py	542.01-矩阵.py
543.二叉树的直径.py	543.二叉树的直径.py
547.省份数量.py	547.省份数量.py
567.字符串的排列.py	567.字符串的排列.py
583.两个字符串的删除操作.py	583.两个字符串的删除操作.py
605.种花问题.py	605.种花问题.py
633.平方数之和.py	633.平方数之和.py
637.二叉树的层平均值.py	637.二叉树的层平均值.py
650.只有两个键的键盘.py	650.只有两个键的键盘.py
652.寻找重复的子树.py	652.寻找重复的子树.py
654.最大二叉树.py	654.最大二叉树.py
665.非递减数列.py	665.非递减数列.py
680.验证回文字符串-ⅱ.py	680.验证回文字符串-ⅱ.py
695.岛屿的最大面积.py	695.岛屿的最大面积.py
700.二叉搜索树中的搜索.py	700.二叉搜索树中的搜索.py
701.二叉搜索树中的插入操作.py	701.二叉搜索树中的插入操作.py
714.买卖股票的最佳时机含手续费.py	714.买卖股票的最佳时机含手续费.py
752.打开转盘锁.py	752.打开转盘锁.py
763.划分字母区间.py	763.划分字母区间.py
875.爱吃香蕉的珂珂.py	875.爱吃香蕉的珂珂.py
876.链表的中间结点.py	876.链表的中间结点.py
934.最短的桥.py	934.最短的桥.py
1011.在-d-天内送达包裹的能力.py	1011.在-d-天内送达包裹的能力.py
1081.不同字符的最小子序列.py	1081.不同字符的最小子序列.py
1110.删点成林.py	1110.删点成林.py
1143.最长公共子序列.py	1143.最长公共子序列.py
1670.设计前中后队列.py	1670.设计前中后队列.py

数据结构思维导图

各排序算法时间复杂度