3.14

deepseek给出的经典必刷题.

1. 字符串处理

   • 必刷题型：字符串反转、子串查找、回文判断、字母统计（ASCII码转换）

   • 偷分技巧：直接用Python的[::-1]、split()、count()等内置函数暴力解题

2. 数组/链表操作

   • 必刷题型：数组去重、两数之和、合并有序数组、链表反转

   • 偷分技巧：遇到链表题优先用**哑结点（dummy node）**简化边界条件

3. 二叉树遍历

   • 必刷题型：前序/中序/层次遍历、求深度、对称二叉树判断

   • 万能模板：递归写法（5行代码搞定）→ 背熟框架直接套用

4. 排序与查找

   • 必刷题型：快速排序实现、二分查找变形题（找旋转数组最小值）

   • 投机策略：直接用sort()函数，除非题目明确要求手写算法

5. 动态规划（仅背经典题）

   • 必背题型：爬楼梯、斐波那契数列、背包问题（01背包）

   • 保命口诀：“递归超时就改DP，状态转移画表格！”

1.树的重心

846. 树的重心 - AcWing题库

#include<iostream>
#include<string>
#include<vector>
#include<cstring>
using namespace std;
const int N=100010,M=2*N;

int n;
int h[N],e[M],ne[M],idx,ans=N;
bool st[N];

void add(int a,int b)//头插法 
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}

int dfs(int u)
{
	int res=0,sum=1;
	st[u]=true;
	
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];//j是u的子节点 
		if(st[j]==false)
		{
			int s=dfs(j);
			res=max(res,s);
			sum+=s;
		}
	}
	
	res=max(res,n-sum);
	ans=min(res,ans);
	
	return sum;
	
}

int main()
{
	memset(h,-1,sizeof h);
	
	scanf("%d",&n);
	
	for(int i=0;i<n-1;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);add(b,a);
	}
	
	dfs(1);
	
	cout<<ans;
	return 0;
}

2.图中点的层次

AcWing 847. 图中点的层次 - AcWing

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=100010;

int h[N],e[N],ne[N],idx;
int n,m;
int d[N];

void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int dfs()
{
	memset(d,-1,sizeof d);
	
	queue<int> q;
	q.push(1);
	d[1]=0;
	
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		
		for(int i=h[t];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(d[j]==-1)
			{
				d[j]=d[t]+1;
				q.push(j);
			}
		}
	}
	return d[n];
}

int main()
{
	cin>>n>>m;
	memset(h, -1, sizeof h);
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
	}
	
	cout<<dfs();
	
	return 0;
}

易错：

• h数组要初始化为-1；