rein07
- 浏览: 21332 次
- 性别:
- 来自: 南京
-
最新评论
文章列表
KMP快速字符串查找算法
- 博客分类：
- 算法
在C/C++语言编程过程中，一般的字符串搜索操作都是通过标准库的strstr()函数来完成的，这在通常的情况下，因为字符串的搜索操作不多，并不会产生效率问题。实际上，这个函数的时间复杂度不容乐观。如果要从长度为n的字符串中查找长度为m的子字符串，那么这个strstr()函数的最坏时间复杂度为O(n*m)，可见，随着子字符串长度m的增大，strstr()函数的时间复杂度也相应地成倍增加，有没有更加高效的算法呢？
KMP（Knuth-Morris-Pratt）算法通过预先计算模式字符串中相应字符处的回溯索引，避免了模式匹配时不必要的回溯操作，从而提高了效率，将时间复杂度变成了O(m+n)。
KM ...
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归或者非递归进行，以此达到整个数据变成有序序列。
下面是快速排序的递归实现：
view sourceprint?01 #include "stdafx.h"
02
03 #define LIST_INIT_SIZE 100 //顺序表初始大小
04 #define LISTINCREMENT 10 //顺序表增量
05 ty ...
乍看这题真够唬人的，群里看到这个题目后争先恐后的说看法。最简单的办法不外乎就是遍历每个数，然后toString() 看看里面有多少个1，最后全部加起来，这是我们得到标准答案的办法。
群里3个人写了3个笨方法都跑出来了，3个笨方法，呵呵 有意思，笨方法也不一样。 程序的实现真是变幻莫测。
view sourceprint?01 var re = /1{1}/g;
02
03 var max = 1 * 10000 * 10000;
04
05 getTotal(f);
06 getTotal(f1);
07 getTotal(f2);
08 ...
最大子序列
最大子序列是要找出由数组成的一维数组中和最大的连续子序列。比如{5,-3,4,2}的最大子序列就是 {5,-3,4,2}，它的和是8,达到最大；而 {5,-6,4,2}的最大子序列是{4,2}，它的和是6。你已经看出来了，找最大子序列的方法很简单，只要前i项的和还没有小于0那么子序列就一直向后扩展，否则丢弃之前的子序列开始新的子序列，同时我们要记下各个子序列的和，最后找到和最大的子序列。
代码如下：
#include<iostream>
using namespace std;
int MaxSubSeq(const int *arr,int len,int *start ...
阿里巴巴的一道面试题：说澳大利亚的父母喜欢女孩，如果生出来的第一个女孩，就不再生了，如果是男孩就继续生，直到生到第一个女孩为止，问若干年后，男女的比例是多少？
刚看到问题是的思维逻辑：用递推法，假设一对夫妻，生了个女儿，就不再要了；另外一对夫妻，生了个儿子，再要一个，是女儿，然后也就不要了。第一感觉，应该是女的比男的多。然后思考如何证明这个结论。用数学可以证明，比如用归纳法，看看男女到底比例应该是多少。
后来用仔细考虑了一下：一个家庭如果一直没有生女孩，不是要生多个男孩才对一个女孩吗？女多于男的结论未必正确。我的一个同事坚持认为，女孩的个数一定多余男孩的个数。哈哈，真是这样吗？
有一点我后 ...