算法和数据结构

第1章 算法概述

1.1 算法和数据结构

1.1.1 算法

算法（algorithm）是用于解决某一类问题的公式和思想

计算机中的算法是一系列程序指令，用于解决待定的运算和逻辑问题

衡量算法好坏的重要标准有两个：

• 时间复杂度
• 空间复杂度

算法的应用领域：

• 运算
• 查找
• 排序
• 最优决策

1.1.2 数据结构

数据结构的组成方式有如下几种

1. 线性结构
2. 树
3. 图
4. 其他数据结构，如：跳表、哈希链表、位图

1.2 时间复杂度

若存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常熟，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称为O(f(n))，O为算法的渐进时间复杂度，简称为时间复杂度

常见的复杂度按照从低到高的顺序，包括O(1)、O(logn)、O(n)、O(nlogn)、O(n²)等

推导时间复杂度常用原则

• 如果运行时间是常数量级，则用常熟1表示
• 只保留时间函数中的最高阶项
• 如果最高阶项存在，则省去最高阶项前面的系数

例：

1. T(n) = 3n，最高项为3n，省去系数3，时间复杂度为：T(n) = O(n)
2. T(n) = 5logn，最高阶项为5logn，省去系数5，时间复杂度为：T(n)= O(logn)
3. T(n) = 2，只有常数量级，时间复杂度为：T(n) = O (1)
4. T(n) = 0.5n²+0.5n，最高阶项为0.5n²，省去系数，时间复杂度为：T(n) = O(n²)

1.3 空间复杂度

空间复杂度是对一 个算法在运行过程中临时占用存储空间大小的量度，用大O表示，记作S(n)=O(f(n))

常见的空间复杂度按照从低到高的顺序，包括O(1)、O(n)、O(n²)等，递归算法的空间复杂度和递归深度成正比

第2章 数据结构基础

2.1 数组

数组是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。

数组是最简单、常用的数据结构，物理存储方式是顺序存储，访问方式是随机访问，利用下标查找元素时间复杂度为O(1)，中间插入删除元素的时间复杂度是O(n)

数组特点：

1. 数组中的每一个元素也有着自己的下标，只不过这个下标从0开始，一直到数组长度-1
2. 数组在内存中顺序存储，因此可以很好的实现逻辑上的顺序表

数组的基本操作：

1. 读取元素：由于数组在内存中顺序存储，所以只要给出一个数组的下标，就可以读取到对应的数组元素
2. 更新元素：要把数组中某一个元素的值替换为一个新值，只需要利用下标，直接把 新值赋给该元素
3. 插入元素：插入元素分为三种基本的情况
   • 尾部插入：直接把元素放在数组的尾部空闲位置
   • 中间插入：需要把插入位置以及后面的元素向后移动，然后再插入元素到对应的位置
   • 超范围插入：如果插入的下标小于0或者大于等于数组长度，会抛出异常，如果需要插入，需要自己对数组金星秀扩容处理
4. 删除元素：数组删除和插入相反，末尾直接删除，如果在中间或者开头，需要把删除元素后面的元素都向前挪动1位

ArrayList是java基于数组实现的一个类，在中间插入和删除元素都涉及到当前位置到末尾需要进行后移或者前移一位，在新增元素的同时还需要判断数组长度是否足够，不够会进行数组扩充*2，然后进行数组的拷贝操作，所以在ArrayList中不建议进行大量的添加和删除操作，查找的时间复杂度为O(1),添加删除的时间复杂度为O(n);

2.2 链表

链表是一种在物理上非连续、非顺序的数据结构，由若干节点(node)组成，每个节点包含指向下一个节点的指针。

链表的物理存储方式是随机存储，访问方式是顺序访问，查找链表节点的时间复杂度是O(n)，中间插入、删除节点的时间复杂度是O(1)。

单链表：每个节点包含两个部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next

双向链表：每个节点除了data和next指针，还有指向前置节点的prev指针

循环链表：最后一个节点的next指针，指向第一个节点

链表的基本操作：

