Jan
9
这是今天算法考试的最后一题，设计一个动态规划的算法来求两个字符串的编辑距离。
以为自己做对了，很happy —— 其实错了，好笨，sigh.
--
Levenshtein Distance (LD, 来文史特距离)也叫edit distance(编辑距离)，它用来表示2个字符串的相似度，LD定义为需要最少多少步基本操作才能让2个字符串相等，基本操作包含3个：插入, 删除, 替换；比如，kiteen和sitting之间的距离可以这么计算：
1，kitten -- > sitten, 替换k为s；
2，sitten -- > sittin, 替换e为i;
3，sittin -- > sitting, 增加g；
所以，其LD为3。
设计状态d[m][n] = d(A[1..m], B[1..n])，易知：
d[0][0] = 0;
d[i][0] = i;
d[0][j] = j;
d[i][j] = min( d[i-1][j-1] + (If A[i]=B[j] Then 0 Else 1 End If), //修改一个字符
d[i-1][j] + 1, //插入一个字符
d[i][j-1] + 1 //删除一个字符
于是可以递推地填满一个 m * n 的矩阵，即得答案。
计算LD的算法表示为(C++代码)：
这个算法其实就是一个矩阵的计算：
最后的d[m][n]就是求得的答案。
@ 2009-06-14
贴一个优化空间复杂度为O(n)的代码(滚动数组)：
以为自己做对了，很happy —— 其实错了，好笨，sigh.
--
Levenshtein Distance (LD, 来文史特距离)也叫edit distance(编辑距离)，它用来表示2个字符串的相似度，LD定义为需要最少多少步基本操作才能让2个字符串相等，基本操作包含3个：插入, 删除, 替换；比如，kiteen和sitting之间的距离可以这么计算：
1，kitten -- > sitten, 替换k为s；
2，sitten -- > sittin, 替换e为i;
3，sittin -- > sitting, 增加g；
所以，其LD为3。
设计状态d[m][n] = d(A[1..m], B[1..n])，易知：
d[0][0] = 0;
d[i][0] = i;
d[0][j] = j;
d[i][j] = min( d[i-1][j-1] + (If A[i]=B[j] Then 0 Else 1 End If), //修改一个字符
d[i-1][j] + 1, //插入一个字符
d[i][j-1] + 1 //删除一个字符
于是可以递推地填满一个 m * n 的矩阵，即得答案。
计算LD的算法表示为(C++代码)：
int d[1010][1010];
int dist(string a, string b){
int m = a.size(), n = b.size(), i, j;
for(i = 0; i <= m; ++i) d[i][0] = i;
for(j = 0; j <= n; ++j) d[0][j] = j;
for (i = 1; i <= m; ++i){
for(j = 1; j <= n; ++j){
// -------------- a, b是从0开始计数的
d[i][j] = d[i-1][j-1] + (a[i-1]==b[j-1]?0:1); //修改一个字符
d[i][j] = min(d[i][j], d[i-1][j] + 1); //插入一个字符
d[i][j] = min(d[i][j], d[i][j-1] + 1); //删除一个字符
}
}
for (i = 0; i <= m; ++i){ //打印矩阵
for(j = 0; j <= n; ++j)
printf("%5d ", d[i][j]);
printf("\n");
}
return d[m][n];
}
int dist(string a, string b){
int m = a.size(), n = b.size(), i, j;
for(i = 0; i <= m; ++i) d[i][0] = i;
for(j = 0; j <= n; ++j) d[0][j] = j;
for (i = 1; i <= m; ++i){
for(j = 1; j <= n; ++j){
// -------------- a, b是从0开始计数的
d[i][j] = d[i-1][j-1] + (a[i-1]==b[j-1]?0:1); //修改一个字符
d[i][j] = min(d[i][j], d[i-1][j] + 1); //插入一个字符
d[i][j] = min(d[i][j], d[i][j-1] + 1); //删除一个字符
}
}
for (i = 0; i <= m; ++i){ //打印矩阵
for(j = 0; j <= n; ++j)
printf("%5d ", d[i][j]);
printf("\n");
}
return d[m][n];
}
这个算法其实就是一个矩阵的计算：
引用
调用dist("abcdef", "acddaf")可以得到输出为:
0 1 2 3 4 5 6
1 0 1 2 3 4 5
2 1 1 2 3 4 5
3 2 1 2 3 4 5
4 3 2 1 2 3 4
5 4 3 2 2 3 4
6 5 4 3 3 3 3
0 1 2 3 4 5 6
1 0 1 2 3 4 5
2 1 1 2 3 4 5
3 2 1 2 3 4 5
4 3 2 1 2 3 4
5 4 3 2 2 3 4
6 5 4 3 3 3 3
最后的d[m][n]就是求得的答案。
@ 2009-06-14
贴一个优化空间复杂度为O(n)的代码(滚动数组)：
int diff(char *a, char *b){
int *d[2], i, j;
int m = strlen(a), n = strlen(b);
d[0] = new int[n + 1];
d[1] = new int[n + 1];
int turn = 0, pre, t;
for (i = 0; i <= n; ++i) d[turn][i] = i;
for (i = 1; i <= m; ++i){
pre = turn;
turn = (turn + 1) % 2;
d[turn][0] = i;
for(int p=0;p<=n;p++)printf("%d ",d[pre][p]);printf("\n");
for(j = 1; j <= n; ++j){
t = d[pre][j-1] + (a[i-1] == b[j-1] ? 0 : 1);
t = min(t, d[pre][j] + 1);
d[turn][j] = min(t, d[turn][j-1] + 1);
}
}
for(int p=0;p<=n;p++)printf("%d ",d[turn][p]);printf("\n");
t = d[turn][n];
delete[] d[0];
delete[] d[1];
return t;
}
int *d[2], i, j;
int m = strlen(a), n = strlen(b);
d[0] = new int[n + 1];
d[1] = new int[n + 1];
int turn = 0, pre, t;
for (i = 0; i <= n; ++i) d[turn][i] = i;
for (i = 1; i <= m; ++i){
pre = turn;
turn = (turn + 1) % 2;
d[turn][0] = i;
for(int p=0;p<=n;p++)printf("%d ",d[pre][p]);printf("\n");
for(j = 1; j <= n; ++j){
t = d[pre][j-1] + (a[i-1] == b[j-1] ? 0 : 1);
t = min(t, d[pre][j] + 1);
d[turn][j] = min(t, d[turn][j-1] + 1);
}
}
for(int p=0;p<=n;p++)printf("%d ",d[turn][p]);printf("\n");
t = d[turn][n];
delete[] d[0];
delete[] d[1];
return t;
}
Jan
9
这两天Xsun同学想让我帮他看看Subpixel，亚像素这个东西。
于是考完就去看了看，觉得蛮有意思，很NB。可惜我帮不上忙，sigh。
贴一些东西出来吧：
其实这个东西我们早就接触到了，因为M$的Windows XP里面有有这个东西，名叫"ClearType"。
zz from http://hi.baidu.com/wingingbob/blog/item/11d43a8175d494debd3e1e35.html
ClearType是由微软在Windows操作系统中提供的屏幕亚像素微调字体平滑工具，让Windows字体更加漂亮。ClearType主要是针对LCD液晶显示器设计，可提高文本的清晰度。基本原理是，将显示器的R, G, B各个次像素也发光，让其色调进行微妙调整，可以达到实际分辨率以上（横方向分辨率的三倍）的纤细文本的显示效果。
1为ClearType线，2是普通的反锯齿线；3和4分别为1和2的四倍放大图；5是1实际显示在液晶显示器上的放大示意图。如图所示，ClearType充分利用LCD色条排列特性，显示出更为完美的斜线。
使用ClearType的显示器放大6倍的效果。由于各个次像素发光，文本边缘带有红、蓝色。
从实际的使用中也能看出来，在启用了ClearType技术以后，字体变得平滑漂亮了。
有兴趣的话还可以再看看这篇文章里的介绍： http://jazzzfish.spaces.live.com/blog/cns!AA856682D7F719B4!302.entry
于是考完就去看了看，觉得蛮有意思，很NB。可惜我帮不上忙，sigh。
贴一些东西出来吧：
其实这个东西我们早就接触到了，因为M$的Windows XP里面有有这个东西，名叫"ClearType"。
zz from http://hi.baidu.com/wingingbob/blog/item/11d43a8175d494debd3e1e35.html
ClearType是由微软在Windows操作系统中提供的屏幕亚像素微调字体平滑工具，让Windows字体更加漂亮。ClearType主要是针对LCD液晶显示器设计，可提高文本的清晰度。基本原理是，将显示器的R, G, B各个次像素也发光，让其色调进行微妙调整，可以达到实际分辨率以上（横方向分辨率的三倍）的纤细文本的显示效果。
1为ClearType线，2是普通的反锯齿线；3和4分别为1和2的四倍放大图；5是1实际显示在液晶显示器上的放大示意图。如图所示，ClearType充分利用LCD色条排列特性，显示出更为完美的斜线。
使用ClearType的显示器放大6倍的效果。由于各个次像素发光，文本边缘带有红、蓝色。
从实际的使用中也能看出来，在启用了ClearType技术以后，字体变得平滑漂亮了。
有兴趣的话还可以再看看这篇文章里的介绍： http://jazzzfish.spaces.live.com/blog/cns!AA856682D7F719B4!302.entry
Jan
8
其实好简单的=.= 为啥以前没去看捏。。。
已知有n个东东为u[1]~u[n], 体积和重量分别是s[1]~s[n]和w[1]~w[n]
有一个包包可以装下大小为S的东东，求这个包包最重可以装多重。
记W[n][S]为要求的东西: 从n个东东里面取出一部分填满体积为S的包包
很容易理解，W[n][S]为以下两个取值的最大值：
1. W[n-1][S] 不取第n个东东，最多可以装多重
2. (s[n] <= S的时候) w[n] + W[n-1][S-s[n]] 一定取第n个东东，重量为v[n]，包包还能装S-s[n]，那么前n-1个东东最多可以装多重。
另外，显然可以看出，当n或者S为0的时候，W[n][S]肯定也为0。
最简单的是写一个递归：
已知有n个东东为u[1]~u[n], 体积和重量分别是s[1]~s[n]和w[1]~w[n]
有一个包包可以装下大小为S的东东，求这个包包最重可以装多重。
记W[n][S]为要求的东西: 从n个东东里面取出一部分填满体积为S的包包
很容易理解，W[n][S]为以下两个取值的最大值：
1. W[n-1][S] 不取第n个东东，最多可以装多重
2. (s[n] <= S的时候) w[n] + W[n-1][S-s[n]] 一定取第n个东东，重量为v[n]，包包还能装S-s[n]，那么前n-1个东东最多可以装多重。
另外，显然可以看出，当n或者S为0的时候，W[n][S]肯定也为0。
最简单的是写一个递归：
Jan
8
昨天看的《C++标准函数库》，看到auto_ptr这一节，说到了关于内存泄露的问题
而且有些情况以前根本没有考虑到，想想觉得好危险。
典型的情况就是如下的代码：
如果在//do sth.的时候退出了函数，比如一个return语句，或者是抛出了一个异常
那么最后的delete p就不会被执行，于是就造成了内存的泄露。
更极端一点的情况是，可能申请了多个内存，有多处return，如果每一个都要处理，那程序就太恶心了。
但是不处理又是不行的——于是需要有一种方式来解决，于是标准库就引进了auto_ptr 智能指针。
这个东西保证它自己被销毁的时候能够释放其指向的对象(使用delete)。
一个简单的例子是:
在退出函数foo()的时候，p的析构函数会被调用，自动释放它指向的classA，于是再也不用费神去写delete了，真好～
不过auto_ptr不是基于引用计数的智能指针，所以有一些很特殊的属性。
如果想要用它，一定一定要都了解了才用哦！就推荐看这本书《The C++ Standard Library》C++标准函数库。
而且有些情况以前根本没有考虑到，想想觉得好危险。
典型的情况就是如下的代码：
void foo(){
int *p = new int[10];
//do sth.
delete[] p;
}
int *p = new int[10];
//do sth.
delete[] p;
}
如果在//do sth.的时候退出了函数，比如一个return语句，或者是抛出了一个异常
那么最后的delete p就不会被执行，于是就造成了内存的泄露。
更极端一点的情况是，可能申请了多个内存，有多处return，如果每一个都要处理，那程序就太恶心了。
但是不处理又是不行的——于是需要有一种方式来解决，于是标准库就引进了auto_ptr 智能指针。
这个东西保证它自己被销毁的时候能够释放其指向的对象(使用delete)。
一个简单的例子是:
#include<memory> //auto_ptr在头文件memory里面哦
using namespace std::auto_ptr; //它在namespace std里面哦
void foo(){
std::auto_ptr<classA> p(new classA);
//do sth.
//no need to free p;
}
using namespace std::auto_ptr; //它在namespace std里面哦
void foo(){
std::auto_ptr<classA> p(new classA);
//do sth.
//no need to free p;
}
在退出函数foo()的时候，p的析构函数会被调用，自动释放它指向的classA，于是再也不用费神去写delete了，真好～
不过auto_ptr不是基于引用计数的智能指针，所以有一些很特殊的属性。
如果想要用它，一定一定要都了解了才用哦！就推荐看这本书《The C++ Standard Library》C++标准函数库。
Dec
29
觉得blog的代码没有高亮非常难看，
但是不想用现成的超级臃肿的代码高亮工具，
于是自己写的一个，效果还行吧^_^
My Simple HighLighter @ CopyLeft
By Felix021 ( http://www.felix021.com ) @ 2008.12.29
一个很简单的基于Javascript的C/C++/...语法高亮代码
用法:
1. 在<head>和</head>之间加上这两句：
<link rel="stylesheet" rev="stylesheet" type="text/css" href="styles.css" />
<script language="javascript" src="hl.js"></script>
2. 需要高亮的代码块，应该是div元素，并且class要设置为code，例如
<div class="code">int main(){}</div>
当然，你也可以改hl.js里面的getElementsByTagName("div")来修改元素类型
修改后面的 if(clsname == "code") 也可以修改class的名字，但是记得也要修改styles.css
3. 在网页底部的</body>之前加上这个
<script language="javascript> highlighter(); </script>
4. 可以修改styles.css自定义元素的样式表
5. 可以修改 hl.js 的keywords列表增加自己想要的关键字list
var keywords = array(
"int", "char", "bool", "class"
);
注意每一个关键字要用引号围起来，而且两个关键字之间要用逗号分开；
最后一个关键字后面没有逗号。
例子参见index.html
下载文件 (已下载 1481 次)
但是不想用现成的超级臃肿的代码高亮工具，
于是自己写的一个，效果还行吧^_^
#include<iostream>
using namespace std;
int main(){
int a, b;
cin >> a >> b;
cout << (a + b) << endl;
return 0;
}
using namespace std;
int main(){
int a, b;
cin >> a >> b;
cout << (a + b) << endl;
return 0;
}
My Simple HighLighter @ CopyLeft
By Felix021 ( http://www.felix021.com ) @ 2008.12.29
一个很简单的基于Javascript的C/C++/...语法高亮代码
用法:
1. 在<head>和</head>之间加上这两句：
<link rel="stylesheet" rev="stylesheet" type="text/css" href="styles.css" />
<script language="javascript" src="hl.js"></script>
2. 需要高亮的代码块，应该是div元素，并且class要设置为code，例如
<div class="code">int main(){}</div>
当然，你也可以改hl.js里面的getElementsByTagName("div")来修改元素类型
修改后面的 if(clsname == "code") 也可以修改class的名字，但是记得也要修改styles.css
3. 在网页底部的</body>之前加上这个
<script language="javascript> highlighter(); </script>
4. 可以修改styles.css自定义元素的样式表
5. 可以修改 hl.js 的keywords列表增加自己想要的关键字list
var keywords = array(
"int", "char", "bool", "class"
);
注意每一个关键字要用引号围起来，而且两个关键字之间要用逗号分开；
最后一个关键字后面没有逗号。
例子参见index.html
下载文件 (已下载 1481 次)
Dec
29
被牛逼哄哄的Snoopy雷到了。
事情是这样的，今天打开 http://acm.whu.edu.cn/woj 检查oak的运行情况
发现在status的第二页有好多个submit都处于Running状态
ssh到服务器上去看了一下，发现Judge在Compile OK以后就挂掉了。
有一堆Stack的信息，但是看不太懂~
DEBUG了一阵，定位到了错误：在判断Restricted_Function的那个函数里面。
加入了调试代码以后的大概结构是这样的：
然后发现非常神奇地，程序输出的是
然后跟上一堆程序出现错误的信息。
于是我就懵了，居然一个return语句也能出现错误？
然后请教snoopy大牛，经过一番七荤八素的DEBUG以后，终于找到了症结所在：
原来在Restricted_Function里面定义的那个char f[30]空间太小了
由于是分配在栈空间里面的，所以在运行的时候，出现了少量越界写入的情况
在程序返回的时候，由于返回地址等被未预料到的字符覆盖了，于是就出现了上述问题。
一个return语句也能"出错"，暴露出这样严重的内存使用问题
——可能存在于任何地方，写程序的时候务必要小心啊！
同时，通过这种方式"定位"到的错误点，未必就是错误真正发生的地方！
事情是这样的，今天打开 http://acm.whu.edu.cn/woj 检查oak的运行情况
发现在status的第二页有好多个submit都处于Running状态
ssh到服务器上去看了一下，发现Judge在Compile OK以后就挂掉了。
有一堆Stack的信息，但是看不太懂~
DEBUG了一阵，定位到了错误：在判断Restricted_Function的那个函数里面。
加入了调试代码以后的大概结构是这样的：
......
bool Restricted_Function(){
char f[30], ...;
......
cout << "DEBUG 1" << endl;
return false;
}
......
bool WOJ_JUDGE(){
......
cout << "DEBUG 0“ << endl;
if(Restricted_Function(){
cout << "DEBUG 2" << endl;
return RF;
}
cout << "DEBUG 2" << endl;
......
}
bool Restricted_Function(){
char f[30], ...;
......
cout << "DEBUG 1" << endl;
return false;
}
......
bool WOJ_JUDGE(){
......
cout << "DEBUG 0“ << endl;
if(Restricted_Function(){
cout << "DEBUG 2" << endl;
return RF;
}
cout << "DEBUG 2" << endl;
......
}
然后发现非常神奇地，程序输出的是
引用
DEBUG 0
DEBUG 1
DEBUG 1
于是我就懵了，居然一个return语句也能出现错误？
然后请教snoopy大牛，经过一番七荤八素的DEBUG以后，终于找到了症结所在：
原来在Restricted_Function里面定义的那个char f[30]空间太小了
由于是分配在栈空间里面的，所以在运行的时候，出现了少量越界写入的情况
在程序返回的时候，由于返回地址等被未预料到的字符覆盖了，于是就出现了上述问题。
一个return语句也能"出错"，暴露出这样严重的内存使用问题
——可能存在于任何地方，写程序的时候务必要小心啊！
同时，通过这种方式"定位"到的错误点，未必就是错误真正发生的地方！
Dec
29
据说MySQL是从v4.0开始支持事务(Transaction)的，一直没去试过。
今天心血来潮，于是就玩了一下。
首先，mysql里面有一个状态量叫做 autocommit ，默认值是1
也就是说，当你提交一个SQL语句以后，这条语句会被立即执行并修改数据库内容(如果有必要的话)。
所以如果你想要开始一个事务，那么首先应该把这个东东设置为0，有这么几种方法：
1. 提交SQL语句 START TRANSACTION;
2. 提交SQL语句 BEGIN;
3. 提交SQL语句 SET AUTOCOMMIT=0;
4. (PHP) mysqli_autocommit($conn, false);
然后就可以开始进行你想做的数据库修改了，比如INSERT, UPDATE, DELETE
修改完以后，如果返回的结果有不对劲的地方，OK，试试
1. 提交SQL语句 ROLLBACK;
2. 或者(PHP) mysqli_rollback($conn);
然后你就会发现数据库好像根本没有操作过似的
(其实仔细观察的话会发现auto_increment那个字段的max值变大了-____-)
如果一切OK，那么就用这个：
1. 提交SQL语句 COMIIT;
2. 或者(PHP) mysqli_commit($conn);
注意，在提交COMMIT以后，数据库的改动就正式写到硬盘，不能撤销啦。
给俩例子吧：
a. 在MySQL命令行下进行的操作
OK，再来个PHP版本的：
今天心血来潮，于是就玩了一下。
首先，mysql里面有一个状态量叫做 autocommit ，默认值是1
也就是说，当你提交一个SQL语句以后，这条语句会被立即执行并修改数据库内容(如果有必要的话)。
所以如果你想要开始一个事务，那么首先应该把这个东东设置为0，有这么几种方法：
1. 提交SQL语句 START TRANSACTION;
2. 提交SQL语句 BEGIN;
3. 提交SQL语句 SET AUTOCOMMIT=0;
4. (PHP) mysqli_autocommit($conn, false);
然后就可以开始进行你想做的数据库修改了，比如INSERT, UPDATE, DELETE
修改完以后，如果返回的结果有不对劲的地方，OK，试试
1. 提交SQL语句 ROLLBACK;
2. 或者(PHP) mysqli_rollback($conn);
然后你就会发现数据库好像根本没有操作过似的
(其实仔细观察的话会发现auto_increment那个字段的max值变大了-____-)
如果一切OK，那么就用这个：
1. 提交SQL语句 COMIIT;
2. 或者(PHP) mysqli_commit($conn);
注意，在提交COMMIT以后，数据库的改动就正式写到硬盘，不能撤销啦。
给俩例子吧：
a. 在MySQL命令行下进行的操作
mysql> use t;
mysql> CREATE TABLE `test`(`id` int primary key auto_increment, `name` char(50));
mysql> START TRANSACTION;
mysql> INSERT INTO `test` VALUES (NULL, 'a');
mysql> COMMIT; #或者 mysql> ROLLBACK;
mysql> SELECT * FROM `test`;
看看效果如何？mysql> CREATE TABLE `test`(`id` int primary key auto_increment, `name` char(50));
mysql> START TRANSACTION;
mysql> INSERT INTO `test` VALUES (NULL, 'a');
mysql> COMMIT; #或者 mysql> ROLLBACK;
mysql> SELECT * FROM `test`;
OK，再来个PHP版本的：
<?php
$conn = new mysqli("localhost", "root", "123456", "t");
$conn->autocommit(false);
$res = $conn->query("INSERT INTO `test` VALUES(NULL, 'a')");
if($res)
$conn->commit();
else
$conn->rollback();
$conn->close();
?>
$conn = new mysqli("localhost", "root", "123456", "t");
$conn->autocommit(false);
$res = $conn->query("INSERT INTO `test` VALUES(NULL, 'a')");
if($res)
$conn->commit();
else
$conn->rollback();
$conn->close();
?>
Dec
29
#include<iostream>
using namespace std;
char l[] = "Felix021";
void print(char a){
for(int i = 7; i >= 0; --i){
cout << ((a >> i ) & 1);
}
}
int main(){
for(int i = 0; l[i]; ++i){
print(l[i]);
}
cout << endl;
return 0;
}
using namespace std;
char l[] = "Felix021";
void print(char a){
for(int i = 7; i >= 0; --i){
cout << ((a >> i ) & 1);
}
}
int main(){
for(int i = 0; l[i]; ++i){
print(l[i]);
}
cout << endl;
return 0;
}
