数据结构----算法--五大基本算法

数据结构----算法–五大基本算法

一.贪心算法

1.什么是贪心算法

在有多个选择的时候不考虑长远的情况，只考虑眼前的这一步，在眼前这一步选择当前的最好的方案

二.分治法

1.分治的概念

分治法：分而治之

将一个问题拆解成若干个解决方式完全相同的问题

满足分治的四个条件

1.问题难度随着数据规模缩小而降低

2.问题可拆分

3.子问题间相互独立

4.子问题的解可合并

2.典型的分治：二分查找(折半搜索) BinaryChop

前提：有序

时间复杂度O(log2的n次方)

1.循环实现二分查找

//循环
int BinaryChop1(int a[], int begin, int end ,int find) {if (a == nullptr || begin > end) return -1;while (begin<= end) {int mid = begin+(end- begin)/2 ;if (a[mid] == find) {cout << "找到了,返回在数组中的下标" << endl;return mid;}else if (a[mid] < find) {begin = mid + 1;}else if (a[mid] > find) {end = mid - 1;}}return -1;
}

2.递归实现二分查找

//递归
int BinaryChop2(int a[], int begin, int end, int find) {if (a == nullptr || begin > end) return -1;int mid = begin+(end- begin)/2;if (a[mid] == find) {cout << "找到了，返回数组下标" << endl;return mid;}else if (a[mid] < find) {begin = mid + 1;}else if (a[mid] > find) {end = mid - 1;}return BinaryChop2(a, begin, end, find);}

三.回溯法

1.回溯法解决的问题

1.求子集的问题

2.求排列的问题

3.求集合的问题

4.求棋盘的问题

2.回溯常见的写法

循环嵌套递归

3.用回溯法解决一道全排列的问题（此题的网址为https://leetcode.cn/problems/permutations/）

此题在之前的博客中具体分析过（博客的网址如下https://blog.csdn.net/m0_73483024/article/details/133589061?spm=1001.2014.3001.5502）

题目：

四.动态规划（Dynamic Programming）

1.动态规划可以解决的问题

动态规划可以用来求最优解（最大、最小、最多等）的问题

2.动态规划操作对象所要满足的性质

大问题可以拆解成解决方案完全相同的子问题，并且要满足以下两个性质

1.满足最优子结构性质（子问题的最优解构成当前问题的最优解）

2.无后效性（一旦某一状态被确定，那么过去这个状态如何求得的我们就再也不关注了）

3.动态规划的求解过程

1.拆分

2.定状态（子问题的最优解）

3.做决策

4.求状态转移方程

4.动态规划的实现手段

1.自顶向下带备忘的解法（大到小）

2.自底向上的解法（小到大）

注意：动态规划的空间消耗是用来换时间了

5.关于动态规划的问题

1.凑钱问题

题目：

有1元，3元，5元面额的钞票，想要凑到n元钱

解决方法：

创建一个f数组

f(n)表示想要凑到n元钱所需要的最小的钞票数

我们观察下面式子，找出规律

f(0)=0

f(1)=f(1-1)+1=1

f(2)=f(2-1)+1=2

f(3)=min{f(3-3)+1=1,f(3-1)+1=3}=1

f(4)=min{f(4-3)+1=2,f(4-1)+1=2}=2

f(5)=min{f(5-5)+1=1,f(5-3)+1=3,f(5-1)+1=3}=1

推导出动态转移方程得

f(i)=min{f(i-v[j])}+1(v[j]<=i)

这里v是一个存1元，3元，5元面额的钞票的数组，j是遍历v数组的变量

2.一维的动态划分问题：最长递增子序列（LIS）

题目：

有一个数组中有6、3、9、8、4、7、2、5、10、1这些元素，找到这个数组中的最长递增子序列

解决方法：

方法一

创建一个f数组

f(n)表示n下标与前序元素构成的LIS的长度

我们观察下面式子，找出规律

f(0)=1

f(1)=1

