常见数据结构与算法小结（Java语言描述）

这是一个数据结构和算法笔记本，书写 并 整理一些常见的数据结构和其对应的相关操作。这其中每一个类文件都是一个可以单独运行查看结果的main方法类 ，相关的关键描述和想说的话都在代码的注释中。（欢迎一同补充和完善，2019年01月04日00:07:40置为public）

1. 数组

   • 搜索二维矩阵
   • 数组中重复的数据
   • 合并两个有序数组
   • 旋转数组
   • 有序数组的平方
   • 寻找数组的中心索引
   • 两个数组的交集II
   • 递增的三元子序列
   • 除自身以外数组的乘积
   • 存在重复元素II
   • 存在重复元素III
   • 矩阵置零
   • 1486.数组异或操作

2. 线性数据结构及其对应的常见算法

   1. 线性表(分别基于数组和链表实现一遍)

      • 线性表的增加（基于顺序存储的物理结构实现）
      • 线性表的删除（基于顺序存储的物理结构实现）
      • 线性表的插入（基于链式存储的物理结构实现）
      • 线性表的删除（基于链式存储的物理结构实现）
      • 线性表的创建（基于链式存储的物理结构）头插法和尾插法
      • 查找线性表中的某一个元素（基于链式存储的物理结构实现）

   2. 栈

      • 顺序栈（基于数组实现的栈）
      • 链式栈（基于链表实现的栈）

   3. 队列

      • 顺序队列（基于数组实现的队列）
      • 链式队列（基于链表实现的队列）
      • 循环队列（基于数组成环）

3. 递归

   • n的阶乘
   • 斐波拉切数列
   • 位于第几排问题（递归、非递归分别实现）
   • n个台阶走法问题（每次可以走1个台阶或者2个台阶）
   • 输出指定路径下的所有文件名（递归、非递归分别实现）

4. 分治

   • x的n次方

5. 堆

   • TopK
   • 数组中的第K个最大元素
   • 前K个高频元素
   • 前K个高频单词

6. 求数

   • 求众数
   • 加一
   • Nim游戏
   • 回文数
   • 猜数字游戏

7. 搜索

   • 广度优先搜索
   • 深度优先搜索

8. 图

   • 图的表示

LeetCode

1. 反转

   • 反转一个数组
   • 206.反转链表
   • 226.翻转二叉树
   • 344.反转字符串
   • 541.反转字符串II
   • 557.反转字符串中的单词III
   • 867.转置矩阵
   • 反转单链表的一部分区间

2. 二叉树

   • 144.二叉树的前序遍历
   • 二叉树的下一个节点
   • 100.相同的树
   • 101.对称二叉树
   • 116.填充每个节点的下一个右侧节点指针
   • 114.将二叉树展开为链表
   • 654.最大二叉树
   • 105.从前序与中序遍历序列构造二叉树
   • 106.从中序与后序遍历序列构造二叉树
   • 寻找重复的子树
   • 297. 二叉树的序列化和反序列化(前序遍历的序列化方式实现)
   • 297. 二叉树的序列化和反序列化(后序遍历的序列化方式实现)
   • 110.平衡二叉树
   • 剑指offer 55.二叉树的深度
   • 104.二叉树的最大深度
   • 559.N叉树的最大深度
   • 111.二叉树的最小深度
   • 二叉树的节点个数
   • 222.完全二叉树的节点个数
   • 572.另一个树的子树
   • 404.左叶子之和
   • 617.合并二叉树
   • 236.二叉树的最近公共祖先
   • 814.二叉树剪枝
   • 965.单值二叉树

3. 二叉查找树

   • 700.二叉搜索树中的搜索
   • 98.验证二叉搜索树
   • 530.二叉搜索树的最小绝对差
   • 783.二叉搜索树节点最小距离
   • 501.二叉搜索树中的众数
   • 230.二叉搜索树中第K小的元素
   • 538.把二叉搜索树转换为累加树
   • 701.二叉搜索树中的插入操作
   • 450.删除二叉搜索树中的节点
   • 二叉查找树的插入、遍历、查找、删除、反转
   • 235.二叉查找树的最近公共祖先
   • 剑指offer 36. 二叉搜索树与双向链表
   • 108.将有序数组转换为二叉搜索树
   • 109.有序链表转换二叉搜索树
   • 剑指offer 54.二叉搜索树的第k大节点

4. 二分查找

   • 704.二分查找
   • 69.x的平方根
   • 374.猜数字大小
   • 33.搜索旋转排序数组
   • 278.第一个错误的版本
   • 162.寻找峰值
   • 852.山脉数组的峰顶索引
   • 剑指 Offer II 069.山峰数组的顶部
   • 153.寻找旋转排序数组中的最小值
   • 34.在排序数组中查找元素的第一个和最后一个位置
   • 二分查找(递归和非递归实现)
   • 查找第一个值等于给定值的元素
   • 查找最后一个值等于给定值的元素
   • 查找第一个大于等于给定值的元素
   • 查找最后一个小于等于给定值的元素
   • 35.搜索插入位置
   • 剑指 Offer II 068.查找插入位置

5. 双指针

   • 141.环形链表
   • 142.环形链表II (已知链表当中有环，返回这个环的起始位置)
   • 876.链表的中间节点
   • 剑指offer 22.链表中倒数第k个节点
   • 167.两数之和II - 输入有序数组
   • 905.按奇偶排序数组
   • 26.删除排序数组中的重复项
   • 83.删除排序链表中的重复元素
   • 27.移除元素
   • 283.移动零
   • 287.寻找重复数
   • 15.三数之和
   • 18.四数之和
   • 剑指offer 05.替换空格
   • 剑指 Offer II 014.字符串中的变位词
   • 剑指 Offer II 015.字符串中的所有变位词
   • 11.盛最多水的容器
   • 42.接雨水

6. 滑动窗口

   • 一个数组所有连续K个元素构成的子集的平均数
   • 最小覆盖子串
   • 字符串的排列
   • 找到字符串中所有字母异位词
   • 无重复字符的最长子串
   • 209.长度最小的子数组
   • 239.滑动窗口最大值

7. 数据结构设计

   • 146.LRU缓存机制
   • 380.常数时间插入、删除和获取随机元素
   • 232.用栈实现队列
   • 225.用队列实现栈

8. 位运算

   • 位1的个数
   • 2的幂
   • 比特位计数
   • 136.只出现一次的数字
   • 缺失数字

9. 回溯(DFS) + 剪枝

   • 排列
     • [46.全排列](/src