首页  思维导图  详情

算法和数据结构基础

2021-08-25 10:58:17   2  举报





AI智能生成

为你推荐

查看更多



左程云老师算法和数据结构基础学习笔记

作者其他创作

大纲/内容

算法和数据结构基础

核心指标

时间复杂度

衡量流程中进行常数操作的次数

原则

需要考虑最差情况

将整个流程拆解为一个一个基本动作，每个动作是常数操作

查看数据量为N时，基本操作和N的关系

最后，只考虑最高阶项

额外空间复杂度

常数项时间

同一复杂度的算法比较的时候，才需要比较

通过大样本数据测试，为简单

与功能无关，实现算法是额外需要的空间

基本数据结构

Stack

Vector

Queue

Linked List

Priority Queue

Heap

Set

Hash Set

Tree Set

Map

HashMap

TreeMap

基本算法

Greedy

Recursion、Backtrace

Traversal

Breadth-first / Depth-first search

Divide and Conquer

Dynamice Programming

Binary Search

Graph

排序

选择排序

O(N^2)

不稳定

冒泡排序

稳定

插入排序

实现

适用于小的数组

当长度小于15，执行时间会比归并实现少10-15%

因为常数项低，当数量少（<=60）时，速度很快

归并排序

左有序，右有序，合并为一个大的有序数组

实质：把比较行为变成了有序信息并传递。大量的比较结果信息被保留传递下去。

时间复杂度O(NlogN)

额外空间复杂度O(N)

核心merge实现总结

三个指针

左半区轮询

R (Mid）

从右半区轮询，第一个是中点加一

K => 目标位置

谁小拷谁，同时移动指针

L==R时，先拷贝L指向的数值到K

穷尽后，剩下未完半区直接拷贝

可以根据具体情况，改变策略

递推实现

由顶向下归并Top-Down Mergesort

应用分治思想(divide-and-conquer)

分解为更小规模的问题，然后递推解决问题

最多访问6NlogN次数组

2N拷贝

2N次拷贝回原数组

最多2N次比较

由底向上归并Down-Top Mergesort

分治

把小问题构建为大一些规模的问题求解

对底层是链表的数据结构，更好可以对链表in-place排序（不需要额外节点)

非递归实现

Tips

长度小于15时，用插入排序提高速度

测试左右半区是否有序，而skip调用merge()

当a[mid] <= a[mid +1]，则skip merge

避免多次拷贝

两个数组，交换职责

应用

计算小和：计算一个数组中，一个数左边比他小的数的总和，叫数的小和。所有数的小和累加起来，叫数组的小和。求数组的小和。

比较一个数和另一半区的比较

逆序对

排序功能不会被破坏，但稳定性破坏

快速排序

给定一个数组，和一个整数num，把小于等于num的数防止数组的左边，大于num的数防止数组右边

分治思想

partition一个数组为两个子数组，对子数组独立排序

partition的时候不能保证稳定性

最差情况O(N^2)

例如对有序数组排序

对策1：随机shuffle数组

对策2：随机选择数组中的一个数为基点

让好情况和差情况都变成概率事件，此模型下时间复杂度为概率的长期期望！“随机”是关键！

额外空间复杂度O(logN)

桶排序Bucket Sort

不基于比较的排序，必须和数据的样本的数据状况强相关当最小值和最大值很窄的才有意义

桶就是一个容器，可以是数组，队列，栈，或状态

计数排序

时间复杂度O(N)

额外空间复杂度O(M)

基数排序

只能为非负整数

理论方法

建十个桶

从个位开始，按此位按队列顺序入桶，然后按队列顺序出桶

然后依次向高位比较入桶，出桶

时间复杂度，实质为O(N*Log(10)N)但经常认为是O(N)

额外空间负载度O(M)

经典实现

核心实现（不用队列实现）

堆排序

优点：有限空间实现O(NlogN)

堆结构：逻辑概念，就是用数组实现的完全二叉树结构实现可以是数组或链表

