首页  思维导图  详情



 



数据结构与算法

2022-08-20 12:41:54   0  举报





AI智能生成

数据结构知识点梳理

数据结构与算法思维导图

面经

java

模板推荐

作者其他创作

大纲/内容

算法

排序

内部——七大排序算法

插入排序

直接插入排序——稳定，O（n^2），当数组近乎有序时，插排效率还是很高的，近乎O（n）

希尔排序——不稳定，O（n^1.3-1.5）

分组，组内插排保证有序，不断/2缩小分组，直至分组为1

选择排序

选择排序——不稳定，O（n^2)

普通：每次在左边无序区间选最大元素，放入无序区间最右，缩小无序范围

进阶：遍历同时找到无序中最小和最大，分别放最左和最右，注意交换成功最小后，注意是否有影响到最大

堆排序——不稳定，O（nlogn)

先将数据堆化（升序建大根堆，降序建小根堆）（堆化：从最后一个非叶子节点到根节点，对每个结点进行下沉操作）

然后将堆顶元素跟最后元素交换，再重新堆化

交换排序

冒泡排序——稳定，O（n^2)

快排——不稳定，O（nlogn)

当数组近乎有序时，快排反而退化为O(n^2），因为二叉树结构单边倾斜

归并排序——稳定，O（nlogn）

外部

桶排序

基数排序

计数排序

分治

贪心

动规

二分

回溯

数据结构

线性结构

顺序表

顺序表的实现

定义——动态数组

准备工作：

构造方法

grow()方法

toString()方法

增加操作

尾部增加

data[size++]=value

头部增加

从后向前依次后移一位用以给头部腾出空间

data[i+1]=data[i]

任意位置增加

与头插法类似，for循环截止条件不同

data[i+1]=data[i]

删除操作

根据索引删

先判断删除位置是否合法

后面的元素覆盖前面的，并注意将删除前的最后一个元素置为0

data[i]=data[i+1]data[size]=0

根据元素值删

只删除第一次出现的元素值

for+ if (data[i] == value)

删除所有与之相等的

for+while(i!=size||data[i]==value))

修改操作

根据索引下标修改元素

注意判断输入的索引下标是否合法

data[index]=newdata

查找操作

是否能查找到

返回boolean类型

根据索引下标查元素

记得判断输入下标是否合法（index<0||index>=size)均不合法

根据元素查索引下标

查到，return(i),查不到，return -1

JDK——ArrayList

链表

链表的实现

单链表（普通）

定义

由Node类（节点类）和SingleList（链表类）两个类组成

其他方法

toString()方法

可将删、修、改的判断Index是否合法抽象为一个方法

增

头插法

链表为空表

if (head == null) { head = node;

链表不为空

node.next=head;head=node;

中间任意位置插入

先判断输入的索引下标是否合法

if（index==0)——头插

for遍历找要插入位置的前驱节点pre for(int i=0;i<index-1;i++) pre=pre.next;

node.next=pre.next;pre.next=node

尾插法

若链表为空表——可调用头插法

链表不为空——可调用令index=size的中间插入法

删

删除指定索引位置的元素

先判断输入的索引值是否合法

判断删除的是否为头节点

if(index==0)Node temp=head;head=head.next;temp.next=null;size--;

else 用for循环遍历找到删除位置的前一个元素pre

Node cur=pre.next;pre.next=cur.next;cyr.next=null;size--;

根据元素值删除，只删除第一次出现的

头节点就是该元素

if(head.next!=null&&head.val==val)

其他位置删除,还是找前一个元素pre

while(pre.next!=null) if(pre.val==val) 删除操作 pre=pre,next;

根据元素值删元素，删除所有该元素

头节点

while(head!=null&&head.val==val) {删除头节点} if(head.next==null) return

非头节点

while(pre.next!=null) if(pre.val==val) 删除操作 else{pre=pre,next;}

改

修改指定索引位置处的元素

先判断索引值是否合法

for循环遍历找到该索引位置cur，cur.val==newValue

查

根据索引位置查元素并返回查到的元素值

先判断索引位置是否合法

for循环遍历查

查找是否能找到某元素，返回boolean类型

