数据结构与算法

参考姥姥：

https://github.com/callmePicacho/Data-Structres/blob/master/README.md

▶

序章

Now,Time to take a leap of FAITH !

关于分治法的时间复杂度证明：

[SCU练习平台题解]课堂练习

练习
PTA
2024/09/05:
NO1，最大子列和问题
在线算法，秒辣！

▶

补：分治法

#include<bits/stdc++.h>
using namespace std;

int Max3(int A,int B,int C)
{
	return A > B ? A > C ? A : C : B > C ? B : C;
}
int DivideAndConquer(int List[],int left ,int right)
{
	int MaxLeftSum,MaxRightSum;
	int MaxLeftBorderSum,MaxRightBorderSum;
	
	int LeftBorderSum,RightBorderSum;
	int center,i;
	
	if(left == right)
	{
		if(List[left] > 0)
		{
			return List[left];
		}else{
			return 0;
		}
	}
	
	center = (left + right) / 2;
	
	MaxLeftSum = DivideAndConquer(List,left,center);
	MaxRightSum = DivideAndConquer(List,center+1,right);
	
	MaxLeftBorderSum = 0,LeftBorderSum = 0;
	for(i = center;i >= left;i --){
		LeftBorderSum += List[i];
		if(LeftBorderSum > MaxLeftBorderSum)
		{
			MaxLeftBorderSum = LeftBorderSum;
		}
	}
	
	MaxRightBorderSum = 0,RightBorderSum = 0;
	for( i = center + 1;i <= right; ++ i)
	{
		RightBorderSum += List[i];
		if(RightBorderSum > MaxRightBorderSum)
		{
			MaxRightBorderSum = RightBorderSum;
		}
	}
	
	return Max3( MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum);
}
int MaxSubseqSum3(int List[],int N)
{
	return DivideAndConquer(List,0,N-1);
}

这题非常经典，分治法当然不是最好的。
“在线算法”实际上是贪心的方法，另一种办法是动态规划

▶

动态规划

#include<bits/stdc++.h>
using namespace std;
int dp[100005];
int main()
{
	int t;cin >> t;
	for(int k = 1;k <= t;++ k)
	{
		int n;cin >> n;
		for(int i = 1;i <= n;++ i)cin >> dp[i];
		int start = 1,end = 1,p = 1;
		int maxsum = dp[1];
		for(int i = 2;i <= n;++ i){
			if(dp[i-1] + dp[i] >= dp[i])
				dp[i] = dp[i-1] + dp[i];
			else p = i;
			if(dp[i] > maxsum)
			{
				maxsum = dp[i];start = p;end = i;
			}
		}
		printf("%d\n",maxsum);
	}
	
	
	return 0;
}

但是时间复杂度是O(n*m)肯定会超时，考虑使用单调队列进行优化：

<div class="fold">  <div class="fold-title fold-info collapsed" data-toggle="collapse" href="#collapse-0ad24a9b" role="button" aria-expanded="false" aria-controls="collapse-0ad24a9b">    <div class="fold-arrow">▶</div>动态规划+前缀和+单调队列  </div>  <div class="fold-collapse collapse" id="collapse-0ad24a9b">    <div class="fold-content">      
#include<bits/stdc++.h>
using namespace std;
deque<int> dq;
int s[100005];
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++ i)scanf("%lld",&s[i]);
	for(int i = 1;i <= n;++ i)s[i] = s[i] + s[i-1];
	int ans = -1e8;
	dq.push_back(0);
	
	for(int i = 1;i <= n;++ i)
	{
		while(!dq.empty()&&dq.front() < i - m)dq.pop_front();
		if(dq.empty())ans = max(ans,s[i]);
		else ans = max(ans,s[i] - s[dq.front()]);
		while(!dq.empty() && s[dq.back()] >= s[i])dq.pop_back();
		dq.push_back(i);
	}
	
	return 0;
}
<p><strong>由此可见，将数据结构与算法结合，威力无穷</strong></p>    </div>  </div></div>

NO2,多项式的加法和乘法

▶

解答

#include<bits/stdc++.h>
using namespace std;
#define maxn 10010
int a[maxn+1];
int b[maxn+1];
int c[maxn+1];
int d[maxn+1];
void getmul()
{
	int flag = 0;
	for(int i = 0;i <= maxn;++ i)
	{
		if(a[i] != 0)
		{
			for(int j = 0;j <= maxn;++ j)
			{
				if(b[j] != 0)
				{
					d[i+j] += a[i] * b[j];
				}
			}
		}
	}
	int mark = 0;
	for(int i = 0;i <= maxn;++ i)
	{
		if(d[i] != 0)
		{
			mark = i;
			break;
		}
	}
	for(int i = maxn;i >= 0;i --)
	{
		if(d[i] != 0)
		{
			flag = 1;
			cout << d[i] << " " << i << " \n"[i==mark];	
		}
	}
	if(flag == 0)
	{
		cout << "0 0" << endl;
	}
}
void getsum()
{
	int flag = 0;
	for(int i = 0;i <= maxn;++ i)
	{
		c[i] = a[i] + b[i];
	}
	int mark = 0;
	for(int i = 0;i <= maxn;++ i)
	{
		if(c[i] != 0)
		{
			mark = i;
			break;
		}
	}
	for(int i = maxn;i >= 0;i --)
	{
		if(c[i] != 0)
		{
			flag = 1;
			cout << c[i] << " " << i << " \n"[i == mark];	
		}
	}
	if(flag == 0)
	{
		cout << "0 0" << endl;
	}
}
int main()
{
	int num1,num2;
	cin >> num1;
	while(num1--)
	{
		int x,y;
		cin >> x >> y;
		a[y] = x;
	}
	cin >> num2;
	while(num2--)
	{
		int x,y;
		cin >> x >> y;
		b[y] = x;
	}
	getmul();
	getsum();
	
	return 0;
}

