算法唯手熟尔(PAT剩余清单 or leetcode)---希望可以日更_c语言b-1 唯手熟尔

作者：煮酒与君饮 | 2024-07-18 08:15:22

踩

c语言b-1 唯手熟尔

文章目录

算法笔记的前十章一眨眼就过去了，每天保证至少一题，题源随意，题目思路都会写在代码思路中，C指的是C with stl，我太菜了
希望可以日更吧
hexo链接：https://woaixiaoyuyu.github.io/2020/03/05/%E7%AE%97%E6%B3%95every-day/#more

2020/3/5

PAT A1119_C

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1119
//二叉树，已知前序和后序，写出一个中序的可能即可
//前序的开始的第一个应该是后序的最后一个是相等的，这个结点就是根结点
//不确定的状态可以都先当作右孩子
//如果只有一个儿子结点的话，在递归判断的时候无法知道是否是左儿子还是右儿子；
//但是如果有两个或者没有的话，是可以判断的
//如果根节点存在右子树，则post序列中倒数第二个节点(即根节点的右子树的根节点)
//在pre中的index与根节点的index差值一定大于1
struct NODE
{
   
    int data;
    struct NODE *left;
    struct NODE *right;
};
vector<int> pre,post;
bool flag=true;
NODE *create(int preL,int preR,int postL,int postR)
{
   
    if(preL>preR) return NULL;
    NODE *node =new NODE;
    node->left=NULL;
    node->right=NULL;
    node->data=pre[preL];
    if(preL==preR) return node;
    int k;
    for(k=preL+1;k<=preR;k++){
   
        if(pre[k]==post[postR-1])
            break;
    }
    int leftnum=k-preL-1;
    if(k-preL>1){
   
        node->left=create(preL+1,preL+leftnum,postL,postL+leftnum-1);
        node->right=create(preL+leftnum+1,preR,postL+leftnum,postR-1);
    }
    else{
   
        flag=false;
        node->right = create(preL+1,preR,postL,postR-1);
    }
    return node;
}

int num=0;

void inOrder(NODE *root)
{
   
    if(root==NULL) return;
    inOrder(root->left);
    if(num==0)
        printf("%d",root->data);
    else
        printf(" %d",root->data);
    num++;
    inOrder(root->right);
}

