以下为配合PAT1086 修改为层次遍历的代码，可以参考我的上一篇文章；原理就是BFSint level_order(TreeNode * Tree){ queue<TreeNode *> q; q.push(Tree); while(!q.empty()){ cout<<q.front()->data<<" "; TreeNode *tmp = new TreeNode; tmp->data=q.front()->data; tmp->left=q.front()->left; tmp->right=q.front()->right; q.pop(); if(tmp->left!=NULL) q.push(tmp->left); if(tmp->right!=NULL) q.push(tmp->right); } cout<<endl; }#include<iostream> #include<algorithm> #include<string> #include<stack> #include<queue> using namespace std; typ ...继续阅读 (47)

以下为配合PAT1086 修改为层次遍历的代码，可以参考我的上一篇文章；原理就是BFSint level_order(TreeNode * Tree){ queueq; q.push(Tree); while(!q.empty()){ coutdata=q.front()->data; tmp->left=q.front()->left; tmp->right=q.front()->right; q.pop(); if(tmp->left!=NULL) q.push(tmp->left); if(tmp->right!=NULL) q.push(tmp->right); } cout<#include#include#include#includeusing namespace std; typedef struct TreeNode { int data; struct TreeNode *left,*right; } TreeNode; TreeNode *pTree = new TreeNode; int n,b=0,b2=0,p,op=0; stacks; int arr_pre[40],arr_mid& ...继续阅读 (16)

#include<iostream> #include<algorithm> #include<string> #include<stack> using namespace std; typedef struct TreeNode { int data; struct TreeNode *left,*right; } TreeNode; TreeNode *pTree = new TreeNode; int n,b=0,b2=0,p,op=0; stack<int> s; int arr_pre[40],arr_mid[40],r[40],h=0; void last_order(TreeNode * Tree){ if(Tree!=NULL){ last_order(Tree->left); last_order(Tree->right); r[h++]=Tree->data; } return; } void Build_Tree(TreeNode* &Tree,int p1/* 中序遍历扫描起点 */,int p2 /* 中序遍历扫描终点 */){ if(p1 ...继续阅读 (59)

#include#include#include#includeusing namespace std; typedef struct TreeNode { int data; struct TreeNode *left,*right; } TreeNode; TreeNode *pTree = new TreeNode; int n,b=0,b2=0,p,op=0; stacks; int arr_pre[40],arr_mid[40],r[40],h=0; void last_order(TreeNode * Tree){ if(Tree!=NULL){ last_order(Tree->left); last_order(Tree->right); r[h++]=Tree->data; } return; } void Build_Tree(TreeNode* &Tree;,int p1/* 中序遍历扫描起点 */,int p2 /* 中序遍历扫描终点 */){ if(p1>p2) return; Tree = new TreeNode; Tree->left = Tree->right = NULL; int pos; for(int ...继续阅读 (16)

#include<iostream> #include<algorithm> using namespace std; struct TreeNode { int data; TreeNode *parent,*left,*right; }; TreeNode *pTree; int arr[1010]; void pre_order(TreeNode *pTree){ if(pTree!=NULL){ cout<< pTree -> data <<" "; pre_order(pTree->left); pre_order(pTree->right); } cout<<endl; } int main() { /*通过插入构造一棵二叉查找树*/ int n,p; cin>>n; for(int i=0; i<n; i++) { cin>>p; arr[i]=p; if(pTree == NULL) { pTree=new TreeNode; pTree->data=p; pTree->left=pTree->right=NULL; } el ...继续阅读 (45)

#include#includeusing namespace std; struct TreeNode { int data; TreeNode *parent,*left,*right; }; TreeNode *pTree; int arr[1010]; void pre_order(TreeNode *pTree){ if(pTree!=NULL){ cout<< pTree -> data <<" "; pre_order(pTree->left); pre_order(pTree->right); } cout<>n; for(int i=0; i>p; arr[i]=p; if(pTree == NULL) { pTree=new TreeNode; pTree->data=p; pTree->left=pTree->right=NULL; } else { TreeNode *point = pTree; while(true) { if(point->data > p) { if(point->left==NULL) { point->left = new TreeNode; point->left->data=p; ...继续阅读 (19)

#include<iostream> #include<algorithm> using namespace std; struct TreeNode { int data; TreeNode *parent,*left,*right; }; TreeNode *pTree; int main() { int n,p; cin>>n; for(int i=0; i<n; i++) { cin>>p; arr[i]=p; if(pTree == NULL) { pTree=new TreeNode; pTree->data=p; pTree->left=pTree->right=NULL; } else { TreeNode *point = pTree; while(true) { if(point->data > p) { if(point->left==NULL) { point->left = new TreeNode; point->left->data=p; point->left->left=point->left- ...继续阅读 (39)

#include#includeusing namespace std; struct TreeNode { int data; TreeNode *parent,*left,*right; }; TreeNode *pTree; int main() { int n,p; cin>>n; for(int i=0; i>p; arr[i]=p; if(pTree == NULL) { pTree=new TreeNode; pTree->data=p; pTree->left=pTree->right=NULL; } else { TreeNode *point = pTree; while(true) { if(point->data > p) { if(point->left==NULL) { point->left = new TreeNode; point->left->data=p; point->left->left=point->left->right=NULL; break; } else { point=point->left; continue; } } if(poi ...继续阅读 (18)

#include<iostream> #include<algorithm> using namespace std; struct TreeNode { int data; TreeNode *parent,*left,*right; }; TreeNode *pTree,*mpTree; int isok=1,isok2=1; int arr1[1010],arr2[1010],arr[1010],b1=0,b2=0; int pre_order(TreeNode *Tree) { if(Tree!=NULL) { arr1[b1++]=Tree->data; pre_order(Tree->left); pre_order(Tree->right); } } int pre_order2(TreeNode *Tree) { if(Tree!=NULL) { arr2[b2++]=Tree->data; pre_order2(Tree->left); pre_order2(Tree->right); } } int last_order(TreeNode *Tree) { if(Tree!=NULL) ...继续阅读 (51)

#include#includeusing namespace std; struct TreeNode { int data; TreeNode *parent,*left,*right; }; TreeNode *pTree,*mpTree; int isok=1,isok2=1; int arr1[1010],arr2[1010],arr[1010],b1=0,b2=0; int pre_order(TreeNode *Tree) { if(Tree!=NULL) { arr1[b1++]=Tree->data; pre_order(Tree->left); pre_order(Tree->right); } } int pre_order2(TreeNode *Tree) { if(Tree!=NULL) { arr2[b2++]=Tree->data; pre_order2(Tree->left); pre_order2(Tree->right); } } int last_order(TreeNode *Tree) { if(Tree!=NULL) { last_order(Tree->left); last_order(Tree->right) ...继续阅读 (15)

昨天的归并排序问题出在 插入排序写错了。今天改了改用在堆排序这道题上 test全过堆排序详解http://blog.csdn.net/xiaoxiaoxuewen/article/details/7570621/#include <iostream> #include <algorithm> using namespace std; int n; int *arr,*s; int isheap=0; bool check() { for(int i=0; i<n; i++) { if(arr[i+1]!=s[i]) return false; } return true; } void insert_once(int a[],int n) { int op; for(int i=1; i!=n; i++) if(a[i-1]>a[i]) { op=i; break; } for(int j=op-1; j>=0&&a[j]>a[j+1]; j--) swap(a[j],a[j+1]); return ; } void HeapAdjust( ...继续阅读 (36)

昨天的归并排序问题出在 插入排序写错了。今天改了改用在堆排序这道题上 test全过堆排序详解http://blog.csdn.net/xiaoxiaoxuewen/article/details/7570621/#include#includeusing namespace std; int n; int *arr,*s; int isheap=0; bool check() { for(int i=0; ia[i]) { op=i; break; } for(int j=op-1; j>=0&&a;[j]>a[j+1]; j--) swap(a[j],a[j+1]); return ; } void HeapAdjust(int *a,int i,int size) { //调整堆 int lchild=2*i; //i的左孩子节点序号 int rchild=2*i+1; //i的右孩子节点序号 int max=i; //临时变量 if(i<=size/2) { //如果i不是叶节点就不用进行调整 if(lchild< ...继续阅读 (19)

前序遍历（ABDECF）：typedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; struct TreeNode *parent; } TreeNode; void pre_order(TreeNode *Node) { if(Node != NULL) { printf("%d ", Node->data); pre_order(Node->left); pre_order(Node->right); } }中序遍历（DBEAFC）：typedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; struct TreeNode *parent; } TreeNode; void middle_order(TreeNode *Node) { if(Node != NULL) { middle_order(Node->left); printf("%d ", Node->d ...继续阅读 (47)

前序遍历（ABDECF）：typedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; struct TreeNode *parent; } TreeNode; void pre_order(TreeNode *Node) { if(Node != NULL) { printf("%d ", Node->data); pre_order(Node->left); pre_order(Node->right); } }中序遍历（DBEAFC）：typedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; struct TreeNode *parent; } TreeNode; void middle_order(TreeNode *Node) { if(Node != NULL) { middle_order(Node->left); printf("%d ", Node->data); m ...继续阅读 (22)

有1个3分test和1个1分test 怎么都过不去，不搞了，代码先备着。 #include <iostream> #include <algorithm> using namespace std; int n; int *arr,*s; int ismerge=0; bool check() { for(int i=0; i<n; i++) { if(arr[i]!=s[i]) return false; } return true; } void insert_once() { //进行一次插入排序 int i, j, k; for (i = 1; i < n; i++) { //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置 for (j = i - 1; j >= 0; j--) if (s[j] < s[i]) break; //如找到了一个合适的位置 if (j != i - 1) { //将比a[i]大的数据向后移 int temp = s[i]; for (k = i - 1; k ...继续阅读 (46)

有1个1分test 怎么都过不去，不搞了，代码先备着。 #include#includeusing namespace std; int n; int *arr,*s; int ismerge=0; bool check() { for(int i=0; ia[i]) { op=i; break; } for(int j=op-1; j>=0&&a;[j]>a[j+1]; j--) swap(a[j],a[j+1]); return; } void Merge(int* pDataArray, int *pTempArray, int bIndex, int mIndex, int eIndex) { int mLength = eIndex - bIndex; int i = 0; int j = bIndex; int k = mIndex; while (j < mIndex && k < eIndex) { if (pDataArray[j] <= pDataArray[k]) { pTempArray[i++] = pDataArray[j]; j++; ...继续阅读 (18)

这两天比赛遇到了一个分数的题，回想起来上课写的分数类，当时写的用上去以后漏洞百出，于是用闲暇时间又重写了一个作为模板。#include<iostream> #include<algorithm> #include<cmath> using namespace std; int gcd(int x, int y) //最大公因数（能整除x y 两数的最大整数） { x = abs(x); y = abs(y); return y == 0 ? x : gcd(y, x%y); } int lcm(int a, int b) //最小公倍数（能将a b 整除的最小整数） { a = abs(a); b = abs(b); int m; a>b?1:m=a,a=b,b=m; return a*b / gcd(a, b); } class Fractions { public: int numerator;//分子 缩写 nmrtr int denominator;//分母 缩写 dnmtr Fractions(int nmrtr = 0,int dnmtr = 1):numera ...继续阅读 (56)

这两天比赛遇到了一个分数的题，回想起来上课写的分数类，当时写的用上去以后漏洞百出，于是用闲暇时间又重写了一个作为模板。#include#include#includeusing namespace std; int gcd(int x, int y) //最大公因数（能整除x y 两数的最大整数） { x = abs(x); y = abs(y); return y == 0 ? x : gcd(y, x%y); } int lcm(int a, int b) //最小公倍数（能将a b 整除的最小整数） { a = abs(a); b = abs(b); int m; a>b?1:m=a,a=b,b=m; return a*b / gcd(a, b); } class Fractions { public: int numerator;//分子 缩写 nmrtr int denominator;//分母 缩写 dnmtr Fractions(int nmrtr = 0,int dnmtr = 1):numerator(nmrtr),denominator(dnmtr) //无参则为0 { ...继续阅读 (25)

以这道题为例子（https://www.izzx.cc/archives/221），简单描述一下Kruskal简单原理。根据代码可以看出 主要运用了 sort排序、 并查集、 结构体来配合使用Kruskal算法。并查集（https://www.izzx.cc/archives/206）先通过sort按照边的长短排序好每一条边，在Kruskal()函数计算时 先初始化各个节点的父节点为自己 再利用并查集 从最短边开始拓展一棵树，边数目越少，计算越快。图解思路 在这里：http://blog.csdn.net/todd911/article/details/9257255  47 total views, 1 views today ...继续阅读 (39)

以这道题为例子（https://www.izzx.cc/archives/221），简单描述一下Kruskal简单原理。根据代码可以看出 主要运用了 sort排序、 并查集、 结构体来配合使用Kruskal算法。并查集（https://www.izzx.cc/archives/206）先通过sort按照边的长短排序好每一条边，在Kruskal()函数计算时 先初始化各个节点的父节点为自己 再利用并查集 从最短边开始拓展一棵树，边数目越少，计算越快。图解思路 在这里：http://blog.csdn.net/todd911/article/details/9257255 751 total views, no views today ...继续阅读 (19)

方法一(来源：http://blog.csdn.net/lyy289065406/article/details/6647346)：//Memory Time //3768K 2422MS #include using namespace std; const int inf=1000000000; //10E __int64 t; //s[]数列逆序数 void compute_t(int* s,int top,int mid,int end) { int len_L=mid-top+1; int len_R=end-mid; int* left=new int[len_L+2]; int* right=new int[len_R+2]; int i,j; for(i=1;i<=len_L;i++) left[i]=s[top+i-1]; left[len_L+1]=inf; //设置无穷上界，避免比较大小时越界 for(j=1;j<=len_R;j++) right[j]=s[mid+j]; right[l ...继续阅读 (72)

利用归并排序算出t（逆序数）代码示例（来源http://blog.csdn.net/lyy289065406/article/details/6647346）：//Memory Time //3768K 2422MS #include<iostream> using namespace std; const int inf=1000000000; //10E __int64 t; //s[]数列逆序数 void compute_t(int* s,int top,int mid,int end) { int len_L=mid-top+1; int len_R=end-mid; int* left=new int[len_L+2]; int* right=new int[len_R+2]; int i,j; for(i=1;i<=len_L;i++) left[i]=s[top+i-1]; left[len_L+1]=inf; //设置无穷上界，避免比较大小时越界 for(j=1;j<=len_R;j++) right[j]=s[ ...继续阅读 (32)

/* * * * 只考虑了 正整数相加 的情况 * */ #include<iostream> #include<string> #include<cstring> using namespace std; int main() { string str1, str2; cin >> str1 >> str2; int a1[1000], a2[1000]; memset(a1, 0, 1000 * sizeof(int)); memset(a2, 0, 1000 * sizeof(int)); int len1, len2, lenmax; len1 = str1.length(); len2 = str2.length(); if (len1>len2) lenmax = len1; else lenmax = len2; int i; for (i = 0; i<len1; i++) a1[i] = str1[len1 - i - 1] - '0'; for (i = 0; i != len2; i++) a2[i] = str2[len2 - i - 1 ...继续阅读 (45)

#include <cstdio> using namespace std; int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int cal(int y, int m) { if(m != 2) return mon[m]; return mon[2]+((y%4==0 && y%100!=0) || y%400==0); } int main() { int t; cin >> t; while(t--) { int y, m, d, yy, mm, dd; scanf("%d%d%d", &y, &m, &d); scanf("%d%d%d", &yy, &mm, &dd); int num = max(0, yy-y-1)/400; int ans = num*(365*400+97); y += 400*num; while(1) { if(y == yy && m == mm && d == dd) break; ans++; d++; if(d > cal(y, m)) { ...继续阅读 (43)

#include<iostream> #include<cstdio> using namespace std; int main() { int a, b, c, d; int z, x, n, v; scanf("%d.%d.%d.%d",&a,&b,&c,&d); scanf("%d.%d.%d.%d", &z, &x, &n, &v); int k = a&z,l=b&x,m=c&n,o=d&v cout << dec << k<< "." << l << "." << m << "." << o << endl; return 0; }13 total views, no views today ...继续阅读 (42)

1.所有STL sort算法函数的名字列表:函数名    　　　　　　　　　功能描述sort 　　　　　　　  对给定区间所有元素进行排序stable_sort 　　　　对给定区间所有元素进行稳定排序partial_sort 　　　　对给定区间所有元素部分排序partial_sort_copy    对给定区间复制并排序nth_element 　　　 找出给定区间的某个位置对应的元素is_sorted               判断一个区间是否已经排好序partition 　　　　    使得符合某个条件的元素放在前面stable_partition      相对稳定的使得符合某个条件的元素放在前面 2.比较函数：当你需要按照某种特定方式进行排序时，你需要给sort指定比较函数，否则程序会自动提供给你一个比较函数vector < int > vect;sort(vect.begin(), vect.end());//此时相当于调用sort(vect.begin(), ve ...继续阅读 (49)

#include<iostream> using namespace std; int main(){ int t,n; int *p; cin >> t; for (int i = 0; i < t; i++) { cin >> n; p = new int[n]; for (int i = 0; i < n; i++) { cin >> p[i]; } int all = 0; int now = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (p[j] < p[i]) now++; } all += now; now = 0; } delete []p; cout << "Scenario #" << i+1 << ":" << endl << all << endl << endl; } return 0; }BrainmanTime Limit:1000MSMemory ...继续阅读 (50)

#include<iostream> #include<algorithm> using namespace std; int main(){ int arr[] = {0,1,2,2,3,0,0,3,4,4,5,5,5,6,6,6}; //相邻去重 需要配合sort() int *r = unique(arr,arr+14); //unique() 的返回值是去重后的尾地址 for (int i = 0; i < r-arr; i++) cout << arr[i] << " "; return 0; }15 total views, 1 views today ...继续阅读 (41)