- 博客(33)
- 收藏
- 关注
RSS订阅原创 广度优先搜索BFS进阶(一)：多源BFS、优先队列BFS、双端队列BFS
普通队列BFS：适用于无权图；双端队列BFS：适用于边权为0或1且到每个顶点的边权都相等的带权图；优先队列BFS：适用于边权不为负且到每个顶点的边权都相等的带权图；如果图上到每个顶点的边权不等，则需使用最短路算法。
2023-01-08 21:47:16
1406
原创 广度优先搜索BFS基础：图与迷宫
与深度优先搜索类似，我们还是以图的搜索引入广度优先搜索的定义。如下是一张无向图，现对其进行广度优先遍历：一种可能的结果是：ABFCIGEDH，与深度优先搜索不同，广搜会优先搜索该结点所有可能的分支，而深搜则是沿某一分支一直搜到底。其具体实现可以利用队列完成：这样的搜索有什么优势呢？那就是将整幅图划分出了层次，第一层：A、第二层：BF、第三层：CIGE、第四层：DH，所以广搜又可以叫做层次遍历。广搜可以用来求得图上任意两结点间的最小间距，其就等于它们分别所在的层数之差的绝对值，如B到H的最小间距为4-2=2。
2022-09-05 23:02:41
634
原创 基本数据结构：图
图是由结点与边构成的集合(V，E)，V是所有点的集合，E是所有边的集和。图中的边是具有方向性的，只能按箭头方向从一点到另一点。我们把以这个结点为起点的有向边的数目称作该结点的出度，把以这个结点为终点的有向边的数目称作该结点的入度。图中的边无方向性，可以由任意方向从一点到另一点。我们把与该结点相连的边的数目称作该结点的度。图中的边带有权值，可以理解为从一个结点到与它相连结点的距离。............
2022-07-10 11:47:08
254
2
原创 华为od面试全流程总结
笔试是三道算法题，时间是150分钟也就是两个半小时，分值是100、100、200，如果是目标院校的话，好像150分就过了，不是的话分数线好像会高很多。我抽到的题不难，满分通过。完整的笔试题和解析见我的博客： 华为机试（6.17笔试题解析）笔试通过后会做一套性格测试题，不要忽视这个环节，这部分是有可能挂人的。（终面的时候面试官告诉我，我的性格测试结果显示我有点焦虑，还让我说明原因）技术一面是你入职后所在的项目组的面试官来面，所以会轻松一点，像我就是全程在和面试官聊天，手撕的代码题也很简单，就不详细说了。...
2022-07-06 12:38:26
28738
16
原创 最长公共子序列（LCS）问题的解决及优化、最长公共子串问题
介绍了LCS问题的动态规划思想，并通过将其转化为LIS问题将时间复杂度优化到对数级；同时介绍了其简化问题最长公共子串的解法。
2022-06-27 21:40:07
3177
原创 优先队列(堆)应用：动态维护可变序列的中位数
有如下一道题：数据流中的中位数如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。数据范围：数据流中数个数满足 1≤n≤1000 ，大小满足 1≤val≤1000 。本题的意思就是给你一个不断添加新元素的序列，动态的维护这个序列的中位数。............
2022-06-22 13:31:36
433
原创 动态规划入门(一)：从爬楼梯开始
动态规划是运筹学的一个概念，是用来解决多阶段决策过程相关问题的一种思想，一般简称为DP（Dynamic Programming），所谓多阶段决策过程是指有一个活动的过程可以分成若干个相互联系的阶段，在它的每一阶段都需要做出决策，不同的决策将影响活动最终的结果，这个过程如下图所示，活动的初始状态为状态0，经过一次决策后转移到状态1，这是一个中间结果，经过n次决策后转移到状态n，而状态n即为活动最终的结果。与多阶段决策过程相关的问题大致有下面2种，它们是使用动态规划来解决的典型问题：最优化问题、决策方案数问题。
2022-06-19 22:33:28
709
原创 最短路径问题（Floyd算法、Dijkstra算法、Bellman-Ford算法、SPFA算法）
导入最短路径问题是指在一幅带权图中，找出连接两个顶点之间的所有路径中，边权和最短的那一条。如下图就是一幅带权图，边上的数字就代表该边的权值。解决最短路径问题有多种不同的算法，本文将对它们的基本思想与优化操作一一进行介绍。.........
2021-12-11 15:53:55
4042
原创 KMP算法
导入使用朴素算法解决字符串问题时，是从主串第一次与模式串开始匹配的位置逐一验证是否能够匹配，如果不匹配，则继续向后搜寻开始匹配的位置，再次验证，依次重复直到扫描完整个主串。然而，该种匹配模式存在最坏情况，例如：主串aaaaaaab与模式串aaaaab，设主串的长度为n，模式串的长度为m，则此时的时间复杂度达到了O（nm），显然是不能处理大部分的字符串匹配问题的。为解决此问题，我们将学习一种能在线性的时间内完成对字符串的匹配的算法——KMP。KMP算法的思想思考如下问题：是否在每次字符串匹配失配的
2021-12-01 01:04:35
286
原创 二分查找给定值、不大于给定值的最大数、不小于给定值的最小数
二分查找给定值，二分查找不大于(<=)给定值的最大数，二分查找不小于(>=)给定值的最小数
2021-11-23 04:25:16
1308
原创 RMQ问题：高效离线算法——ST
ST算法的实现ST算法是一种解决静态询问区间最值问题的高效离线算法，算法上采用了倍增的思想，而实现上则是利用了动态规划，具体流程如下所示：对于区间[begin , end]，将其拆分为两个区间：[begin , begin+]、[end-, end]，，每个区间的长度为。然后继续拆分这两个区间，此时区间的长度为，此后每次拆分都将区间缩短一半(x-1)，不断拆分直到区间长度为1（即x=0）...
2020-03-10 11:25:57
239
原创 基本数据结构：二叉堆（堆排序）
我们在解决问题时经常会遇到需要不断维护一段数据内最值的情况，用更精确的话来说就是：存在集合S，里面的元素可能会随时增加、删除、修改，而我们需要做到随时返回集合内的最值，如果采用遍历的方式维护最值，则每次维护都将遍历所有数据，其效率往往十分低下。为解决这个问题，我们就引入了一个新的数据结构——二叉堆。.........
2020-03-07 18:16:03
483
原创 根号算法：莫队算法
导入 莫队算法，也算是一个黑科技算法，能切掉好多区间题啊，和分块一样属于一个ACMer/IOer必备的算法，而由于莫队算法里面用到了一点点分块的内容，所以先弄懂分块还是有必要的。同时由于和分块扯上了关系，那么它的时间复杂度也就自然而然地是根号级别的了，能解决的数据规模还是挺大的。ok，那么莫队算法到底是什么呢，下面就来介绍这个黑科技算法。 普通莫队 先来直接看看莫队的思想：莫队算...
2019-12-03 09:13:15
1408
原创 根号算法：分块
导入 众所周知，我们熟悉的算法时间复杂度有常数级，对数级、线性级、次方级、指数级等等，其中为应对题目规模对时间复杂度的要求，我们一般要将算法的时间复杂度优化到对数级，但是实际上我们还有一种优化方法——根号算法，它的时间复杂度为级，同样可以应对大部分的题目规模，并且具有相当大的可拓展性。和对数算法基本对应分治类似，根号算法也对应着一种操作，就是本篇博客要介绍的分块。 什么是分块？ ...
2019-11-09 02:23:43
917
原创 高级数据结构：树状数组（区间修改、逆序对问题）
我们经常会遇到求一段区间的连续和问题，直接暴力求解（从左端点一直累加到右端点）时间复杂度为o(n)，貌似也不低...但是对于有m次询问的题，时间复杂度为O(mn)就显得有点捉襟见肘了，此时一个好的想法就是使用前缀和数组。所谓前缀和数组，顾名思义就是维护段序列的前缀和的数组，其实现也相当简单：定义前缀和数组sum[N]，全部初始化为0，输入第i个数据x时，只要将sum[i]=sum[i-1]+x，就能递推得到整个前缀和数组，但要注意i要从1开始。得到了前缀和数组，我们再来看求一段区间的连续和问题，如果左端点.
2019-09-25 22:13:30
1061
原创 巧解回文串：Manacher算法
我们正式开始进行Manacher操作，其实质是要实现在线性时间内计算出所有的R[i]。Manacher算法优化时间的操作主要在于充分利用了回文串的对称性，一个回文串关于中心点是完全对称的，也就是说一个位置与它关于中心点的对称位置，它们附近的字符是一样的，这样当我们确定了一个回文串中的前几个位置，同时就能确定它们关于中心点对称的位置，同样要计算R[i]，也可以根据其关于中心点的对称位置j的R[j]来确定
2019-09-22 11:34:53
218
原创 浅析数位DP
数位DP的搜索顺序是从高位出发，然后向低位递归搜索，也就是说数位DP是先搜索000，然后是001、002······009，然后才是010~019、020~029······以此类推直到n。由于最高位是处于受限状态的（我们一般都是从高位向低位搜索，最早搜索的是最高位，而最高位一定是受限的），只能搜到它在该位上对应的数字temp[pos]=2，也就是我们在这个位置上只能搜索0~2，对于这个位置上搜到的数，都是作为最高位的，比如搜到1，那么它代表的范围就是100~199。...
2019-08-04 00:56:20
247
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人