Question

字符串1：只含有英文字母
字符串2：含有英文字母和*，其中符号*表示匹配任意字符0或者多次，即正则表达式里面的含义。

现在给定这样的两个串，要求判断是否匹配？
bool isMatch ( const char *str1, const char *str2)

例如：str1 = “hello”, str2 = “he*o”，则二者匹配，返回true,str1 = “hello”, str2 = “he*l”，则不匹配，返回false。

Read the rest of this entry »

快速排序详细分析

注：REF[n]为参考资料，列于文章结尾。

看了编程珠玑Programming Perls第11章关于快速排序的讨论，发现自己长年用库函数，已经忘了快排怎么写。于是整理下思路和资料，把至今所了解的快排的方方面面记录与此。

Read the rest of this entry »

输入：一个字符串，单词用某个特定符号分割（比如空格）
输出：一个字符串，单词顺序和原串相反

看到倒置，一般的做法是用栈，要么自己建个数组、要么STL，或者递归用程序栈。

优雅的递归

void reverse_token() {
  char str[MAX] = {0};
  if (scanf("%[^#]", str) != EOF)  { //利用scanf的正则式特性
      getchar();
      reverse_token();
      printf("%s ", str);
  } 
}

Read the rest of this entry »

看MIT算法导论视频真是收获不蜚，今天学会了求Fibonacci数最快的方法～

Fibonacci（斐波那契）数列小学生都知道的，求Fibonacci数也不是什么难事，可以用递推式一步一步推(线性)。有没有更快的方法呢，你可能马上就想到了通项公式:

这个公式要算一个数的n次方，由于一个数的n次方可以由一个分治算法在logn时间内得到：

Read the rest of this entry »