f(2)=max{9>3 f(1)+1=2

​ 9>6 f(0)+1=2

​ 1(只有自己本身，长度为1)

​ }=2

f(3)=max{8>3 f(1)+1=2

​ 8>6 f(0)+1=2

​ 1(只有自己本身，长度为1)

​ }=2

f(4)=max{4>3 f(1)+1=2

​ 1(只有自己本身，长度为1)

​ }=2

f(5)=max{7>4 f(4)+1=3

​ 7>3 f(1)+1=2

​ 7>6 f(0)+1=2

​ 1(只有自己本身，长度为1)

​ }=3

推导出动态转移方程得

f(i)=max(f(j)+1,1) (v[j]<v[i],0<=j<i)

这里v是数组，i和j是遍历v数组的变量

方法二（相较于方法一优化）

创建一个数组用来存等长LIS右边界的最小值（下标当作长度）

从左到右遍历数组，对创建的数组进行更新，最后数组的使用量就是最长递增子序列的长度

看下面进行理解

f(0)=1

f(1)=1

f(2)=2

f(3)=2

f(4)=2

f(5)=3

下面的过程就不再写了

方法三（在方法二的基础上，进行二分搜索，在进行数组的更新时使用二分搜索）

3.二维的动态规划问题：捡苹果

题目：

有一个m*n的格子，每个格子中有数量不一的苹果，一个小机器人（只能往右或者往下走）从左上角走到它不能再走了，求它最多能捡到多少个苹果

解决：

状态转移方程为 c[i] [j]=max{c[i-1] [j],c[i] [j-1]}+A[i] [j]

c数组存的是到每个位置所能捡到的最大苹果数量，A数组存的是每个位置的苹果数量

4.二维的动态规划问题且带附加条件的:最长公共子序列（LCS）

题目：

求X数组{A,B,B,D,C,B,C}与Y数组{B,C,D,B,A,C}的最长公共子序列

解决：

状态转移方程为 c[i] [j]={c[i-1] [j-1]+1 xi==yi

​ max{c[i-1] [j],c[i] [j-1]}} xi!=yi

​ }

c数组存的是x数组走到数组中的某个元素和y数组走到数组中的某个元素时，二者所构成的LCS的长度

c[i] [j]存的是x数组走到第i个元素，y数组走到第j个元素，二者所构成的LCS的长度

四.博弈树

1.博弈树（Game Tree）

棋类中用到的博弈树满足的条件

1.二者零和

2.全信息

3.非偶然

注意：博弈树要在时间消耗和结果准确度中做一个平衡

2.极大极小搜索树（是在原有博弈树的基础上实现的）

看下面这张图理解博弈树

甲是自己要选择尽量大的

乙是对手要使我们最小，所以乙选择尽量小的

3.α-β剪枝（对极大极小树的优化）

看下面图片（都是部分图，不是完整的）理解α-β剪枝

图片一

注意：这是一个深搜过程（图中数字表示处理的步骤）

当此图第4步得到的值小于第3步得到的值，那么第5步就不用处理了

图片二

注意：这是一个深搜过程（图中数字表示处理的步骤）

当此图第9步得到的值大于第7步得到的值，那么第11步和第12步就不用处理了

五.银行家算法

1.使用银行家算法要满足的条件

1.固定数量的进程共享固定数量的资源

2.进程最大请求资源数

3.单次申请的资源数不能超出可分配资源数

4.不是一次性全部申请，分批次进行

5.进程等待资源的时间是有限的（不会无休止等待）

6.当满足进程的最大资源需求，进程应该在有限时间内归还资源

2.银行家算法的操作步骤

A：总资产

B：所需的最大资源数

C：已经分配的资源数

D：仍然需要的资源数

E：每次请求的资源数

F：可分配的资源数

1.看E<=F是否满足

​ 如果不满足就等待

​ 如果满足就进行下一步

2.看E<=D是否满足

​ 如果不满足，失败

​ 如果满足就进行下一步

3.假装分配，更新各个值

​ C=C+E

​ D=D-E

​ F=F-E