完全二叉树数组实现的时候：i =>LC: 2*i + 1 RC: 2*i + 2 Parant: (i - 1)/ 2

改进：0位置不用，从1位置开始排列。i => LC: 2 * i ==> i << 1 LR: 2 * i + 1 ==> (i << 1 | 1) Parent : i / 2 ==> i >> 1

位运算快！

完全二叉树中，如果每棵子树的最大值都在顶部，就是大根堆

完全二叉树中，如果每棵子树的最小值都在顶部，就是小根堆

结构中heapSize的作用

堆有效数值的个数

堆中最后一个有效位置

参与到运算中判断越界的条件

重要操作：

heapInsert

1. Insert到数组的下一个位置（index）；2. arr[index]和父节点进行比较，直到不比父节点大的时候结束。（实际有两个条件：1）不比父节点大；2）来到根节点因为：当为根节点的时候，根节点的本身不会大于自己，所以该条件等同条件1）。）

插入操作的时间复杂度O(logN)也就是树的高度

heapify

从index位置，往下看，不断下沉；当1）我的孩子都不再比我大；或2）已经没有孩子了，停止

比较操作的时间复杂度O(LogN)

优先级队列结构，就是堆结构

参考实现：algorithmbasic2020/src/class04/Code02_Heap01.java

额外空间复杂度O(1)

结构类型

大根堆

小根堆

PriorityQueue默认是小根堆

堆排序算法

将数组变成大根堆

从上到下的方法：时间复杂度为O(N*LogN)

从下到上的方法，时间复杂度为O(N)

对0~(N-2)做heapify操作，获得另一个大根堆

时间复杂度O(N*LogN)

重复2nd，直到0

参考代码：algorithmbasic2020/src/class04/Code04_HeapSort.java

两种堆调整的代价heapify

从上往下

复杂度高因为页节点，节点数多，且复杂度最高（移动logN步）

靠近上层节点少，移动代价低靠近下层节点多，移动代价高

从下往上

复杂度低因为层级越多，复杂度越少，页节点，则都不会产生移动

靠近上层的节点少，移动代价高靠近下层的节点多，移动代价低

“从下往上”快

语言提供的堆结构 vs 手写堆结构

取决于，有没有动态该信息的需要！

语言提供的堆结构，如果动态改数据，不保证依然有序

代码示例：algorithmbasic2020/src/class04/Code03_Heap02.java

例如：迪杰斯特拉算法(Dijkstra) （见下，“图”那一节）

手写堆结构，因为增加了对象的位置表，所以能满足动态改信息的需求

例题：已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的。请选择一个合适的排序策略，对这个数组进行排序。两个参数：arr + k参考代码：algorithmbasic2020/src/class04/Code05_SortArrayDistanceLessK.java

1.建一个k+1的小根堆

小根堆放的是当前位置的最小的可能性

2. 从0 - k+1加入小根堆，弹出小根堆头，然后放到 0 位置

3. 从k+2加入小根堆，然后放到1位置

4. 重复3，直到遍历结束

时间复杂度O(N*Logk)当k<<N，效率很高

O(N^2)的核心原因：浪费大量的比较操作

排序算法的稳定性

稳定性指同样大小的样本再排序后会不会改变相对顺序

对基础类型而言，稳定性没有意义

对非基础类型而言，稳定性有重要意义

总结

不基于比较的排序，对样本数据有严格要求，不易改写

基于比较的排序，只要规定好连个样本怎么比较大小就可以直接复用

基于比较的排序，时间复杂度的极限是O(N*logN)

时间复杂度O(N*logN)，额外空间复杂度低于O(N)，且稳定的基于比较的排序是不存在的

为了绝对的速度选快排

为了省空间选堆排

为了稳定选归并

常见的坑

归并排序的额外空间复杂度可以变成O(1)，但是不再稳定搜索“归并排序内部缓存法”

应该用堆排

\"原地归并排序“是垃圾帖，会让时间复杂度变成O(N^2)

快速排序稳定性改进，“01 stable sort”，但是对样本数据要求更多

