Programming 归档

「编程笔记」ST表的实现与使用

ST表，全称SparseTable，也叫做稀疏表。是用来解决区间和和区间最大最小值问题的一种工具。其实推广开来，其可以用来解决任何可重复贡献（associative）问题。使用条件可重复贡献问题 ST表要求其处理的问题必须具有“可重复贡献”这一特征。具体是什么意思呢？假设有操作F，使得F(a, b, c) == F(F(a, b), c) == F(a, F(b, c))，则称F符合可重复贡献问题的特征。如图，不难发现max()最大值函数就符合可重复贡献问题的特征；读者可以自行验证，sum()，min()等函数都符合这个特征，这也证明了ST表可以解决最大最小值以及区间和等问题。元数据可不能改变噢在使用ST表解决问题时，我们必须确保所有的查询结束前，ST表所对应的元数据都不改变。有些数据结构（比如线段树）在元数据更新之后（比如原来的数组中，某个数值由3变成了5），可以有对应的事件复杂度比较低的方法对结构进行更新，以达到一边更新一边查询的效果。ST表则无法提供类似的方法，所以确保你的问题中没有要求在查询期间动态调整元数据的要求。 SparseTable意义与使用接下来，我们采用由表及里的过程，先了解ST表的意义以及使用方法，之后再来说明如何生成ST表。一些准备——向下取整的Log2函数由于SparseTable的特性，无论是根据数据生成ST表，还是得到ST表后对数据进行查询，都会比较频繁的用到向下取整的log2函数，所以特地说明。我们对于向下取整的log2运算稍加分析，可以得到log2(x)向下取整的具体意义是：对于某一个数N，返回可能的最大的数字n，使得2的n次方小于等于N，且2的n+1次方必定大于N。比如对于7，log2(7)向下取整为2，2的2次方不超过7，但可以保证2的3次方一定大于7（8>7）。了解了这个之后，让我们来看看SparseTable如何快速解决规模庞大的可重复贡献问题吧~ ST表中数据的意义我们接下来选择一个经典的可重复贡献问题——区间最大值问题，作为示例。假设我们有一个数组 {3, 2, 1, 4, 5, 9, 7}, 其数据元素个数为7，要求必须在非常低的事件复杂度内，查询某个特定区间（比如从下标0到下标5）的最大值。此时，如果直接循环求解，会导致复杂度随着查询区间长度不断增高，这就是ST表登场的时候啦。如上图，对数组进行处理之后，就可以得到下方的二维数组，也就是我们大名鼎鼎的SparseTable——ST表。那么问题来了，图中ST表中的数据，到底具有什么含义呢？首先需要知道的是，ST表正常情况下使用一个二维数组st[idx][pow]来储存。下面对这个二维数组每一个位置元素的意义做出解释：数组中，每一个特定位置(idx, pow)的值，都代表对应问题在某个区间的解。这个区间的开始坐标为idx。这个区间的长度为2的pow次方。例如，对于区间最大值问题，假设原数组为arr，处理后得到的ST表中，st[1][2] = 5，则说明：原数组，从下标为1开始，长度为2^2=4的区间内，最大值是5。特定区间的查询知道了ST表的数据的意义，我们就可以着手解决特定区间查询问题。这里需要注意的是，虽然ST表可以解决不同的可重复贡献问题，但是其在面对不同的可重复贡献问题时，最优查询方式可能有一定的区别。接下来，我们先通过上方的“区间最大值”例子，介绍一下区间最值问题的ST表查询。合适的长度首先，为了降低时间复杂度，我们希望用尽可能少的区间查询来拼凑出完整答案。可以证明，在ST表处理区间最值问题时，无论区间长度位置，我们都可以用ST表支持的两个区间，拼接出答案。比如对于区间(1, 6)，可以由区间(1, 4)和区间(3, 6)区间的结果再求最值得到。对于“最值”问题，我们只需要保证选择的区间完整覆盖住所求区间，且不超过所求区间即可，而这多个区间允许有重复部分。同时，为了保证所用区间尽可能少，每个区间就要尽可能大。这个时候，上方说到的log2向下取整计算就派上用场了。由于ST表代表的区间长度只能是2的n次方倍，所以，不超过区间范围的区间，其最长长度就是log(区间长度)向下取整。Continue reading “「编程笔记」ST表的实现与使用”