for(Node temp=head;node.next!=null;node=node.next

带虚拟头节点的单链表

虚拟头节点避免了单独处理头节点的特殊情况

虚拟头节点：Node dummyHead=new Node(value:-1),其中value为任意不在链表范围内的值

双链表

定义

头节点head,尾节点tail，每个节点既有前驱pre又有后继next

其他辅助方法

private boolean isRange(int index)

输入的索引是否合法

public String toString()

输出格式

public Node find(int index)

查找指定索引位置的节点或前节点

private void deleteNode(Node 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

应用场景

撤销操作

网页的回退

字符串倒序输出等

队列

基于链表实现

分类

基础队列

Queue

offer()/add

poll()/remove

peek()/element

基于优先级的队列

PriorityQueue

双端队列

Deque

循环队列

应用场景

解决现实情境，比如排队，次序问题

字符串

非线性结构

树形结构

常用的树形结构

二叉树

普通二叉树

左根右

根左右

左右根

层序

完全二叉树

满二叉树

BST——二分搜索树

定义

二叉树

子树根节点大于左子树所有结点，小于右子树所有结点

方法实现

插入add

新插入的结点最后一定插入在了叶子节点，所以可递归判断插左还是插右

判断是否存在某value值

递归找左右子树

查找并返回最大/小值

递归找最左/最右

删除最大/小值并返回

以最小值为例，删除最小值，再将最小值的右子树与最小值的根节点直接相连（递归中删除后返回右即可）

删除值为value的某节点

value值只有左结点没有右节点

删除后直接连接左节点即可

value值只有右节点没有左节点

删除后直接连接右节点即可

value值既有左又有右

找前驱替换value值，所谓前驱，可以是左子树中最大的也可以是右子树中最小的

替换value值

无法直接修改，只能先删除，再插入

注意！BST很高效，但是当BST左右子树高度严重不平衡时，比如退化成单链表

所以，引入了平衡二分搜索树

平衡二分搜索树

AVL——严格平衡，任意子树左右高度差<=1

红黑树——非严格平衡，只有黑节点遵循严格平衡

堆

大根堆/小根堆（基于二叉树）

构造方法

内部是动态数组

根据子节点序号找父节点序号——parent(int k)

根据父节点序号找左右子节点序号——leftChild(int k)、rightChild(int k)

上浮操作——siftUp(int k)

下沉操作——siftDown(int k)

向最大堆中添加一个新元素——add(int val)

将该元素添加到数组末尾，然后进行上浮操作

取到并删除当前堆的最大元素——pollMax()

最大元素即索引为0的，将该元素替换为最后一个元素，然后进行下沉操作

取到当前堆的最大元素——peekMax()

即索引为0的元素

将任意数组堆化——heapify

方式一：不断add元素，当数据量大时，不易操作，不建议

方式二：从最后一个非叶子节点-索引为0的结点依次进行下沉操作，最后一个非叶子节点即最后一个元素的父节点

优先级队列（基于最大堆/最小堆）JDK中内置的PriorityQueue默认是基于最小堆

内置方法

offer()/add()

poll()/remove()

peek()/element()

isEmpty()

自定义优先级

方法一：本类中实现Comparable接口，实现compareTo方法

方法二：新建类，实现Comparator接口，实现compare方法

TopK问题

取大用小（取前k个最大的，则建小根堆）

取小用大（取前k个最小的，建立大根堆）

并查集

字典树——字符串、线段树

散列表（HashMap)

添加键值对——put

根据Key值删除对应的键值对——remove(key)

查找是否存在某key值

查找是否存在某value值

扩容

图

集合框架

Iterable

Collection（接口）

List

ArrayList

顺序表，动态数组

线程不安全

扩容操作：默认扩容为1.5倍，并将原数组拷贝到新数组中

LinkedList

链表

线程不安全

Vector

Stack

线程安全，但是对所有操作直接加synchronized锁，效率极低，是“失败品”不建议使用

CopyOnWriteArratList

读操作不加锁，即只对增删改操作加锁

适用于多读少写的场景，比如黑名单

缺点

因为有数据拷贝，所以内存占用大

只能保证最终的数据一致性，并不能保证实时数据一致性

Queue

PriorityQueue

优先级队列，默认是基于小根堆

泛型类可自定义优先级

实现Comparable接口，覆写compareTo方法

实现Comparator接口，覆写compare方法

函数式编程也很好用

Queue<Student> mypri1 = new PriorityQueue<>(((o1, o2) -> o1.age - o2.age));

Deque

LinkedList

Deque是双端队列接口，LinkedList是实现类，一般队列和栈都用该类

Set

HashSet

本质其实就是HashMap，添加进的元素都是key值，value值为null或者虚值而已

SortedSet

TreeSet

有序的Set集合

Java类库中已有的类（实现过Comparable接口的）可以按照自然排序add

自定义类，必须实现Comparable接口并重写compareTo()方法才能add进去

Map

HashMap

(Key,Value)的键值对，key和value均可以为null

无序，插入顺序并不代表实际存储顺序

线程不安全

解决哈希冲突

闭散列

线性探测——向后查空余

二次探测——对得到的哈希值再次哈希，直到找到不冲突位置

开散列

把冲突位置转换为链表——HashMap使用的

底层结构与扩容问题

JDK1.7

数组+链表（链表是为了解决哈希冲突）

扩容：扩大为两倍后，重新计算原数组在新的数组中的索引位置，拷贝过去

JDK1.8

数组+链表+红黑树（当链表长度超过8（8是由泊松分布得来）且数据总量超过64转红黑树）

扩容：扩大为两倍后，无需重新计算索引位置，元素的位置在原来的位置，或者原来的位置 +oldCap (原来哈希表的长度）

只需要看看原来的 hash 值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引 + oldCap ”

扩容

默认负载因子 α = 填入表中的元素个数/散列表总长度 = 0.75，0.75是对时间和空间的折中

如果内存空间很充足，需要时间效率高的话可以降低α

如果内存空间紧张，时间效率要求不高的话可以提升α

超过α，就会扩容，扩容为原来的两倍，把每个元素重新计算在新数组中的位置拷贝过去

线程不安全

多线程拷贝时头插易形成环形链表——所以1.8就改成了尾插，尾插只是不至于死循环，但还是错的

多线程put操作数据易被覆盖丢失

put和get并发时，put时扩容，导致get到null值

put操作步骤

1.哈希运算得到存储索引下标

2.判断数组是否为空，如果为空，先resize初始化

3.根据索引下标插入

如果没有冲突，直接插入主题

如果有冲突，判断Key是否存在

如果存在直接覆盖原value值

如果不存在，如果插入位置是红黑树，直接插入

如果不存在，插入位置是链表，判断链表长度是否大于8

链表长度<8，直接插入链表

链表长度>8，且数据总长度<64，先扩容再插入

链表长度>8，且数据总长度>64，转红黑树插入

Hash算法

1.根据hashcode(key)计算出hashCode值——h = hashCode(key)

哈希函数Hashcode（）方法

常见的MD5算法

2.根据hashcode值计算出hash值——hash = h ^ ( h >>> 16)

为什么要高16位异或低16位，是为了在数组长度即使很小的时候，也保证高低位都参与到了Hash运算中同时不会有太大开销

3.对hash值进行取模得到最后的存储位置——hash&（length-1）

源代码中&length-1其实就是在取模——当 length 总是 2 的n次方时，h& (length-1) 运算等价于对length取模，也就是 h%length，但是 & 比 % 具有更高的效率。

遍历Map

获取所有key集合

Set<K> keys = map.keySet();

获取所有value集合

Collection<V> valusa = map.values();

获取所有key-value键值对

Set<Map.Entry<K,V>> entry = hashMap.entrySet();

for循环遍历

for(Map.Entry<String,Integer> temp : map.entrySet()){ System.out.print(temp.getKey() + "=" + temp.getValue() + " "); }

LinkedHashMap

key和value都可为null

插入顺序就是输出顺序，在HashMap的基础上维护了一个链表用于记录元素插入顺序

HashTable

线程安全的，但是也是对所有操作直接加synchronized锁，key值不允许为null

ConcurrentMap

ConcurrentHashMap

1.8

数组+链表+红黑树

key值不允许为null

读操作没有加锁(但是使用了 volatile 保证从内存读取结果), 只对写操作进行加锁.

线程安全：CAS+synchronized.

加锁的方式仍然是是用 synchronized, 但是不是锁整个对象, 而是 "锁桶" ,只针对同一个链表的操作进行互斥；只有两个线程访问的恰好是同一个哈希桶上的数据才会锁冲突，大大降低了锁冲突的概率

当前遇到扩容的线程，只扩容和搬一个元素（搬什么呢，把老数组中的每个key-value重新计算下标放入新数组新位置，只搬移一个，其他元素交给同时间的其他线程干），期间新老数组同时存在

SortedMap

TreeMap

有序的哈希表

Java类库中已有的类（实现过Comparable接口的）可以按照自然排序add

自定义类，必须实现Comparable接口并重写compareTo()方法才能add进去

底层结构：红黑树

key不能为null,value可以为null

迭代器

Iterator

可以遍历所有集合，如Map，List，Set

只能单向向前遍历

无法向集合中添加元素、修改元素、无法获取集合中元素的索引

ListIterator

只能遍历List实现的对象

可以向前也可以向后遍历

可以向集合中添加元素、set方法修改元素、也可以获取集合中元素的索引

 Collect

Get Started

数据结构与算法汇总

 Collect

Get Started

数据结构&算法

 Collect

Get Started

数据结构与算法

 Collect

Get Started

数据结构与算法





0 条评论

下一页