通过补充 减治、分治、变治 的教材知识梳理，收获：
1、以前以数据结构划分的经典题，在算法这里出现的时候，会赋予这道题新的生命力。
典型表现就是：
- 一道之前解的题，有了很系统的从简单到精巧的算法精进过程、
- 一道之前解过的题，用了新的方法，并且知道了原来这个方法就是xx算法，理解了题同时更理解了这个算法思想；即那些之前框定在相应数据结构的题，可能因为某种解法他们相聚在了xx算法这里，然后一起丰富了该算法的生命力。
2、收获了很多数学知识：产生了想法——积累日常遇到过的数学基础题，他们以后是解决几何知识、n皇后等棋盘问题的杀手锏武器。
比如：
- 最大公约数、最小公倍数
- 霍纳法则计算多项式、解决x^n问题的二进制幂
3、想从数据结构从头梳理到现在的算法、之后的动态规划，感觉我的算法与数据结构知识图快要呼之欲出了。（从0到1的那种）
下面简单记录一下 分治系列的问题 补充可以在哪些数据结构知识里 加料
4、额外收获：这个老外作者的写作风格好有趣啊。拍了几张照，对我写讲解知识点的文章 的写作风格 有影响呢，以后我也要这么幽默(俏皮一点）+ 顺便输出自己的学习态度
梳理
数据结构相关
链表
栈、队列：
优先队列的实现:无序数组、有序数组、avl、堆 实现优先队列的 效率分析
优先队列的应用：操作系统的调度，网络流量管理、prim算法、dij算法、哈夫曼编码
击鼓传花/约瑟夫问题：1、循环队列的解法；2、减治-减常量因子解法
散列表：
towsum：1、蛮力 2、散列 3、预排序
字母异位词：1、散列 2、预排序
求众数:1、散列(计数) 2、预排序 3、分治
元素去重：1、蛮力、2、散列表 3、预排序
树：
二叉树的遍历：（分治思想
1、二叉树层数、2、二叉树叶子数
从二叉查找到AVL：变治的实例化简
从二叉查找到2-3树：变治的改变表现形式
堆：
优先队列的实现
检查数组是否符合堆要求
算法
排序：
选择排序、冒泡排序（蛮力法
插入排序（减治
拓扑排序：1、DFS 2、减治（不断的排除已经选择过的点和边，减少子规模输入常量
快速排序（中值选择、分治
归并排序（分治
查找：
折半（减常因子
普通查找：预排序 + 折半
深度优先搜索：
检查图的连通性质、
图是否含有回路
关节点
广度优先搜索：
检查图的连通(有向无环图)
图是否含有环
最少边路径：两点之间最短距离
np问题
旅行商：1、蛮力 2、回溯
01背包：1、蛮力 2、回溯
任务分配：1、蛮力；
n皇后问题：1、蛮力法 2、回溯
回溯：
幻方：
数独：
减治：
插入排序、
拓扑排序
组合对象（全排列、子集问题
折半查找
假币问题 n/2 好 还是 n/3
俄式乘法（不用背99乘法表啦
约瑟夫问题
最大公约数的减治解法
中值问题=> 快速排序、求中位数、快速选择第k大元素
分治：
归并排序（good：稳定性，bad：空间复杂度
快速排序：
快排的最差、最优、平均的复杂度分析
快排的改进：算法教材p139：
- 更好的基准选择法：随机快速排序、三平均划分法 （面临有序或者近乎有序的数组时，会退化成为一个O(n算法
本文原创发布于慕课网 ，转载请注明出处，谢谢合作
- 当数组足够小的时候(5-15) ： 使用插入排序
- 划分方法改进:三路划分(如荷兰国旗应用
荷兰国旗
二叉树遍历
大整数乘法
矩阵乘法
最近对
变治:
预排序思想:
二进制反射格雷码：
生成子集
汉诺塔问题
中值问题：1、Lomuto划分 2、Hoare划分；
应用： 快速排序
快速选择：基于Lomotu划分的快速选择，求中位数，选择出第k大元素
数学
最大公约数：1、连续整数检测、2、质因数、3、欧几里得算法-扩展欧几里得算法
最小公倍数：1、中学法 2、利用最大公因数
矩阵乘法：1、基于定义的矩阵乘法(蛮力法） 2、strassen乘法(分治)
大整数乘法：分治思想
组合对象：
全排列：0、从底向上最小变化 、2、johnson算法（带箭头的那种）、3、字典序、
4、回溯解
组合：
生成子集：1、回溯 2、生成位串的最小变化算法-二进制反射格雷码；
俄式乘法：妈妈再也不用担心我背九九乘法表啦
霍纳法则：解多项式
副产品：长除法 vs 综合除法
x^n的计算：与幂乘不一样，幂乘是 2^n , x^n是指数不变，底变
1、霍纳法则
2、使用指数n的二进制表示
平面几何
平面对问题：1、蛮力：2、分治+ 预排序
若有收获，就点个赞吧
0 人点赞