「编程笔记」关于Bellman Ford单源最短路算法

开始之前本Blog之前已经介绍过一种单源最短路算法——Dijkstra算法。但Dijkstra算法也有着自己的缺点，其中最明显的问题就是无法处理带负权边的图，其原因与其算法中包含的贪心原理有关。而接下来介绍的算法，则拥有处理负权边的能力，该算法就是Bellman Ford单源最短路算法。该算法的核心思想是，对图中的每条边，都进行足够次数的Relaxation（松弛）操作，从而逐步推导出每个点距离出发点都最短路径长度。关于Bellman Ford算法的原理和代码实现，网络中已有大量优秀的资料，这里便不再说明算法本身的详细工作流程。接下来着重说明一些Bellman Ford算法中一些限制条件，及其相关的一些理解。 Bellman Ford算法特性当出现负权回路时… 在通过Bellman Ford算法计算单源最短路时，会要求所计算的图中不得存在权值为负值的回路。这个限制相对较好理解，下面举一个简单的例子。如图，图中的A->B->C->A便是一个负权回路。而假设我们现在需要以A点作为出发点计算最短距离，请问A->D的最短距离应该是多少？不难发现这里出现了死循环。我们可以从原点出发，不停的走A->B->C->A这条路，每循环一次，我们距离出发点的距离就会越来越小。这也就意味着，只要我们的路径不断的在负权回路中重复足够多次，每一个点距离出发点的距离都可以认为是无穷小，这显然是不合理的。负权回路对于图来说是存在特殊意义的，比如在经济学的部分领域中，“负权回路”是一个非常具有吸引力的词，因为可能代表着可持续的收益链，也可以代表着套利的机会，但Bellman Ford不认这些，在单元最短路算法的世界中，我们暂且不接受“套利机会”的存在。也就是说我们不允许待处理的图中出现负权回路，以此来保证计算结果是有意义的。对于Bellman Ford算法的一些理解迭代次数的理解 Bellman Ford算法的核心思想，在于每迭代一次，就对所有边进行遍历，并执行Relaxation操作。这里不难发现，迭代k次时，得到的结果，可以保证至少是路径条数为k时的最优解。为什么说是至少呢，因为其遍历的结果可能跟边遍历的顺序有关，如下图：如图，我们发现对于图中的无向图，如果从左边的边开始遍历，实际上遍历一次之后我们就已经得到了最优解。而如果从右边开始遍历，我们就需要遍历3次才能得到最优解。按照这个思路理解，不难推出，遍历k次时，得到的答案，只能保证，至少是路径条数为k限制下的最优解。这里对路径条数做出说明，一个路径由多个边组成，上方所说的“路径条数”，指的是对于某条路径，其经过的边的个数的和。为什么迭代次数等于点的个数？上方我们已经论述了迭代次数k的意义，迭代k次时，得到的结果至少是路径条数k情况下的最优解，部分点的数据可能比会更优，但对于所有的点，只能保证其为路径条数k情况下的最优解。那么我们到底需要迭代几次呢？根据定义，我们将问题转换成为：对于一个无向图，其某个点A到某个点B的全局最优路径中，最多可能经过几条边。经过思考之后发现，最坏情况下，最优路径将会不重复的经过所有点。接下来对这个结论进行简单的说明：首先是经过所有点。如果我们想要强迫最优路径经过尽可能多的点，最坏的情况之一，便是这个图形成了一个没有分叉的纯线性结构（就像上方对于迭代次数解释时所用图一样，每两个点用一条边链接，总边数为点数-1），这样从最左边到最右边的点，最优路径边毋庸置疑是经过所有的点。其次是不重复。为什么我们可以确保最优路径中不会重复经过同一个点呢？这从某个角度上来说得益于算法前面的一个前提条件——不允许负权回路。想象一下，如果路径重复经过了同一个点，说明这个路径必定存在一段回路（从重复点出发，经过某个路径，又回到重复点）。而此时如果这个回路确定不是负权回路，那么说明如果跳过这段回路，我们可以得到一个权重更短的路径，反向说明了目前的路径不是最优路径。因而可以确定，如果一个路径被确定为最优路径，且该图中没有负权回路，那么这个路径绝对不会重复经过同一个点。说明完毕，接下来让我们看看这两个结论，不难发现，不重复经过所有点，那么对于一个点个数为N的图，符合条件的路径，最长只能是N-1（因为一旦大于N-1，说明必定要产生回路，与条件冲突），所以最终确定，如果需要得到全局最优，其最少迭代次数为N-1。综上所述，容易得到，算法的时间复杂度为O(N*M)。其中，N为点的个数，M为边的个数。为什么它能攻克负权边？在Dijkstra算法的文章中，笔者提到了一个观点，Dijkstra的核心是基于贪心的，而贪心带来了局部最优解这一隐患。带着这个角度再来看Bellman Ford算法，是否有一种熟悉的感觉？Bellman Ford算法的每次迭代都基于上一次的迭代结果。先知道路径条数1情况下的最优解，再根据此状态推出条数2情况下的解，以此类推最终得到路径条数为N-1时的最优解（也就是全局最优解），是不是有点「动态规划」的味道了呢？正是借助这这种工作模式，不像Dijkstra算法一样看到一点点甜头就着急的把点Close掉，Bellman Ford拥有了不被眼前甜美假象迷惑的能力，坚持着自己的本分，不断想着正确的道路一步步迈进，最终终于得到了令人满意的结果。相关链接 GeeksForGeeks Bellman Ford算法介绍（英文）「编程笔记」Dijkstra算法为什么无法处理带有负权边的图

