常用算法以及使用场景,实现

时间复杂度计算

  1. 只关注循环执行次数最多的一段代码
  2. 加法法则:总复杂度等于量级最大那段代码复杂度(如:多个循环最最大那个 n 5n n平方)、
  3. 乘法法则 嵌套代码复杂度等于嵌套内外代码复杂度乘积

常见复杂度量级 O(1):常数级,一般算法中不存在循环语句,递归语句,即使有成千上万,复杂度也是O(1)

O(logn):对数阶,不管底数为多少以此表示

i=1
while(i<=n) {
    i= i*2
    // i= i*3
}

O(n),O(nlogn), O(2n平方),O(n!),O(n2平方),O(n3立方),O(nk次方)

数组:连续内存地址,支持随机下标访问,增加,删除特定位置元素会造成,其他元素在数组中位置的移动。

链表:离散内存地址,不支持随机下标访问,因为会存储其他引用,索引占用内存会比数组多几倍,但是删除,增加操作的实际复杂度为O(1);

链表实现代码需要注意几点:1理解引用的含义 2警惕指针丢失和内存泄露 3利用哨兵简化实现难度 4重点留意边界问题(链表为空;一个节点;两个节点;在处理头结点和尾节点的时候逻辑是否支持等情况;另外举例画图,辅助思考,多写多练)

链表中几个极具操作有效的练习 1 单链表反转 2 链表中环的检测 3 两个有序的链表合并 4 删除链表倒数第几个节点 5求链表的中间结点

栈:数组和链表在功能上面来说可以代替栈,但是,数组和链表暴露太多借口,操作上的灵活会导致使用的不可控,根据栈的先进后出特性适用合适的场景。用数组实现称为顺序栈,用链表实现称为链式栈

队列:特性为先进先出,也分为顺序队列和链式队列,主要使用场景为大部分资源有限的场景

递归:利:简化代码,增加可读性;弊:需要注意的是 堆栈溢出和重复计算的问题,还有时间,空间复杂度的问题

排序算法的执行效率分析:

  1. 最好情况,最坏情况,平均时间复杂度
  2. 时间复杂度系数,常数,低阶
  3. 比较次数和交换的次数(内存消耗,算法稳定性)

跳表: 链表加索引的结构,跳表索引动态更新通过一个随机函数,决定要插入的节点插入到第几级索引当中

散列表: 通过键和值的结构存储数据, 散列函数设计基本要求

  1. 散列函数计算得到的散列值为一个非负整数
  2. 如果key1=key2,那么hash得到的值时相等的
  3. 尽量避免大量的hash冲突

hash冲突解决方案

工业级散列函数:

动态扩容: 不要求当原有数组空间不足时,一次性扩展数组的容量,新建一个散列表,新旧数据结构一起使用,逐步转移原有数据到新空间

LRU缓存淘汰算法 通过散列表和双向链表的组合使用可以做到在缓存中的添加,删除,查找数据的时间复杂度为O(1)

LinkedHashMap是通过双向链表和散列表者2两种数据结构组合实现的

hash算法:通过讲仁义长度二进制值串映射为固定长度的二进制值串。

hash算法的作用: 安全加密,唯一标识,数据校验,散列函数,负载均衡,数据分片,分布式存储

二叉树存储方法:

二叉查找树,增加,查询,最大,最小,都是高效的,删除情况比较复杂,分是否有节点有不同处理方式,同时二叉查找树通过中序遍历可以得到有序序列。重复数据的二叉查找树存储处理,1.链表 2重复数据放到右节点,查询,删除的时候要求一直遍历右节点,直到不等值

散列表和二叉树:

红黑树不一定完全平衡,最优平衡,红黑树的平衡方法,节点旋转

递归树:通过将大问题分解为小问题进行求解,一层一层分解可比做一棵树

堆: 1 必须是完全二叉树,2 堆中每个节点值必须大于等于其子树每个节点的值(或小于)

堆化: 堆中元素插入和删除后,需要进行调整,让其满足堆的特性,这个过程叫做堆化。 从下往上,或从上往下进行元素删除,增加,每个节点进行对比,交换位置。

堆排序和快速排序:

  1. 堆排序数据访问方式没有快速排序友好,前者跳着访问的,对cpu缓存不友好
  2. 对于同样数据,在排序过程中,堆排序的数据交换次数要多于快速排序

堆的应用:

图:

有向图:某个节点关注某个节点,不关注其他节点,分为入度和出度 无向图:节点之间互相关注 带权图:每条边都有一个权重,可以通过权重表示每个顶点之间的热度

图的存储:

邻接矩阵很容易导致空间的浪费,比如无向图和稀疏图;优点是存储方式简单,方便计算

微博,微信等好友互关的场景,适合使用邻接表,逆邻接表。使用hash算法进行数据分片,再把数据进行邻接表存储,使用外部存储数据库存储索引

搜索算法 大部分设计搜索的场景都可以抽象成图

字符串匹配算法

可以通过优化hash计算,相邻两个子串具有重叠的字符部分,得到的hash值是一样的

  1. 坏字符规则,模式串和主串匹配时,按照模式串下标从大到小顺序进行匹配。当我们发现某个字符没法匹配时,把这个没有匹配的字符称为坏字符。当发生不匹配时,坏字符对应模式串中字符下标记作si。如果坏字符在模式串中存在,这个下标记作xi,不存在xi记作-1.模式串向后移动位数等于si-xi
  2. 好后缀规则 我们把已经匹配的字符叫作好后缀,记作{u},我们拿它在模式串中查找,如果找到另一个跟{u}相匹配的子串{u},我们就将模式串滑动到子串{u}与主串中{u}对其的位置,但是这样很可能导致过度移动,导致好后缀中部分字符串与模式串中前缀字符匹配的丢失

坏字符在模式串中遍历查找时,会很低效,可以将模式串中的字符及其下标存储到散列表中。这样就可以快速找到坏字符在模式串中位置下标

如何快速找到子节点的指针,通过hash表的思想,存储字符的hash到对应的数组下标。时间复杂度为O(n),空间复杂度为O(26的你n次方)

trie树与散列表,红黑树都可以实现字符串匹配的问题

1Trie树要求字符串包含字符集不能太多,会造成大量空间的浪费2要求字符串前缀重合比较多3通过指针串起来的数据块不是连续的,对缓存不友好

AC自动机 针对大量字符串过滤,Trie树可以做到多模式串匹配,我们把用户输入内容作为主串从第一个字符开始匹配,当匹配到Trie树叶子节点或中途遇到不匹配字符时,将主串开始匹配位置后移,重新再Tire树中匹配。那么这个后移也可以想KMP算法一样进行优化。

AC自动机通过在Trie树上,加了类似KMP的next数组

贪心算法能解决问题,但是不一定是最优解(因为前面的选择会影响后面的选择)