PTA甲级模拟第一d:1132-1135

pta主要是打基础的哈,练完了考虑去刷leetcode,希望尽快练完叭~

本次模拟题目：甲级1132-1135
失分点：1133和1135

1133 Splitting A linked List (25 分)
22/25 模拟得分

#include
using namespace std;
//负数 0-k 其他
const int maxn=1000000;
struct Node{
	int addr;
	int value;
	int next=-1;
}nodes[maxn];
int n,k,head;
void show(){
	int p=head;
	while(p!=-1){
		printf("%05d %d %05d",nodes[p].addr,nodes[p].value,nodes[p].next);
		//顺序 
		p=nodes[p].next;
		printf("n");
	}
}
int addr,value,nextnode;
//下面主要是重新排序
struct newNode{
	int id;
	int addr;
	int value;
	int next=-1;
	int kind;
}; 
vectornewnodes; 
bool cmp(newNode a,newNode b){
	if(a.kind!=b.kind){
		return a.kind 
订正思路
 
 
 
利用vector本身的性质，由题意可知将list分成三段重新排序，那么第一步是按照list顺序重新输出list保存，注意，保存的时候调用三段list，这样之后合并就可以按照自己想要的顺序。
 
 
#include
using namespace std;
const int maxn=101100;
struct Node{
	int addr;
	int value;
	int next;
}nodes[maxn];
int head,n,k;
int addr,value,nextid;
vectorv1,v2,v3;
int main(){
	scanf("%d%d%d",&head,&n,&k);
	for(int i=0;i 
2. 1135红黑树 
1135 Is It A Red-Black Tree (30 分)
 诚实来讲,不看任何资料的话,应该拿不到10+,悄咪咪看了模板才勉强上20
 
模板的话,涉及到中序遍历+()遍历的树结构的重构问题
 
21/30 模拟得分
 
#include
using namespace std;
//红黑树的判别 :21分 
int k; 
int n;
vectornodes;//前序遍历
vectormidnodes;//中序遍历
struct Node{
	int value;
	Node* lchild;
	Node* rchild;
}; 
Node* Create(int posL,int posR,int inL,int inR){
	//中序遍历和前序遍历确定二叉树
	if(posL>posR){
		return NULL;//递归边界 
	}
	Node * root=new Node;
	//根节点是前序遍历的第一个结点
	root->value=nodes[posL];
	
	int l;
	for(l=inL;l<=inR;l++){
		if(root->value==midnodes[l]){
			break;
		}
	} 
	//中序：左子树元素个数
	int left_num=l-inL;
	root->lchild=Create(posL+1,posL+left_num,inL,l-1);//left
	root->rchild=Create(posL+left_num+1,posR,l+1,inR);//right
	return root;
}
//前序遍历
int PreTravel(Node *root) {
	if(root==NULL)return 1;
	if(root->value<0&&(root->lchild!=NULL&&root->lchild->value<0||root->rchild!=NULL&&root->rchild->value<0)){
		return 0;
	}else if(root->lchild!=NULL&&root->rchild!=NULL&&root->lchild->value*root->rchild->value<0){
		return 0;
	}
	else return PreTravel(root->lchild)*PreTravel(root->rchild);
}

bool cmp(int a,int b){
	return abs(a)value<0) {
		return false;
	}
	//遍历：非黑即红，红色结点的两个孩子都是黑色的
	if(PreTravel(root)==0)return false;
	//对于每一个结点，从该节点到比它小的所有叶子结点所经过的黑色结点都相同 
	return true;
} 
int main(){
	scanf("%d",&k);
	while(k--){
		scanf("%d",&n);
		nodes.resize(n);
		midnodes.resize(n);
		for(int i=0;i 
订正思路
 
 
 
前序遍历不需要结合中序遍历求解,直接一边输入一遍插入建树,判断的方法这边首先判断是否存在红节点的子节点中出现红节点(非法),接着判断到达每一个结点时,该结点到叶子结点路线上的黑节点是否相等,不相等则判定为非法
 
 
参考了柳神的代码,觉得自己思路好冗余
 
#include
using namespace std;
//首先定义树结点
struct Node{
	int value;
	Node *lchild;
	Node *rchild;
}; 
vectorvec;
int k,n;
//value<0 红色结点
Node *build(Node *root,int value){
	if(root==NULL){
		root=new Node();
		root->value=value;
		root->lchild=root->rchild=NULL;
	}else if(abs(value)value)){
		root->lchild=build(root->lchild,value);
	}else{
		root->rchild=build(root->rchild,value);
	}
	return root;
} 
bool isok1(Node*root){
	if(root==NULL)return true;
	if(root->value<0){
		if(root->rchild!=NULL&&root->rchild->value<0)return false;
		if(root->lchild!=NULL&&root->lchild->value<0)return false;
	}
	return isok1(root->lchild)&&isok1(root->rchild);
}
int getNum(Node*root){
	if(root==NULL)return 0;
	int l=getNum(root->lchild);
	int r=getNum(root->rchild);
	return root->value>0?max(l,r)+1:max(l,r); 
}
bool isok2(Node*root){
	//一个结点到叶子结点经过的黑色节点个数相同
	if(root==NULL)return true;
	int l=getNum(root->lchild);
	int r=getNum(root->rchild);
	if(l!=r)return false;
	return isok2(root->lchild)&&isok2(root->rchild);
}

int main(){
	scanf("%d",&k);
	for(int i=0;i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5714325.html