常见算法集锦

二．算法

2.1 进制转换

  • 十进制转化二进制：短除法
  • 二进制转化十进制：按位相加
  • 二进制转化成十六进制(A,B,C,D,E,F):四位转化一位
  • 二进制转化成八进制:三位转化一位

有符号数:二进制第一位为数字的正负 1代表负 0代表正

2.2.1 前缀表达式（波兰表达式）

从右往左写，遇到数字就进栈，遇到符号就弹出栈顶的两个数字，结果进栈

2.2.2 后缀表达式（逆波兰表达式）

从左往右写，遇到数字就进栈，遇到符号就弹出栈顶的两个数字，结果进栈

2.3 基本逻辑符号:与、或、非、异或

  • 与（等价于交）(&，∩): 1 & 0 = 0 1 & 1 = 1 0&0 = 0
  • 或(等价于并)(| 、 U)：1 | 0 = 1 0 | 0 = 0 1| 1 = 1
  • 非(!、横折、~) ：逻辑是按位取反
  • 异或(^): 1 ^ 1 = 0 1^0 = 1 0 ^ 0 = 0

优先级:非>与>异或>或

  • >>= ：右移之后再赋值
  • &=:按位与再赋值
  • |=：按位或之后再复制

2.4 图论

  • 迪杰斯特拉算法(Dijkstra)、弗洛伊德算法(Floyd): 前提不能有负权边，应用在有权连通图，是有权连通图求最小生成树的算法 时间复杂度

(其中n代表顶点数量，m代表边数量)

  • Dijkstra时间复杂度 O(n^2), 使用优先队列可以优化到 O((n+m)log n)
  • Floyd时间复杂度 O(n^3)

连通图:从任意一点出发可以抵达其余任何点的图

最短路径：所有边的权值加起来最小

  • Prim算法:从起点开始，选和我现在已有的结点相连的边里权值最短的边，但是选这条边的前提是不能产生环（回路），直到所有点都联通

  • Kruskal算法:最开始就将所有的结点加入，然后按大小顺序取边，先取最小的边，然后依次取第二小的边，前提是不能产生环路，直到所有点联通

无向图的度:有几条边和这个结点相连，这个结点的度就是多少

有向图的出度:有多少条边以这个点为起点出发 有向图的入度:有多少条边以这个点为终点 有向图的度等于出度+入度

递推式的时间复杂度由第n项的通式的最高项次决定，解题思路是先将题目中的第n项表达式借助的项次写出来，比如T（n） = T（n-1）+1 ，所以第n项借助n-1项描述，再将第n项借助的项式套回原公式，代入第一项，比如T（n-1） = T（n-2）+1，代回，T（n） = T（n-2）+2,再总结通项规律，所以T（n） = T（n-k）+k（其中k为一个常数），最后将题目中已知的最低项代回原式就可以得到答案，比如题目中已知第一项T（1） = 1 ，所以假设n-k = 1，k即等于n-1，所以原式等于T（n） = 1+n-1 = n ，关于n的最高项次为1次，时间复杂度为O（n）

对数运算运算的基本规则:

  • log a ^mn = log a ^m + log a ^ n
  • log a ^m/n = log a ^m - log a ^ n
  • a^log a ^m = m
  • log a ^m^n = nlog a^m

2.5 原、反、补

  • 原码:首位是符号位的正常二进制数
  • 反码:除了首位以外，在原码的基础上每一位取反
  • 补码:在反码的基础上加1 正数的原、反、补码都是本身，负数的原、反、补码才要按上述规则变形

2.6 组合数学

  • N个小球，放进m个箱子里，要求每个箱子里至少要一个小球，问有几种方法？

插板法:C (m-1) (n-1)

  • N个小球，放进m个箱子里，每个箱子里可以没有球，问有几种方法？

假设借了m个球，将问题转为n+m个球，放进m个箱子里，要求每个箱子里至少有一个球，问有几种方法？

C(n+m-1) (m-1)

2.7 散列

按照一个散列函数，把查找表中的关键字映射成该关键字对应的地址 散列函数:hash(Key) = 一个数学函数 (key 是你要存放的关键字的值)

  1. 直接定址法 H(Key) = a*key+b 计算最简单，而且不会有冲突的地址
  2. 保留余数法 H(Key) = key%a

当产生地址冲突时，处理地址冲突 的策略：

  1. 线性探测法：当一个位置地址冲突的时候，按顺序检查下一个位置是不是冲突
  2. 平方探测法: 当一个位置地址冲突的时候，按1^2,-1^2,2^2,-2^2……的增量检查是否产生冲突
  3. 线性探测再散列：一旦发生地址冲突，就拿我第一次算出来的结果，代入题目提供的地址冲突时需要代入的公式

ASL查找成功的次数 = 每个数字需要的查找次数的总和/散列表的长度

2.8 哈夫曼编码

求最小生成树的一种编码方式 (保证了 使用频率最高的字符编码长度最短)

哈夫曼编码不会对根节点编码，只会对叶节点编码

编码思路：先把所有字符按照使用频率排序，每次选两个最小的数字，组成一个根节点，再删除这两个数字，加入组合成的新的结点数字，画出的二叉树里左边的路为0，右边的路为1，写出到叶节点的路上的数字就是这个叶节点的编码

Edit this page