数据结构+贪心专题

• 数据结构
• • 树
  • • 这是二叉搜索树吗？
    • 树的遍历
    • 玩转二叉树(中序+前序建树 + 翻转输出)
    • 二叉搜索树的结构(map 建立二叉搜索树)
  • 完全二叉树的层序遍历(由单个遍历结果建树)
  • 并查集
  • • 排座位
    • 家庭房产
    • 部落
    • L1-020 帅到没朋友(维护集合大小的并查集)
• 线性结构
• • 链表
  • • 重排链表

数据结构

树

这是二叉搜索树吗？

题目链接
解题思路：
此题我们知道了二叉搜索树的性质：左子树小于根，右子树大于等于根。
且输入的是前序遍历，则对一个二叉树[l,r]：a[l]是根，[l+1,r]是左右子树范围。
其中，前x项若都小于根，剩下的都大于等于根：则从l+1开始的前x个就是左子树，剩下的都是右子树。如此就分出了左右子树[l1,r1][l2,r2]，然后再对左右子树递归即可。

由于输出要后序遍历，则我们只需：递归左子树，递归右子树，存根 （按照后序遍历的顺序）即可。

代码：

#include #include #include #include using namespace std;const int N = 10010;int n, flag;int t[N];vector<int>ans;void solve(int l, int r) {if (r < l)return ;int i = l + 1, j = r;if (!flag) {while (i <= r && t[i] < t[l]) // 最后停止在大于等于的位置，比正确位置后移了一位i++;while (j > l && t[j] >= t[l]) // 最后停在小于的位置，比正确位置前移了一位j--;if (i - j != 1) // 只有当两者相差1也就是中间没有元素的时候才正确return ;solve(l + 1, i - 1);solve(j + 1, r);ans.push_back(t[l]); } else {while (i <= r && t[i] >= t[l])i++;while (j > l && t[j] < t[l])j--;if (i - j != 1)return ;solve(l + 1, i - 1);solve(j + 1, r);ans.push_back(t[l]);}}int main() {int f = 0;cin >> n;for (int i = 1 ; i <= n ; ++i)cin >> t[i];solve(1, n);if (ans.size() == n) {puts("YES");for (auto x : ans) {if (f)cout << " ";cout << x;f++;}} else {ans.clear();flag = 1;solve(1, n);if (ans.size() == n) {puts("YES");for (auto x : ans) {if (f)cout << " ";cout << x, f++;}} elseputs("NO");}return 0;}

树的遍历

题目链接

解题思路：

思路：(1)通过后序遍历找到根结点，再通过根结点在中序遍历的位置找出左子树、右子树。(2)根据左子树在后序遍历结果的顺序，找到左子树的根结点，视左子树为一棵独立的树，转步骤(1)。(3)根据右子树在后序遍历结果的顺序，找到右子树的根结点，视右子树为一棵独立的树，转步骤(1)。

注意点：
函数参数需要一个创建二叉树的指针 ，和后序的左右指针，以及中序的左右指针，5个参数。

代码：

#include #include #include #include #include using namespace std;const int N = 1010;int n ;int in[N], nx[N];typedef struct node {int val;struct node *l, *r;} BitNode, *BiTree;void build(BiTree &T, int L1, int R1, int L2, int R2) {T = (BiTree)malloc(sizeof (BitNode));T->val = nx[R1];int in_root ;for (int i = L2 ; i <= R2 ; ++i)if (in[i] == nx[R1]) {in_root = i ;break;}if ( in_root - L2 != 0 ) {build(T->l, L1, L1 + in_root - L2 - 1,  L2,  in_root - 1);} elseT->l = NULL;if (R2 - in_root != 0) {build(T->r, R1 - (R2 - in_root), R1 - 1, in_root + 1, R2 );} elseT->r = NULL;}void bfs(BiTree T) {queue<BiTree>q;q.push(T);int f = 0;while (q.size()) {auto u = q.front();q.pop();if (f)cout << " ";cout << u->val;f++;if (u->l)q.push(u->l);if (u->r)q.push(u ->r);}}int main() {BiTree t;cin >> n;for (int i = 1 ; i <= n ; ++i)cin >> nx[i];for (int j = 1; j <= n ; ++j)cin >> in[j];build(t, 1, n, 1, n);bfs(t);return 0;}

玩转二叉树(中序+前序建树 + 翻转输出)

题目链接