在整型数组中个，请把奇数放在数组左边，偶数放在数组右边，要求所有奇数之间原始的校对次序不变，所有偶数之间的原始相对次序不变。时间复杂度做到O(1)，额外空间复杂度做到O(1)

同理“01 stable sort\"但对样本数据要求更多

工程上对排序的改进

通常对稳定性进行考虑

实现时，查排序的数据类型，如果为基础数据，则采用快排

如果是非基础类型，则采用归并排序==>为了保持稳定性

需充分考虑利用O(N*logN) 和 O(N^2) 排序的各自优势

例如在归并排序中，经常存在：if (L + 60 < R) { 选用插入排序算法}

快排、堆排、归并，虽然排序调度算法很好，为O(N*logN)，但常数项很高，在少量样本排序的时候，比插入排序慢。

栈和对列

均为逻辑概念

双向链表

数组

参考代码：algorithmbasic2020/src/class02/Code03_DoubleEndsQueueToStackAndQueue.java

Ring Buffer实现

判断栈满或空的方法

方法1：浪费Buffe中的一个slotFull => head + 1 == tailEmpty => head == tail

一个slot可能的代价比较大，如果成员是一个大Obj

方法二：用size变量记录成员个数

方法三：用一个布尔变量full和额外逻辑判断。Full => full == trueEmpty => (head == tail) && !fullfull在每次添加成员的时候，判断赋值。eg static void add(Node N) {..... if (head == tail) this.full = true;}

逻辑相对复杂，而且每次添加均需要判断

固定长度

实现一个栈，push/pos/getMin的复杂度都是O(1)

设计两个栈，一个Data，一个Min

比较：

方法二：push压入Data栈，同时比较Min栈顶，如果New<=Min栈顶，则压入Minpop当Data栈顶和Min栈顶相等的时候，Data和Min均需要弹出getMin直接从Min栈顶返回

空间换时间的思想

用队列实现栈

两个队列：Data 和 Helper

用栈实现队列

两个栈：Push和Pop

pop栈需要为空

push必须一次性倒完

递归

只有递归规模是等规模的时候，如果递归的复杂度符合公式：T(N) = a * T(N/b) + O(N^d)a: 调用次数b: 分治大小d: 除递归以外部分的指数

递归实现的三个条件

可分解性

一个问题可以分解为几个问题的解

分解后的等价性

这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样

存在递归终止条件

写出递推公式找到终止条件

递归都可以用非递归的方式表示

缺点

警惕堆栈溢出

代码中限制递归调用的深度

警惕重复计算

通过Hash表来保存已经求解过的f(k)

函数调用耗时多

考虑空间复杂度

哈希表HashMap/HashSet

增删改查，使用时，时间复杂度O(1)

HashMap中，基础类型作为Key，即便是Wrapper例如：Integer，Double等，永远按值传递

(HashMap中，非基础类型作为Key，则按引用传递

有序表TreeMap

时间复杂度O(logN)

Key有序

底层实现通常为

平衡二叉树

AVL

SB （Size-Balance） Tree

红黑树

跳表（Skip Map)

比较器

实质：重载比较运算符

返回负数的时候，第一个参数排在前面返回正数的时候，第二个参数排在前面返回0的时候，谁在前面无所谓

应用在特殊标准的排序上

应用在根据特殊标准排序的结构上

简化代码，适用于泛型编程

代码示例：algorithmbasic2020/src/class04/Code01_Comparator.java

前缀树

单个字符串中，字符从前到后的加到一棵多叉树上字符防在路上，字节上有专属的数据项（常见的是pass和end值）所有样本都这样添加，如果没有路就新建，如有路就复用沿途节点的pass值加1，每个字符串结束时来到的节点end值增加可以完成前缀相关的查询

实现一

Node结构：public class TerieTree { public static class Node1 { private int pass = 0; private int end = 0; private Node1[] nexts; public Node1() { pass = 0; end = 0; nexts = new Node1[26]; } } public static class Ter1() { private Node1 root; public Trie01() { root = new Node1(); } ...... }}

插入Insert

查找Word单词出现的次数

