算法和数据结构—概述

学习方法

数据结构，就是一组数据的存储结构。

算法，就是操作数据的一组方法。数据结构是为算法服务的，算法要作用在特定的数据结构之上。

首先要掌握一个数据结构与算法中最重要的概念——复杂度分析, 这个必须要搞懂，且要很熟练

20个工作面试常用的数据结构与算法

  1. 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树；
  2. 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

千万不要被动地记忆，要多辩证地思考，多问为什么。要学习它的“来历”“自身的特点” “适合解决的问题”以及“实际的应用场景”。

学习建议

  1. 边学边练，适度刷题。最好能用代码实现一遍。
  2. 多问、多思考、多互动
  3. 学习的过程中，碰到最大的问题就是，坚持不下来。
  4. 知识需要沉淀，不要想试图一下子掌握所有

学习了，也理解了，当时可以写出代码来，但是长时间就忘记了😣，这个难道真的如果日常不用的话，的确会忘记. 作者回复: 完全不需要死记硬背的，我也记不住快排，红黑树，但是只要你掌握分析的能力，等你真的需要的时候，花不到半个小时就弄懂了。你要记住的是，这些算法的特点，应用场景，用到了能想到他就好了。

复杂度分析

复杂度分析是学习算法的前提，必须要掌握才能继续

###时间复杂度 所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

大 O 时间复杂度表示法 T(n) = O(f(n))

大 O 时间复杂度表示法：并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，即时间复杂度。

T(n) 我们已经讲过了，它表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。 当 n 增大时，当n无限大时公式中的低阶、常量、系数三部分并不会随之增长，可以忽略。只需要留下最高阶即可。故 T(n) = O(2n^2+2n+3)就变成了T(n) = O(n^2)

时间复杂度分析技巧

  1. 只关注循环执行次数最多的一段代码
  2. 加法法则：总的时间复杂度就等于量级最大的那段代码的时间复杂度。

  3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

  4. 常量阶 O(1)， 只要代码的执行时间不随 n 的增大而增长，都是。
  5. 对数阶 O(logn)
  6. 线性阶 O(n)
  7. 对数线性阶 O(nlogn)
  8. 平方阶 O(n^2)， 立方方阶 O(n^3)， K次方阶 O(n^k)
  9. 指数阶 O(2^n)
  10. 阶乘阶 O(n!)

多项式量级和非多项式量级,非多项式量级只有两个：O(2n) 和 O(n!)。当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，甚至无限增大，效率极低。

常量阶 Ο(1)：

  • 一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，代码的执行时间不随 n 的增大而增长，其时间复杂度也是Ο(1)。

对数阶 O(logn)、O(nlogn)

  • 相对来说最难分析
  • 忽略对数底数；对数，不论底数是2,3或者10，随着n增大，都忽略，都记为O(logn)

O(m+n)、O(m*n)

  • 这种是针对有两个变量m和n，实现又无法确定谁的量级大

最好情况时间复杂度, 最坏情况时间复杂度, 平均情况时间复杂度

  • 在大多数情况下，我们并不需要区分最好、最坏、平均情况时间复杂度三种情况。只有同一块代码在不同的情况下，时间复杂度有量级的差距，我们才会使用这三种复杂度表示法来区分。

