动态规划: 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?

阅读全文

动态规划: Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given

s = "leetcode",

dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

阅读全文

堆排序(heap sort)

###二叉堆
二叉堆是一个数组,它可以被看成一个近似的完全二叉树。如图一。树上的每个节点都对应数组中的一个元素。除了最底层外,该树是完全充满的,而且是从左向右填充。

kmp1

二叉堆可以分为两种形式:最大堆和最小堆。在最大堆中,每一个父节点的值都要大于子节点的值;在最小堆中,每一个父节点的值都要小于子节点的值。

阅读全文

图:无向图(undirected graph)

###1.无向图的数据结构
我们一般有两种方式来表示图:

  • 邻接矩阵:我们用一个V*V的布尔矩阵来表示一个无向图。当顶点v和顶点w之间有相连接的边时,定义v行w列的元素值为true,否则为false。这种表示方法最简单,但当图的顶点太多,且为一个稀疏矩阵时,空间就有点浪费了。

阅读全文

单词查找树(Tries)

###单词查找树
单词查找树是由字符串键中的所有字符构造而成,允许使用被查找键中的字符进行查找。比如说有一个字典,我们想要查询一个单词的释义,我们就可以根据单词生成一个单词查找树,然后将释义保存在值中。由于单词查找树的查找时间为单词字符串的长度,所以查找效率有时比排序的算法还要高。

阅读全文

子字符串查找——暴力查找与KMP算法

在这篇文章里,主要分析子字符串查找的两种算法:暴力查找和KMP算法。

###1.暴力查找
子字符串查找最简单的方法就是在需要查找的字符串(text)中模式(pattern)可能出现匹配的任何地方检查匹配是否存在。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int search(String pat, String text) {
int M = pat.length();
int N = text.length();
for (int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++) {
if (text.charAt(i) != pat.charAt(j))
break;
}
if (j == M)
return i; //找到匹配
}
return -1; //没找到匹配,返回-1
}

阅读全文

Ubuntu 12.04 配置两级Rsyslog

###升级Rsyslog
由于要使用Rsyslog的日志动态文件名的功能,必须将Rsyslog升级到高的版本(ubuntu上自带的版本为5.8.*)。升级的方式使用apt-get install

1
2
3
4
5
6
7
8
9
10
11
1.修改/etc/apt/sources.list,添加如下两行:
deb http://ubuntu.adiscon.com/v7-stable precise/
deb-src http://ubuntu.adiscon.com/v7-stable precise/
2.添加PGP Key
sudo apt-key adv --recv-keys --keyserver keyserver.ubuntu.com AEF0CF8E
gpg --export --armor AEF0CF8E | sudo apt-key add -
2.sudo apt-get update && apt-get upgrade
如果出现:
The following packages have been kept back:
rsyslog
使用apt-get install rsyslog安装

阅读全文