4 数组×40044 字节/数组=160176 字节
这大约是 156.5 KB。
这样虽然过了，但是没考虑过空间浪费。

#include<bits/stdc++.h>
using namespace std;
#define maxn 10010
typedef struct LNode *List;
struct data{
	int x;
	int y;
};
struct LNode{
	struct data Data[maxn];	
	int Last;
};
List init()
{
	List L = (List)malloc(sizeof(struct LNode));
	L->Last = -1;
	return L;
}
void insert(int x,int y,List L)
{	
	L->Last++;
	L->Data[L->Last].x = x;
	L->Data[L->Last].y = y;
	return ;
}
//int Length(List L){
//	return L->Last+1;
//} 
void getsum(List L1,List L2)
{
	int pointer1 = 0;
	int pointer2 = 0;
	while(pointer1 <= L1->Last && pointer2 <= L2->Last)
	{
		if(L1->Data[pointer1].y > L2->Data[pointer2].y)
		{
			printf("%d %d ",L1->Data[pointer1].x,L1->Data[pointer1].y);
			pointer1++;
		}else if(L1->Data[pointer1].y < L2->Data[pointer2].y)
		{
			printf("%d %d ",L2->Data[pointer2].x,L2->Data[pointer2].y);
			pointer2++;
		}else{
			printf("%d %d ",L1->Data[pointer1].x + L2->Data[pointer2].x,L1->Data[pointer1].y);
			pointer1++;
			pointer2++;
		}
	}
	if(pointer1 <= L1->Last)
	{
		printf("%d %d ",L1->Data[pointer1].x,L1->Data[pointer1].y);
		pointer1++ ;
	}else if(pointer2 <= L2->Last)
	{
		printf("%d %d ",L2->Data[pointer2].x,L2->Data[pointer2].y);
	    pointer2++ ;
	}
}
//void getmul(List L1,List L2)
//{
//	int pointer1 = 0;
//	int pointer2 = 0;
//	for(;pointer1 <= L1->Last;pointer1++ )
//	{
//		for(;pointer2 <= L2->Last;pointer2++ )
//		{
//			
//		}
//	}
//}
int main()
{
	int num1,num2;
	cin >> num1 ;
	List L1 = init();
	while(num1--)
	{
		int x,y;
		cin >> x >> y;
		insert(x,y,L1);
	}
	cin >> num2;
	List L2 = init();
	while(num2--)
	{
		int x,y;
		cin >> x >> y;
		insert(x,y,L2);
	}
//	for(int i=0;i<Length(L1);i++)
//		printf("%d %d ",L1->Data[i].x,L1->Data[i].y);
//	printf("\n");
//	for(int i=0;i<Length(L2);i++)
//		printf("%d %d ",L2->Data[i].x,L2->Data[i].y);
	printf("\n");
	getsum(L1,L2);
//	getmul();
	
	return 0;
}

这段中尝试使用了动态数组实现顺序表的办法，完成了多项式加法

• 优势：相比上一份静态数组，处理数据时拿多少用多少。比如同样一组输入，空间占用从165kB降至不到100B。
• 缺点：虽然实现，但是代码中有几个问题：
• 1.在线算法，算一条输出一条，不灵活，这也解释了为什么乘法部分没有继续写。更好的做法是再开一个数组存答案。
• 2.输出部分未封装，题目部分有格式要求，较复杂的输出适合单独封装一个函数做输出。
• 3.空间连续，这是开数组和开链表的重要区别：数组空间必须物理上连续，而实际上计算机内存物理上并不连续，你以为的连续实际上是操作系统给出的抽象层，造成了空间连续的假象（逻辑上连续），这就会在要求比较苛刻的情况中浪费空间。

Tips：看懂一份代码不难，重要的是如何独立写出来。一个好办法是阅读注释，注释和编写过程中的调试遗迹是好东西，编写边调试即可化难为简。
可惜的是，大多数题解将调试遗迹删去。

最优解法：链表

#include<stdio.h>
#include<stdlib.h>
typedef struct Node *List;
struct Node{
	List Next;
	int z;   // 指数 
	int x;  // 系数 
};