查找有几个字符串是以pre这个字符串为前缀的

删除

实现二

当字符比较多的时候，用Hash表的方式来代表每一条路。

实现三（Brute Force）

应用和扩展

如果某个问题带有前缀查找特征，则可以在节点内部增加某种特定信息，从而用前缀树的方法来处理

链表

面试方法论

笔试，重点考察时间复杂度

面试，时间复杂度依然第一位，但一定要找到空间最省的方法

面试常用数据结构和技巧

使用容器（哈希表，数组等）

快慢指针

输入链表头节点，奇数长度返回中点，偶数长度返回上中点

arr.get((arr.size() - 1) / 2)

输入链表头节点，奇数长度返回中点，偶数长度返回下中点

arr.get(arr.size() / 2)

输入链表头节点，奇数长度返回中点，偶数长度返回上中点前一个Node

arr.get((arr.size() - 3) / 2)

输入链表头节点，奇数长度返回中点，偶数长度返回下中点前一个Node

arr.get((arr.size() - 2) / 2)

链表的反转

参考代码：algorithmbasic2020/src/class02/Code01_ReverseList.java

单链表实现

双链表实现

链表删除特定值

参考代码：algorithmbasic2020/src/class02/Code02_DeleteGivenValue.java

考虑删除值为头节点的连续的节点

删除从新节点开始的后续节点中，给定值的节点

常见面试题：给定一个单链表的头节点head，请判断该链表是否为回文结构。

笔试：遍历链表，每个节点加入一个栈。然后再次遍历，每一个动作，从栈中弹出一个节点进行比较。如果有不同，则返回false。否则，true。因为stack加入，再弹出，表示一个逆序。

利用快慢指针：找到中点，然后从慢指针开始，后半部压入栈，然后从链表头开始比对栈中的每一个出栈节点，直到栈为空。如果有任何一个栈节点不等于链表的节点，则为false，否则为true。

利用快慢指针：找到中点；调整中点指向null；中点后的next指针反转指向前一个节点；然后从两端向中间遍历，如果有不等，则为false。直到任何L指针或R指针指向null，则结束比较，返回true

单链表逆序实现

常见面试题：将单链表按某值划分成左边小，中间相等，右边大的形式

笔试：把链表放在数组里，在数组上做partition

常见面试题：一种特殊的单链表类如下：class Node { int value; Node next; Node rand; Node(int val) { value = val;}}rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。给定一个有Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。【要求】时间复杂度O(N)，空间复杂度O(1)

面试：不用Hash表，强制将Clone Node插入原链表中。如 1->2->3 ==> 1->1'->2->2'->3->3'利用此结构代替Hash表，记录新老Node对信息。

常见面试题：难度 *****给定两个可能有环也可能无环的单链表，头节点head1和head2，请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回null【要求】如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)相交，在此同节点上的值没有关系，指的是内存地址。code：algorithmbasic2020/src/class06/Code05_FindFirstIntersectNode.java

判断是否有环，有环的情况下返回第一个入环的节点

方法一：利用Set Map

方法二：利用快慢指针1. S指针一次走一步，F指针一次走两步，然后从开头一起出发，最后到相遇；2. 相遇后，F指针从头开始走，一次走一步，S指针从相遇的节点开始走，直到下次相遇。此节点为产生环的第一个节点。

如果两个链表都无环，则此两链表一定最后的节点是相同的节点。实现：

如果为两个有环链表，放回第一个相交节点，否则不相交，返回null。如果两个有环链表相交，一定共用环。

如果一个有环，一个无环，则这两个链表不可能相交。

主方法

常见面试题：能不能不给单链表的头节点，只给想要删除的节点，就能做到在链表上把这个节点删除掉？

取巧的办法可以。来到删除节点，copy下一个节点的值到该节点，然后删除下一个节点。

实质：不行。删除必须给出头节点。

问题1：其实采用了copy方法，并没有删除自己

问题2：如果节点不能调用copy或构造方法，则有问题

问题3: 绝对无法删除最后一个节点

