1. 知识点总结
本次作业,涉及到的知识点有:
- STL
- 二叉树(后序+前序)
- AVL二叉平衡树
因为是凑得题目,所以按照难度分值排序
题号 | 难度 | 题型 |
---|---|---|
1120 | 🐸 | set基础 |
1121 | 🐸 | map键值判断是否存在 |
1119 | 🐸🐸😅 | 格式巨坑😓,前序+后序输出中序,会根据数据结构推解题思路即可 |
1123 | 🐸🐸🐸 | 强调AVL树,考的感觉不多,但是自己还不会盲打,打咩! |
2. 分题题解
2.1 第一题:1120 Friend Numbers (20 分)
简单题,用了set,所以不需要自己重新排序
#include<bits/stdc++.h>
using namespace std;
int N;
vector<int>num;
set<int>fid;
int countDigit(int x){
int sum=0;
while(x){
sum+=x%10;
x/=10;
}
return sum;
}
int main(){
scanf("%d",&N);
num.resize(N);
for(int i=0;i<N;i++){
scanf("%d",&num[i]);
int sum=countDigit(num[i]);
fid.insert(sum);
}
printf("%d\n",fid.size());
for(set<int>::iterator it=fid.begin();it!=fid.end();it++){
if(it!=fid.begin()){
printf(" ");
}
printf("%d",*it);
}
return 0;
}
2.2 第二题:1121 Damn Single (25 分)
碎碎念:好家伙,标题学到了,下次别出了😅,有被冒犯到
考察的是基本的图论,检查M个客人中那些单身或者已婚但是配偶未到场的即可
set存储避免了按照ID升序排序的麻烦
简单题,之前也遇到过
#include<bits/stdc++.h>
using namespace std;
int N;
int M;
map<int,int>couple;
map<int,bool>iscome;
set<int>dog;
set<int>guest;
int a,b,id;
int main(){
scanf("%d",&N);
for(int i=0;i<N;i++){
scanf("%d%d",&a,&b);
couple[a]=b;
couple[b]=a;
}
scanf("%d",&M);
for(int i=0;i<M;i++){
scanf("%d",&id);
guest.insert(id);
iscome[id]=true;
}
for(set<int>::iterator it=guest.begin();it!=guest.end();it++){
if(couple.count(*it)==0){//情侣中不存在
dog.insert(*it);
}else if(!iscome[couple[*it]]){//有情侣但是情侣不在
dog.insert(*it);
}
}
printf("%d\n",dog.size());
for(set<int>::iterator it=dog.begin();it!=dog.end();it++){
if(it!=dog.begin()){
printf(" ");
}
printf("%05d",*it);
}
return 0;
}
2.3 第三题:1119 Pre- and Post-order Traversals (30 分)
疯了,卡了一个小时的格式错误爆零,结果是最后要输出一个printf(“\n”),麻了🙄
- 注意最后输出printf(“\n”)
- 多解的情况在于preR-preL+1==2的时候,没有办法确定具体是左还是右
#include<bits/stdc++.h>
using namespace std;
int N;
bool flag=true;
vector<int>pre;
vector<int>post;
struct Node{
int val;
Node *left=NULL;
Node *right=NULL;
};
//Yes---唯一
//No--- 不唯一
Node *build(int preL,int preR,int postL,int postR){
//打印每次
// printf("post:");
// for(int i=postL;i<=postR;i++)printf("%d ",post[i]);
// printf("\n pre:");
// for(int i=preL;i<=preR;i++)printf("%d ",pre[i]);
// printf("\n");
// printf("postnum%d prenum%d\n",postR-postL+1,preR-preL+1);
if(preR-preL+1==2&&postR-postL+1==2){
flag=false;
}
if(preR<preL){
return NULL;
}else if(preR==preL){
Node *root=new Node;
root->val=pre[preL];
return root;
}
//找到公共左节点,右节点
Node *root=new Node;
root->val=pre[preL];
int k;
int preVal=pre[preL+1];
for(k=postL;k<=postR;k++){
if(post[k]==preVal){
break;
}
}
int left_num=k-postL+1;
root->left=build(preL+1,preL+left_num,postL,postL+left_num-1);
root->right=build(preL+left_num+1,preR,postL+left_num,postR-1);
return root;
}
bool ok=false;
vector<int>in;
void inTravel(Node*root){
if(root==NULL){
return ;
}
inTravel(root->left);
in.push_back(root->val);
inTravel(root->right);
}
int main(){
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=build(0,N-1,0,N-1);
//打印结果
if(!flag){
printf("No\n");
}else{
printf("Yes\n");
}
inTravel(root);
for(int i=0;i<in.size();i++){
if(i)printf(" ");
printf("%d",in[i]);
}
printf("\n");
return 0;
}
2.4 第四题: 1123 Is It a Complete AVL Tree (30 分)
二叉平衡树:说实话好久没看模板忘光了😱~
下面是看《算法笔记》找回来的一点点记忆,考前绝对是必看知识点(万一考到,基本上不看很难立马推出来┗|`O′|┛ 嗷~~)
- 完全二叉树:倒数第二层单独判断,其余层(除了倒数第一层)必须是满的
- AVL树
#include<bits/stdc++.h>
using namespace std;
int N;
vector<int>nodes;
struct Node{
int val;
int height=1;
Node*left=NULL;
Node*right=NULL;
};
int getHeight(Node*root){
if(root==NULL){
return 0;
}else{
return root->height;
}
}
int getBalanceFactor(Node*root){
return getHeight(root->left)-getHeight(root->right);
}
void updateHeight(Node* &root){
root->height=max(getHeight(root->left),getHeight(root->right))+1;
}
void L(Node* &root){
Node *temp=root->right;
root->right=temp->left;
temp->left=root;
updateHeight(root);
updateHeight(temp);
root=temp;
}
void R(Node* &root){
Node *temp=root->left;
root->left=temp->right;
temp->right=root;
updateHeight(root);
updateHeight(temp);
root=temp;
}
void build(Node* &root,int val){
if(root==NULL){
root=new Node;
root->val=val;
}else{
if(val<root->val){//插入到左子树
build(root->left,val);
updateHeight(root);//更新根节点在内树的高度
if(getBalanceFactor(root)==2){
//左边
if(getBalanceFactor(root->left)==1){//LL
R(root);
}else if(getBalanceFactor(root->left)==-1){//LR形状
L(root->left);
R(root);
}
}
}else{
build(root->right,val);
updateHeight(root);//更新根节点在内树的高度
if(getBalanceFactor(root)==-2){
//右边
if(getBalanceFactor(root->right)==-1){//RR
L(root);
}else if(getBalanceFactor(root->right)==1){//RL形状
R(root->right);
L(root);
}
}
}
}
return ;
}
//层次遍历
bool flag=true;
int max_level=-1;
void levelTravel(Node*root){
//层次遍历最后一层,要
queue<Node*>q;
root->height=1;
q.push(root);
bool ok=false;
while(!q.empty()){
Node*top=q.front();
max_level=max(max_level,top->height);
q.pop();
Node *temp;
if(top->left!=NULL){
temp=top->left;
temp->height=top->height+1;
q.push(temp);
}
if(!ok){
ok=true;
}else{
printf(" ");
}
printf("%d",top->val);
if(top->right!=NULL){
temp=top->right;
temp->height=top->height+1;
q.push(temp);
}
}
return ;
}
void check(Node*root){
queue<Node*>q;
root->height=1;
q.push(root);
bool ok=false;
int nu=0;
while(!q.empty()){
Node*top=q.front();
max_level=max(max_level,top->height);
q.pop();
Node *temp;
if(top->left!=NULL){
temp=top->left;
q.push(temp);
}
if(top->right!=NULL){
temp=top->right;
q.push(temp);
}
//判断
if(top->left==NULL&&top->right!=NULL){
flag=false;
}
if(top->height<max_level-1&&(top->left==NULL||top->right==NULL)){
flag=false;
}else if(top->height==max_level-1){
if(!nu&&(top->left==NULL||top->right==NULL)){
nu=1;
}else if(nu&&(top->left!=NULL||top->right!=NULL)){
flag=false;
}
}
}
return ;
}
int main(){
scanf("%d",&N);
nodes.resize(N);
for(int i=0;i<N;i++){
scanf("%d",&nodes[i]);
}
Node *root=NULL;
for(int i=0;i<N;i++){
build(root,nodes[i]);
}
//输出答案
levelTravel(root);
printf("\n");
check(root);
//对比
if(flag){
printf("YES\n");
}else{
printf("NO\n");
}
return 0;
}
3. 参考资料
《算法笔记》AVL树part