均摊时间复杂度 场景比较特殊，所以我们并不会经常用到。场景：对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，而且这些操作之间存在前后连贯的时序关系，而且这些操作之间存在前后连贯的时序关系， 每一次 O(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的n-1 次耗时少的操作上，这一组连续的操作的均摊时间复杂度就是 O(1)。 评论：平均和平摊基本就是一个概念，平摊是特殊的平均。不用花太多精力区分

空间复杂度

全称渐进空间复杂度：表示算法的存储空间与数据规模之间的增长关系。 常见的空间复杂度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时用不到。 空间复杂度分析比时间复杂度分析要简单很多。这些就够用了 空间复杂度指除了原本的数据存储空间外，算法运行还需要额外的存储空间。比如程序中有个int a[10]的数组来放数据，这个不算、

渐进时间复杂度和空间复杂度只是一个理论模型，给我们一个分析时间和空间的一个参考。不能说O(logN)的算法一定优于O(n),针对不同的宿主环境，不同的数据集，不同的数据量的大小，在实际应用上面可能真正的性能会不同

数组

数组（Array）是一种线性表数据结构。它用一组连续内存空间，来存储一组具有相同类型的数据。 在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

  • 但是如果不急着回收空间，可以只是标记删除位置；如果顺序不重要，知否可以直接用尾部的数据填补空洞呢？

为何数组的下标都是从0开始

  • a[key] 下标key时表示偏移量offset，如果从1开始计数，每次随机访问数组元素都多了一次减法运算，多一次cpu减法指令。

特点：

  • 需连续内存，
  • 随机访问快速，根据下标k访问数据快速（根据首地址和下标即可计算得地址），时间 O(1)
  • 插入和删除搬移数据时间O(n)

##链表 链表的种类很多，常用的如：单链表，双向链表，循环链表

特点

  • 无需连续内存
  • 插入删除快速，时间 O(1)
  • 根据k访问元素低效，需遍历链表，时间O(n)

由于数组是连续存储的，可以充分利用CPU缓存机制，预读。而链表非连续存储则不行。 数组的大小总是固定的，预先申请一片连续内存。如果不够还需重新申请更大的内存，再把数据拷贝过去。 如果对链表过频繁的插入和删除，会造成内存频繁的申请和释放，容易造成内存碎片。

利用链表实现缓存淘汰算法LRU 如果已经被缓存在链表中了,则移动到链表前面；如果不在链表中，链表没满则在头部插入，满了则先删除尾部数据，再开头插入。可以在引入hash表记录数据位置，把访问时间降为O(1)

链表的插入、删除操作，需要对插入第一个结点和插入、删除操作，需要首尾节点重点考虑。 引入哨兵节点，简化编程。哨兵结点是不存储数据的。让节点的逻辑统一。 在软件开发中，边界最易初bug，需要重点留意。链表为空时，链表只有一个节点时，处理头节点和尾节点还能否正常

举例画图，辅助思考 多练多写，没有捷径

常见链表操作：最好代码写出来

  1. 单链表反转(把链表头变成尾，尾变成头)
  2. 链表中环的检测
  3. 两个有序链表合并
  4. 删除链表倒数第n个节点 (如果一次遍历实现删除. count = n + ( count - n) )
  5. 求链表的中间节点 (fast每次两步。slow每次一步，fast到头，slow刚好走一半)

链表中环的检测

检测单链表中是否存在环。 方法：用快指针fast, 每次走2步。slow指针每次走1步。同时从头开始走，若发fast与slow相遇，则存在环。若最终若快指针指向null，则无环。 原因：若有环，快指针先行进环，在环中绕圈，慢指针后入环，也在环中绕圈，由于快指针每次比慢指针多走一步，意味着两个指针在环中的位置每次都缩短一步，所以若有环，两个指针在环中必能相遇。

栈

栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。

栈的应用:

  • 浏览器前进后退
  • 函数调用栈，用来存储函数调用时的临时变量
  • 编译器如何利用栈来实现表达式求值 34+13*9+44-12/3

leetcode上关于栈的题目：20,155,232,844,224,682,496.

队列queue

对头出，对尾进 实现：

  • 数组实现
  • 链表实现

循环队列 解决数据搬移问题 重点关注队列满和空的边界条件

  • 队列空 head == tail
  • 队列满 (tail + 1) % capacity == head

阻塞队列 队列为空的时候，从队头取数据会被阻塞。队列已经满了，那么插入数据的操作就会被阻塞。可以用来实现一个”生产者 - 消费者模型”。可以有效地协调生产和消费的速度

并发队列 即在入队，出队加锁。 如何通过CAS实现无锁并发队列？ 则在入队前，获取tail位置，入队时比较tail是否发生变化，如果否，则允许入队，反之，本次入队失败。出队则是获取head位置，进行cas。

递归

弄清楚递归，也是算法的基础，务必要掌握 递归 : 去的过程叫“递”，回来的过程叫“归” 优点：代码的表达力很强，写起来非常简洁； 缺点：空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。

递归需满足三个条件：

  1. 一个问题的解可以分解为几个子问题的解
  2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
  3. 存在递归终止条件

怎么写递归代码？ 方向：写出递推公式，找到终止条件

递归代码要警惕堆栈溢出 函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。 限制递归调用的最大深度，递归调用超过一定深度（比如 1000）之后，我们就不继续往下再递归了，直接返回报错。

递归代码要警惕重复计算

空间复杂度上，因为递归调用一次就会在内存栈中保存一次现场数，据所以在分析递归代码空间复杂度时，需要额外考虑这部分的开销。

斐波那契数列

如：0、1、1、2、3、5、8、13、21、34、……

F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）

//F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）  如：0、1、1、2、3、5、8、13、21、34、……
//输入n求F(n)
public int fb(int n) {
	if (n < 2) {
		return n;
	}
	return fb(n - 1) + fb(n - 2);
}

斐波那契数列时间复杂度怎么分析？

排序

  • 冒泡
  • 选择排序
  • 归并排序
  • 快速排序
  • 堆排序
  • 桶排序
  • 插入排序
  • 计数排序
  • 基数排序

查找

  • 二分查找
  • 排序对于找来说的重要性

数组

  • 有序数组

链表

  • 单向链表
  • 双向链表
  • 循环链表

跳跃表

队列

  • 单向队列
  • 双向队列
  • 优先级队列

栈 散列

  • 实现方式
  • 冲突解决
  • 扩容
  • 装载因子

树

  • 二叉树
  • 满二叉树
  • 完全二叉树（存储方式）
  • 二叉查找树
  • 平衡树
  • 红黑树
  • B+树
  • 堆

堆 集合 图

  • 广度优先
  • 深度优先
  • 最短路径
  • 拓扑排序

位图

  • 布隆过滤器

算法思想

  • 分治法
  • 贪心算法
  • 回溯算法
  • 动态规划

字符串匹配

  • BM
  • KMP
  • 暴力匹配
  • RK
  • AC自动机
  • Trie树

TODO

  • 红黑树删除
  • 最短路径
  • 最长公共子串

更新时间: