本题要求输出全部拓扑排序的序列。 还好本题的数据量不是很大,限制在26个大写英文字母,故此可以使用递归法输出。 这个递归输出全部解在Leetcode很多这样的题目的,不小心的话,还是很难调试的。 总体考了递归和拓扑排序,还有判断是否可以拓扑排序-就是是否图有环。 考了三大知识点,难度还是有的。因为数据量不大,故此判断环可以使用一般递归方法,递归只需要注意细节就好了。 #include <stdio.h> #include <vector> #include <string.h> …

2014年7月6日 0条评论 9点热度 阅读全文

Dijsktra算法不能计算带负数路径的图 - 因为Dijsktra只更新当前最小路径的权值,并不会更新之后找到的新的最短路径值 - 当有负数的时候这种情况是会出现的,没有负数的情况下是不可能出现的。 而Bellman Ford是可以处理这种情况的。 但是注意两种算法都不肯能处理出现负权值环的问题,负权值环出现好像也没有实际意义吧?没仔细研究过,不过负权值的环会导致无限小的的值,因为可以无线走这个环换取更小的权值。 参考:http://www.geeksforgeeks.org/dynamic-programmin…

2014年6月3日 0条评论 4点热度 阅读全文

算法思路: 1 创建一个set,这个set可以使用bool数组表示,如果是真标明已经选择了这个点,否则还没选择。 2 创建一个数组保存路径,初始化为最大值,并初始化源点是0,这样确保我们第一个选择的点就是这个源点 3 循环寻找最短路径的点,设set数组这个点为真,表示已经选择,更新所有路径的最短距离值。 注意: 当源点到其他点没有路径的时候会容易出bug。 两个处理方法: 1 Geeks网站的: 没有路径的点也选择上,这样循环所有点,不过不会更新路径值,因为路径值还是最大值。 2 没有可选的路径的时候,直接brea…

2014年5月12日 0条评论 3点热度 阅读全文

Dijkstra算法-(迪杰斯特拉)算法之迭代实现 Dijkstra算法-(迪杰斯特拉)算法之优先队列实现 该算法的核心原理,很简单,如下图所示: 先说说Dijkstra算法-(迪杰斯特拉)算法之迭代实现,如下图为详细步骤, 代码如下,两种实现方法都有,用优先队列实现的算法更优秀。 package com.collonn.algorithm; import java.util.PriorityQueue; /** * 带权有向图的单源最短路径<br/> * Dijkstra算法-(迪杰斯特拉)算法<…

2014年1月11日 0条评论 1点热度 阅读全文

Climbing Stairs   You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? 简单题目,相当于fibonacci数列问题,难点就是要会思维转换,转换成为递归求解问题,多训练就可以了。 所以这种类型的题…

2013年12月21日 0条评论 1点热度 阅读全文

最少钱币数 【问题描述】 这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数,一般而言有多种方式。例如:给定了6种钱币面值为2、5、10、20、50、100,用来凑  15元,可以用5个2元、1个5元,或者3个5元,或者1个5元、1个10元,等等。显然,最少需要2个钱币才能凑成15元。 你的任务就是,给定若干个互不相同的钱币面值,编程计算,最少需要多少个钱币才能凑成某个给出的钱数。 之前使用了贪心法求解,贪心法是有一定条件才能成立的,具体什么条件,这里暂时不探讨,以后有机会我总结一下。 这个问题可以…

2013年11月21日 0条评论 1点热度 阅读全文

二分法已经非常快速了,但是还是可以改进二分法查找: 不要使用中间元素, 而是使用更为精确的区间,找到关键字在上面区间内,使其收敛更快。 使用Fibonacci序列数字来确定这个区间,就是Fibonacci Search。   二分法请参考:  http://blog.csdn.net/kenden23/article/details/16113241   下面是Wiki对Fibonacci Search的叙述: To test whether an item is in the lis…

2013年11月14日 0条评论 1点热度 阅读全文

 Knuth-Morris-Pratt 字符串查找算法(常简称为 “KMP算法”)是在一个“主文本字符串”S 内查找一个“词”W 的出现,通过观察发现,在不匹配发生的时候这个词自身包含足够的信息来确定下一个匹配将在哪里开始,以此避免对以前匹配过的字符重新检查。--Wiki定义 这个算法乍看不难,细细考虑起来,却是很难的算法,网上有很多介绍了,我在这里也不重复啰嗦,贴出参考资料,然后给出我自己的例子,程序和分析,以作为这些资料的补充资料。 他们next数组第一个值肯定是-1,我觉得这就不好看,网上的一般都是…

2013年11月13日 0条评论 3点热度 阅读全文

 Knuth-Morris-Pratt 字符串查找算法(常简称为 “KMP算法”)是在一个“主文本字符串”S 内查找一个“词”W 的出现,通过观察发现,在不匹配发生的时候这个词自身包含足够的信息来确定下一个匹配将在哪里开始,以此避免对以前匹配过的字符重新检查。--Wiki定义 这个算法乍看不难,细细考虑起来,却是很难的算法,网上有很多介绍了,我在这里也不重复啰嗦,贴出参考资料,然后给出我自己的例子,程序和分析,以作为这些资料的补充资料。 他们next数组第一个值肯定是-1,我觉得这就不好看,网上的一般都是…

2013年11月13日 0条评论 1点热度 阅读全文

之前用了个分治法用O(n)时间复杂度简洁查找diK大数的问题。可以参考下面博客: http://blog.csdn.net/kenden23/article/details/14645619 但是由于过于复杂,估计很多人都不想使用。 下面我用随机法来解决这个问题吧,据复杂的数学分析随机法的时间是少于4n的,而分治法反而是4n,所以其实随机法更加优化了,而且更加重要的是更加简单了。 我刚看到这个算法也是震惊了,只有分治法的不到三分之二的长度。细读一下你会发现真的是很好很强大! 下面看完整程序是如何的: 原创出处:靖空…

2013年11月9日 0条评论 2点热度 阅读全文