数据结构与算法训练：第二十一弹

1. 知识点总结

耗时：2h😃

得分：83/100😅

考察知识点：暴力求解（数学）、链表操作、插入排序、堆排序、排序二叉树

2. 分题题解

2.1 1096 Consecutive Factors

这题主要是暴力破解，找出最大的连续数乘积为N的因数即可,但是第一版在做的时候没有注意到N是在1到$2^{31}$之间的，即使加了限制也是没有解决一个测试点超时的问题

#include
using namespace std;
typedef long long ll;
ll N,NN;
int len=0,cnt=0;
//输出最大的连续的数字个数，同时输出最小的连续的 
vector<ll>ans,temp;
int main(){
	scanf("%lld",&N);
	NN=N;
	for(ll i=2;i<=N;i++){
		if(N-i+1<=len){
			break;
		}
		if(NN%i==0){
			NN/=i;
			temp.push_back(i);
			cnt++;
		}else{
			if(cnt>len&&N%NN==0){
				ans=temp;
				len=cnt;
			}
			temp.clear();
			cnt=0;
			NN=N;
		}
	}
	if(cnt>len){
		ans=temp;
		len=cnt;
	}
	printf("%d\n",len);
	for(int i=0;i<len;i++){
		if(i){
			printf("*");
		}
		printf("%lld",ans[i]);
	}
	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

参考了柳神的代码，主要从连续数的最大长度进行二次限制来降低时间复杂度：

#include
using namespace std;
//枚举长度：最长不会超过12
typedef long long ll;
ll N; 
int main(){
	scanf("%lld",&N);
	int maxn=sqrt(N);
	for(int len=12;len>=1;len--){
		for(int start=2;start<=maxn;start++){
			ll temp=1;
			for(int i=start;i<=start+len-1;i++){
				temp*=i;
			}
			if(N%temp==0){
				printf("%d\n",len);
				for(int i=start;i<=start+len-1;i++){
					if(i!=start){
						printf("*");
					}
					printf("%d",i);
				}
				return 0;
			}
		}
	}
	printf("1\n%lld",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

2.2 1097 Deduplication on a Linked List

基础的链表操作，题目的意思是：将原始链表中第i(i>1)次出现的abs(数字)摘出来添加到新的链表list2中,剩余节点构成的为list1，先输出list1再输出list2

#include
using namespace std;
int N,head,Addr,Key,Next;
struct Node{
	int addr;
	int val;
	int next;
};
map<int,Node>node;
map<int,bool>vis;
vector<Node>list0,list1,list2;
void Print(vector<Node>node){
	int len=node.size();
	for(int i=0;i<len;i++){
		if(i){
			printf(" %05d\n",node[i].addr);
		}
		printf("%05d %d",node[i].addr,node[i].val);
	}
	if(len){
		printf(" -1\n");
	}else{
		//printf("\n");
	}
}
int main(){
	scanf("%d%d",&head,&N);
	for(int i=0;i<N;i++){
		scanf("%d%d%d",&Addr,&Key,&Next);
		node[Addr].addr=Addr;
		node[Addr].val=Key;
		node[Addr].next=Next;
	}
	while(head!=-1){
		list0.push_back(node[head]);
		head=node[head].next;
	}
	for(int i=0;i<list0.size();i++){
		Key=abs(list0[i].val);
		if(vis.find(Key)!=vis.end()){
			list2.push_back(list0[i]);
		}else{
			vis[Key]=true;
			list1.push_back(list0[i]);
		}
	}
//	printf("-----\n");
	Print(list1);
	Print(list2);
	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

2.3 1098 Insertion or Heap Sort

被遗忘的知识点：主要是考察堆排序和插入排序的操作步骤，但是sort用多了真的忘了怎么写堆排序了,后来看了教材补上了堆排序。

除此之外需要考虑的是插入排序的判断要在还没有排序就开始，否则会有一个测试点报错。

#include
using namespace std;
//插入排序和堆排序 :堆排序忘记了 
int N;
vector<int>v0,v1,temp;
void show(vector<int>v){
	for(int i=0;i<v.size();i++){
		if(i){
			printf(" ");
		}
		printf("%d",v[i]);
	}
}
bool insertSort(){
	temp=v0;
	bool flag=false;
	if(v0==v1){
		flag=true;
	}
	for(int i=0;i<N-1;i++){
		int sign=temp[i+1];
		if(sign>=temp[i]){
			continue;
		}
		bool in=false;
		for(int j=i+1;j>0;j--){
			if(sign<=temp[j]&&sign>=temp[j-1]){
				temp[j]=sign;
				in=true;
				break;
			}else{
				temp[j]=temp[j-1];
			}
		}
		if(!in){
			temp[0]=sign;
		}
		if(flag){
			break;
		}
		if(temp==v1){
			flag=true;
		}
	} 
	return flag;
}
void Adjust(vector<int>&v,int len,int index){
	int left=index*2+1;
	int right=index*2+2;
	int max_index=index;
	if(left<len&&v[left]>v[max_index])max_index=left;
	if(right<len&&v[right]>v[max_index])max_index=right;
	if(max_index!=index){
		swap(v[index],v[max_index]);
		Adjust(v,len,max_index);
	}
} 
bool heapSort(){
	temp=v0;
	bool flag=false;
	//初始化 
	for(int i=(N-1)>>1;i>=0;i--){
		Adjust(temp,N,i);
	}
	for(int i=N-1;i>=1;i--){
		if(temp==v1){
			flag=true;
		}
		swap(temp[0],temp[i]);
		Adjust(temp,i,0);
		if(flag){
			break;
		} 
	}
	return flag;
}
int main(){
	scanf("%d",&N);
	v0.resize(N);
	v1.resize(N);
	for(int i=0;i<N;i++){
		scanf("%d",&v0[i]);
	}
	for(int i=0;i<N;i++){
		scanf("%d",&v1[i]);
	}
	if(insertSort()){
		printf("Insertion Sort\n");
		show(temp);
	}else{
		printf("Heap Sort\n");
		heapSort();
		show(temp);
	}
	
	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

2.4 1099 Build A Binary Search Tree

首先需要构建二叉树，在构建好的基础上，先将原始数组从小到大排序，最后中序遍历将数组的值填入树中，层次遍历输出结果

#include
using namespace std;
int N,index1=0;
int root=0;
struct Node{
	int val;
	bool hasVal;
	int left,right;
};
vector<Node>nodes;
vector<int>v;
void inTravel(int root){
	if(index1>=N){
		return;
	}
	if(root==-1){
		return;
	}else{
		inTravel(nodes[root].left);
		nodes[root].val=v[index1++];
		inTravel(nodes[root].right);
	}
}
void Insert(int root){
	sort(v.begin(),v.end());
	inTravel(root);
}
void levelTravel(int root){
	queue<int>q;
	q.push(root);
	bool flag=false;
	while(!q.empty()){
		int top=q.front();
		q.pop();
		if(flag){
			printf(" ");
		}else{
			flag=true;
		}
		printf("%d",nodes[top].val);
		if(nodes[top].left!=-1){
			q.push(nodes[top].left);
		}
		if(nodes[top].right!=-1){
			q.push(nodes[top].right);
		}
	}
}
int main(){
	scanf("%d",&N);
	nodes.resize(N);
	v.resize(N);
	for(int i=0;i<N;i++){
		scanf("%d%d",&nodes[i].left,&nodes[i].right);
		nodes[i].hasVal=false;
	}
	for(int i=0;i<N;i++){
		scanf("%d",&v[i]);
	}
	Insert(root);
	levelTravel(root);
	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

3. 参考资料

1. 1096. Consecutive Factors (20)-PAT甲级真题_柳婼的博客-CSDN博客
2. 1098 Insertion or Heap Sort测试样例2_njtechlcj的博客-CSDN博客
3. 堆排序原理及其实现(C++)_大白技术控的博客-CSDN博客_堆排序c++实现