算法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改進：考慮如下情況：