「编程笔记」Dijkstra算法为什么无法处理带有负权边的图

前言 Dijkstra算法是一种可以计算有向或无向图中单源最短路的算法。其工作模式与图的BFS（广度优先遍历）有些相似，通过类似于广度遍历的方式，逐渐从某个设定好的起点向外推进，一步步的计算出所有点到该点的距离。本文不过多介绍Dijkstra单源最短路算法本身，如果仍然没有掌握该算法，可以先自行了解该算法的工作模式。下面提供一些可供参考的资料：知乎：通俗易懂理解——dijkstra算法求最短路径负权边对于Dijkstra算法的影响 Dijkstra算法工作模式要了解该影响，首先需要明确Dijkstra算法的工作模式。其维护两个点集合。一个是“仍未确定最优解的点（S）”，一个是“已经确定最优解的点（U）”。且有一个重点：在算法工作期间内，如果某点被认为已经得到最优解，则该点会被从S移动到U，可以认为，从此以后该点已经被Closed（关闭），即解已经确定，且不容被更改。为了方便，我们称在S中的点为opening vertex，U中的点为closed vertex 当图中出现负权边… 了解这一点后，让我们来看看下面这个图片示例，看看当负权边出现在图中时，可能会对算法造成什么影响：如上图，假设我们尝试使用Dijkstra算法，计算该图中各个点距离C点的距离。图中，绿色的点为closed vertex，白色的点为opening vertex，点上方的方框代表该点的，实时更新的计算距离。 1：算法首先锁定C点，将C点到C点的距离标记为0，并认定为最优解，然后根据C点尝试更新与其相连的opening vertex的距离（这里为A，B点，得到更新后距离是为1和5）。 2：剩余的opening vertex中，A距离出发点（C点）最小，距离为1，故锁定A点，（注意：锁定A点说明算法认为A点的最优解就是1，且之后算法也不可能再次更新A点的距离值，因为A点已经为Closed状态了），同时，锁定A点之后，再次更新与A点相连的opening vertex的值（与A点相连的点有B和C，但因为C点为closed vertex，故仅仅尝试更新B点的值），计算得到B点最新距离为min(5, 1+(-10)) = -9 3：最后，锁定B点，算法计算完成。上方便是Dijkstra算法在示例图中的运行步骤和结果。不难发现，算法对于A点的最短距离出现了计算失误：实际上，A点的最短距离走法并不是C->A (1)，而是C->B->A (-5)。怎会如此？分析之后可以发现，Dijkstra算法的核心，就在于每次都选择S集合中距离最小的点，并将其锁定，再通过这个点进一步更新其他点的距离。但为什么Dijkstra认为S集合中目前距离最小的点就是最优解呢？有没有可能从其他的点出发可以得到更小的距离呢？比如在上述的示例图中，锁定C点后，算法认为A点的距离是1，B点的距离是5，所以A点的距离为1一定是最优解。那么有没有可能实际上1并不是C到A的最优解，我们通过B点走其他的路径最终可以得到更小的解呢？答案是，当边的权值非负时，不可能，当边的权值存在负值时，则有可能。当权值非负时，B点已经离出发点有5点的距离，所以所有从出发点出发经B点的路径，其长度必定大于等于5，但是当权值存在负数的时候，这一点就无法确定，经过B点的路径如果后续经过负权边，其路径长度总和也有可能再次小于5，此时，我们就无法确定C->A的1距离一定是最优解了，因为我完全有可能经由B路径得到一条总距离小于1的路径到达A。上方的论证可能并不全面和严谨，不能作为Dijkstra算法相关特性的严格证明，但对我们进一步理解Dijkstra算法有着一些帮助。一些有趣的说法不难发现，实际上Dijkstra算法的设计和「贪心」有着很大的联系，实际上在S集合中选点就是一种贪心的行为。而我们都知道贪心算法的局限性，就是在部分情况下，其可能陷入局部最优解。而我们可以认为，当Dijkstra遇上负权边，就导致了其中贪心部分陷入了局部最优解（只考虑眼前的最短边（比如在5和10两条边中毫不犹豫的选择5），而忽略了目前看似落后的边未来的长期收益（比如那条权值为10的边链接的点，接下来将经过一条绝对值非常大的负权边-10000之类的），这也警示我们不要贪图眼前的小利，眼光应当长远（雾如果我就是想拿下负权边呢？噢亲爱的读者，相信我，不止你一个人有这种想法；实际上上百年前就已经有两名小伙想要拿下他，他们的名字分别是Richard Bellman 和Lester Ford Jr，接下来，就是Bellman Ford算法的表演时间了。如果你对与这个Bellman Ford算法感兴趣，可以在互联网上找到很多关于这个算法的优质教程，其通过一次次迭代，对边进行Relaxation操作，实现了对于单源最短路径的求解，在本Blog的另外一篇文章「编程笔记」关于Bellman Ford单源最短路算法中，也对这个算法做出了一些讨论，希望能对您产生一些帮助和启发。

