经典算法合集

 1 #include "stdafx.h"
 2 #include"iostream"
 3 #include"vector"
 4 #include"iterator"
 5 #include"algorithm"
 6 #include"vector"
 7 #include"string"
 8 #include"memory.h"
 9 #include"stdlib.h"
10 #include"queue"
11 #include"math.h"
12 #include"list"
13 using namespace std;

1 class TreeNode {
2   public:
3     int val;
4     TreeNode *left, *right;
5     TreeNode(int val) {
6          this->val = val;
7          this->left = this->right = NULL;
8     }
9   };

 1 void print(int left,int right,vector<int>temp){
 2     if(left==0&&right==0){
 3         for(int i=0;i<temp.size();i++){
 4            if(temp[i]==0)
 5                cout<<"(";
 6            if(temp[i]==1)
 7                cout<<")";
 8         }
 9         cout<<endl;
10         return ;
11     }
12     if(left>0){
13         temp.push_back(0);
14         print(left-1,right,temp);
15         temp.pop_back();
17     }
18     if(right>0&&left<right){
19        temp.push_back(1);
20        print(left,right-1,temp);
21        temp.pop_back();
22     }
24 }
25 int printBracketMain(){
26   vector<int> temp;
27   print(3,3,temp);
28   return 0;
29 }

 1 class Solution {
 2 public:
 3     bool isPart(TreeNode *T1, TreeNode *T2){
 4         if(T2==NULL) 
 5             return true;
 6         if(T1==NULL)
 7             return false;
 8         if(T1->val==T2->val)
 9             return isPart(T1->right,T2->right)&&isPart(T1->left,T2->left);
10         return false;
11     }
12 
13     bool isSubtree(TreeNode *T1, TreeNode *T2) {
14         bool ispart = false;
15         if(T1!=NULL){
16         if(T1->val==T2->val)
17             ispart = isPart(T1,T2);
18          if(!ispart)
19           ispart = isSubtree(T1->left,T2);
20          if(!ispart)
21             ispart =  isSubtree(T1->right,T2);
22         }
23          return ispart;
24     }
25 };

 1 class Solution {
 2 public:
 3     int getMax(int a,int b){
 4       return a>=b?a:b;
 5     }
 6     int getAbs(int a){
 7        return a<0?-a:a;
 8     }
 9     int height(TreeNode *root){
10         if(root==NULL) return 0;
11         int leftH = height(root->left)+1;
12         int rightH = height(root->right)+1;
13         if(leftH==-1||rightH==-1)
14             return -1;
15         if(abs(leftH-rightH)>1)
16             return -1;
17         return getMax(leftH,rightH);
18      }
19     bool isBalanced(TreeNode *root) {
20         int isBalance = height(root);
21         if(isBalance==-1)
22             return false;
23         return true;
24     }
25 };

 1 int longestIncreasingSubsequence(vector<int> nums) {
 2     int len = nums.size();
 3     vector<int> ans(nums.size(),1);;
 4     int maxlen = 0;
 5     ans[0] = 1;
 6     for(int i=0;i<len;i++){
 7       for(int j=0;j<i;j++){
 8           if(nums[j]<nums[i])
 9               ans[i] = max(ans[i],ans[j]+1);
10       }
11       if(ans[i]>maxlen)
12           maxlen = ans[i];
13     }
14     return maxlen;
15 }
16 int LisMain(){
17     vector<int> nums;
18     int n=0,temp=0;
19     cin>>n;
20     while(n--){
21        cin>>temp;
22        nums.push_back(temp);
23     }
24     int len = longestIncreasingSubsequence(nums);
25     cout<<len<<endl;
26     return 0;
27 }

 1 int dis[1001][1001];
 2 int set[1001];
 3 int path[1001];
 4 #define INF  9999999;
 5 
 6 void init(){
 7    for(int i=0;i<1001;i++)
 8        for(int j=0;j<1001;j++)
 9            dis[i][j]=INF;
10 }
11 
12 void printPath(int begin,int end,int N){
13     stack<int> s;
14     int i=end;
15     while(path[i]!=0){
16         s.push(path[i]);
17         i = path[i];
18     }
19     cout<<begin<<" ";
20     while(!s.empty()){
21         cout<<s.top()<<" ";
22         s.pop();
23     }
24     cout<<end<<" ";
25 }
26 
27 void djs(int start,int end,int N){
28   while(true){
29       int min=INF;
30       int index=0;
31       //find min
32       for(int i=1;i<=N;i++){
33           if(i!=start&&set[i]==0)
34              if(dis[start][i]<min){
35                  min = dis[start][i];
36                  index = i;
37              }
38       }
39       if(index==0)//no ans
40           break;
41       set[index]=1;//set the flag
42       for(int i=1;i<=N;i++){
43           if(i!=start)
44              if(dis[start][i]>dis[start][index]+dis[index][i]){
45                  dis[start][i] = dis[start][index]+dis[index][i];
46                  path[i] = index;
47              }
48       }
49    }
50 }
51 
52 int djsMain(){
53     int N=0,M=0,S=0,T=0;
54     init();
55     cin>>N>>M>>S>>T;//node edge start end
56     int temp=0,s=0,e=0;
57     for(int i=0;i<M;i++){
58        cin>>s>>e>>temp;
59        if((dis[s][e]>temp)){
60             dis[s][e]=temp;
61             dis[e][s]=temp;
62        }
63     }
64     djs(S,T,N);
65     cout<<dis[S][T]<<endl;
66     //printPath(S,T,N);
67     return 0;
68 }

 1 #define N 1001 
 2 #define INF 99999
 3 int dis[N][N];
 4 
 5 void initDis(){
 6      for(int i=0;i<N;i++)
 7          for(int j=0;j<N;j++){
 8              if(i==j)
 9                  dis[i][j] = 0;
10              else
11                 dis[i][j] = INF;
12          }
13 }
14 void output(int n){
15      for(int i=1;i<=n;i++){
16         for(int j=1;j<=n;j++)
17             {   
18                 if(j!=1)
19                     cout<<" ";
20                 cout<<dis[i][j];
21             }
22         cout<<endl;
23     }
24 }
25 void floyd(int n){
26     for(int k=1;k<=n;k++)
27         for(int i=1;i<=n;i++)
28             for(int j=1;j<=n;j++)
29             {
30                  if(dis[i][j]>dis[i][k]+dis[k][j])
31                      dis[i][j] = dis[i][k]+dis[k][j];
32             }
33 }
34 
35 int floydMain(){
36     int n=0,m=0;
37     initDis();
38     int temp = 0,i=0,j=0;
39     while(cin>>n>>m){
40         for(int k=0;k<m;k++){
41             cin>>i>>j>>temp;
42             if(temp<dis[i][j]){
43                  dis[i][j] = temp;
44                 dis[j][i] = temp;
45             }
46         }
47         floyd(n);
48         output(n);
49     }
50     return 0;
51 }