解题思路：
题目的要求很清楚了，就是通过前序序列和中序序列将树建立出来。至于后面的镜面反转输出，我们在用BFS输出的时候，原本我们是先左子树再右子树。那么我们只需改变顺序，变成先右子树，再左子树就满足要求了。

代码：

#include #include #include #include using namespace std;const int N = 50;int n, in[N], pre[N];typedef struct node {int val;node *l, *r;} TNode, * Tree;void build(Tree &T, int L1, int R1, int L2, int R2) {T = (Tree)malloc(sizeof (TNode));T->val = pre[L1];int root;for (int i = L2 ; i <= R2 ; ++i)if (in[i] == pre[L1]) {root = i;break;}if (root - L2 != 0) {build(T->l, L1 + 1, L1 + root - L2, L2, root - 1 );} elseT->l = NULL;if (R2 - root != 0) {build(T->r, R1 - (R2 - root) + 1, R1, root + 1, R2);} elseT->r = NULL;}void bfs(Tree T) {queue<Tree>q;q.push(T);int f = 0;while (q.size()) {auto u = q.front();q.pop();if (f)cout << " ";cout << u->val;f++;if (u->r)q.push(u->r);if (u->l)q.push(u->l);}}int main() {Tree t;cin >> n;for (int i = 1; i <= n  ; ++i)cin >> in[i];for (int j =  1; j <= n ; ++j)cin >> pre[j];build(t, 1, n, 1, n);bfs(t);return 0;}

二叉搜索树的结构(map 建立二叉搜索树)

题目链接

解题思路：
这可以说是一个很复杂的数据结构的题了。对于建树方面，由于要判断是否存在节点，因此，我们用map替代数组来存节点。

1. 在插入节点的同时我们顺便记录一下每一个节点的高度。
2. 对于操作的读入，我们需要快速的读取出关键的信息。一个是标号，另一个是操作的功能。因为操作的格式是固定的，因此我们可以先读入一些字符之后再进行判断后边的读入形式，同时不用写那么多变量，我们只取我们需要的。因此就可以在字符读入的时候进行覆盖。

代码：

#include #include #include #include using namespace std;const int N = 110;int n, a[N], m, rt;struct node {int l = -1, r = -1, f = -1, h;} ;map<int, node>t;void insert(int u, int h, int v) {if (u == -1)return ;int uu = v < u ? t[u].l : t[u].r;if (uu != -1)insert(uu, h + 1, v);else {if (v < u)t[u].l = v ;elset[u].r = v;t[v].f = u, t[v].h = h;}}bool judge(int u, int a, int b, string lk) {if (lk == "root")return a == u;if (t.find(a) == t.end() || t.find(b) == t.end())return false;if (lk == "siblings")return t[a].f == t[b].f;if (lk == "parent")return t[a].l == b || t[a].r == b;if (lk == "left")return t[b].l == a;if (lk == "right")return t[b].r == a;if (lk == "level")return t[a].h == t[b].h;return false;}int main() {cin >> n >> rt;for (int i = 2 ; i <= n ; ++i) {int x ;cin >> x;insert(rt, 1, x);}cin >> m;while (m--) {string str, lk ;int a = 0, b = 0;cin >> a >> str;if (str == "and") {cin >> b >> str >> str;if (str == "siblings")lk = str;elsecin >> str >> str >> lk;} else {cin >> str >> lk;if (lk == "parent")cin >> str >> b;else if (lk != "root")cin >> str >> str >> b;}if (judge(rt, a, b, lk))cout << "Yes\n";elsecout << "No\n";}return 0;}

完全二叉树的层序遍历(由单个遍历结果建树)

题目链接

题目大意：
题目给了我们完全二叉树后序遍历的结果，让我们输出层次遍历的结果。

解题思路
对于一般的树而已单单一个后序遍历时无法建立的，但是完全二叉树例外，因为有n个节点我们就可以知道哪些节点又值，哪些没有，

• if 2 * i <= n ; 说明 i节点左节点存在 ，右节点是 2 * i + 1

因此我们可以先预处理出哪些节点存在，之后递归进行一次后序遍历，只不过在原本输出的地方变成输入。并且节点是紧挨的所有可以直接遍历输出。

代码：