「编程笔记」Flutter中局部Provider的跨Page传递

开发过Flutter项目的同学应该对于Provider不陌生，Provider是Flutter中的一个状态管理包之一，也是Flutter官方推荐的状态管理Flutter实现。Provider通过Flutter的InheritWidget实现了状态的寄存和管理，使得子Widget可以访问和修改父Widget的数据，同时父Widgets的数据被修改后，支持自动按需重构Widgets，这里不对Provider做过多介绍。一般情况下，我们创建的Provider会置于Flutter App的最根部，也就是MaterialApp或者CupertinoApp组件上，这种情况下，无需额外的操作，就可以在应用中的任何未知，通过Consumer<T>来访问和修改Provider<T>中的数据。但部分情况下，我们不想让Provider置于项目的最根部，详情可以查看这个StackOverFlow Question，比如一个局部的List，仅仅在项目的某一个子Widgets树部分会被访问，所以理论上，我们将Provider尽可能的放到Widgets树的更低位置是一个更优的选择。比如Page1中创建Provider，同时Page1以及其下的Page2和Page3可以访问到这个Provider，但是在Page1之上的Widgets无需也不能访问到这个Provider。理论上这是可行的，根据理论我们只需要保证Provider是Consumer的祖先即可。但这里出现了一个问题，也就是如果我们尝试在Provider生效的范围内使用Navigator.push()导航到另一个页面，我们便无法正常的在被push的页面访问到Provider。如上图，我们如果直接使用Navigator.push()，那么被Push的页面（途中是SecondPage）便无法访问到之前在FirstPage创建的数据。下面介绍一种解决办法，我们可以在Navigator.push的时候，在push的PageRoute外嵌套一层Provider.value()，如下图可以看下面的代码帮助理解：可以看出，我们通过在PageRoute外层加入一个ChangeNotifierProvider.value()实现了传递Provider的效果。注意，这里使用Provider.value()而不是Provider()，因为我们的Provider实际上不是“新建”，而是“传递”，这说明我们实际上不能新建一个DAOrgInfoProvider class的实例，而是复用之前的Provider创建时使用的实例，在这里则是orgProvider。那么如何获取之前Provider创建时的实例呢，一个比较傻但是直观的方法就是在Navigator外再次嵌套一个Consumer来获取数据，代码如下以上就介绍完了如何通过Navigator传值的方法

