常见数据结构与算法小结（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.全排列
     • 47.全排列II
   • 组合
     • 77.组合
     • 216.组合总和III
     • 39.组合总和
     • 17.电话号码的字母组合
     • 40.组合总和II
   • 分割
     • 131.分割回文串
     • 93. 复原IP地址
   • 子集
     • 78.子集
     • 90.子集II
     • 491.递增子序列
   • 棋盘
     • 51.N皇后
     • 37.解数独
   • 路径
     • 112.路径总和
     • 113.路径总和II
     • 257.二叉树的所有路径

10. 广度优先搜索(BFS)

    • 111.二叉树的最小深度
    • 102.二叉树的层序遍历
    • 107.二叉树的层序遍历II
    • 199.二叉树的右视图
    • 637.二叉树的层平均值
    • 429.N叉树的层序遍历
    • 513.找树左下角的值
    • 剑指offer 32 - I.从上到下打印二叉树
    • 剑指offer 32 - II.从上到下打印二叉树II
    • 剑指offer 32 - III.从上到下打印二叉树III
    • 103.二叉树的锯齿形层次遍历
    • 117.填充每个节点的下一个右侧节点指针II

11. 数组

    • 59.螺旋矩阵II
    • 384.打乱数组

12. 链表

    • 203.移除链表元素
    • 707.设计链表
    • 剑指offer 06.从尾到头打印链表
    • 剑指offer 18.删除链表中的节点
    • 234.回文链表

13. 哈希表

    • 242.有效的字母异位词
    • 349.两个数组的交集
    • 202.快乐数
    • 1.两数之和
    • 454.四数相加II
    • 383.赎金信
    • 有效的异位词
    • 两数之和IV - 输入BST
    • 存在重复元素
    • 字典序列化
    • 560.和为 K 的子数组
    • 剑指 Offer II 011.0 和 1 个数相同的子数组
    • 剑指 Offer II 012.左右两边子数组的和相等
    • 剑指 Offer II 013.二维子矩阵的和

14. 字符串

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

15. 排序

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

16. 贪心

    • 455.分发饼干
    • 376.摆动序列
    • 53.最大子序和
    • 122.买卖股票的最佳时机II

17. 动态规划(DP)

    • 斐波拉切
      • 斐波拉契数列的4种解法
      • 509.斐波那契数
      • 70.爬楼梯
      • 746.使用最小花费爬楼梯
    • 路径
      • 60.不同路径
      • 63.不同路径II
    • 96.不同的二叉搜索树
    • 343.整数拆分
    • 三角形最小路径和
    • 乘积最大子序列
    • 打家劫舍
      • 198.打家劫舍
      • 213.打家劫舍II
      • 337.打家劫舍III
    • 杨辉三角
      • 118.杨辉三角
      • 119.杨辉三角II

18. 栈

    • 20.有效的括号
    • 1047.删除字符串中的所有相邻重复项
    • 150.逆波兰表达式求值
    • 单调栈
      • 739.每日温度

多线程

• 1114.按序打印
• 1115.交替打印FooBar
• 1116.打印零与奇偶数
• 1117.H2O生成
• 1195.交替打印字符串
• 1226.哲学家进餐

SQL

• 175.组合两个表
• 176.第二高的薪水
• 177.第N高的薪水
• 178.分数排名
• 180.连续出现的数字
• 181.超过经理收入的员工
• 182.查找重复的电子邮箱
• 183.从不订购的客户
• 196.删除重复的电子邮箱
• 197.上升的温度
• 511.游戏玩法分析I
• 584.寻找用户推荐人
• 595.大的国家
• 1757.可回收且低脂的产品
• 1873.计算特殊奖金
• 627.变更性别
• 586.订单最多的客户
• 620.有趣的电影
• 596.超过5名学生的课
• 1667.修复表中的名字
• 1484.按日期分组销售产品
• 1527.患某种疾病的患者
• 607.销售员
• 608.树节点
• 1084.销售分析III
• 626.换座位
• 1050.合作过至少三次的演员和导演
• 1148.文章浏览I
• 1179.重新格式化部门表
• 1407.排名靠前的旅行者
• 1581.进店却未进行过交易的顾客
• 1795.每个产品在不同商店的价格
• 1965.丢失信息的雇员
• 1729.求关注者的数量
• 1890.2020年最后一次登录
• 1393.股票的资本损益
• 1141.查询近30天活跃用户数
• 184.部门工资最高的员工
• 1741.查找每个员工花费的总时间
• 1587.银行账户概要II
• 1158.市场分析I

华为OD

• HJ1.字符串最后一个单词的长度
• HJ2.计算某字符出现次数
• HJ3.明明的随机数
• HJ4.字符串分隔
• HJ5.进制转换
• HJ6.质数因子
• HJ7.取近似值
• HJ8.合并表记录
• HJ9.提取不重复的整数
• HJ10.字符个数统计
• HJ11.数字颠倒
• HJ12.字符串反转
• HJ13.句子逆序
• HJ14.字符串排序
• HJ15.求int型正整数在内存中存储时1的个数
• HJ106.字符逆序

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分)
15. 1017. A除以B(20分)