context
leetcode
数据结构和算法是一个程序员的基石，本仓库用于个人学习基本数据结构和算法。
题目完成度：[263/500]
[TOC]
一、基本数据结构
线性表(Linear List)是由N(N>=0)个数据元素组成的有限序列，一般记为a[0], a[1], ..., a[n-1]。
其中，表中的数据元素个数N定义为表的长度，当N=0称为空表。
数组属于线性表的一种，底层使用连续的空间进行存储，因此在声明数组的时候需要指定数组的大小，即需要申请多大的内存空间。
根据数组长度是否可以调整，还有动态数组的概念，即数组的长度是可调节的。golang语言中动态数组即为切片，Slice。
链表也属于线性表的一种，底层使用非连续的空间进行存储，因此在声明链表的时候不需要指定链表大小。
由于链表不必按照顺序存储，链表的插入操作可以达到O(1)的时间复杂度，而数组相应的操作平均需要O(logN)时间复杂度；但是，链表的查找和访问平均需要O(N)的时间复杂度，而数组相应的操作需要O(1)时间复杂度。
链表有很多不同的类型：单向链表，双向链表，以及循环链表。
相关题目
2 两数相加【M】
19 Remove Nth Node From End of List【M】
21 合并两个有序链表
23 合并K个排序链表
24 两两交换链表中的节点
61 Rotate List【旋转链表】
82 Remove Duplicates From Sorted List II
83 Remove Duplicates From Sorted List
86 Partition List
92 反转链表II
141 Linked List Cycle【E】
142 Linked List Cycle II【M】
143 Reorder List
147 Insertion Sort List【对链表进行插入排序】【M】
148 排序链表
160 Intersection of Two Linked List【E】
203 移除链表元素【E】
206 反转链表【E】
234 回文链表【E】
328 奇偶链表【M】
707 设计链表【M】
876 Middle of the Linked List
单向链表的排序
基本定义
相关题目
621 Task Scheduler【任务调度器】
622 Design Circular Queue
641 Design Circular Deque【M】
933 Number of Recent Calls
golang语言中byte是uint8的别名，rune是int32的别名，字符串中的单个字符有byte表示。
相关题目
14 Longest Common Prefix
有效的字母异位词
反转字符串
246 中心对称数【E】
58 最后一个单词的长度
521 最长特殊序列I【E】
哈希表的原理
哈希集合的设计
哈希映射的设计
相关题目
1 两数之和
202 快乐数
36 有效的数独
170 两数之和III - 数据结构设计
349 两个数组的交集
652 寻找重复的树【中等】
49 字母异位词分组【M】
四数相加II
常数时间插入，删除和获取
146 LRU缓存机制【M】
相关题目
8 String to Integer
9 Palindrome Number
15 三数之和
二、抽象数据结构
优先队列是一种抽象的数据结构，可以使用堆实现。
堆的定义
堆的算法
堆的排序
相关题目
912 排序数组【M】
1046 最后一块石头的重量
215 数组中第K个最大元素
面试题40 最小的K个数
面试题17.09 第K个数
二叉树属于非线性表的一种，与链表不同的是，二叉树有两个后继节点。
什么是二叉树
二叉树的遍历
前序遍历（递归和迭代）
中序遍历（递归和迭代）
后序遍历（递归和迭代）
层序遍历（广度优先搜索和深度优先搜索）
前中后三种遍历算法的迭代版本一定会使用栈数据结构，通过出栈检查每个结点来完成遍历；
层序遍历的广度优先搜索一定会使用队列，通过入队与出队检查每一层的结果。
递归解决二叉树问题
递归通常是解决树的相关问题最有效和最常用的方法之一，分为自顶向下和自底向上两种。
自顶向下的解决方案
自顶向下意味着在每个递归层级，需要先计算一些值，然后递归调用并将这些值传递给子节点，视为前序遍历。参见题目【二叉树的最大深度】
自底向上的解决方案
自底向上意味着在每个递归层级，需要先对子节点递归调用函数，然后根据返回值和根节点本身得到答案。
总结：
当遇到树的问题时，先思考一下两个问题：
1.你能确定一些参数，从该节点自身解决出发寻找答案吗？
2.你可以使用这些参数和节点本身的值来决定什么应该是传递给它子节点的参数吗？
如果答案是肯定的，那么可以尝试使用自顶向下的递归来解决问题。
当然也可以这样思考：对于树中的任意一个节点，如果你知道它子节点的结果，你能计算出该节点的答案吗？如果答案是肯定的，可以尝试使用自底向上的递归来解决问题。
相关题目
95 不同的二叉搜索树 II【中等】
98 验证二叉搜索树【中等】
101 对称二叉树【简单】
104 二叉树的最大深度【简单】
105 从前序与中序遍历序列构造二叉树【中等】
106 从中序和后序遍历序列构造二叉树【中等】
110 平衡二叉树【简单】
111 二叉树的最小深度【简单】
112 路径总和【简单】
156 上下翻转二叉树【中等】
199 二叉树的右视图【中等】
236 二叉树的最近公共祖先【中等】
257 二叉树的所有路径【简单】
270 最接近的二叉搜索树值【简单】
538 把二叉树转换成累加树【简单】
543 二叉树的直径【简单】
545 二叉树的边界【中等】
563 二叉树的坡度【简单】
617 合并二叉树【简单】
654 最大二叉树【中等】
655 输出二叉树【中等】
662 二叉树的最大宽度【中等】
669 修剪二叉搜索树【简单】
703 数据流中第K大元素【简单】
814 二叉树剪枝【中等】
993 二叉树的堂兄弟节点【简单】
1104 二叉树寻路【中等】
面试题27 二叉树的镜像【简单】
什么是二叉搜索树
二叉搜索树的基本操作
查询
最小关键字元素
最大关键字元素
前继节点
后继节点
插入
删除
相关题目
98 验证二叉搜索树【M】
108 将有序数组转换为二叉搜索树【M】
235 二叉搜素树的最近公共祖先
450 删除二叉搜索树中的节点
1038 从二叉搜索树到更大和树【M】
1214 查找两棵二叉搜索树之和【M】
面试题 17.12 BiNode【E】
面试题54 二叉搜索树的第K大节点
1.结构介绍
2.问题定义
3.表面形式
3.1更新操作
3.2求和操作
4.工作原理
5.代码实现
三、基本算法理论
算法不仅仅是一种解决问题的思路，更是一种思想。
排序算法
相关题目
704 二分查找
162 寻找峰值
658 找到K个最接近的元素
算法介绍
相关题目
55 跳跃游戏
45 跳远游戏II
递归思想
算法介绍
解题思路
相关题目
64 最小路径和【M】
70 爬楼梯
72 编辑距离【H】
121 买卖股票的最佳时机
122 买卖股票的最佳时机II
123 买卖股票的最佳时机III
188 买卖股票的最佳时机IV
746 使用最少花费爬楼梯
264 丑数【M】
300 最长上升子序列【M】
剪枝思想
剪枝是搜索算法的优化手段，目的是为了去掉不必要的搜索。
位1的个数
汉明距离
292 Nim游戏
89 格雷编码
最后更新于