#include#includeusing namespace std;const int N = 110;struct node{    int val;    int l ,r;}p[N];int n; void postOrder(int u){     if(p[u].l != 0)   postOrder(p[u].l);     if(p[u].r != 0)   postOrder(p[u].r);  cin>>p[u].val;      }int main(){    cin>>n;    for(int i = 1; i <= n ; ++i){ if(2 * i <= n)p[i].l = 2*i; if(2*i + 1 <= n)p[i].r = 2 * i + 1;    }    postOrder(1);    int f = 0;    for(int i = 1 ;i <= n ;++i){ if(f)cout<<" "; cout<<p[i].val ,f++;    }    cout<<endl;    return 0;}

并查集

排座位

题目链接

解题思路：
由于题目说了只要朋友关系具有传递性。因此我们只对朋友关系利用并查集维护。至于敌人关系我们就可以用一个邻接矩阵来存。如果是敌人就是1.

代码：

#include #include using namespace std;const int N = 110;int g[N][N];int f[N], n, m, k;int find(int x) {if (x == f[x])return x;elsereturn f[x] = find(f[x]);}void join(int x, int y) {x = find(x), y = find(y);if (x != y)f[x] = y;}int main() {cin >> n >> m >> k;for (int i = 1; i <= n ; ++i)f[i] = i;while (m--) {int a, b, c;cin >> a >> b >> c;if (c == 1)join(a, b);elseg[a][b] = g[b][a] = c;}while (k--) {int a, b;cin >> a >> b;if (find(a) == find(b) && g[a][b] == 0)cout << "No problem\n";else if (g[a][b] == 0)cout << "OK\n";else if (find(a) == find(b) && g[a][b] == -1)cout << "OK but...\n";elsecout << "No way\n";}return 0;}

家庭房产

题目链接

解题思路：

1. 关键点1是如何在维护家庭关系的同时记录最小的值：由于并查集中的祖先其实就是等价类中的代表元素，因此我们只需要在合并的时候，一直令最小的值来充当代表元素即可。
2. 对于数据的数理：起初我们用一个结构体记录下一个人的父母，房产，面积等信息。同时将这个值以及父母的值记录下来。之后，我们用另一个结构体来存下每一个家庭的值（即题目所要求的信息）我们遍历所有的值。如果标记过那么找到其代表元素，同时将代表元素标记上。这样在遍历之后，一个家庭所要求的信息都存在了代表元素上。那么我们对其进行排序后输出（由于题目是数值有大到下，因此有数值肯定比没有数值的大，因此排序完成之后有价值的值都放到了前边）即可。

代码：

#include #include #include #include using namespace std;const int N = 10100;int n ;int f[N], cnt;bool st[N];struct node {int f, m ;int child[10];int t, sum;} p[N];int find(int x) {if (f[x] == x)return x;return f[x] = find(f[x]);}void join(int x, int y) {x = find(x), y = find(y);if (x != y) {if (y < x)f[x] = y;elsef[y] = x;}}struct Date {int flag, cnt, id ;double avg,  sum;bool operator < ( Date w) {if (sum == w.sum)return id < w.id;elsereturn sum > w.sum;}} sg[N];bool cmp(Date a, Date b) {if (a.sum != b.sum)return a.sum > b.sum;elsereturn a.id < b.id;}int main() {cin >> n;for (int i = 1 ; i < N ; ++i)f[i] = i;for (int i = 1; i <= n ; ++i) {int a, b, c, k;cin >> a ;st[a] = 1;cin >> p[a].f >> p[a].m >> k;if (p[a].f != -1)join(a, p[a].f), st[p[a].f] = 1;if (p[a].m != -1)join(a, p[a].m), st[p[a].m ] = 1;for (int j = 0 ; j < k ; ++j) {int x;cin >> p[a].child[j];join(a, p[a].child[j]);st[p[a].child[j]] = 1;}cin >> p[a].t >> p[a].sum;}for (int i = 0 ; i < N ; ++i)if (st[i]) {int pa = find(i);sg[pa].flag = 1;sg[pa].id = pa;sg[pa].cnt ++;sg[pa].avg += p[i].t;sg[pa].sum += p[i].sum;}for (int i = 0 ; i < N ; ++i)if (sg[i].flag) {sg[i].avg = sg[i].avg * 1.0 / sg[i].cnt;sg[i].sum = sg[i].sum * 1.0 / sg[i].cnt;}sort(sg, sg + N - 1 );int idx = 0;for (int i = 0 ; sg[i].flag ; ++i)idx++;cout << idx << endl;for (int i = 0 ; sg[i].flag ; ++i)printf("%04d %d %.3lf %.3lf\n", sg[i].id, sg[i].cnt, sg[i].avg, sg[i].sum);return 0;}