int main()
{
   
    int n;
    scanf("%d",&n);
    pre.resize(n);
    post.resize(n);
    for(int i=0;i<n;i++) scanf("%d",&pre[i]);
    for(int i=0;i<n;i++) scanf("%d",&post[i]);
    NODE *root=create(0,n-1,0,n-1);
    if(flag==true)printf("Yes\n");
	if(flag==false)printf("No\n");
	inOrder(root);
	printf("\n"); //一定要加，不加全错
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

2020/3/6

PAT A1123_C

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;
//PAT A1123
//平衡二叉树（AVL）
//生成平衡二叉树 + 层序遍历 + 判断是否为完全二叉树
//用队列层序输出时，判断第一个无孩子结点之后输出的结点是否有孩子，用来判断是否是完全二叉树
int od[30];
struct NODE
{
   
    int data;
    int height;
    struct NODE *left;
    struct NODE *right;
};

//生成一个新节点
NODE *newNode(int v)
{
   
    NODE *node=new NODE;
    node->data=v;
    node->height=1;
    node->left=node->right=NULL;
    return node;
}
//获取节点height
int getHeight(NODE *node)
{
   
    if(node==NULL) return 0;
    else return node->height;
}
//计算节点平衡因子
int getBalance(NODE *node)
{
   
    return getHeight(node->left)-getHeight(node->right);
}
//更新节点高度
void updateHeight(NODE *node)
{
   
    node->height=max(getHeight(node->left),getHeight(node->right))+1;
}
//左旋
void L(NODE* &node)
{
   
    NODE* temp=node->right;
    node->right=temp->left;
    temp->left=node;
    updateHeight(node);
    updateHeight(temp);
    node=temp;
}
//右旋
void R(NODE* &node)
{
   
    NODE* temp=node->left;
    node->left=temp->right;
    temp->right=node;
    updateHeight(node);
    updateHeight(temp);
    node=temp;
}

void insert(NODE* &root,int v)
{
   
    if(root==NULL){
   
        root=newNode(v);
        return;
    }
    if(v<root->data){
   
        insert(root->left,v);
        updateHeight(root);
        if(getBalance(root)==2){
   
            if(getBalance(root->left)==1){
   
                R(root);
            }
            else if(getBalance(root->left)==-1){
   
                L(root->left);
                R(root);
            }
        }
    }
    else{
   
        insert(root->right,v);
        updateHeight(root);
        if(getBalance(root)==-2){
   
            if(getBalance(root->right)==-1){
   
                L(root);
            }
            else if(getBalance(root->right)==1){
   
                R(root->right);
                L(root);
            }
        }
    }
}

NODE* create(int data[],int n)
{
   
    NODE *root=NULL;
    for(int i=0;i<n;i++){
   
        insert(root,data[i]);
    }
    return root;
}

int num=0;
bool complete=true;
bool havechild=true;
void levelOrder(NODE *root)
{
   
    queue<NODE*> q;
    q.push(root);
    while(!q.empty()){
   
        NODE *node=q.front();
        q.pop();
        if(node->left!=NULL){
   
            q.push(node->left);
            if(!havechild) complete=false;
        }
        else havechild=false;
        if(node->right!=NULL){
   
            q.push(node->right);
            if(!havechild) complete=false;
        }
        else havechild=false;
        if(num==0) printf("%d",node->data);
        else printf(" %d",node->data);
        num++;
    }
    printf("\n");
}

int main()
{
   
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&od[i]);
    //生成平衡二叉树
    NODE *root=create(od,n);
    //层序遍历
    levelOrder(root);
    if(complete) printf("YES\n");
    else printf("NO\n");
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181

PAT A1115_C

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1115
//建立一个二叉树
//统计最后两层的节点的数量
struct NODE
{
   
    int data;
    int layer;
    struct NODE* left;
    struct NODE* right;
};
const int maxn=1010;
int od[maxn];

NODE* newNODE(int v)
{
   
    NODE* node=new NODE;
    node->data=v;
    node->layer=1;
    node->left=node->right=NULL;
    return node;
}

void insert(NODE* &root,int v)
{
   
    if(root==NULL){
   
        root=newNODE(v);
        return;
    }
    if(v<=root->data){
   
        insert(root->left,v);
    }
    else{
   
        insert(root->right,v);
    }
}

NODE* create(int data[],int n)
{
   
    NODE *root=NULL;
    for(int i=0;i<n;i++){
   
        insert(root,data[i]);
    }
    return root;
}

int level[maxn]={
   0}; //记录每一行的节点数
int deep=-1;
void levelOrder(NODE* root)
{
   
    queue<NODE*> q;
    q.push(root);
    while(!q.empty()){
   
        NODE* node =q.front();
        deep=max(deep,node->layer);
        q.pop();
        if(node->left!=NULL){
   
            node->left->layer=node->layer+1;
            q.push(node->left);
        }
        if(node->right!=NULL){
   
            node->right->layer=node->layer+1;
            q.push(node->right);
        }
        level[node->layer]++;
    }
}

int main()
{
   
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
   
        scanf("%d",&od[i]);
    }
    NODE* root=create(od,n);
    levelOrder(root);
    //printf("%d",level[deep]);
    //printf("%d",level[deep-1]);
    printf("%d + %d = %d\n",level[deep],level[deep-1],level[deep]+level[deep-1]);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

PAT A1114_C

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
//去TY的并查集，真复杂，直接邻接表
using namespace std;
typedef long long LL;
const int maxn = 10000;
struct Person{
    int e,a;}per[maxn]; //存放住宅数，住宅面积
struct Family{
   
    int id,member;
    double avga,avge;
    Family(int a,int b,double c,double d): id(a), member(b), avge(c), avga(d) {
   }
};
bool table[maxn],vis[maxn];
vector<int> adj[maxn];
vector<Family> ans;
bool cmp(Family a,Family b){
   
    return a.avga!=b.avga?a.avga>b.avga:a.id<b.id;
}
void DFS(int u,LL &sumE,LL &sumA,int &member){
   
    vis[u] = 1;
    member++;
    sumE += per[u].e;
    sumA += per[u].a;
    for(int i=0;i<adj[u].size();i++){
   
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】