数据结构算法练习

说明

• github地址：https://github.com/lawlite19/AlgorithmExercises

  一、 排序算法

  1. 交换排序

  • 冒泡排序
• 冒泡排序改进1
• 冒泡排序改进2
• 冒泡排序改进3
  • 快速排序

2. 插入排序

• 直接插入排序
  • 直接插入排序递归版
• 希尔排序

3. 选择排序

• 简单选择排序
  • 二元选择排序
• 堆排序

4. 归并排序

• 二路归并排序递归版
• 二路归并排序非递归版

二、 字符串

1. 字符串旋转

• 字符串旋转_暴力法
• 字符串旋转_三步翻转法

2. 字符串包含

• 字符串包含判断_遍历
• 字符串包含判断_排序
• 字符串包含判断_素数乘积
• 字符串包含判断_哈希 ★★★

3. 回文

• 回文判断

4. 最长回文子串长度

• 最长回文子串长度_一般解法
• 最长回文子串长度_Manacher ★★★
  • 算法说明

5. 全排列

• 全排列_递归
• 全排列_字典序排列
• 字典序全排列

6. 变形词

• 变形词判断

7. 字符串中数字串之和

• 字符串中数字串之和 ★

8. 去除字符串中连续K个0串

• 去除字符串中连续K个0串

9. 整数字符串转整数值

• 整数字符串转整数值 ★★

10. 字符串匹配问题

• 字符串匹配_KMP ★★★★★
  • 算法说明

三、 数组和矩阵

1. 二维数组查找

• 二维数组查找

2. 矩阵相关操作

• 转圈打印矩阵

3. 最小的k个元素

• 最小的k个元素_堆
• 最小的k个元素_BFPRT ★★★★★
  • 算法说明

4.中间数

• 中间数_辅助数组 ★

5.非负数组和为K的最长子数组

• 非负数组和为K的最长子数组_双指针 ★★★

8.次数出现大于N/K的数

• 次数出现大于N/2的数 ★
• 次数出现大于N/K的数 ★★★

9.逆序对

• 逆序对数_分治归并★

10.两个有序数组的中位数

• 两个有序数组的中位数_分治★★★★
  • 算法说明

四、 递归和动态规划

1. 斐波那契问题

• 矩形覆盖_递归

• 矩形覆盖_dp ★

• 矩阵覆盖_矩阵转化_class实现 ★★★

• 矩阵覆盖_矩阵转化_vector实现 ★★★

  • 算法说明

• 爬楼梯_递归

• 爬楼梯_dp ★

• 变态跳台阶_递归

• 变态跳台阶_直接计算 ★

2. 最大子数组和相关问题

• 最大子数组和_dp ★
• 两个不相容子数组最大和_辅助数组 ★★

3. 最长递增子序列相关问题

• 最长递增子序列_一般dp
• 最长递增子序列_dp优化 ★★
• 摞数组问题(俄国沙皇问题)_纯代码实现 ★★★★
• 摞数组问题（俄国沙皇问题）_借助stl ★★★★

五、 栈和队列

1. getMin功能栈

• getMin功能栈_方案1
• getMin功能栈_方案2

2. 两个栈实现队列功能

• 两个栈实现队列

七、二叉树

1. 遍历

• 先、中、后序遍历_递归
• 先、中、后序遍历_非递归 ★★

八、位运算

• 出现奇数次的数