约瑟夫环？？？？

二叉树Binary Tree

结构Class Node { V value; Node left; Node right;}

深度优先遍历

递归实现

递归调用在此是利用了递归序。每个调用有三次处理head，具体在三次中哪一次处理head（在此是打印动作）。分别产生了先序、中序和后序。先序：第一次处理节点的时候，进行处理（在此为打印），则为先序说明任何一个节点都可以去左子树遍历，收集信息，然后去右子树收集信息，最后在第三次回到此节点（头节点），对信息做整合。==>树上做动态规划的基础

先序：任何子树的处理顺序都是，先头节点，再左子树，然后右子树

中序：任何子树的处理顺序都是，先左子树，再头节点，然后右子树

后序：任何子树的处理顺序都是，先左子树，再右子树，然后头节点

先序：利用一个栈压头节点，以后按统一逻辑计算：1. 弹出打印2. 如有右，要入右3. 如有左，压入左

中序：1. 整条左边界依次入栈：2. 如1无法继续，则弹出节点，就打印，且来到节点右树上，继续执行条件1.

其实每一棵树都可以用“左头”分解，而且每个节点是处理完了左子树，然后再处理右子树，继续用“左头“的方式分解

后序：利用两个个栈压头节点，以后按统一逻辑计算：1. 弹出，压入栈22. 如有左，压入左3. 如有右，要入右4. 从栈2中出栈，然后打印

后序实现2

宽度优先，按层遍历

用队列头压队列队列不为空，弹出，加左，再加右，

利用flag实现监控某层是否结束

求树最大宽度

用map机制

不用map

二叉树的序列号和反序列化

可以用先序或者中序或者后序或者按层遍历，来实现二叉树的序列化用了什么方式序列化，就用什么方式反序列化

利用null补齐树，不要忽略空，然后进行遍历

先序实现

序列化把序列化的时机放在加入队列的时候

反序列化

宽度优先序列化实现

序列化

如何设计一个打印整棵树的打印函数

二叉树结构定义如下：Class Node { V value; Node left; Node right; Node parent;}给你二叉树中的某一个节点，找出后继节点

Broto force方法

实现：1. 当X有右树的时候，后继节点是右子树的最左的节点；2. 当X没有右树的时候，X节点是后继父节点的左子树的最右的孩子。方法：向上找父节点，直到自己是父节点的左孩子，且父节点不是空，则此父节点是后继；如果父节点为空，则X为此树的最右节点，不存在后继节点

题目：请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折一次，压出折痕后展开。此时折痕是凹下去的，即折痕凸起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。给定一个输入参数N，代表纸条都从下边向上方连续对折N次。请从上到下打印所有折痕的方向。例如：N=1时，打印：down; N=2时，打印down down up。

二叉树的递归套路

可以解决面试中绝大多数的二叉树问题，尤其是树形dp问题

本质是利用递归遍历二叉树的便利性

套路

假设以X节点为头，假设可以向X左树和X右树要任何信息

在上一步的假设下，讨论以X为头节点的树，得到答案的可能性（最重要）

常见分类：需获取信息和X有关还是无关？

与X无关

不通过X

与X有关

通过X

列出所有可能性后，确定到底需要向左树和右树要什么样的信息

把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息S

递归函数都返回S，每一颗子树都这么要求

写代码，在代码中考虑如何把左树的信息和右树的信息整合出整棵树的信息

递归套路

给定一棵二叉树的头节点head，返回这颗二叉树是不是平衡二叉树

实现：

给定一棵二叉树的头节点head，任何两个节点之间都存在距离，返回整棵二叉树的最大距离

取max值

左树最大距离

右树最大距离

左树高度 + 右树高度 + 1

给定一棵二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的size搜索二叉树：整个二叉树没有重复值，且左树比头节点小，右树比头节点大，每棵子树都如此

可获得信息：最大子搜size bool isAllBSTmaxValue minValue

左树是最大二叉搜索子树

右树是最大二叉搜索子树

左树和右树都是最大二叉搜索子树，且左树（最大值）小于X，右树（最小值）大于X

