Dive Into Haskell(3) 函数

 PUBLISHED ON February 20, 2015

在Haskell中,一切皆函数。

定义一个函数

haskell中,可以通过如下方式定义一个简单的函数:

doubleMe x = x + x

这样的做法其实是实现了一个绑定(binding)。更广泛的函数定义的方法:

func1 :: Int -> String
{- function body. -}

func2 :: Int->Int -> String
{- function body. -}

func3 :: (Integral a) => a -> String

{- function body. -}

func4 :: (Integral a) => a->a -> String
{- function body. -}


Javascript 变量作用域与闭包

 PUBLISHED ON February 18, 2015

Javascript 中的变量

Javascript 中的变量可分为全局变量和局部变量两种。

Javascript 中使用 var 语句声明变量。例如:

var x = 10;
var y = ["a", 20, true]

变量相等性比较

Javascript 中,比较两个变量是否想等是,必须注意 ===== 之间的区别。

==只比较变量的值,而 ===既比较变量的值,又比较变量的类型。如下例:


字符串的编辑距离

 PUBLISHED ON February 17, 2015

问题描述

对于存在差异的字符串,我们可以通过如下三种方式使它们变得相同:

  1. 修改一个字符;
  2. 增加一个字符;
  3. 删除一个字符。

能够通过如上三种变换使得两个字符串相同的最小操作数记为两个字符串的编辑距离。

两个字符串的相似度定义为 编辑距离+1 的倒数。

分析


Linux 文件解压及压缩命令

 PUBLISHED ON February 17, 2015

Linux下,通常需要用tar命令进行解压和压缩操作,针对不同的压缩文件格式,tar命令的参数也不相同。

tar 命令的常用参数含义:

Main operation mode:

 -A, --catenate, --concatenate   append tar files to an archive
 -c, --create               create a new archive
 -d, --diff, --compare      find differences between archive and file system
     --delete               delete from the archive (not on mag tapes!)
 -r, --append               append files to the end of an archive
 -t, --list                 list the contents of an archive
     --test-label           test the archive volume label and exit
 -u, --update               only append files newer than copy in archive
 -x, --extract, --get       extract files from an archive

常见压缩文件格式解压参数

  1. .tar.Z 格式

    解压: tar Zxvf FileName.tar.Z
    压缩: tar Zcvf FileName.tar.Z
    
  2. .zip 格式


KMP算法

 PUBLISHED ON February 17, 2015

一、概述

KMP算法(Knuth–Morris–Pratt algorithm)是一种快速模式串匹配算法,其核心是next数组的求解和使用。时间复杂度O(mn),与BF等需要回溯的算法相比,KMP算法具有极高的性能。

二、next数组的求解

next数组的含义是:next[i]为i之前的字符串的前缀和后缀的共有元素的最长长度。具体计算可以有递推式产生。若pattern[i] == pattern[j],则pattern[i+1] = pattern[j+1],否则,依次使j = next[j],向前寻找匹配位置。具体实现代码如下:


星期的计算

 PUBLISHED ON February 16, 2015

经常需要通过日期来计算对应的星期,相关的方法主要有蔡勒公式和基姆拉尔森公式。

蔡勒公式

蔡勒(Zeller)公式

$$ w = (y+\lfloor{y/4}\rfloor+\lfloor{c/4}\rfloor-2c+\lfloor{26(m+1)/10}\rfloor+d-1)\ mod\ 7 $$

参数含义解释

蔡勒公式中个参数的含义如下:

  • y: 年份的后两位数;
  • c: 年份的前两位数;
  • m: 月份;注意:月份的值在3-14之间,1月和2月应当作为上一年的13、14月来考虑。
  • d: 日。


Boyer-Moore 算法

 PUBLISHED ON February 14, 2015

Boyer-Moore 算法由 Robort S.Boyer 和 J Strother Moore 在1977年提出,可以在O(1)的时间复杂度内完成字符串的匹配,其在绝大部分场合的性能表现要优于KMP算法。GNU grep使用了此算法进行字符串匹配,同时也被很多文本编辑器用进行字符串的查找。

一、概述

二、移动规则

“坏字符”规则

坏字符规则(bad-character shift)用来计算当前模式串与源串失配时的模式串指针的移动方案。具体计算方法如下:


计算几何算法

 PUBLISHED ON February 13, 2015

1. 矢量叉积

设矢量P(x1, y1), Q(x2, y2),如果:

1. P x Q > 0 : 则P在Q的顺时针方向;
2. P x Q < 0 : 则P在Q的逆时针方向;
3. P x Q = 0 : 则P与Q共线,但可能同向或也可能反向。

2. 向量拐向判断

已知线段PQ和QR,记 ans = (R-P) x (Q-P),有如下结论:

1. ans > 0: PQ在Q点向右侧拐后得到QR;
2. ans < 0:PQ在Q点向左侧拐后得到QR;
3. ans = 0: P、Q、R 三点共线。


RMQ与LCA之间的转换

 PUBLISHED ON February 12, 2015

RMQ(Range Maximum/Minimum Query) 和 LCA(Least Common Ancestor) 问题是关联度十分高的两类问题。既可以把LCA问题转化为RMQ问题,也可以把RMQ问题转换为LCA问题。本文主要探讨如何通过笛卡尔树(Cartesian Tree)来建立起这两类问题之间的联系。

笛卡尔树的特点

笛卡尔树的特点如下:

  • 每一个节点的值都是该节点极其子树的最小值。


Mathematica 编程

 PUBLISHED ON February 12, 2015

赋值方式

Mathematica提供了两种类型的赋值方式。

即时赋值

即时赋值是指在赋值时就对值进行计算,即时赋值用=表示。例如:

var = value

在赋值时就计算出value的值。

延迟赋值

延迟赋值是指调用赋值语句时(使用被赋值的变量时)才对值进行计算,并且在每次调用时,其值都会重新计算。延迟赋值用:=表示。例如:

var := value

在调用var是才计算value的值。

清除赋值

使用如下语法可以做到清除赋值:

x = .
t = .

这样处理以后,x, t都会重新成为一个没有值得符号。