1     int LCS(string s1, string s2){//公共子序列 2         int length1=s1.length(); 3         int length2=s2.length(); 4  5         int **A; 6         A=new int*[length1+1]; 7         for(int i=0;i<=length1;i++) 8             A[i]=new int[length2+1]; 9 10         for(int i=0;i<=length1;i++)11             A[i][0]=0;12         for(int i=0;i<=length2;i++)13             A[0][i]=0;14 15         for(int i=1;i<=length1;i++)16             for(int j=1;j<=length2;j++){17             if(s1[i-1]==s2[j-1])18                 A[i][j]=A[i-1][j-1]+1;19             else{20                 A[i][j]=max(A[i-1][j],A[i][j-1]);21             }22         }23         return A[length1][length2];24     }25     int LCSstrict(string s1, string s2){//连续公共子串26         int length1=s1.length();27         int length2=s2.length();28         int Max=INT_MIN;29         int **A;30         A=new int*[length1+1];31         for(int i=0;i<=length1;i++)32             A[i]=new int[length2+1];33 34         for(int i=0;i<=length1;i++)35              for(int j=0;j<=length2;j++)36             A[i][j]=0;37 38         for(int i=1;i<=length1;i++)39             for(int j=1;j<=length2;j++){40             if(s1[i-1]==s2[j-1])41                 A[i][j]=A[i-1][j-1]+1;42                 if(Max<A[i][j])43                     Max=A[i][j];44             else{45                 A[i][j]=0;46             }47         }48         return Max;49     }

 1 class Solution { 2 public: 3     void QuickSort(vector<int> & A,int left, int right){ 4         //int b[]={1,2,4,3,5,1,4,2,6}; 5         //vector<int> a(b,b+9); 6         //for(vector<int>::iterator iter=a.begin();iter!=a.end();iter++)cout<<*iter<<" "; 7         if(left<right){ 8             int index=rand()%(right-left)+left; 9 10             swap(A[left],A[index]);11             int  i=left,j=right+1;12             do{13                 do i++;14                 while(A[i]<A[left]);15                 do j--;16                 while(A[j]>A[left]);17                 if(i<j)18                 swap(A[i],A[j]);19                 //else  break;20             }while(i<j);21 22              swap(A[left],A[j]);23 24             QuickSort(A,left,j-1);25             QuickSort(A,j+1,right);26         }else return;27     }28     void MergeSort(int *A, int left,int right){29         if(left<right){30             int index=(left+right)/2;31             MergeSort(A,left,index);32             MergeSort(A,index+1,right);33             Merge(A,left,right);34         }else return;35     }36     void InsertSort(int *A, int length){37         //把数插入到已排好序的数组中，插入位置后面数据依次后移38         for(int i=1;i<length;i++){39             int j=0;40             while(A[j]<A[i]&&j<i)j++;41             int tmp=A[j];42             A[j]=A[i];43             for(int x=i;x>j;x--)44                 A[x]=A[x-1];45         }46     }47     void BubbleSort(int *A, int length){48         //相邻元素交换位置，使小值上移49         for(int i=0;i<length--;){50             for(int j=0;j<length;j++){51                 if(A[j]>A[j+1])52                     swap(A[j],A[j+1]);53             }54         }55     }56     void SelectSort(int *A , int length){57         //选出当前数组中最值，放于相应位置58         for(int i=0;i<length;i++){59             int Min=A[i],index=i;60             for(int j=i;j<length;j++){61                 if(Min>A[j]){62                     index=j;63                     Min=A[j];64                 }65             }66             swap(A[i],A[index]);67         }68     }69  private:70     void Merge(int *A, int left,int right){71         int index=(left+right)/2;72         int *B=new int[index-left+1];73         int *C=new int[right-index];74         for(int i=0,j=left;i<index-left+1;i++,j++)75             B[i]=A[j];76         for(int i=0,j=index+1;i<right-index;i++,j++)77             C[i]=A[j];78 79         for(int i=left,x=0,y=0;i<=right;i++){80             if((B[x]<C[y]&&(x<index-left+1))||y==right-index){81                 A[i]=B[x];82                 x++;83             }else{84                 A[i]=C[y];85                 y++;86             }87         }88             delete B,C;89     }90    };

 1     void permut1 (vector<int> &A, int Start, int End, vector<vector<int> > &B){ 2         if(Start>=End){ 3             B.push_back(A); 4         }else{ 5             for(int i=Start;i<End;i++){ 6                 swap(A[i],A[Start]); 7                 permut1(A,Start+1, End,B); 8                 swap(A[i],A[Start]); 9             }10         }11         /*调用及输出参考12         int b[]={1,2,3,4,5,6};13     vector<int> A(b,b+6);14     vector<vector<int> > B;15     sol->permut1(A,0,A.size(),B);16     int i=0;17     for(vector<vector<int> >::iterator iter=B.begin();iter!=B.end();iter++){18             cout<<++i<<" ";19         for(vector<int>::iterator item=(*iter).begin();item!=(*iter).end();item++)20             cout<<*item<<" ";21         cout<<endl;22     }23         */24     }25     void permut2(vector<int> &A, int Start, int End){26         // sol->permut2(A,0,A.size());27         if(Start>=End){28             for(vector<int>::iterator iter= A.begin();iter!=A.end();iter++)29                 cout<<*iter<<" ";cout<<endl;30         }else{31             for(int i=Start;i<End;i++){32                 swap(A[i],A[Start]);33                 permut2(A,Start+1, End);34                 swap(A[i],A[Start]);35             }36         }37     }38     void combination(vector<int> &A){39         int length=A.size();40         float sum=pow(2.0,(float)length);41         for(int i=0,x;i<sum;i++){42             x=i;43             for(int j=0;j<length;j++){44                 if(x%2==1)45                     cout<<" "<<A[length-1-j];46                 x=x>>1;47             }cout<<endl;48         }49     }50    

 1     int binarySearch(int *A, int k,int length){ 2         //折半搜索 3         //cout<<sol->binarySearch(b,-10,sizeof(b)/sizeof(*b))<<endl; 4         int left=0,right=length; 5         int index=(left+right)/2; 6         while(index!=left&&index!=right){ 7             if(A[index]==k) 8                 break; 9             if(A[index]<k){10                     left=index;11                     index=(left+right)/2;12             }13             if(A[index]>k){14                 right=index;15                 index=(right+left)/2;16             }17             cout<<left<<"-"<<index<<"-"<<right<<"-"<<endl;18         }cout<<endl;19         if(A[index]==k)20         return index;21         else return -1;22     }

 1     void PreOrderSearch(TreeNode *p){ 2         if(p){ 3             cout<<p->val<<" "; 4             PreOrderSearch(p->left); 5             PreOrderSearch(p->right); 6         } 7     } 8     void InOrderSearch(TreeNode *p){ 9         if(p){10             InOrderSearch(p->left);11             cout<<p->val<<" ";12             InOrderSearch(p->right);13         }14     }15     void PostOrderSearch(TreeNode *p){16         if(p){17             PostOrderSearch(p->left);18             PostOrderSearch(p->right);19             cout<<p->val<<" ";20         }21     }

 1     bool isSameTree(TreeNode *p, TreeNode *q) { 2         if(p==NULL&&q==NULL) 3             return true; 4         else if((p==NULL&&q!=NULL)||(q==NULL&&p!=NULL)||(p->val!=q->val)) 5             return false; 6         if(p->val==q->val) 7         return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right); 8  9     }10  

 1     bool hasCycle(ListNode *head) { 2         ListNode * p1=head; 3         ListNode * p2=head; 4         while(p1!=NULL&&p2!=NULL&&p2->next!=NULL){ 5             p1=p1->next; 6             p2=p2->next->next; 7             if(p1==p2) 8                 return true; 9         }10         return false;11     }

 1     int numTrees(int n) {//BST数量 2         int* A=new int[n+1]; 3         A[0]=1;A[1]=1;A[2]=2; 4         for(int x=3;x<=n;x++) 5         { 6            A[x]=0; 7         for(int i=0,j=x-1;i<x;i++,j--){ 8             A[x]+=A[i]*A[j]; 9         }10         }11         return A[n];12     }