可获得信息：左：最大子搜size bool isAllBST maxValue

可获得信息：右：最大子搜size bool isAllBST minValue

给定一棵二叉树的头节点，返回这颗二叉树中最大的二叉搜索子树的头节点

派对的最大快乐值：员工信息定义如下：class Employee { public int happy; // 这名员工可以带来的快乐值 List<Employee> subordinates; // 这名员工有哪些直接下级}公司的每个员工都符合Employee结构。整个公司的人员机构可以看做是一棵标准的、没有环的多叉树。树的头节点是公司唯一的老板。除老板外的每一个员工都有唯一的直接上级。叶节点是没有任何下属的基层员工（subordinates列表为空），除基层员工外，每一个员工都有一个或多个直接下级。

X来：X.happya不来的子树的最大快乐值b不来的子树的最大快乐值c不来的子树的最大快乐值

X不来：X = 0；a来的子树的最大值，或a不来的子树的最大值；b来的子树的最大值，或b不来的子树的最大值;c来的子树的最大值，或c不来的子树的最大值

ChildTopic

判断是否是满二叉树

判断是否为完全二叉树

宽度优先遍历：1）任何节点，有右无左，则false。否则继续。2）一旦遇到左右孩子不双全，后续遇到的所有节点必须为叶节点。

实现1

递归套路：

1. 满二叉树，无缺口；2. 有缺口：1）左树有缺口（没有越过左树）==>左完全，右树满，左高 = 右高 + 12）左树刚满 ==> 左满，右满，且左高= 右高 + 13）右树有缺口 ==> 左满，右是完全二叉树，且左高 = 右高

信息：左树是否满，是否完全二叉树及高度右树：是否满，是否完全二叉树及高度

测试

难度：***给定一棵二叉树的头节点head，和另外两个节点a和b。返回a和b的最低公共祖先。

方法1：通过遍历，生成一个map<节点，父节点>。对a遍历，把所有的父节点加入一个set对b遍历，查看是否父节点在set中。第一个发现的节点，则是最低公共祖先。

方法2：递归套路

Info：1）任何子树的交汇节点 2）是否有O1； 3）是否有O2；

4) 没有交汇点（ans = null）

贪心算法

1）最自然智慧的算法；2）用一种局部最功利的标准，总是做出在当前看来最好的选择；3）难点在于证明局部最功利的标准可以得到全局最优解；4）对于贪心算法的学习主要以增加阅历和经验为主

给定一个由字符串组成的数组strs，必须把所有的字符串拼接起来，返回所有可能的拼接结果中，字典序最小的结果

标准过程：1. 分析业务；2. 根据业务逻辑找到不同的贪心策略；3. 对于能举出反例的策略直接跳过，不能举出反例的策略要证明有效性

解决套路：1. 实现一个不依靠贪心策略的解法X，可以用最暴力的尝试；2. 脑补出贪心策略A，贪心策略B，贪心策略C。。。3. 用解法X和对数器，用实验的方法得知哪个贪心策略正确；4. 不用纠结贪心策略的证明

例题：一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目开始时间和结束时间，你来安排宣讲的日程，要求会议室进行的宣讲场次最多。返回最多的宣讲场次。

用对数器验证核心：不用证明！

暴力解法

贪心算法：选择对结束时间进行排序，早结束的先安排

例题：给定一个字符串str，只由'X'和'.'两种字符构成。'X'表示墙，不能放灯，也不需要点亮，'.'表示居民点，可以放灯，需要点亮，如果灯放在i位置，可以让i-1，i和i+1三个位置点亮返回如果点亮str中所有需要点亮的位置，至少需要几盏灯？

暴力解法：1。每个位置去放灯，和不放灯；2. 验证是否满足条件

例题：输入：正数数组costs，正数数组profits，正数K和Mcost[i]表示i号项目的花费profits[i]在i号厦门在扣除花费后还能挣到的钱（利润）K表示你只能串行的最多做K个项目M表示你的初始资金说明：每一个项目做完马上获得利润，可以支持去做下一个项目。不能并行地做项目。输出：你最后获得的最大钱数。

