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

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

LeetCode

1. 数组

   • 搜索二维矩阵
   • 数组中重复的数据
   • 合并两个有序数组
   • 删除排序数组中的重复项
   • 旋转数组
   • 有序数组的平方
   • 寻找数组的中心索引
   • 移动零
   • 打乱数组
   • 两个数组的交集II
   • 递增的三元子序列
   • 除自身以外数组的乘积
   • 存在重复元素II
   • 存在重复元素III
   • 矩阵置零
   • 最大子序和
   • 按奇偶排序数组

2. 链表

   • 从尾到头打印链表
   • 移除链表元素
   • 删除链表中的节点
   • 删除排序链表中的重复元素
   • 判断链表是否有环

3. 字符串

   • 替换字符串中的空格
   • Fizz Buzz
   • 验证回文字符
   • 最后一个单词的长度
   • 最常见的单词
   • 字符串中的第一个唯一字符
   • 根据字符出现频率排序
   • 验证回文串
   • 分割回文串
   • 单词拆分

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

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

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

   2. 栈

      • 顺序栈（基于数组实现的栈）
      • 链式栈（基于链表实现的栈）
      • 有效的括号
      • 用两个栈实现一个队列

   3. 队列

      • 顺序队列（基于数组实现的队列）
      • 链式队列（基于链表实现的队列）
      • 循环队列（基于数组成环）
      • 滑动窗口最大值
      • 用两个队列实现一个栈

5. 递归

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

6. 分治

   • x的n次方

7. 排序

   • 冒泡排序
   • 插入排序
   • 选择排序
   • 快速排序
   • 计数排序

8. 二分查找

   • 二分查找(递归和非递归实现)

9. 二分查找变种

   • 查找第一个值等于给定值的元素
   • 查找最后一个值等于给定值的元素
   • 查找第一个大于等于给定值的元素
   • 查找最后一个小于等于给定值的元素
   • x的平方根

10. 反转

    • 反转一个数组
    • 反转一个单链表
    • 反转一颗二叉树
    • 反转字符串
    • 反转字符串中的单词III
    • 转置矩阵

11. 二叉树

    1. 二叉树

       • 二叉树的下一个节点
       • 相同的树
       • 对称二叉树

    2. 二叉查找树

       • 二叉查找树的插入、遍历、查找、删除、反转
       • 二叉树的最近公共祖先
       • 二叉查找树的最近公共祖先
       • 验证二叉搜索树(递归和非递归实现)
       • 二叉搜索树中第K小的元素
       • 二叉树的右视图
       • 二叉树的锯齿形层次遍历

12. 堆

    • 大顶堆、堆排序
    • TopK
    • 数组中的第K个最大元素
    • 前K个高频元素
    • 前K个高频单词

13. 散列表

    • 有效的异位词
    • 两数之和
    • 两数之和II - 输入有序数组
    • 两数之和IV - 输入BST
    • 存在重复元素
    • 字典序列化

14. 求数

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

15. 贪心

    • 买卖股票的最佳时机
    • 分发饼干

16. 搜索

    • 广度优先搜索
    • 深度优先搜索
    • 二叉树的层次遍历
    • 二叉树的最大深度(广度优先的非递归实现和深度优先的递归实现)
    • 二叉树的最小深度

17. 图

    • 图的表示

18. 剪枝

    • 数独(sudoku)

19. LRUCache(最近最少使用缓存)

    • LRUCache的实现

20. 动态规划(DP)

    • 爬楼梯
    • 三角形最小路径和
    • 乘积最大子序列
    • 斐波拉契数列的4种解法

21. 位运算

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

22. 滑动窗口

    • 一个数组所有连续K个元素构成的子集的平均数

PAT

1. 1001. 害死人不偿命的(3n+1)猜想(15分)
2. 1002. 写出这个数(20分)
3. 1004. 成绩排名(20分)
4. 1005. 继续(3n+1)猜想(25分)
5. 1006. 换个格式输出整数(15分)
6. 1007. 素数对猜想(20分)
7. 1008. 数组元素循环右移问题(20分)
8. 1009. 说反话(20分)
9. 1010. 一元多项式求导(25分)
10. 1011. A+B 和 C(15分)
11. 1012. 数字分类(20分)
12. 1014. 福尔摩斯的约会(20分)
13. 1015. 德才论(25分)(Java版本运行超时)
14. 1016. 部分A+B(15分)