Algorithms change the world

经典算法的实现(使用C++11标准):

• 🔧逆波兰符实现

• 🔧Manacher算法

• 🔧字符串匹配算法

  • 朴素字符串匹配算法

  • Rabin-Karp算法

  • 有限自动机的字符串匹配算法

  • KMP算法

• 🔧哈夫曼编码算法

• 🔧快速排序的递归和非递归实现

• 🔧堆排序和优先队列

• 🔧桶排序

• 二叉树(以下代码都是在刷LeetCode时写的, 所有只有功能函数, 请见谅！另外前序、中序、后序遍历算法都给出了递归和非递归两种实现方式)

  • 二叉树的前序遍历

  • 二叉树的中序遍历

  • 二叉树的后序遍历

  • 二叉树的层次遍历

  • 从前序和中序遍历序列构造二叉树

  • 从中序和后序遍历序列构造二叉树

• 🔧二叉搜索树(BST)(其中删除节点操作在LeetCode刷题时使用了递归方法, 中序遍历给出了递归、使用栈的非递归以及不使用栈的非递归实现)

• 🔧一种自平衡二叉搜索树---红黑树

• 🔧图的两种遍历方式

  • 广度优先遍历 这种方式最终会生成关于图的一棵广度优先树, 得到源点s到其余点的最短路径(边数最少)

  • 深度优先遍历 这种方式最终会生成关于图的深度优先森林, 节点访问时间和结束时间具有括号化结构

• 🔧有向无环图的拓扑排序算法

• 🔧最小生成树

  • Kruskal算法

  • Prim算法

• 🔧单源点最短路径

  • 一般情况下的Bellman-Ford算法

  • 有向无环图的基于拓扑排序的DAG算法

  • 使用动态规划的非负权重有向图的Dijkstra算法

• 🔧所有节点对最短路径

  • 基于重复平方矩阵乘法的动态规划算法

  • Floyd-Warshall算法

  • 有向图的传递闭包求解算法

部分题目的证明:

• 🔧第287题证明(映射,环检测)

• 🔧309题状态机用到动态规划

• 🔧Catalan公式证明(建立双射法)

• 🔧回文子串问题(Manacher算法的说明)

• 🔧环链表问题(快慢指针法的证明)

• 🔧编辑距离问题(算法导论中6种字符操作, LeetCode中3种字符操作)

LeetCode刷题:

• 🎉 感谢gzh提供了Java的解题代码。
• C++、Python、Go的代码由我完成。

