Alias算法

问题描述 O(1)时间内产生离散随机数的方法。 class Alias{ public: double* p; int* h; int* map1; int* map2; int n; Alias(vector<pair<int, double> > pi){ double sum = 0; n = pi.size(); stack<int> small; stack<int> big;...

各式排序算法及其c语言实现

问题描述 排序算法可以说是算法的一个基础,这里在我水平范围内进行总结和归纳,并给出我自己实现的源码。 以下,归纳基于比较的排序方法,因此,其运行时间上限基本都是O(nlog(n)) 时间对比 排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性 冒泡排序 O(n) O(1) 稳定 插入排序 O(n) O(1) 稳定 希尔排序 O(1) 不稳定 堆排序 O(nlogn) O(nlogn) O(1) 不稳定 归并排序 O(nlogn) O(nlogn) O(n)...

模式匹配之KMP算法

#问题描述 模式匹配:字串的定位操作通常被称为串的模式匹配 最简单的模式匹配方式:从主串S的第pos个字符起和模式的第一个字符比较之,若相等,则继续逐个比较后续字符;否则从主串S的下一个字符起再重新和模式的字符比较之。依次类推,直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等,则称匹配成功,函数值为和模式T中第一个字符相等的字符在主串中的序号,否则称匹配失败。 模式匹配的改进算法 D.E.Knuth 、V.R.Pratt 和 J.H.Morris同时发现,其算法的本质改变在于:每当一趟匹配过程中出现字符比较不等时,不需要回溯指针,而是利用已经得到的部分匹配结果将模式向右移动尽可能远的一段距离后,继续进行比较。 在此不对算法本身做太多阐述,网上有很多说明,仅仅是,完成我自己在理解此算法之后,写出相应的代码。 求next与nextval与匹配 #include<stdio.h> #include<string.h> #include<malloc.h> #include<memory.h> #include<time.h> void Next1(char *pattern, int next[]){ int length=strlen(pattern); *(next)=0; *(next+1)=1; for(int i=2;i<length;i++){ int aim=i-1; while(pattern[i-1]!=pattern[next[aim]-1]){ aim=next[aim]-1;...

C and C++ HelloWorld

第一篇博客 关于 Hello World C #include<stdio.h> int main(){ printf("HelloWorld"); return 0; } C++ #include<iostream> using namespace std; int main(){ cout<<"HelloWorld"<<endl; }