算法Tips杂乱整理

2019-11-08 01:44:12

字体：大中小

来源：转载

供稿：网友

1.埃氏筛

① 给定一个正整数n(n<=10^6)，问n以内有多少个素数？做法：做法其实很简单，首先将2到n范围内的整数写下来，其中2是最小的素数。将表中所有的2的倍数划去，表中剩下的最小的数字就是3，他不能被更小的数整除，所以3是素数。再将表中所有的3的倍数划去……以此类推，如果表中剩余的最小的数是m，那么m就是素数。然后将表中所有m的倍数划去，像这样反复操作，就能依次枚举n以内的素数，这样的时间复杂度是O(nloglogn)。 ② 区间素数筛：给定两个正整数a、b(a

2.欧几里得（辗转相除法）—-最小公约数

这里写图片描述

注：最大公倍数求法，先求最小公约数rem，最大公倍数= a/rem * b/rem * rem ;

3. 计算int x的二进制包含几个1

int func(x){ int count=0; while(x){ count++; x= x&(x-1); } return count;}

4.队列

循环队列当 rear=front时，为空，当还剩下一个空间的时候，表示队列满了循环队列满的条件：（rear+1）%QueueSize == front 循环队列的长度： (rear – front + QueueSize) %QueueSize

5.KMP模式匹配算法

KMP模式匹配算法的目的在于减少不必要的匹配次数，从而提高匹配效率。KMP的核心在于next数组的推导，而next数组完全有模式串决定。 next数组意义：表示若在改位j匹配失败，则将j=next[j]进行继续匹配，从而减少不必要的匹配。这里写图片描述

void get_next(char T[],int next[]){ int i=1,j=0; next[i]=0; while(i<T[0]){ if(j==0 || T[i]==T[j]){ ++i; ++j; next[i]=j;//这里可以改进 } else j=next[j];//回溯j }}

KMP改进：考虑如下情况：