算法必须掌握几种方法

分治

分治的策略就是大事化小,特别要注意观察找出与原问题同质的子结构。

1.归并排序

一半一半地分治,排好序的左右两半以O(n)合并到一起。

2.K-th Number

找到一个序列中第K大/小的数
从序列中选一个目标数,把序列分成比小于目标数、等于目标数和大于的三部分,此时比较三部分中数的个数可知第K个数落在哪部分。

3.整数乘法

两n位整数相乘要做n^2次一位的乘法,找一个更高效的做法
两乘数都分为左右两部,可写成(Xl+Xr)(Yl+Yr)的形式,这里面的四次乘法可以化简为三次。
4.矩阵乘法:两n*n矩阵相乘复杂度为n^3,找一个更高效的算法
类似地每个矩阵分解为[[A B][C D]]四块,易得用8个子矩阵乘积表示的结果,而经过精细复杂的代数分解,可以降到7个。

5.快速傅里叶变换

两d次多项式做乘法复杂度为d^2,找一个更高效的算法
乘积为2d次的多项式,可由2d+1个点唯一确定。如C(x) = A(x) * B(x),选好2d+1个x后,分别算出A(xi)和B(xi)对应相乘即可得到2d+1个C(xi),最后插值得到C的多项式。其中,对多项式做变形发现求得A(xi)则易知A(-xi),因此把问题规模降了一半。

贪心

这种思想特别贴合人类最朴素思维。我在往贪心上想的时候往往会问自己,如果不是机器做解题,而是人来解那会往哪个方向贪?最关注的点是什么?不过也是特别容易陷进死胡同。

1.课程规划

给一些课程,时间可能冲突,怎样尽量多上一些课

2.最小生成树

选出一些边构成树,要包含所有顶点且边的和最小
Prim:从起始点开始,从连接选中点集和剩余点集的边中选一条最短的,然后将该边对应的新点加进选中点集中,直到选中所有点。
Kruskal:对边排序,从最短的开始,只要不会使得当前选中的子图成环,那么就选择这条边,直到选中所有点。

图论

图论呢,要说它是一种算法思想,那大概是指将问题抽象为图的表示这点。在读题的时候忍不住要在纸上画一些点,以及连一些线来表示点之间的联系的,基本上可以转化为图没跑了。
而要说图论是一类问题,它涵盖面又很广,上面的最小生成树也是图论中的问题。作为一个独立的数学分支,我一个小菜鸟来看,目前接触的算法都是被前人仔细研究然后确定下来了的,也就是转化好问题之后有固定的套路可以用,不像其他算法有很大活用的空间。
最基本的遍历算法BFS、DFS我就不多说了。

基于dfs引出图的分解

1.拓扑排序

dfs访问完节点的顺序是拓扑序逆序。
也有基于入度为0的解法

2.找强连通分量

一个强连通分量内部任意两个顶点互相可达
Kosaraju:先dfs遍历,记录访问完成时间;然后按时间降序dfs遍历反向图,得到的每个联通块就是一个SCC。
Tarjan:每个SCC对应dfs中的一棵子树,回溯可达父节点说明与父节点在同一SCC。

基于bfs引出路径问题

路径问题又有很多分类,像最短/长路(下面又有细分以及各种解法)、欧拉/汉密尔顿回路等等,学得不好,就不展开了,只讲两种最基本的单源最短路算法

1.Bellman-Ford

每个点到源点的距离在bfs的过程中更新,遍历到一个点就检查是否有边能使得距离更新,即对于e(u, v),Distant[u] + w(u, v) < Distant[v]。

2.Dijkstra

每次从可达点中找一个最近的,并试着更新这个点的邻居的最短距离。

动态规划

这是一很强大的算法,适用范围广,老师也喜欢考。做的练习比较多,所以就多罗列了一些问题,力求涵盖各种题型。
动态规划是最讲套路的了,关键就是那个状态转移方程。尝试着定义子状态dp[i],赋予它一定含义,顺着题目要求看看状态如何转移。这个定义行不通就换一个,一维状态不够就加一维,题目见多了就会熟能生巧。下面对各种题型做了简单的分类,相同题型的状态转移方程有相似性。

单序列前i

1.最长递增子序列:求其长度

给每个数维护一个L值,表示到这个数为止能找到的最大长度。
优化方案是维护一个最优秀的递增子序列(最终找到的结果)新数和这一列最末的数比较

2.DAG上的最短/长路

拓扑排序然后Bellman-Ford。

单序列i到j

1.矩阵连乘

找到一个计算顺序(使用结合律)使得矩阵链乘所做乘法次数最少
最优的下一状态可以表示为一个最优分割,最外层循环是子问题规模。
优化方案是用到 记忆化搜索

双序列

1.编辑距离

允许插入、删除、替换操作,求把一个字符串变成另一个字符串的操作步数
在三种操作对应的代价中取最小作为下一状态值。

2.最长公共子序列:可不连续

dp[i][j]为两个序列前面一段的最长公共长度。

3.最长公共子串:连续

dp[i][j]表示子串必须以i、j结尾,仍然保留这条转移方程dp[i][j] = dp[i-1][j-1] + 1。

加条件

1.最短可靠路径:规定路径跳数不超过k

定义dist(v,i)为从源到v跳数i的最短路径长度。

2.01背包问题:不超过容量使总价值最大,物品只有一件选或不选

定义f[i][v]为前i件物品放进背包获得的最大值,只要放得下,第i件在前i-1的基础上要么不放,要么容量减少价值增加。

3.重复背包问题:物品可以取任意多件

f[v]表示N种物品放入一个容量为v的背包可以获得的最大价值,f[v]=max{ f[v-c[i]]+w[i] | v>=c[i], i=1, 2, …, N}。
4.二维背包问题:除了体积,选择某种物品还多了一种代价——多维背包类似
费用加了一维,只需状态也加一维即可。f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价,f[i][v][u]=max{ f[i-1][v][u], f[ i-1 ][ v-a[i] ][ u-b[i] ] + w[i] }。

5.分组背包:一组内最多选一件物品

每组物品有若干种策略:是选择本组的某一件,还是一件都不选。设f[k][v]表示前k组物品花费费用v能取得的最大权值,f[k][v]=max{ f[k-1][v], f[k-1][v-c[i]]+w[i] | 物品i属于组k}。

1.树中的最小点覆盖:覆盖是指每条边的两个顶点至少有一个被选中,要求选中点最少

用ans[i][0]表示在不选择结点i的情况下,以i为根的子树,最少需要选择的点数;ans[i][1]表示选的。选了根孩子们可选可不选——挑一种少的;不选根孩子们都要选。
可转化为最大独立集和最大团问题

其他

1.所有顶点间的最短路径

定义dist(i, j, k)为从i到j只经过1,2…k的最短路,则可以从子状态(i, j, k-1)转移过来。跑三层循环得到结果,最外层为k。
或者调用|V|次Bellman-Ford

2.带权有向图的最长简单路径:不走重复节点

ans[j][i] = max(graph[j][k] + ans[k][s])表示j经过点集i中的点一次的路径最长值,k是i中挑出的一个点,s=i-k。
有一个状态压缩的小技巧

如果大家对java架构相关感兴趣,可以关注下面公众号,会持续更新java基础面试题, netty, spring boot,spring cloud等系列文章,一系列干货随时送达, 超神之路从此展开, BTAJ不再是梦想!

《算法必须掌握几种方法》

    原文作者:fking86
    原文地址: https://blog.csdn.net/jinxinxin1314/article/details/105725143
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