并查集UnionFind

如果两个user，a字段一样，或者b字段一样，或者c字段一样，就认为是同一个人，请合并users，返回合并后的用户数量

可以利用数组下标代表user标号=>优化

图

结构定义：

Node节点定义：// 点结构的描述 A 0public class Node { public int value; public int in; // 直接入度 public int out; // 直接出度 public ArrayList<Node> nexts; //直接邻居（由自己出发能到达的节点） public ArrayList<Edge> edges; //到达直接邻居的边 public Node(int value) { this.value = value; in = 0; out = 0; nexts = new ArrayList<>(); edges = new ArrayList<>(); }}

当输入的结构不同于此结构，则建立一个类转化输入结构为此结构，此后的图的相关算法均按此结构展开。类似：

宽度优先遍历bfs

Set：标记访问过的节点（避免环的访问）

队列：

深度优先遍历dfs

栈：记录遍历时走的路径

业务处理在第一次入栈的时候做

拓扑排序算法

1）在图中找到所有入度为0的点输出2）把所有入度为0的点在图中删除，继续找入度为0的点输出，周而复始3）图的所有点都被删除后，依次输出的顺序就是拓扑排序要求：有向图且其中没有环应用：事件安排、编译顺序

最小生成树算法（Spanning Tree）Kruskal Algo

中心思想时始终以边为主袋地位，无论如何都要选择权值最小的边，但是前提是使用此边后不能构成连通图。所以这个算法的第一步是将所有的边从小到大排序，之后按排列的顺序来一步一步选择我们需要的边。

1）总是从权值最小的边开始考虑，依次考察权值依次变大的边；2）当前的边要么进入最小生成树的集合，要么丢弃3）如果当前的边进入最小生成树的集合中不会形成环，就要当前边4）如果当前的边进入最小生成树的集合中会形成环，就不要当前边4）考察完所有边之后，最小生成树的集合也就得到了

时间复杂度为O(e⋅loge)，e为边的数目，与顶点数量无关，适合稀疏图。

最小生成树算法Prim算法

从某个顶点v开始，列出顶点 v 所有邻接点的边，选择权值最小的边（vi-->vj）加入到最小生成树中，并标记该边已被访问过；再从vj开始列出顶点vj所有邻接点的边，从中选择所有未被访问过的边中权值最小的边 vj-->vk 加入到最小生成树中，并标记该边已被访问过。重复上述操作，直到找到n-1条边为止。

时间复杂度为O(n2)，n为顶点的数量，其时间复杂度与边得数目无关，适合稠密图。

贪心算法的一种

暴力递归

就是尝试：把问题转化为规模缩小了的同类问题的子问题；有明确的不需要继续进行的递归的条件（base case）；有当得到了子问题的结构之后的决策过程；不记录每一个子问题的解；

汉诺塔问题：有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：1. 每次只能移动一个圆盘；2. 大盘不能叠在小盘上面。提示：可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。

分解为三步

N-1个圆盘移动到B杆

第N个圆盘移动到B杆

N-1个圆盘移动到C杆

考虑所有的情况

A到C

A到B

B到A

B到C

C到A

C到B

所有情况都归结为一种实现：From，To， Other从From移动到To，依靠Other做辅助

N: From to To

最优解时间复杂度O（2^N - 1)

例题：给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现？

两次递归调用

打印一个字符串的全部子序列

子串：子序列：位置先后不能乱，但可以不连续

打印一个字符串的全部排列

打印一个字符串的全部排列，要求不要出现重复的排列

利用“分治限界”的思想

从左往右的尝试模型1规定1和A对应、2和B对应、3和C对应。。。那么一个数字字符串比如“111”就可以转化为：AAA，KA和AK给定一个只有数字字符组成的字符串str，返回有多少种转化结果？

algorithmbasic2020/src/class11/Code06_ConvertToLetterString.java

实现方法一

