【搜索】基础搜索算法(递推/递归/dfs/bfs/topsort)_bfs和dfs 递归-爱代码爱编程
递推和递归 对于一个带求解的问题,当它局限在某处边界,或者是某种特殊情况下时,答案往往是已知的。 如果能将该解答的应用场景扩大到原问题的状态空间,并且扩展扩展的每个步骤都具有相似性,可以考虑递归或者是递推求解。 以已知的“问题边界”为起点向“原问题”的正向推导的拓展方式就是递归。 以“原问题”为起点尝试寻求把状态空间缩小从而
代码编织梦想
递推和递归 对于一个带求解的问题,当它局限在某处边界,或者是某种特殊情况下时,答案往往是已知的。 如果能将该解答的应用场景扩大到原问题的状态空间,并且扩展扩展的每个步骤都具有相似性,可以考虑递归或者是递推求解。 以已知的“问题边界”为起点向“原问题”的正向推导的拓展方式就是递归。 以“原问题”为起点尝试寻求把状态空间缩小从而
二分查找:(又叫折半查找) 算法原理:对查找序列进行有序排列,每一次查找的中间状态,取当前查找区间的中间值,与查找目标比较,从而缩小查找区间,直到查找成功或者查找失败为止。 二分查找的时间复杂度分析: 二分查找的查找区间
互质与欧拉函数 定义 ,若,则称 a,b 互质 对于三个数或更多数的情况,我们把 的情况称为 a, b, c 互质。 把 称为 a,b,c 两两互质。后者显然是一个更强的条件 欧拉函数 1 ~ N 中与 N 互质的数的个数被称为欧拉函数,记为 若在算数基本定理
背包问题的分类 01背包问题 输入样例 4 5 1 2 2 4 3 4 4 5 输出样例: 8 在求选 第 i 个物品的状态转移方程的时候,我们可以取出 的最大值再加上 w[i] 不选第 i 个物品的话,状态转移方程就是 #include <iostream>
回顾一下 01 背包问题 (每个物品只能选一次) 集合划分的依据:用“最后一步”来划分 完全背包问题:每个物品可以选 0,1,2,3... 个 通过比较可以得到: 背包问题的注意事项 当空间优化到1维之后,只有完全背包问题的体积是从小到大循环的 for 物品 for 体积
如果一张无向图的 N 个结点 可以分成 A,B 两个非空集合,其中 ,并且在同一集合内的点之间都没有边相连,那么称这张无向图为一张二分图。A.B分别称为二分图的左部和右部。 二分图的判定 定理: 一张图是二分图,当且仅当图中不存在奇数环(长度是奇数的环)。 染色法判二分图 根据上述的定理,我们可以用染色法进行二分图判定
哈希表 (Hash) 哈希表又称为散列表,一般是由Hash函数(散列函数)与链表结构共同实现。与离散化的思想类似,当我们要对若干复杂信息进行统计的时候,可以用Hash函数将这些复杂的信息映射到一个容易维护的值域内。因为值域变简单、范围变小,有可能造成两个不同的原始信息被Hash函数映射为相同的值,所以我们要处理这种冲突情况。 拉链法
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择。
1.过程溢出:运算中溢出 1.过程中的最大值会达到2^32-2,溢出int范围,因此可以采用long long,8字节范围2.或者n%2==0?sum=n/2*(n+1):sum=((n+1)/2)*(n),首先使值的范围
1.不定数量输入 EOF与cin 2.n个输入,0为结尾 3.每行给定输入的数量,以0为结尾 #include <iostream> #include <vector> #include
质数 若一个正整数无法被1和它自身之外的任何自然数整除,则称该数为质数(或者素数),否则则称该正整数为合数。 在整个自然数集合中,质数的数量不是很多,分布比较稀疏,对于一个足够大的整数 N ,不超过 N 的质数大约有 N/lnN 个,即每 lnN 个数中大约有 1 个质数。 质数的判断 试除法 若一个正整数 N 为合数,
并查集 ①合并两个集合 ②查询某个元素的祖宗节点 查找 通俗地讲一个故事:几个家族进行宴会,但是家族普遍长寿,所以人数众多。由于长时间的分离以及年龄的增长,这些人逐渐忘掉了自己的亲人,只记得自己的爸爸是谁了,而最长者(称为「祖先」)的父亲已经去世,他只知道自己是祖先。为了确定自己是哪个家族,他们想出了一个办法,只要问自
Trie Trie(字典树)是一种用于实现字符串快速检索的多叉树结构。Trie树的每个结点都拥有若干个字符指针,若在插入或者检索字符串时扫描到一个字符 c,就沿着当前结点的 c 字符指针,走向该节点指向的节点。 AcWing 835. Trie字符串统计 输入样例: 5 I abc Q abc Q ab
在平时的算法考试中,我们一般不采用指针链表的方式来模拟链表 我们采用数组来模拟链表 单链表:邻接表 -> 存储图和树 AcWing 826. 单链表 输入样例: 10 H 9 I 1 1 D 1 D 0 H 6 I 3 6 I 4 5 I 4 5 I 3 4 D 6 输出样例: 6 4 6 5
迭代加深 深度优先搜索每次固定选定一个分支,不断深入,直到达到递归边界才回溯。这种策略带有一定的缺陷,假设有以下情况:搜索树每个结点的分支很多,并且问题的答案在一个较浅的结点上。如果深搜在一开始选错了分支,就很可能在不包含答案的深层子节树上浪费许多时间。 如下图所示,左半部分是问题的状态空间,菱形表示答案,那么深度优先搜索产生的搜索树如下图所示
剪枝 剪枝,是为了减少搜索树规模,尽早排除搜索树中不必要的分支的一种手段。形象的说,就像是剪掉了搜索树的枝条,故称为“剪枝”。在深度优先搜索中,有以下几类常见的剪枝方式: 1.优化剪枝顺序 在一些搜索问题中,搜索树的各个层次、各个分支之间的顺序不是固定的。不同的搜索顺序会产生不同的搜索树形态,其规模大小也相差甚远。 以下的: 在“小猫爬山”
AcWing 1112. 迷宫 输入样例: 2 3 .## ..# #.. 0 0 2 2 5 ..... ###.# ..#.. ###.. ...#. 0 0 4 0 输出样例: YES NO #include <iostream> #include <algorithm>
双向广搜 一般用于求解“最小步数”模型问题 双向广搜可以避免在深层子树上浪费时间。 在一些问题中,问题不但具有“初态”,还具有明确的“终态”,并且从初态开始搜索到终态开始逆向搜索产生的搜索树能够覆盖整个状态空间。 在这种条件下,可以采用双向广搜——从初态和终态出发各搜索一半状态,产生两棵深度减半的搜索树,在中间交会,组合成最终的答案。
AcWing 173. 矩阵距离 (多源BFS) 输入样例: 3 4 0001 0011 0110 输出样例: 3 2 1 0 2 1 0 0 1 0 0 1 在多源最短路的问题中,如果我们采用每个点的单源最短路,很大概率会超时 所以我们需要用到一个 “超级源点” 思想 建立一个虚拟源点,将所有的起点和这
Flood Fill 洪水填充(Flood fill)算法:从一个起始节点开始把附近与其连通的节点提取出或填充成不同颜色颜色,直到封闭区域内的所有节点都被处理过为止,是从一个区域中提取若干个连通的点与其他相邻区域区分开(或分别染成不同颜色)的经典算法。 可以在线性时间复杂度内,找到某个点所在的连通块 如果采用DFS,可能会出现“爆栈