PAT甲级 1167 Cartesian Tree

阅读: 评论:0

PAT甲级 1167 Cartesian Tree

PAT甲级 1167 Cartesian Tree

已知是heaporderinorder排序,然后gen树,要判断在inorder前一个节点的左右,就可以左右依次gen,得到相应的内容;

也可以不用gen树拿到最小值和index直接保存层序遍历,最小堆,最小值就是根节点划开左右branch,使用map自动排序的特点

不能使用数组存储res(10741824, -999)

res[index] = v[pot];

会越界,要使用map存储并自动排序

update1

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int m, cnt = 0;
vector<int> arr, cp;
unordered_map<int, int> ump;
struct nod{nod *l=NULL, *r=NULL; int val=-99;};
nod *recursion(nod *root, int start) {if(root==NULL) {root = new(nod);root->val = cp[start];}if(ump[cp[start]] < ump[root->val]) root->l = recursion(root->l, start);if(ump[cp[start]] > ump[root->val]) root->r = recursion(root->r, start);return root;
}
int main(int argc, char **argv){int i, j, k, n;cin>>m;for(i = 0; i < m; i++){cin>>k;arr.push_back(k);ump[k] = i;}cp = arr;sort(cp.begin(), cp.end());nod *root = NULL;for(i = 0; i < m; i++)root = recursion(root, i);vector<int> lev;queue<nod *> q;q.push(root);while(q.size()!=0) {nod *tmp = q.front();if(tmp->l!=NULL) q.push(tmp->l);if(tmp->r!=NULL) q.push(tmp->r);lev.push_back(tmp->val);q.pop();}printf("%d", lev[0]);for(i = 1; i< lev.size(); i++) printf(" %d", lev[i]);return EXIT_SUCCESS;
}

old before 

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
#include<queue>
using namespace std;
vector<int> v;
unordered_map<int, int> mp;
struct nod{nod *l=NULL, *r=NULL; int val;};
nod* generate(nod *root, int val) {int ind = mp[val];if(root==NULL){root = new(nod);root->val = val;}else if(ind < mp[root->val])root->l = generate(root->l, val);else if(ind > mp[root->val])root->r = generate(root->r, val);return root;
}
int main(void) {int i, j, k, m, n;cin>>m;for(i = 0; i < m; i++) {cin>>n;v.push_back(n);mp[n] = i;}sort(v.begin(), v.end());nod *nd, *root = NULL;for(i = 0; i < v.size(); i++)root = generate(root, v[i]);queue<nod *>q;q.push(root);while(q.size() > 0) {nd = q.front();if(nd->l!=NULL) q.push(nd->l);if(nd->r!=NULL) q.push(nd->r);cout<<nd->val;if(q.size()!=1) cout<<" ";q.pop();}return 0;
}

update2

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int m, lev[1000];
vector<int> arr;
map<int, int> mp;
//树的遍历和产生key是split 左右branch的条件,然后将根节点入栈
void recursion(int index, int l, int r) {//最小堆,最小值就是根节点划开左右branchif(l >= r) return;int minmin = 999999999, id=l;for(int i = l; i < r; i++) {if(minmin > arr[i]) {minmin = arr[i];id = i;}}mp[index] = arr[id];recursion(index * 2, l, id);recursion(index * 2 + 1, id + 1, r);
}
int main(int argc, char **argv){int i, j, k, n, maxmax = -999999999;cin>>m;for(i = 0; i < m; i++){cin>>k;arr.push_back(k);if(maxmax < k) maxmax = k;}recursion(1, 0, m);for(map<int, int>::iterator it=mp.begin(); it!&#d(); it++) {printf("%d", it->second);if(it->second!=maxmax) printf(" ");}return EXIT_SUCCESS;
}


GitHub - ZouJiu1/PAT: 浙江大学PAT题目解答内容浙江大学PAT题目解答内容. Contribute to ZouJiu1/PAT development by creating an account on GitHub.

本文发布于:2024-01-28 09:06:53,感谢您对本站的认可!

本文链接:https://www.4u4v.net/it/17064040176323.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

标签:PAT   Tree   Cartesian
留言与评论(共有 0 条评论)
   
验证码:

Copyright ©2019-2022 Comsenz Inc.Powered by ©

网站地图1 网站地图2 网站地图3 网站地图4 网站地图5 网站地图6 网站地图7 网站地图8 网站地图9 网站地图10 网站地图11 网站地图12 网站地图13 网站地图14 网站地图15 网站地图16 网站地图17 网站地图18 网站地图19 网站地图20 网站地图21 网站地图22/a> 网站地图23