「编程笔记」Dart中重新加载FutureBuilder的一种方法

在实战过程中，我们常常遇到需要刷新界面的需求，比如搜索时出现了网络错误，我们为用户提供一个Retry按钮，用户点击后，我们希望整个FutureBuilder重新加载一下，比如下图：本页面通过一个FutureBuilder加载搜索结果，同时遇到网络错误时显示以上界面，代码的大致结构如下：这时，假设我们的NetworkErrorPage的位置需要添加一个按钮，实现FutureBuilder重新刷新，一种简单的方法是直接调用该FutureBuilder所在界面的setState()方法，每当FutureBuilder的父Widget的setState()方法被调用，都会使得FutureBuilder重新获取异步数据，代码大致如下：但如果我们按照上述结构实现刷新的工作，我们会发现，虽然在我们点击按钮之后，刷新的工作有在进行，但是页面并不会在点击Try Again按钮后重新回到LoadingPage界面，而是等到加载好之后直接更新界面为showDataPage或者Error的相关界面，这是因为snapshot的hasData和hasError变量仅仅在每次future任务完成后才会刷新。如果我们想实现点击Try Again按钮之后实时回到LoadingPage界面的话，可以使用snapshot.connectionState进行判断，具体代码如下：通过以上方法，即可实现点击按钮后立即回到加载界面，直到下一次加载完成之后再次更新界面的效果。

「编程笔记」关于Dart类构造函数

