算法与数据结构

定义

算法: 算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入.

数据结构: 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率.

先说数据结构,毕竟算法也得有东西算,才又算法,所谓先有鸡后有蛋

数据结构:既然是结构，里面肯定是有不同的数据的，与其叫数据结构，不如叫数据流,数据流中包含了各种数据，数据结构构成流，流亦是数据结构，面向对象就是，万物皆数据，以流的形式呈现.

算法就是解决问题的方法,以函数或者是类的形式出现，它决定传入的参数，对数据流进行修改，留下需要的，抛弃不需要的，将数据和其他数据组成在一起，形成数据流，将数据流和数据流组成在一起，形成新的数据流，将数据流拆分成数据，再聚合，这就是算法的作用。

算法就是数据流的灵魂,没有算法的数据其实没有灵魂的

数据结构

1. 数据结构的分类：

   线性结构：静态数组，动态数组，链表，队列，栈，字符串

   树形结构：二叉树，B/B+/B-树，红黑树，哈夫曼树

   图形结构：图

   其他：跳跃表，map，set

2. 基于数据结构的基本算法：

   数组的算法：插入，删除，新建，查找

   链表的算法：插入，删除，合并，查找

   栈的算法：新建，进栈，出栈

   队列的算法：新建，入队，出队，优先队列

   字符串的算法：查找，字串匹配

   二叉树的算法：前中序遍历，查找，深度，平衡二叉树的插入删除等等

   图的算法：DFS/BFS，图的结构，Prim算法，Dijkstra算法，kruskal算法，拓扑排序

   排序算法：各种排序算法

   以上是的这些算法都是比较基本的，在学习其数据结构时，就依附存在的算法

算法

算法是一种解题思想，解决问题的方法

1. 算法的分类

   算法的复杂度分析

   递归与分治算法

   动态规划

   贪心算法

   回溯算法

   分支限界算法

   概率算法

2. 具体概念讲解

   • 算法的复杂度

     时间复杂度和空间复杂度的分析：应该会对自己写的代码进行复杂度分析，比如空间和时间复杂度是多少。

     PS：排序的时间复杂度：最优的情况是O(nlogn)，最坏的情况是O(n^2),有一个特殊情况是O(n)–位排序和计数排序

   • 递归和分治算法

     **递归：直接或间接调用自身的算法成为递归算法。**PS：树结构非常适合递归算法

     递归的一个例子：斐波那契数列（入门必学的一个错误的递归算法），可以用递归来做，但是实际上效率比较低。

     分治算法：将一个大问题分解为k个规模比较小的子问题，并且这些子问题互相独立，但是又与原问题相同。

     PS：分治思想是一个基本的思想，递归和其后的dp(动态规划)以及贪心算法很多时候都是基于分治来做。

     从分治出发设计出来的算法，一般是递归算法。

     常见的分治算法：排序算法中的归并排序，快速排序，二分搜索

   • 动态规划算法

     动态规划算法：与分治算法思想类似，两者不同点在于，dp的子问题并不是互相独立的，在分治算法中，有些子问题会被重复计算，效率很低，因此，动态规划，对分治有了优化，记录子问题，去掉重复性。

     PS：动态规划是对分治算法的优化

     动态规划适用于最优化算法

     使用动态规划特征：

     1. 求一个问题的最优解
     2. 大问题可以分解为子问题，子问题还有重叠的更小的子问题
     3. 整体问题最优解取决于子问题的最优解（状态转移方程）
     4. 从上往下分析问题，从下往上解决问题
     5. 讨论底层的边界问题

     注意上面的三点：子问题重叠，状态转移方程，边界问题

     PS：尝试使用动态规划去解斐波那契数列

     常见的动态规划题目：最长公共子串，最长公共子序列，最长回文串，矩阵乘法，背包问题

   • 贪心算法

     贪心算法：类似于动态规划，两者不同点在于，贪心算法考虑局部最优，动态规划考虑全局最优，如果一个问题，全局最优是通过局部最优逼近的，那么此时可以考虑贪心算法

     PS：贪心算法不能对所有的问题都能得到整体最优解，但对某些问题可以。

     贪心算法是对某些动态规划问题的一个简化

     常见的贪心算法：图的单源最短路径，最小生成树的问题。

     PS：如何区别贪心算法和动态规划呢？

   • 回溯算法

     回溯算法：回溯算法具有"通用解题法"之称， 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

     PS：它是用于求解组合数较大的问题。

     回溯法的解题步骤：

     1. 针对所给问题，确定问题的解空间： 首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
     2. 确定结点的扩展搜索规则。
     3. 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

     常见的回溯算法：皇后问题，输出不重复数字的全排列，求一个集合的所有子集

   • 分支限界算法

     分支限界算法：分支限界算法类似于回溯算法，两者不同点在于，回溯算法是找出解空间中的所有解，分支限界算法是找出某一个解(这个解或者是最优的)，其次，回溯算法是用深度优先方式搜索解空间，分支限界算法以广度优先的方式搜索解空间。

     PS：某种意义上来说，分支限界算法也是寻找最优解。

     常见的分支限界算法：TSP（旅行商问题），单源最短路径

   • 概率算法

     概率算法分类：

     1. 数值概率算法：用于求解没有精确解的数值问题
     2. 蒙特卡罗算法：求解问题的准确解
     3. 拉斯维加斯算法：不会得到不正确的解，眼下之意，要么不存在，要么正确
     4. 舍伍德算法：总能求问题的某一个解，且必然正确

     常见的概率算法：

     1. 数值概率：设计伪随机数
     2. 舍伍德算法：跳跃表
     3. 拉斯维加斯算法：皇后问题
     4. 蒙特卡罗算法：素数测试

其他的未提到的算法

1. 字符串的算法：

   • KMP算法
   • Manacher算法
   • 最长回文串，公共子串，公共子序列
   • 全排列
   • 字符串替换
   • 正则表达式

2. 数组

   • 丑数
   • 水仙花
   • 剩余定理
   • 乘积数组
   • 矩阵中路径
   • 逆序对
   • 连续数组最大和

3. 链表

   • 链表的合并
   • 重复节点删除
   • 反转链表
   • 链表环的入口

4. 查找

   • 二叉搜索
   • 约瑟夫环
   • 二进制1的个数
   • 二维数组的查找

5. 排序

   • 大约9个排序算法，分析时间空间复杂度，分析稳定性

6. 二叉树

   • 对称二叉树
   • 层次遍历
   • 序列话二叉树
   • 非递归的前中后序遍历
   • 二叉搜索树的第k个节点

7. map,set,array在java、C++的用法

8. 剩余定理

9. 快速幂取模

10. 欧几里德算法