部落

题目链接

解题思路
对于一个圈子，我们选出一个人，令其是是圈子的根，同时利用一个bool数组记录出现的值。在对每一个圈子都操作完之后，我们遍历1~N的所有数，如果记录中就加一，同时如果它直接就是根则互不相交的部落的个数加1.

代码:

#include #include using namespace std;const int N = 1e4 + 10;int n, m ;int f[N];bool st[N];int find(int x) {if (x ==  f[x])return x;elsereturn f[x] = find(f[x]);}void join(int x, int y) {x = find(x), y = find(y);if (x != y)f[x] = y;}int main() {cin >> n;for (int i = 1 ; i < N ; ++i)f[i] = i;while (n--) {int k;cin >> k;int f = 0;while (k--) {int x;cin >> x;st[x] = 1;if (!f)f = x;elsejoin(x, f);}}int cnt = 0, num = 0;for (int i = 1 ; i < N ; ++i) {if (st[i])num++;if (st[i] && f[i] == i)cnt++;}cout << num << " " << cnt << endl;cin >> m;while (m--) {int x, y;cin >> x >> y;if (find(x) == find(y))cout << "Y" << endl;elsecout << "N\n";}return 0;}

L1-020 帅到没朋友(维护集合大小的并查集)

题目链接

解题思路
我们在维护并查集的同时维护一下其祖先的集合大小，之后询问的时候，如果这个元素的祖先的集合大小为1就说明该集合只有自己。

模板

维护size的并查集：    int p[N], size[N];    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量    // 返回x的祖宗节点    int find(int x)    { if (p[x] != x) p[x] = find(p[x]); return p[x];    }    // 初始化，假定节点编号是1~n    for (int i = 1; i <= n; i ++ )    { p[i] = i; size[i] = 1;    }    // 合并a和b所在的两个集合：    size[find(b)] += size[find(a)];    p[find(a)] = find(b);

代码：

#include using namespace std;const int N = 1e5 + 10;int f[N], s[N];int n, m ;bool st[N];void init() {for (int i = 1 ; i < N ; ++i)s[i] = 1, f[i] = i;}int find(int x) {if (x == f[x])return x;elsereturn f[x] = find(f[x]);}void join(int x, int y) {x = find(x), y = find(y);if (x != y)f[x] = y, s[y] += s[x];}int main() {init();cin >> n;while (n--) {int k, a;cin >> k;for (int i = 1 ; i <= k ; ++i) {int x;cin >> x;if (i == 1)a = x;elsejoin(x, a);}}bool flag = true;int f = 0;cin >> m;while (m--) {int x;cin >> x;if ( !st[x] && s[find(x)] == 1) {if (f)cout << " ";printf("%05d", x), f++;flag = false;st[x] = 1;}}if (flag)cout << "No one is handsome";    cout<<endl;return 0;}

线性结构

链表

重排链表

题目链接

解题思路：
对于这里的地址节点，直接当成字符串处理就好多了。利用map存一个节点的前后节点。重派的操作分为奇偶来进行曹组。t一直是跟再head的后边，并连上head。而head的情况则要根据奇偶次数来判断是往前还是往后。如图

注意事项：
有的测试数据中会包含错误结点，这些结点不会被用上。

代码：

#include #include #include #include using namespace std;int n, cnt ;string rt, trail;map<string, string>pre, ne;map<string, int > ans;void get(string h) {while (h != "-1") {h = ne[h];cnt++;}}int main() {cin >> rt >> n;for (int i = 1 ; i <= n ; ++i) {string s1, s2;int x;cin >> s1 >> x >> s2;if (s2 == "-1")trail = s1;ans[s1] = x ;ne[s1] = s2;pre[s2] = s1;}get(rt); // 由于有的节点没用，不在链表中因此需要先求出真实的长度string head = rt, t = trail, tp, nx ;int f = 0;while (1) {tp = t , nx = ne[t];ne[t] = head;t = head; f++;if (f & 1) // 奇数head = pre[tp];elsehead = nx;if (f == cnt) {     ne[t] = "-1";     break; }}    string s = trail;for (int i = 1 ; i <= n ; ++i) {cout << s << " " << ans[s] << " " << ne[s] << endl;s = ne[s]; if(s == "-1")break;}return 0;}