构造函数的形式无参数构造函数在Dart中，每一个类（Class）都有一个不包含任何参数的默认构造函数，当你调用[ClassName]()时，就会调用默认的构造函数。Dart会为每个类自动添加默认的构造函数，但你也可以显式的声明你的构造函数，例子如下上面的构造函数被调用时，会更新实例的成员变量。同时注意到在声明成员变量name的时候，我们使用了?符号，代表name的值是允许为空的，如果删除?符号，本段代码将会报错，编译器会提示你没有在类初始化的时候为name这个成员变量赋值，报错提示如下：其中一个解决办法是，在声明成员变量name的时候使用late关键字：late String name; 这么做相当于你告诉编译器，我现在暂时可能没有对name变量进行赋值，但是我确定在将来我要使用它之前，肯定会给他赋值，只不过不是现在。这样，编译器就不会强制要求你在构造时立即初始化这个变量。但这时可能有同学会问：“我明明在A的构造函数中已经为成员变量A赋值了classA，为什么说我没有为name赋值？”，这里需要注意的是，如果我们想要让Dart编译器知道我们已经在构造函数中初始化了某个成员变量，就需要另一种写法。带参数构造函数当然，上面代码中的构造函数已经不属于无参数构造函数了，其构造参数中包含一个位置变量。当然，你也可以为其添加命名变量。有两点需要提及一下，Dart允许类的构造函数中，快速的对成员变量进行赋值，要做到这一点，只需要使用this关键字即可，比如上方代码中的构造函数A(this.name)就代表传入的第一个位置参数赋值给name这个成员函数。同样的，您也可以在命名参数中使用this，比如A({this.name}); 这种情况下，调用构造函数的格式变为 A(name: ‘YOUR_NAME_HERE’) 命名构造函数我们可以发现，上方提到的两种构造函数中，构造函数都是直接使用类的名称，比如类的名称是Book，那么构造函数的名称也是Book，这在Dart中属于 unnamed constructor（未命名构造函数），这种构造函数可以直接用类名调用，比较方便，但是一个类只能有一个未命名的构造函数，这里涉及到Dart语言的设计，Dart语言的设计已经决定了Dart不支持方法/函数重载，也就是说两个名称相同但是输入的参数列表不同的函数不允许同时出现。因此，构造函数显然也不能通过不同类型的输入重载，您可以阅读关于Dart不支持方法重载的相关文章，加深理解。这里就需要介绍Dart的命名构造函数了。就如其名字一样，命名构造函数允许你设定这个构造函数的名字，进而可以实现多个不同的构造函数，代码如下注意，子类不会继承父类的命名构造函数，如果您想要子类在初始化的时候调用父类的命名构造函数，则需要手动进行调用super.[yourNamedConstructor]() 工厂构造函数在实际开发过程中，有时我们希望一个类的构造函数并不是每次都返回一个新构造的示例，比如，有时我们希望从内存中读取已有的示例，或者是我们想返回该类的某个子类示例，此时可以运用factory关键字实现工厂构造函数，工厂构造函数可以返回此类或者此类的子类的示例。值得注意的是，工厂构造函数不得访问this，也就是说工厂函数不能直接访问成员变量。如果你想在工厂构造函数中返回本类实例，可以先在工厂构造函数中构建实例，然后返回你新构建的实例。其实在这里，目前我自己也存在着一定的疑问，比如，虽然factory构造函数可以返回内存中的实例或者是子类的实例，但是，实际操作过程中，即使返回的是子类实例，我们也无法直接访问子类实例的变量和函数，而还是只能访问父类的变量和函数。比如上述代码，即使我们可以发现最终person变量的runtimeType是Female，但是当我们尝试添加print(person.beautyIndex);这行代码的时候，编译器会报错，提示person实例没有beautyIndex成员变量。直观上来说，大概是编译器因为Person.fromSex()方法返回的是Person类的变量，所以后续的类型推断和错误检查都会以Person类为基础。这么做也有道理，因为Person.fromSex()有可能返回的是Person类自己的实例。有没有什么办法，既可以实现动态的返回子类型，同时又可以允许我们自由的读取子类型的变量呢？以下抛砖引玉的提供两个方法，第一个，也是最直接的方法，是在父类中增加子类所用到的成员变量，同时将其标记为可空，例如，上述代码中，可以在Person类中添加一行int? beautyIndex; 然后子类重载这个变量即可。这种方法显然不是很好，当子类越来越多，我们需要添加到父类的变量也就越来越多，这就意味着每次功能更新都需要修改父类。这不符合对修改关闭原则。另一种方法是进行类型检查(typecheck)和类型转换(type cast)，也就是如果我们确定了工厂构造函数返回了某个子类的示例，我们可以将这个实例进行特定的类型转换，将其转换到某个子类。 factory实现单例模式工厂构造函数除了上面的用法，还可以用于实现单例模式，代码如下通过以上特点，你可以通过class实现类似于但更方便于enum的效果，代码如下：上述代码通过首先通过static和final关键字，创建了不同的AppleDevice实例来当作不同的枚举类型使用，又通过factory函数，实现了根据不同的数据判断出需要的不同的“枚举类型”（实际上是一个AppleDevice实例）。这种方法不但实现了枚举的基本功能，后期还可以根据自己的需要不断的为其添加功能，扩展新好于Dart中的基本枚举类型。值得一提的是，Dart2.7更新之后，已经支持使用extensions on关键字对于枚举类型的功能扩展，您可以阅读Dart枚举类型扩展的相关的文章，了解extenstions的用法。但是毋庸置疑的是，当你需要一个多功能的枚举类的时候，使用class实现应该能更好的满足你。 Dart类成员的初始化在Dart中，类成员的初始化一共有4种方法，分别是：需要注意，最后一种方法只适用于非final类成员。类的声明定义中初始化你可以在编写Dart类的时候直接指定某个变量的值，代码如下： class A{ int a = 10;} Dart构造函数的快捷用法初始化列表除了使用this关键字以外，Dart还允许您使用初始化列表对成员变量进行初始化，代码如下指定父类构造函数默认情况下，在子类的构造函数没有指定调用之前，子类会调用父类的默认未命名构造函数，如果你想让子类指定使用父类的某个构造函数，并且需要传递参数，则可以在序列化列表之后选择特定的父类构造函数，代码如下：如上，我们不但使用了上方所讲的初始化列表的语法，同时还添加了super.fromData(…) 这一行，而这一行的实际作用便是让B中的构造函数指定使用其父类（也就是A类）的fromData构造函数