算法

算法总结

  

2020-03-25 23:07:55

算法 图的遍历 广度优先遍历 广度优先遍历实际上是借助于队列结构的先进先出的特点完成遍历任务的。目标呢是从起点出发,一层一层的向外不断扩散遍历所有节点,也有来寻找某两个节点之间的最短距离。 具体思路: 先把读到当前节点入队,然后出队,将相邻节点一次入段,与此同时不断将队头的节点出队,直到队内不再有节点时结束,实现广度优先遍历。 例子:从上往下打印出二叉树的每个节点,同层节点从左至右打印。 这个问题...

DFS序 对树进行dfsdfsdfs遍历,所形成的序列就叫做树的dfsdfsdfs序。 DFS序有一个很强的性质: 一颗子树的所有节点在DFS序内是连续的一段, 利用这个性质我们就可以将树形结构转化为线性结构 处理。 欧拉序 以下转自Pealicx 树的欧拉序是对树进行DFS的一种序列。有两种形式:1、在每个结点进和出都加进序列。2、只要到达每一个结点就把他加进序列。 例如:给出一棵树: 第一种方...

Algorithms Unlocked

算法总结

  

2020-05-05 18:31:53

Algorithms Unlocked 1.what Are Algorithms and why should you care? 1.1Algorithms-what? 1.2Algorithms-get? 1.3Algorithms-correctness 1.3Algorithms-Resource usage 2.How to Decribe and Evaluate Compute A...

数组-贪心算法 1007. Minimum Domino Rotations For Equal Row 1007. Minimum Domino Rotations For Equal Row 题目链接 In a row of dominoes, A[i] and B[i] represent the top and bottom halves of the i-th domino. (A do...

每天至少一道题目,遇到有趣的题目,就贴在这儿吧。 文章目录 信息学一本通 1195:判断整除(DP) 信息学一本通 1195:判断整除(DP) 思路:DP。 如果考虑每个数字前的符号是正是负的话,那么就是指数级的复杂度,肯定不行。就这个这个题目的范围来看,nnn的范围1e5,而kkk的范围100。我们最后要看的是最后是否会有一种组合使其%k=0\%k=0%k=0。 我们设f[i][j]f[i][j...

看到一个很好的讲树状数组的博客,就直接借鉴过来了 ^_^ 注明,转载自 https://www.cnblogs.com/findview/archive/2019/08/01/11281628.html 树状数组入门(简单的原理讲解) 树状数组可以解决什么样的问题: 这里通过一个简单的题目展开介绍,先输入一个长度为n的数组,然后我们有如下两种操作: 输入一个数m,输出数组中下标1~m的前缀和 对某...

分块算法的基本思想是通过适当的划分,预处理一部分的信息并保存下来,用空间换取时间,达到时空平衡。 分块1 给定长度为N的数列A,然后输入M行操作指令。 第一类指令形如“C l r d”,表示把数列中第l~r个数都加d。 第二类指令形如“Q X”,表示询问数列中第x个数的值。 对于每个询问,输出一个整数表示答案。 区间修改,单点查询 分块2 给定一个长...

并查集【模板】

算法总结

  

2020-08-19 03:04:09

思路 并查集:树形数据结构 find函数(查找所有结点的根结点): 关于find函数还有个路径压缩的知识点: 第二个代码优化时间的方法就叫路径压缩。 如图,求这棵树所有结点的祖先,时间复杂度取决于这棵树的深度,是O(n²)。 如图,求这棵树所有结点的祖先,时间复杂度取决于结点的个数,是O(n)。 ∴路径压缩能优化时间复杂度。 join函数(合并两个结点的根结点): 判断(两...

单片机课程设计-温度检测(STM32) 原理 KEY配置 ADC配置 中断配置 UI及主函数 原理 STM32ADC采样,我选用PA5作为ADC接口,并做了UI设计。 KEY配置 key.c key.h ADC配置 adc.h adc.c 中断配置 定时器配置 中断服务函数 UI及主函数...