分类 算法 下的文章

递归与递推的区别

今天在学习递归和动态规划时有点迷糊了,两者无法区别,在网上差了下,总接如下: 首先要清楚,递推就是迭代。 1.递归其实就是利用系统堆栈,实现函数自身调用,或者是相互调用的过程.在通往边界的过程中,都会把单步地址保存下来,知道等出边界,再按照先进后出的进行运算,这正如我们装木桶一样,每一次都只能把东西方在最上面,而取得时候,先放进取的反而最后取出.递归的数据传送也类似.但是递归不能无限的进行下...

继续阅读 »

括号平衡检查及标记

采用链表栈实现括号匹配检测及标记,代码如下: #include "StackList.h" #include <string> #include <iostream> #include <vector> /* * 检查括号匹配,并给出不匹配的括号。 * 采用链表栈实现 * - 检查范围:...

继续阅读 »

两个水壶问题 [经典算法]

文章来源:http://liujiacai.net/blog/2014/08/16/two-pot-question/ 作者:liujiacai 问题描述是这样的: 假设有一个池塘,里面有无穷多的水。现有2个空水壶a,b,其容积分别为6升和5升。如何只用这2个水壶从池塘里取得3升的水**(最后,这三升水,在其中一个壶里)。 这个问题不难,大家自己完成可以推理出来,但是如何让计算机程序自己...

继续阅读 »

算法 - Rabin-Karp (字符串快速查找)

Go 语言的 strings 包(strings.go)中用到了 Rabin-Karp 算法。Rabin-Karp 算法是基于这样的思路:即把字符串看作是字符集长度进制的数,由数值的比较结果得出字符串的比较结果。 朴素的字符串匹配算法为什么慢?因为它太健忘了,前一次匹配的信息其实有部分可以应用到后一次匹配中去,而朴素的字符串匹配算法只是简单的把这个信息扔掉,从头再来,因此,浪费了时间。好好的...

继续阅读 »