// 读入链表 
List Read(){
	List L = (List)malloc(sizeof(struct Node));
	List head = L;
	int n;
	int i=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		int x;
		int z;
		List t = (List)malloc(sizeof(struct Node));
		scanf("%d %d",&x,&z);
		t->x = x;
		t->z = z;
		L->Next = t;
		L = L->Next;
	}
	L->Next = NULL;
	return head->Next;
}

// 实现加法运算 
List addition(List L1,List L2){
	List tmpL1 = L1;
	List tmpL2 = L2;
	List add=(List)malloc(sizeof(struct Node));
	add->Next = NULL;
	List head = add;
	List t;
	while(tmpL1 && tmpL2){
		t = (List)malloc(sizeof(struct Node));
		if(tmpL1->z == tmpL2->z){  //指数相等，系数相加  
			t->x = tmpL1->x + tmpL2->x;
			t->z = tmpL1->z;
			tmpL1 = tmpL1->Next;
			tmpL2 = tmpL2->Next;
		}else if(tmpL1->z < tmpL2->z){   // L2 结点指数更大，把 L2 结点加入链表 
			t->x = tmpL2->x;
			t->z = tmpL2->z;
			tmpL2 = tmpL2->Next;
		}else if(tmpL2->z < tmpL1->z){   // L1 结点指数更大，把 L1 结点加入链表 
			t->x = tmpL1->x;
			t->z = tmpL1->z;
			tmpL1 = tmpL1->Next;
		}
		add->Next = t;
		add = add->Next; 
	}
	if(tmpL1)   // 若 L1 不等于 NULL，将剩下结点加入其后 
		add->Next = tmpL1;
	else if(tmpL2)  // 同理 
		add->Next = tmpL2;
	return head->Next; // head 结点只有指针域存值 
}

// 实现乘法运算 
List multiplication(List L1,List L2){
	List tmpL1 = L1;
	List tmpL2 = L2;
	List mul=(List)malloc(sizeof(struct Node));
	mul->Next = NULL;
	List head = mul;
	List t;
	for(;tmpL1;tmpL1=tmpL1->Next)
		for(tmpL2 = L2;tmpL2;tmpL2=tmpL2->Next){
			t = (List)malloc(sizeof(struct Node));
			t->x = tmpL1->x * tmpL2->x;  // 系数相乘
			t->z = tmpL1->z + tmpL2->z;  // 指数相加
			t->Next = NULL;
			head = addition(t,mul);  // 将新增结点和之前已经排好序的结点排序 
			mul = head; // 重新确定开头 
		}
	return head;
}
void Print(List L){
	List t = L;
	int flag = 1;
	for(;t;t = t->Next){
		if(!flag && t->x)   //控制空格输出
			printf(" ");
		if(t->x){   // 如果系数为 0，不输出 
			printf("%d %d",t->x,t->z);
			flag =0;		
		}
	}
	if(flag)
		printf("0 0");
	printf("\n");
}
int main(){
	List L1,L2,add,mul;
	L1 = Read();
	L2 = Read();
	add = addition(L1,L2);
	mul = multiplication(L1,L2);
	Print(mul);
	Print(add);
	return 0;
} 

0908
NO3,树的同构

▶

同构。

#include<iostream>
#include<malloc.h>
#define null -1
using namespace std;
struct TreeNode{
	char data;    // 存值 
	int left;   // 左子树的下标 
	int right;  // 右子树的下标 
}T1[10],T2[10];
// 返回根结点 
int create(struct TreeNode T[]){
	int n;
	int root = 0;
	char left,right;
	cin>>n;
	if(!n)
		return null;
	for(int i=0;i<n;i++){
		cin>>T[i].data>>left>>right;
		if(left=='-')
			T[i].left = null;
		else{
			T[i].left = left-'0';
			root -= T[i].left;
		}
		if(right=='-')
			T[i].right = null;
		else{
			T[i].right = right-'0';
			root -= T[i].right;
		}
		// 0 累加到 n-1 
		root +=i;	
	}
	return root;
}
// 判断是否同构
bool judge(int R1,int R2){
	if(R1 == null && R2 == null)   // 都为空 
		return true;
	if(R1 == null && R2 != null || R1 != null && R2 == null)    // 一个为空，一个不为空
		return false;
	if(T1[R1].data != T2[R2].data)   // 值不同
		return false;
	if((T1[R1].left != null && T2[R2].left != null )&&(T1[T1[R1].left].data == T2[T2[R2].left].data))  // 左儿子不为空且值相等
		return judge(T1[R1].left,T2[R2].left) && judge(T1[R1].right,T2[R2].right);
	else   // 左儿子不为空且值不等  或者 某一个左儿子为空 
		return judge(T1[R1].right,T2[R2].left) && judge(T1[R1].left,T2[R2].right);
} 
int main(){
	int R1,R2;
	R1 = create(T1);
	R2 = create(T2);
	if(judge(R1,R2))
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
} 

感觉难度明显上升了~，已经听开小白专场了。。。