• Feb 17, 2015

    字符串的编辑距离

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

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

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

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

  • Feb 17, 2015

    KMP算法

    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],向前寻找匹配位置。具体实现代码如下：

  • Feb 16, 2015

    星期的计算

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

    蔡勒公式

    蔡勒(Zeller)公式

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

    参数含义解释

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

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

    Boyer-Moore 算法

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

  • Feb 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共线，但可能同向或也可能反向。

    1. 向量拐向判断

    已知线段 $PQ$ 和 $QR$，记 $ans = (R-P) \times (Q-P)$，有如下结论：

    1. ans > 0: PQ在Q点向右侧拐后得到QR；
2. ans < 0：PQ在Q点向左侧拐后得到QR；
3. ans = 0: P、Q、R 三点共线。
  • Feb 12, 2015

    Mathematica 编程

    赋值方式

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

    即时赋值

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

    var = value

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

    延迟赋值

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

    var := value

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

    清除赋值

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

    x = .
t = .

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

  • Feb 12, 2015

    Mathematica中的列表(List)

    List是Mathematica中的一种重要的数据结构。

    ** 在Mathematica中使用List时必须注意：Mathematica的List的索引是从1开始的，不是0! **

    List的表示

    List用{}来表示。如：

    {1, 2, 3, 4}

    List的生成

    Mathematica中，有以下三种方式来生成List。

    1. Range 命令
    Range[Subscript[i, max]] 
    生成列表 {1,2,\[Ellipsis],Subscript[i, max]}.
Range[Subscript[i, min],Subscript[i, max]] 
    生成列表 {Subscript[i, min],\[Ellipsis],Subscript[i, max]}.
Range[Subscript[i, min],Subscript[i, max],di] 
    使用步长 di 生成列表. 
  • Feb 12, 2015

    RMQ与LCA之间的转换

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

    笛卡尔树的特点

    笛卡尔树的特点如下：

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

    Haskell 数据类型和类型类(Typeclasses)

    静态类型

    Haskell是静态类型(Static Type)语言，在编译时期每个表达式的类型都已经确定下来。如果在代码中有类型错误，就不可能通过编译。这极大地提高了代码的安全性。在Haskell中，所有东西都有类型。

    GHCi中查看数据类型

    在GHCi中，通过 :t <name> 或者 :type <name>来查看变量、常量或表达式的数据类型。例如：

    Prelude> let a = 1
Prelude> :t a
a :: Num a => a
Prelude> :type True
True :: Bool
Prelude> :t 4 == 5
4 == 5 :: Bool

    基本数据类型

    Haskell有以下几种基本数据类型：

  • Feb 11, 2015

    背包问题总结

    背包问题是动态规划思想和方法的经典应用问题，本文将从0-1背包，完全背包和混合背包三个角度来分析简单背包问题的求解方法。

    背包问题

    背包问题本质上是规划型问题，问题的核心在于在满足约束条件下，找到一种选择方案，使得目标值达到最优。通过动态规划的方法，可以将此类问题限制在多项式复杂度的时间内求解。

Subscribe via RSS

← Newer
Older →