1. 查找节点：链表中的数据只能按顺序进行访问，最坏的时间复杂度为O(n)
2. 更新节点：在不考虑查找节点的过程情况下，链表更新过程只需要直接把旧数据替换成新数据就行
3. 插入节点：和数组类似，分为三种基本情况
   • 尾部插入：直接把最后一个节点的next指针指向新插入的节点就可以
   • 头部插入：1. 把新节点的next指针指向原先的头节点 2. 把新节点变成链表的头节点
   • 中间插入：1. 新节点的next指针指向插入位置的节点 2.插入位置前置节点的next指针，指向新节点
4. 删除元素：删除同样分为三种情况
   • 尾部删除：把倒数第二个节点的next指针置空
   • 头部删除：把链表的头节点设置为原先头节点的next指针
   • 中间删除：把要删除节点的前置节点的next指针，指向要删除元素的下一个节点

	查找	更新	插入	删除
数组	O(1)	O(1)	O(n)	O(n)
链表	O(n)	O(1)	O(1)	O(1)

LinkList的元素一般是定义的一个Node，同时Node内会分别有字段指向该节点的后面一位和前面一位，Java中LinkList是双向链表,查找的时间复杂度为O(n),添加和删除的时间复杂度为O(1)

2.3 栈(Stack)

栈是一种线性逻辑结构，可以用数组实现，也可以用链表实现

栈包含入栈和出栈操作，遵循先入后出的原则（FILO）

第一个进入的元素存放的位置叫做栈底（bottom），最后进入的元素存放的位置叫做栈顶（top）

入栈（push）：将新的元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置会成为新的栈顶

出栈（pop）：把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶

栈的输出顺序和输入顺序相反，所以栈通常用于对“历史”的回溯，一般递归逻辑可以用栈来代替

2.4 队列(Queue)

队列也是一种线性逻辑结构，可以用数组实现，也可以用链表实现

队列包含入队和出队操作，遵循先入先出的原则（FIFO）

队列的出口端叫做队头（front），队列的入口端叫做队尾（rear）

入队（enqueue）：把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾

出队（dequeue）：把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头

队列 输出顺序和输入顺序相同，所以队列通常用于对历史的回放，也就是按照历史的顺序，把历史重演一遍

特殊队列

1. 循环队列⚠️

   循环队列的队尾指针指向的位置永远空一位，所以最大容量会比数组长度小1

   当循环队列储存满时，(队尾下标 + 1) % 数组长度 = 队头下标

2. 双端队列

   通过结合队列和栈的特点，实现可以从对头一端入队或出队，从队尾一端也可以入队或出队

3. 优先队列

   该队列不属于线性数据结构，是基于二叉堆来实现的

2.5 散列表（哈希表）

散列表也叫哈希表，是存储key-value映射的集合。对于某一个key，散列表可以在接近O(1)的时间内进行读写操作。散列表通过哈希函数实现key和数组下标的转换，通过开放寻址法和链表法来解决哈希冲突

散列表中会用一个哈希函数来实现key和数组下标的转换，最简单的方法如下

index = HashCode(Key) % Array.length

散列表的常用操作：

• 写操作（put）：写操作就是在散列表中插入新的键值对
  1. 通过哈希函数，把key转化成数组下标
  2. 如果数组下标n对应的位置没有元素，就把这个entry填充到数组下标n的位置，如果下标n位置有元素，则会产生哈希冲突，可以通过开放寻址法和链表法解决
     • 哈希冲突 ：因为数组长度有限，当插入的Entry越来有越多时，不同的key通过哈希函数获得的下标可能相同的情况
     • 开放寻址法：当一个key通过哈希函数获得对应的数组下标已被占用时，可以根据某种规则寻找下一个空挡位置
     • 链表法：HashMap数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可。
• 读操作（get）
  1. 通过哈希函数，把Key转化成数组下标
  2. 找到数组下标所对应的元素，如果这个元素的Key为查找的Key，那么就找到了，如果Key不是查找的Key，由于每个元素都与一个链表对应，可以顺着链表往下找

第3章 树

3.1 树和二叉树

树（tree）是n（n>=0）个节点的有限集。当n=0时，称为空树。在任意一个非空树中，有如下特点。

• 有且仅有一个特定的称为根的节点
• 当n>1时，其余节点可分为m（m>0）个互不相交的有限集，没一个集合本身又是一个树，并称为根的子树

二叉树：二叉树是树的一种特殊形式，每个节点最多有两个子节点

