数据结构与算法
2022-08-20 12:41:54 0 举报AI智能生成
登录查看完整内容
数据结构知识点梳理
作者其他创作
大纲/内容
直接插入排序——稳定，O（n^2），当数组近乎有序时，插排效率还是很高的，近乎O（n）
分组，组内插排保证有序，不断/2缩小分组，直至分组为1
希尔排序——不稳定，O（n^1.3-1.5）
插入排序
普通：每次在左边无序区间选最大元素，放入无序区间最右，缩小无序范围
进阶：遍历同时找到无序中最小和最大，分别放最左和最右，注意交换成功最小后，注意是否有影响到最大
选择排序——不稳定，O（n^2)
先将数据堆化（升序建大根堆，降序建小根堆）（堆化：从最后一个非叶子节点到根节点，对每个结点进行下沉操作）
然后将堆顶元素跟最后元素交换，再重新堆化
堆排序——不稳定，O（nlogn)
选择排序
冒泡排序——稳定，O（n^2)
当数组近乎有序时，快排反而退化为O(n^2），因为二叉树结构单边倾斜
快排——不稳定，O（nlogn)
交换排序
归并排序——稳定，O（nlogn）
内部——七大排序算法
桶排序
基数排序
计数排序
外部
排序
分治
贪心
动规
二分
回溯
算法
定义——动态数组
构造方法
grow()方法
toString()方法
准备工作：
data[size++]=value
尾部增加
data[i+1]=data[i]
从后向前依次后移一位用以给头部腾出空间
头部增加
与头插法类似，for循环截止条件不同
任意位置增加
增加操作
data[i]=data[i+1]data[size]=0
后面的元素覆盖前面的，并注意将删除前的最后一个元素置为0
先判断删除位置是否合法
根据索引删
for+ if (data[i] == value)
只删除第一次出现的元素值
for+while(i!=size||data[i]==value))
删除所有与之相等的
根据元素值删
删除操作
data[index]=newdata
注意判断输入的索引下标是否合法
根据索引下标修改元素
修改操作
返回boolean类型
是否能查找到
记得判断输入下标是否合法（index<0||index>=size)均不合法
根据索引下标查元素
根据元素查索引下标
查找操作
顺序表的实现
JDK——ArrayList
顺序表
由Node类（节点类）和SingleList（链表类）两个类组成
定义
可将删、修、改的判断Index是否合法抽象为一个方法
其他方法
if (head == null) { head = node;
链表为空表
node.next=head;head=node;
链表不为空
头插法
先判断输入的索引下标是否合法
if（index==0)——头插
node.next=pre.next;pre.next=node
for遍历找要插入位置的前驱节点pre for(int i=0;i<index-1;i++) pre=pre.next;
中间任意位置插入
若链表为空表——可调用头插法
链表不为空——可调用令index=size的中间插入法
尾插法
增
先判断输入的索引值是否合法
if(index==0)Node temp=head;head=head.next;temp.next=null;size--;
判断删除的是否为头节点
Node cur=pre.next;pre.next=cur.next;cyr.next=null;size--;
else 用for循环遍历找到删除位置的前一个元素pre
删除指定索引位置的元素
if(head.next!=null&&head.val==val)
头节点就是该元素
根据元素值删除，只删除第一次出现的
while(head!=null&&head.val==val) {删除头节点} if(head.next==null) return
头节点
非头节点
根据元素值删元素，删除所有该元素
删
先判断索引值是否合法
for循环遍历找到该索引位置cur，cur.val==newValue
修改指定索引位置处的元素
改
先判断索引位置是否合法
for循环遍历查
根据索引位置查元素并返回查到的元素值
for(Node temp=head;node.next!=null;node=node.next
查找是否能找到某元素，返回boolean类型
查
单链表（普通）
虚拟头节点避免了单独处理头节点的特殊情况
带虚拟头节点的单链表
输入的索引是否合法
private boolean isRange(int index)
输出格式
public String toString()
查找指定索引位置的节点或前节点
public Node find(int index)
删除节点node
private void deleteNode(Node node)
其他辅助方法
头插、尾插、中间位置插入
删除指定索引位置，删除指定元素值
查找是否存在某值，查找具体索引位置的值
将指定索引位置的元素的值修改为新的值
双链表
虚拟头节点避免了考虑头节点的特殊情况
带虚拟头节点的双链表
链表的实现
JDK——LinkedList
https://blog.csdn.net/m0_58652786/article/details/121731740
相关面试/笔试题—
链表
基于数组实现
push() ——入栈
pop() ——返回栈顶元素并删除栈顶
peek() ——返回栈顶元素
常用操作
https://blog.csdn.net/m0_58652786/article/details/122715063
单调栈问题
撤销操作
网页的回退
字符串倒序输出等
应用场景
栈
基于链表实现
offer()/add
poll()/remove
peek()/element
Queue
基础队列
PriorityQueue
基于优先级的队列
Deque
双端队列
循环队列
分类
解决现实情境，比如排队，次序问题
队列
字符串
线性结构
力扣232、225
用栈实现队列/用队列实现栈
左根右
根左右
左右根
层序
普通二叉树
递归/迭代两种方法都必须掌握
完全二叉树
满二叉树
二叉树
子树根节点大于左子树所有结点，小于右子树所有结点
新插入的结点最后一定插入在了叶子节点，所以可递归判断插左还是插右
插入add
递归找左右子树
判断是否存在某value值
递归找最左/最右
查找并返回最大/小值
以最小值为例，删除最小值，再将最小值的右子树与最小值的根节点直接相连（递归中删除后返回右即可）
删除最大/小值并返回
删除后直接连接左节点即可
value值只有左结点没有右节点
删除后直接连接右节点即可
value值只有右节点没有左节点
找前驱替换value值，所谓前驱，可以是左子树中最大的也可以是右子树中最小的
value值既有左又有右
删除值为value的某节点
无法直接修改，只能先删除，再插入
替换value值
方法实现
所以，引入了平衡二分搜索树
注意！BST很高效，但是当BST左右子树高度严重不平衡时，比如退化成单链表
BST——二分搜索树
AVL——严格平衡，任意子树左右高度差<=1
红黑树——非严格平衡，只有黑节点遵循严格平衡
平衡二分搜索树
满二叉树是特殊的完全二叉树，完全二叉树就是满二叉树缺了一个右下角
内部是动态数组
根据子节点序号找父节点序号——parent(int k)
根据父节点序号找左右子节点序号——leftChild(int k)、rightChild(int k)
上浮操作——siftUp(int k)
下沉操作——siftDown(int k)
将该元素添加到数组末尾，然后进行上浮操作
向最大堆中添加一个新元素——add(int val)
最大元素即索引为0的，将该元素替换为最后一个元素，然后进行下沉操作
取到并删除当前堆的最大元素——pollMax()
即索引为0的元素
取到当前堆的最大元素——peekMax()
方式一：不断add元素，当数据量大时，不易操作，不建议
方式二：从最后一个非叶子节点-索引为0的结点依次进行下沉操作，最后一个非叶子节点即最后一个元素的父节点
将任意数组堆化——heapify
大根堆/小根堆（基于二叉树）
offer()/add()
poll()/remove()
peek()/element()
isEmpty()
内置方法
方法一：本类中实现Comparable接口，实现compareTo方法
方法二：新建类，实现Comparator接口，实现compare方法
自定义优先级
取大用小（取前k个最大的，则建小根堆）
取小用大（取前k个最小的，建立大根堆）
TopK问题
优先级队列（基于最大堆/最小堆）JDK中内置的PriorityQueue默认是基于最小堆
堆
并查集
字典树——字符串、线段树
常用的树形结构
树形结构
添加键值对——put
根据Key值删除对应的键值对——remove(key)
查找是否存在某key值
查找是否存在某value值
扩容
散列表（HashMap)
图
非线性结构
数据结构
线程不安全
顺序表，动态数组
扩容操作：默认扩容为1.5倍，并将原数组拷贝到新数组中
ArrayList
LinkedList
线程安全，但是对所有操作直接加synchronized锁，效率极低，是“失败品”不建议使用
Stack
Vector
读操作不加锁，即只对增删改操作加锁
适用于多读少写的场景，比如黑名单
因为有数据拷贝，所以内存占用大
只能保证最终的数据一致性，并不能保证实时数据一致性
缺点
考虑用其他容器，比如ConcurrentHashMap
CopyOnWriteArratList
List
实现Comparable接口，覆写compareTo方法
实现Comparator接口，覆写compare方法
泛型类可自定义优先级
函数式编程也很好用
优先级队列，默认是基于小根堆
Deque是双端队列接口，LinkedList是实现类，一般队列和栈都用该类
本质其实就是HashMap，添加进的元素都是key值，value值为null或者虚值而已
HashSet
Java类库中已有的类（实现过Comparable接口的）可以按照自然排序add
自定义类，必须实现Comparable接口并重写compareTo()方法才能add进去
有序的Set集合
TreeSet
SortedSet
Set
Collection（接口）
Iterable
无序，插入顺序并不代表实际存储顺序
线性探测——向后查空余
二次探测——对得到的哈希值再次哈希，直到找到不冲突位置
闭散列
把冲突位置转换为链表——HashMap使用的
开散列
解决哈希冲突
数组+链表（链表是为了解决哈希冲突）
扩容：扩大为两倍后，重新计算原数组在新的数组中的索引位置，拷贝过去
JDK1.7
数组+链表+红黑树（当链表长度超过8（8是由泊松分布得来）且数据总量超过64转红黑树）
只需要看看原来的 hash 值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引 + oldCap ”
扩容：扩大为两倍后，无需重新计算索引位置，元素的位置在原来的位置，或者原来的位置 +oldCap (原来哈希表的长度）
JDK1.8
底层结构与扩容问题
如果内存空间很充足，需要时间效率高的话可以降低α
如果内存空间紧张，时间效率要求不高的话可以提升α
默认负载因子 α = 填入表中的元素个数/散列表总长度 = 0.75，0.75是对时间和空间的折中
超过α，就会扩容，扩容为原来的两倍，把每个元素重新计算在新数组中的位置拷贝过去
多线程拷贝时 头插 易形成环形链表——所以1.8就改成了尾插，尾插只是不至于死循环，但还是错的
多线程put操作数据易被覆盖丢失
put和get并发时，put时扩容，导致get到null值
1.哈希运算得到存储索引下标
2.判断数组是否为空，如果为空，先resize初始化
如果没有冲突，直接插入主题
如果存在直接覆盖原value值
如果不存在，如果插入位置是红黑树，直接插入
链表长度<8，直接插入链表
链表长度>8，且数据总长度<64，先扩容再插入
链表长度>8，且数据总长度>64，转红黑树插入
如果不存在，插入位置是链表，判断链表长度是否大于8
如果有冲突，判断Key是否存在
3.根据索引下标插入
put操作步骤
常见的MD5算法
哈希函数Hashcode（）方法
1.根据hashcode(key)计算出hashCode值——h = hashCode(key)
为什么要高16位异或低16位，是为了在数组长度即使很小的时候，也保证高低位都参与到了Hash运算中同时不会有太大开销
2.根据hashcode值计算出hash值——hash = h ^ ( h >>> 16)
源代码中&length-1其实就是在取模——当 length 总是 2 的n次方时，h& (length-1) 运算等价于对length取模，也就是 h%length，但是 & 比 % 具有更高的效率。
3.对hash值进行取模得到最后的存储位置——hash&（length-1）
Hash算法
Set<K> keys = map.keySet();
获取所有key集合
Collection<V> valusa = map.values();
获取所有value集合
for循环遍历
获取所有key-value键值对
遍历Map
HashMap
key和value都可为null
插入顺序就是输出顺序，在HashMap的基础上维护了一个链表用于记录元素插入顺序
LinkedHashMap
线程安全的，但是也是对所有操作直接加synchronized锁，key值不允许为null
HashTable
数组+链表+红黑树
key值不允许为null
线程安全：CAS+synchronized.
当前遇到扩容的线程，只扩容和搬一个元素（搬什么呢，把老数组中的每个key-value重新计算下标放入新数组新位置，只搬移一个，其他元素交给同时间的其他线程干），期间新老数组同时存在
1.8
JDK1.7用的还是数组+链表，加锁机制是分段锁（把几个桶划分为一段）；
ConcurrentHashMap
ConcurrentMap
有序的哈希表
底层结构：红黑树
TreeMap
SortedMap
Map
可以遍历所有集合，如Map，List，Set
只能单向向前遍历
无法向集合中添加元素、修改元素、无法获取集合中元素的索引
Iterator
只能遍历List实现的对象
可以向前也可以向后遍历
可以向集合中添加元素、set方法修改元素、也可以获取集合中元素的索引
ListIterator
迭代器
集合框架
数据结构与算法
0 条评论
回复 删除
下一页
