有向无环图(DAG)模型是一个相当重要的模型，很多看似与DAG毫无关联的题目，其实都可以转化为DAG模型求解，因此掌握好有向无环图经典问题的动态规划思路，是深入学习动态规划必不可少的一步。本文将详细介绍DAG模型经典问题的动态规划求解思路，并通过几个例题展示如何看破问题的本质，将其转化为DAG问题求解。

介绍了LIS问题的动态规划思想，并通过二分查找将其时间复杂度优化到对数级。

文章摘要：本文介绍了二分答案算法在解决复杂问题时的应用。当直接求解困难时，可通过验证特定答案的正确性来逆向求解。以数列分段问题为例，通过二分查找确定每段和的最大值x的最小可能值。

笔试是三道算法题，时间是150分钟也就是两个半小时，分值是100、100、200，如果是目标院校的话，好像150分就过了，不是的话分数线好像会高很多。我抽到的题不难，满分通过。完整的笔试题和解析见我的博客： 华为机试（6.17笔试题解析）笔试通过后会做一套性格测试题，不要忽视这个环节，这部分是有可能挂人的。（终面的时候面试官告诉我，我的性格测试结果显示我有点焦虑，还让我说明原因）技术一面是你入职后所在的项目组的面试官来面，所以会轻松一点，像我就是全程在和面试官聊天，手撕的代码题也很简单，就不详细说了。...

本文重点介绍了并查集的实现与它的两种优化方式：路径压缩与按秩合并。

有关left join慢查询的优化

选择排序、冒泡排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、基数排序

普通队列BFS：适用于无权图；双端队列BFS：适用于边权为0或1且到每个顶点的边权都相等的带权图；优先队列BFS：适用于边权不为负且到每个顶点的边权都相等的带权图；如果图上到每个顶点的边权不等，则需使用最短路算法。

与深度优先搜索类似，我们还是以图的搜索引入广度优先搜索的定义。如下是一张无向图，现对其进行广度优先遍历：一种可能的结果是：ABFCIGEDH，与深度优先搜索不同，广搜会优先搜索该结点所有可能的分支，而深搜则是沿某一分支一直搜到底。其具体实现可以利用队列完成：这样的搜索有什么优势呢？那就是将整幅图划分出了层次，第一层：A、第二层：BF、第三层：CIGE、第四层：DH，所以广搜又可以叫做层次遍历。广搜可以用来求得图上任意两结点间的最小间距，其就等于它们分别所在的层数之差的绝对值，如B到H的最小间距为4-2=2。

图是由结点与边构成的集合(V，E)，V是所有点的集合，E是所有边的集和。图中的边是具有方向性的，只能按箭头方向从一点到另一点。我们把以这个结点为起点的有向边的数目称作该结点的出度，把以这个结点为终点的有向边的数目称作该结点的入度。图中的边无方向性，可以由任意方向从一点到另一点。我们把与该结点相连的边的数目称作该结点的度。图中的边带有权值，可以理解为从一个结点到与它相连结点的距离。............

有如下一道题：数据流中的中位数如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。数据范围：数据流中数个数满足 1≤n≤1000 ，大小满足 1≤val≤1000 。本题的意思就是给你一个不断添加新元素的序列，动态的维护这个序列的中位数。............

介绍了LCS问题的动态规划思想，并通过将其转化为LIS问题将时间复杂度优化到对数级；同时介绍了其简化问题最长公共子串的解法。

6.17号参加华为机试题的题目分享与解答，三题均通过。

我们经常会遇到求一段区间的连续和问题，直接暴力求解（从左端点一直累加到右端点）时间复杂度为o(n)，貌似也不低...但是对于有m次询问的题，时间复杂度为O(mn)就显得有点捉襟见肘了，此时一个好的想法就是使用前缀和数组。所谓前缀和数组，顾名思义就是维护段序列的前缀和的数组，其实现也相当简单：定义前缀和数组sum[N]，全部初始化为0，输入第i个数据x时，只要将sum[i]=sum[i-1]+x，就能递推得到整个前缀和数组，但要注意i要从1开始。得到了前缀和数组，我们再来看求一段区间的连续和问题，如果左端点.

介绍了最大子段和两种O(n)级别的算法：前缀和优化和动态规划，以及该问题的二维形式最大子矩阵和问题。

动态规划是运筹学的一个概念，是用来解决多阶段决策过程相关问题的一种思想，一般简称为DP（Dynamic Programming），所谓多阶段决策过程是指有一个活动的过程可以分成若干个相互联系的阶段，在它的每一阶段都需要做出决策，不同的决策将影响活动最终的结果，这个过程如下图所示，活动的初始状态为状态0，经过一次决策后转移到状态1，这是一个中间结果，经过n次决策后转移到状态n，而状态n即为活动最终的结果。与多阶段决策过程相关的问题大致有下面2种，它们是使用动态规划来解决的典型问题：最优化问题、决策方案数问题。

不定期更新一些贪心算法题。

数位DP的搜索顺序是从高位出发，然后向低位递归搜索，也就是说数位DP是先搜索000，然后是001、002······009，然后才是010~019、020~029······以此类推直到n。由于最高位是处于受限状态的（我们一般都是从高位向低位搜索，最早搜索的是最高位，而最高位一定是受限的），只能搜到它在该位上对应的数字temp[pos]=2，也就是我们在这个位置上只能搜索0~2，对于这个位置上搜到的数，都是作为最高位的，比如搜到1，那么它代表的范围就是100~199。...

我们在解决问题时经常会遇到需要不断维护一段数据内最值的情况，用更精确的话来说就是：存在集合S，里面的元素可能会随时增加、删除、修改，而我们需要做到随时返回集合内的最值，如果采用遍历的方式维护最值，则每次维护都将遍历所有数据，其效率往往十分低下。为解决这个问题，我们就引入了一个新的数据结构——二叉堆。.........

导入最短路径问题是指在一幅带权图中，找出连接两个顶点之间的所有路径中，边权和最短的那一条。如下图就是一幅带权图，边上的数字就代表该边的权值。解决最短路径问题有多种不同的算法，本文将对它们的基本思想与优化操作一一进行介绍。.........