从左往右的尝试模型2给定两个长度都为N的数组weights和valuesweight[i]和values[i]分别代表i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少？

背包问题

对应code：algorithmbasic2020/src/class11/Code07_Knapsack.java

动态规划实现

对应code： algorithmbasic2020/src/class12/Code03_Knapsack.java

范围上尝试的模型给定一个整型数组arr，代表数值不同的纸牌排成一条线，玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每一个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。

对应code：algorithmbasic2020/src/class11/Code08_CardsInLine.java

基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

时间复杂度O(N^N)

应用位运算方法，减少常数项，加速了常数时间

假设有排成一行的N个位置，记为1~N，N一定大于等于2开始时机器人在其中的M位置（M一定是1~N中的一个）如果机器人来到1位置，那么下一步只能往右来到2位置；如果机器人来到N位置，那么下一步只能往右来到N-1位置；如果机器人来到中间位置，那么下一步可以往左走或者往右走；规定机器人必须走K步，最终来到P位置（P也是1~N的一个）的方法有多少种给定四个参数N、M、K、P，返回方法数。

code link：algorithmbasic2020/src/class12/Code01_RobotWalk.java

可以利用缓存子过程的结果

也称为“记忆化搜索”

给定一个字符串str，给定一个字符串类型的数组arrarr里的每一个字符串，代表一张贴纸，可以把单个字符剪开使用，目的是拼出str来返回需要至少多少张贴纸可以完成这个任务。例如：str=\"babac\

code：algorithmbasic2020/src/class12/Code02_StickersToSpellWord.java

arr中的顺序完全无所谓

两个字符串的最长公共子序列问题

algorithmbasic2020/src/class12/Code05_PalindromeSubsequence.java

做一个二维表

填充第一行和第一列

dp[i][j]

公共子序列：即不以st1r[i]结尾，也不以str2[j]结尾此时dp[i][j] = dp[i-1][j-1]

公共子序列：以st1r[i]结尾，但不以str2[j]结尾此时dp[i][j] = dp[i][j-1]

公共子序列：不以st1r[i]结尾，但以str2[j]结尾此时dp[i][j] = dp[i-1][j]

公共子序列：即以st1r[i]结尾，也以str2[j]结尾也即是str[i] == str[j]时候，此时dp[i][j] = dp[i-1][j-1] + 1

以两个str的结尾的字符是否属于公共子序列为条件分类

返回dp[str1.length -1][str2.length - 1]

动态规划Dynamic programming

常见的4种尝试模型

从左往右的尝试模型

范围上的尝试模型

多样本位置全对应的尝试模型

寻找业务限制的尝试模型

面试中设计递归过程的原则：

每一个可变参数的类型，一定不要比int类型更加复杂

原则1）可以违反，让类型突破到一维线性结构，那必须是唯一可变参数

如果发现原则1）被违反，但不违反原则2），只需要做到记忆化搜索即可

可变参数的个数，尽可能少！

思路：1）设计暴力递归：重要原则+4种常见尝试模型；2）分析有没有重复解：套路解决;3）用记忆化搜索-->用严格表结构实现动态规划：套路解决4）看看能否继续优化：套路解决

图例

可变参数数量尽可能少

暴力递归到动态规划的套路

1）已经有了一个不违背原则的暴力递归，而且的确存在解的重复调用；2）找到哪些参数的变化会影响返回值，对每一个列出变化范围；3）参数间的所有的组合数量，意味着表的大小；4）记忆化搜索的方法就是傻缓存，非常容易得到；5）规定好严格表的大小，分析位置的依赖顺序，然后从基础填写到最终解：6）对于有枚举行为的决策过程，进一步优化

动态规划的进一步优化

空间压缩

状态化简

四边形不等式

其他

什么暴力递归可以继续优化？

有重复调用同一个子问题的解，这种递归可以优化

如果每一个子问题都是不同的解，无法优化也不用优化

暴力递归和动态规划的关系

摸一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划

任何动态规划问题，都一定对应着某一个有解的重复调用的暴力递归

但不是所有的暴力递归，都一定对应着动态规划