清泉逐流

做着努力,等待幸福到来
» 日志

如果你不懂算法

时间 : 2014-04-20 11:14 标签 : 算法  

判断链表是否有环?

使用两个指针,从头开始,一个一次前进一个节点,一个前进2个节点,则最多2N,后两个指针可以重合;如果无环,则正常停止。

设计一个复杂度为n的算法找到链表倒数第m个元素,最后一个元素假定是倒数第0个。

双指针查找

用最简单的方法判断一个LONG整形的数A是2^n

查看全文 »

字串搜索核对算法

时间 : 2012-10-25 23:42 标签 : 算法  

  说明今日的一些高阶程式语言对于字串的处理支援越来越强大(例如Java、Perl等),不过字串搜寻本身仍是个值得探讨的课题,在这边以Boyer- Moore法来说明如何进行字串说明,这个方法快且原理简洁易懂。

  解法字串搜寻本身不难,使用暴力法也可以求解,但如何快速搜寻字串就不简单了,传统的字串搜寻是从关键字与字串的开头开始比对,例如Knuth-Morris-Pratt 演算法字串搜寻,这个方法也不错,不过要花时间在公式计算上;Boyer-Moore字串核对改由关键字的后面开始核对字串,并制作前进表,如果比对不符合则依前进表中的值前进至下一个核对处,假设是p好了,然后比对字串中p-n+1至p的值是否与关键字相同。

  如果关键字中有重复出现的字元,则前进值就会有两个以上的值,此时则取前进值较小的值,如此就不会跳过可能的位置,例如texture这个关键字,t的前进值应该取后面的3而不是取前面的7。

#include <stdio.h> #include <stdlib.h> #include <string.h> void t

查看全文 »

ArrayList与LinkedList比较

时间 : 2011-11-16 21:28 标签 : 算法  链表  

  ArrayList底层采用数组完成,而LinkedList则是以一般的双向链表完成,其内每个对象除了数据本身外,还有两个引用,分别指向前一个元素和后一个元素。

  如果我们经常在List的开始出增加元素,或者在List中进行插入和删除操作,我们应该使用LinkedList,否则,使用ArrayList将更加快速。

查看全文 »

使用LinkedList实现队列和栈

时间 : 2011-11-16 21:26 标签 : 算法  

  //Java中栈的实现

  class MyStack

  {

      private LinkedList ll=new LinkedList();

      pulbic void push(Object o)

      {

          ll.addFirst(o);

      }

      public Object pop()

      {

  &

查看全文 »
» 日志标签