ID	Title	Difficulty	C++	Java	Python	Go
001	两数之和	Easy	Code	Code	Code	Code
002	两数相加	Medium	Code	Code	Code	Code
003	无重复字符的最长子串	Medium	Code	Code	Code
004	两个排序数组的中位数	Hard	Code	Code	Code
005	最长回文子串	Medium	Code	Code	Code
006	Z字形变换	Medium	Code	Code	Code
007	反转整数	Easy	Code	Code	Code
008	字符串转整数 (atoi)	Medium	Code	Code	Code
009	回文数	Easy	Code	Code	Code
010	正则表达式匹配	Hard	Code	Code	Code
011	盛最多水的容器	Medium	Code	Code	Code
012	整数转罗马数字	Medium	Code	Code	Code
014	最长公共前缀	Easy	Code	Code	Code
015	三数之和	Medium	Code	Code	Code
016	最接近的三数之和	Medium	Code	Code	Code
017	电话号码的字母组合	Medium	Code	Code	Code
018	四数之和	Medium	Code	Code	Code
019	删除链表的倒数第N个节点	Medium	Code	Code	Code
020	有效的括号	Easy	Code	Code	Code
021	合并两个有序链表	Easy	Code	Code	Code
022	括号生成	Medium	Code	Code	Code
023	合并K个排序链表	Hard	Code	Code	Code
024	两两交换链表中的节点	Medium	Code	Code	Code
026	删除排序数组中的重复项	Easy	Code	Code	Code
027	移除元素	Easy	Code	Code	Code
030	与所有单词相关联的字串	Hard	Code	Code	Code
031	下一个排列	Medium	Code	Code	Code
032	最长有效括号	Hard	Code	Code	Code
033	搜索旋转排序数组	Medium	Code	Code	Code
034	在排序数组中查找元素的第一个和最后一个位置	Medium	Code	Code	Code
035	搜索插入位置	Easy	Code	Code	Code
036	有效的数独	Medium	Code	Code	Code
037	解数独	Hard	Code	Code	Code
039	组合总和	Medium	Code	Code	Code
040	组合总和2	Medium	Code	Code	Code
041	缺失的第一个正数	Hard	Code	Code	Code
042	接雨水	Hard	Code	Code	Code
043	字符串相乘	Medium	Code	Code	Code
044	通配符匹配	Hard	Code	Code	Code
045	跳跃游戏2	Hard	Code	Code	Code
046	全排列	Medium	Code	Code	Code
047	全排列2	Medium	Code	Code	Code
048	旋转图像	Medium	Code	Code	Code
049	字母异位词分组	Medium	Code	Code	Code
050	Pow(x,n)	Medium	Code	Code	Code
051	N皇后	Hard	Code	no	Code
052	N皇后2	Hard	Code	no	Code
053	最大子序和	Easy	Code	Code	Code
054	螺旋矩阵	Medium	Code	Code	Code
055	跳跃游戏	Medium	Code	Code	Code
056	合并区间	Medium	Code	Code	Code
057	插入区间	Hard	Code	Code	Code
058	最后一个单词的长度	Easy	Code	Code	Code
059	螺旋矩阵2	Medium	Code	Code	Code
060	第k个排列	Medium	Code	Code	no
061	旋转链表	Medium	Code	Code	no
062	不同的路径	Medium	Code	Code	no
063	不同路径	Medium	Code	Code	no
064	最小路径和	Medium	Code	Code	no
065	有效数字	Hard	Code	Code	no
066	加一	Easy	Code	Code	no
067	二进制求和	Easy	Code	Code	no
068	文本左右对齐	Hard	Code	Code	no
070	爬楼梯	Easy	Code	Code	no
071	简化路径	Medium	Code	Code	no
072	编辑距离	Hard	Code	Code	no
074	搜索二维矩阵	Medium	Code	Code	no
075	分类颜色	Medium	Code	Code	no
076	最小覆盖子串	Hard	Code	Code	no
077	组合	Medium	Code	Code	no
078	子集	Medium	Code	Code	no
079	单词搜索	Medium	Code	Code	no
080	删除排序数组中的重复项2	Medium	Code	Code	no
082	删除排序链表中的重复元素2	Medium	Code	Code	no
083	删除排序链表中的重复元素	Easy	Code	Code	no
084	柱状图中的最大矩形	Hard	Code	Code	no
085	最大矩形	Hard	Code	Code	no
086	分隔链表	Medium	Code	Code	no
090	子集2	Medium	Code	Code	no
091	解码方法	Medium	Code	no	no
092	反转链表2	Medium	Code	no	no
093	复原IP地址	Medium	Code	no	no
094	二叉树的中序遍历	Medium	Code	no	Code	Code
095	不同的二叉搜索树2	Medium	Code	no	Code	Code
096	不同的搜索二叉树	Medium	Code	no	Code	Code
097	交错字符串	Hard	Code	no	no
098	验证二叉搜索树	Medium	Code	no	Code	Code
099	恢复二叉搜索树	Hard	Code	no	Code	Code
100	相同的树	Easy	Code	no	Code	Code
101	对称二叉树	Easy	Code	no	Code	Code
102	二叉树的层次遍历	Medium	Code	no	Code	Code
103	二叉树的锯齿层次遍历	Medium	Code	no	Code	Code
104	二叉树的最大深度	Easy	Code	no	Code	Code
105	前序中序构造二叉树	Medium	Code	no	Code	Code
106	中序后序构造二叉树	Medium	Code	no	Code	Code
107	二叉树的层次遍历2	Easy	Code	no	Code	Code
108	将有序数组转换为二叉搜索树	Easy	Code	no	Code	Code
109	有序链表转换二叉搜索树	Medium	Code	no	Code	Code
110	平衡二叉树	Easy	Code	no	Code	Code
111	二叉树的最小深度	Easy	Code	no	Code	Code
112	路径总和	Easy	Code	no	Code	Code
113	路径总和2	Medium	Code	no	Code	Code
114	二叉树展开为链表	Medium	Code	no	Code	Code
115	不同的子序列	Hard	Code	no	no
116	填充同一层的兄弟节点	Medium	Code	no	Code	没有解题选项
117	填充同一层的兄弟节点2	Medium	Code	no	Code	没有解题选项
118	杨辉三角形	Easy	Code	no	no
119	杨辉三角形2	Easy	Code	no	no
120	三角形最短路径和	Medium	Code	no	no
121	买卖股票的最佳时机	Easy	Code	no	no
122	买卖股票的最佳时机2	Easy	Code	no	no
123	买卖股票的最佳时机3	Hard	Code	no	no
124	二叉树中的最大路径和	Hard	Code	no	Code	Code
127	单词接龙	Medium	Code	no	no
128	最长连续序列	Hard	Code	no	no
129	求根到叶子节点数字之和	Medium	Code	no	Code	Code
131	分割回文串	Medium	Code	no	no
132	分割回文串2	Hard	Code	no	no
133	克隆图	Medium	Code	no	no
134	加油站	Medium	Code	no	no
135	分发糖果	Hard	Code	no	no
139	单词拆分	Medium	Code	no	no
140	单词拆分2	Hard	Code	no	no
141	环形链表	Easy	Code	no	no
142	环形链表2	Medium	Code	no	no
144	二叉树的前序遍历	Medium	Code	no	Code	Code
145	二叉树的后序遍历	Hard	Code	no	Code	Code
146	LRU缓存机制	Hard	Code	no	no
147	对链表进行插入排序	Medium	Code	no	no
148	排序链表	Medium	Code	no	no
150	逆波兰符求值	Medium	Code	no	no
152	最大乘积子序列	Medium	Code	no	no
160	相交链表	Easy	Code	no	no
162	寻找峰值	Medium	Code	no	no
164	最大间距	Hard	Code	no	no
165	比较版本号	Medium	Code	no	no
168	Excel表列名称	Easy	Code	no	no
169	求众数	Easy	Code	no	no
172	阶乘后的零	Easy	Code	no	no
173	二叉搜索树迭代器	Medium	Code	no	Code	Code
174	地下城游戏	Hard	Code	no	no
179	最大数	Medium	Code	no	no
188	买卖股票的最佳时机IV	Hard	Code	no	no
198	打家劫舍	Easy	Code	no	no
199	二叉树的右视图	Medium	Code	no	Code
200	岛屿的个数	Medium	Code	no	no
203	删除链表中的节点	Easy	Code	no	no
206	反转链表	Easy	Code	no	no
207	课程表	Medium	Code	no	no
208	实现Trie(前缀树)	Medium	Code	no	no
209	长度最小的子数组	Medium	Code	no	no
210	课程表2	Medium	Code	no	no
211	添加与搜索单词-数据结构设计	Medium	Code	no	no
212	单词搜索2	Hard	Code	no	no
213	打家劫舍2	Medium	Code	no	no
214	最短回文串	Hard	Code	no	no
215	数组中第k大个元素	Medium	Code	no	no
216	组合总和3	Medium	Code	no	no
218	天际线问题	Hard	Code	no	no
221	最大正方形	Medium	Code	no	no
222	完全二叉树的节点个数	Medium	Code	no	no
223	矩形面积	Medium	Code	no	no
226	翻转二叉树	Easy	Code	no	no
228	汇总区间	Medium	Code	no	no
229	求众数2	Medium	Code	no	no
230	二叉搜索树中第K小的元素	Medium	Code	no	no
234	回文链表	Easy	Code	no	no
235	二叉搜索树的最近公共祖先	Easy	Code	no	no
236	二叉树的最近公共祖先	Medium	Code	no	no
237	删除二叉树中的节点	Easy	Code	no	no
238	除自身以外数组的乘积	Medium	Code	no	no
239	滑动窗口最大值	Hard	Code	no	no
240	搜索二维矩阵2	Medium	Code	no	no
241	为运算表达式设计优先级	Medium	Code	no	no
257	二叉树的所有路径	Easy	Code	no	no
264	丑数2	Medium	Code	no	no
274	H指数	Medium	Code	no	no
279	完全平方数	Medium	Code	no	no
282	给表达式添加运算符	Hard	Code	no	no
284	顶端迭代器	Medium	Code	no	no
287	寻找重复数	Medium	Code	no	no
289	生命游戏	Medium	Code	no	no
295	数据流的中位数	Hard	Code	no	no
297	二叉树的序列化与反序列化	Hard	Code	no	Code	没有解题选项
299	猜数字游戏	Medium	Code	no	no
300	最长上升子序列	Medium	Code	no	no
301	删除无效的括号	Hard	Code	no	no
303	区域和检索-数组不可变	Easy	Code	no	no
304	二维区域和检索-矩阵不可变	Medium	Code	no	no
309	最佳买卖股票时机含冷冻期	Medium	Code	no	no
310	最小高度树	Medium	Code	no	no
312	戳气球	Hard	Code	no	no
315	计算右侧小于当前元素的个数	Hard	Code	no	no
316	去除重复字母	Hard	Code	no	no
319	灯泡开关	Medium	Code	no	no
321	拼接最大数	Hard	Code	no	no
322	零钱兑换	Medium	Code	no	no
326	3的幂	Easy	Code	no	no
328	奇偶链表	Medium	Code	no	no
329	矩阵中的最长递增路径	Hard	Code	no	no
331	验证二叉树的前序序列化	Medium	Code	no	no
332	重新安排行程	Medium	Code	no	no
334	递增的三元子序列	Medium	Code	no	no
336	回文对	Hard	Code	no	no
337	打家劫舍3	Medium	Code	no	no
341	扁平化嵌套列表迭代器	Medium	Code	no	no
343	整数拆分	Medium	Code	no	no
344	反转字符串	Medium	Code	no	no
347	前K个高频元素	Medium	Code	no	no
354	俄罗斯套娃信封问题	Hard	Code	no	no
357	计算各个位数不同的数字个数	Medium	Code	no	no
365	水壶问题	Medium	Code	no	no
368	最大整除子集	Medium	Code	no	no
373	查找和最小的K对数字	Medium	Code	no	no
376	摆动序列	Medium	Code	no	no
377	组合总和Ⅳ	Medium	Code	no	no
378	有序矩阵中第K小的元素	Medium	Code	no	no
380	常数时间插入、删除和获取随机元素	Medium	Code	no	no
381	O(1)时间插入、删除和获取随机元素-允许重复	Hard	Code	no	no
387	字符串中的第一个唯一字符	Easy	Code	no	no
394	字符串解码	Medium	Code	no	no
395	至少有K个重复字符的最长子串	Medium	Code	no	no
396	旋转函数	Medium	Code	no	no
402	移掉K位数字	Medium	Code	no	no
403	青蛙过河	Hard	Code	no	no
404	左叶子之和	Easy	Code	no	no
406	根据身高重建队列	Medium	Code	no	no
409	最长回文串	Easy	Code	no	no
413	等差数列划分	Medium	Code	no	no
416	分割等和子集	Medium	Code	no	no
424	替换后的最长重复字符	Medium	Code	no	no
429	N叉树的层序遍历	Easy	Code	no	no
433	最小基因变化	Medium	Code	no	no
435	无重叠区间	Medium	Code	no	no
436	寻找右区间	Medium	Code	no	no
437	路径总和3	Easy	Code	no	no
442	数组中的重复数据	Medium	Code	no	no
445	两数相加2	Medium	Code	no	no
449	序列化和反序列化二叉搜索树	Medium	Code	no	no
450	删除二叉搜索树中的节点	Medium	Code	no	no
451	根据字符出现频率排序	Medium	Code	no	no
452	用最少数量的箭引爆气球	Medium	Code	no	no
454	四数之和2	Medium	Code	no	no
456	132模式	Medium	Code	no	no
462	最少移动次数使数组元素相等2	Medium	Code	no	no
472	连接词	Hard	Code	no	no
474	一和零	Medium	Code	no	no
486	预测赢家	Medium	Code	no	no
488	祖玛游戏	Hard	Code	no	no
491	递增子序列	Medium	Code	no	no
494	目标和	Medium	Code	no	no
495	提莫攻击	Medium	Code	no	no
501	二叉搜索树中的众数	Easy	Code	no	no
503	下一个更大元素2	Medium	Code	no	no
508	出现次数最多的子树元素和	Medium	Code	no	no
513	找树左下角的值	Medium	Code	no	no
515	在每个树行中找最大值	Medium	Code	no	no
516	最长回文子序列	Medium	Code	no	no
518	零钱兑换2	Medium	Code	no	no
520	检测大写字母	Easy	Code	no	no
524	通过删除字母匹配到字典里最长单词	Medium	Code	no	no
525	连续数组	Medium	Code	no	no
526	优美的排列	Medium	Code	no	no
538	把二叉搜索树转换为累加树	Easy	Code	no	no
540	有序数组中的单一元素	Medium	Code	no	no
542	01矩阵	Medium	Code	no	no
543	二叉树的直径	Easy	Code	no	no
547	朋友圈	Medium	Code	no	no
552	学生出勤记录	Hard	Code	no	no
554	砖墙	Medium	Code	no	no
559	N叉树的最大深度	Easy	Code	no	no
560	和为K的子数组	Medium	Code	no	no
572	另一个树的子树	Easy	Code	no	no
576	出界的路径数	Medium	Code	no	no
583	两个字符串的删除操作	Medium	Code	no	no
589	N叉树的前序遍历	Easy	Code	no	no
590	N叉树的后序遍历	Easy	Code	no	no
617	合并二叉树	Easy	Code	no	no
623	在二叉树中增加一行	Medium	Code	no	no
630	课程表3	Hard	Code	no	no
637	二叉树的层平均值	Easy	Code	no	no
646	最长数对链	Medium	Code	no	no
647	回文子串	Medium	Code	no	no
650	只有两个键的键盘	Medium	Code	no	no
654	最大二叉树	Medium	Code	no	no
655	输出二叉树	Medium	Code	no	no
658	找到 K 个最接近的元素	Medium	Code	no	no
662	二叉树最大宽度	Medium	Code	no	no
670	最大交换	Medium	Code	no	no
671	二叉树中第二小的节点	Easy	Code	no	no
673	最长递增子序列的个数	Medium	Code	no	no
677	键值映射	Medium	Code	no	no
678	有效的括号字符串	Medium	Code	no	no
679	24点游戏	Hard	Code	no	no
684	冗余连接	Medium	Code	no	no
688	“马”在棋盘上的概率	Medium	Code	no	no
692	前K个高频单词	Medium	Code	no	no
700	二叉搜索树中的搜索	Easy	Code	no	no
701	二叉搜索树中的插入操作	Medium	Code	no	no
704	二分查找	Easy	Code	no	no
712	两个字符串的最小ASCII删除和	Medium	Code	no	no
718	最长重复子数组	Medium	Code	no	no
721	账户合并	Medium	Code	no	no
725	分隔链表	Medium	Code	no	no
729	我的日程安排表1	Medium	Code	no	no
731	我的日程安排表2	Medium	Code	no	no
738	单调递增的数字	Medium	Code	no	no
739	每日温度	Medium	Code	no	no
740	删除与获得点数	Medium	Code	no	no
743	网络延迟时间	Medium	Code	no	no
765	情侣牵手	Hard	Code	no	no
797	所有可能路径	Easy	Code	no	no
802	找到最终的安全状态	Medium	Code	no	no
807	保持城市天际线	Medium	Code	no	no
814	二叉树剪枝	Medium	Code	no	no
841	钥匙和房间	Medium	Code	no	no
894	所有可能的满二叉树	Medium	Code	no	no
919	完全二叉树插入器	Medium	Code		Code	Code
987	二叉树的垂序遍历	Medium	Code