当前位置：首页 > article >正文

寒假总结。

article 2025/2/25 18:36:48

这个寒假主要学了的知识点是深度优先搜索和广度优先搜索，栈和队列，动态规划，并查集，二分查找。

一、深度优先搜索（DFS）

模板

int check(参数)
{
    if(满足条件)
        return 1;
    return 0;
}
 
void dfs(int step)
{
        判断边界
        {
            相应操作
        }
        尝试每一种可能
        {
               满足check条件
               标记
               继续下一步dfs(step+1)
               恢复初始状态（回溯的时候要用到）
        }
}

1.递归只是一种实现方法，分治法和搜索都可以采用递归实现，且相对其他方法更简单，只是运行效率低且容易爆站，所以需要算法优化；
2.分治法和搜索虽然实现方式都是递归，但在分析问题时是两种不同的是思想；
3.回溯优化是指当递归满足某些条件时就可以停止递归返回上一层，所以回溯的前提是必须存在可行解保证可以走到递归边界，否则会死递归；
4.注意优化和递归边界的区别，递归边界是问题必须满足的最后条件，而优化是在题目条件的限制上来减少计算量；
5.搜索算法并不只存在于数据结构的图论中，虽然最初接触DFS和BFS时是在数据结构中，但实际这是一种算法，当问题满足可以搜索的性质时，就可以运用搜索算法；
6.全排列适合用分治解决，组合适合用搜索解决；

二、广度优先搜索（BFS）

步骤：
1.创建一个队列，将起始节点加入队列；
2.创建一个集合，用于存储已经访问过的节点；
3.从队列中取出一个节点，并将其标记为已访问；
4.访问该节点的所有相邻节点，如果相邻节点未被访问，则将其加入队列；
5.重复步骤3和步骤4，直到队列为空。

区别：

BFS：更适用于需要找到最短路径或最少步骤的场景，如地图导航、社交网络中的最短路径问题等。
DFS：更适用于需要深入探索分支的场景，如解决迷宫问题、遍历文件系统等。

三、栈和队列

栈（后进先出）：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。

步骤：

InitStack(&S)：初始化一个空栈S。
StackEmpty(S)：判断一个栈是否为空，若栈为空则返回true，否则返回false。
Push(&S, x)：进栈（栈的插入操作），若栈S未满，则将x加入使之成为新栈顶。
Pop(&S, &x)：出栈（栈的删除操作），若栈S非空，则弹出栈顶元素，并用x返回。
GetTop(S, &x)：读栈顶元素，若栈S非空，则用x返回栈顶元素。
DestroyStack(&S)：栈销毁，并释放S占用的存储空间（“&”表示引用调用）。

队列（先进先出）：允许插入的一端称为队尾，允许删除的一端称为队头。

步骤：

InitQueue(&Q)：初始化队列，构造一个空队列Q。
QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
EnQueue(&Q, x)：入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue(&Q, &x)：出队，若队列Q非空，删除队头元素，并用x返回。
GetHead(Q, &x)：读队头元素，若队列Q非空，则将队头元素赋值给x。

四、动态规划之背包问题

01背包问题

n件物品背包容量为n，每件物品只能用一次。

完全背包问题

n件物品背包容量为n，每件物品可以用无限次。

多重背包问题

完全背包问题是第i件物品可以选任意多个，而多重背包只限制了第i件物品最多选s[i]个。

分组背包

分组背包问题就是在01背包问题的基础之上，多了一个在每个组中选出最优的那个物品（或者不选）。

并查集

定义：
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。

步骤：