满二叉树：一个二叉树的所有与非叶子节点都存在左右孩子节点，并且所有叶子节点都在同一层级上

完全二叉树：对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号从1到n。这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同。完全二叉树只需要保证最后一个节点之前的节点都齐全。

二叉树常用存储结构

1. 链式存储结构：没一个节点最多指向左右两个孩子节点，所以二叉树的每一个节点包含3部分
   • 存储数据的data变量
   • 指向左孩子的left指针
   • 指向右孩子的right指针
2. 数组：数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置上，如果某一个节点的左孩子或右孩子空缺，则数组的对应位置也空出来
   • 假设一个父节点的下标是parent，那么它的左孩子节点下标就是2*parent+1;右孩子节点下标是2*parent+2
   • 假设一个左孩子节点的下标是leftChild，那么它的父节点下标就是(leftChild-1)/2

二叉树的应用

1. 查找

   二叉查找树（节点分部相对比较均衡的二叉查找树，如果节点总数是n，那么搜索节点的时间复杂度就是O(logn)）在二叉树的基础上增加了以下几个条件：

   • 如果左子树不为空，则左子树上所有节点的值均小于根节点的值
   • 如果右子树不为空，则右子树上所有节点的值均大于根节点的值
   • 左、右子树也是二叉查找树

2. 维持相对顺序

   二叉查找树要求左子树小于父节点，右子树大于父节点，这样可以保证二叉树的有序性

   通过二叉树的自平衡可以优化树，如红黑树、AVL树、树堆

   除了二叉查找树，二叉堆也维持着相对的顺序

3.2 二叉树的遍历

从节点之间位置关系的角度来看，二叉树的遍历分为4种

• 前序遍历：按照根–>左孩子–>右孩子的顺序遍历（根左右，根在前面）
• 中序遍历：按照左孩子–>根–>右孩子的顺序遍历（左根右，根在中间）
• 后序遍历：按照左孩子–>右孩子–>根的顺序遍历（左右根，根在后面）
• 层序遍历

从宏观的角度来看，二叉树的遍历归结为两大类

• 深度优先遍历（前序、中序、后序）：
  • 深度优先遍历可以通过递归方法实现，只需要调整三者的顺序
  • 也可以通过栈来实现，栈实现遍历，可以通过将遍历过的节点放入栈中，依次遍历，没有后续的节点可以通过接节点回溯，依次出栈，找到有后续的节点，然后继续操作（已经遍历完成的节点可以直接出栈，无需继续放在栈中）
• 广度优先遍历（层序）：层序遍历可以通过队列实现，从根节点依次放入队列，每次节点出队后，将该节点的左右孩子节点入队，重复操作至遍历结束

3.3 二叉堆

二叉堆本质上是一种完全二叉树，可以分为两个类型

1. 最小堆（小顶堆）：任意一个父节点的值，都小于或等于它左右孩子节点的值
2. 最大堆（大顶堆）：任意一个父节点的值，都大于或等于它左右孩子节点的值

二叉堆的根节点叫作堆顶，大顶堆的堆顶是整个堆中最大元素，小顶堆的堆顶是整个堆中最小的元素

二叉堆的操作

1. 插入节点：直接插入完全二叉树的最后一个位置，然后依次和父节点对比和交换位置，直到和当前父节点对比满足堆的条件或者已经成为根节点后，不再交换位置
2. 删除节点：二叉堆删除的是处于堆顶的节点，删除堆顶的节点后，把堆最后一个节点临时补充到原本堆顶的位置，然后依次和左右孩子对比，小顶堆与小的孩子节点交换位置（大顶堆与大的孩子节点交换位置），直到成为叶子节点，或者满足堆的条件后结束
3. 构建二叉堆：将一个无序的完全二叉树调整为二叉堆，本质就是让所有的非叶子节点依次”下沉“

二叉堆的代码实现

二叉堆的存储方式不是链式存储，而是链式存储，所有的节点都存储在数组中。

如果父亲节点的下标是parent，那么左孩子的下标就是2*parent +1，右孩子的下标是2*parent +2

如果一个孩子的节点下标是child，那么它的父亲节点的下标是(child-1)/2

赏

谢谢你请我吃炸鸡

支付宝

微信