Dawn-K's Blog

「From ashes to the empire」

「CodeNote」 二叉树构造

二叉树构造&&遍历 基于二分搜索的启发，将查找的复杂度由朴素的O(n) 降低至 O(log n),故产生此数据结构 : 二叉树。 二叉树有两种构造方式，一种是顺序存储格式，也就是用数组来存储；另一种是链表。 他们的优缺点和线性表中几乎一样： 数组支持随机存取，实现简单，结构直观，缺点是添加删除不便，而且空间固定，不易修改，要么不足，要么浪费。 链式的结构复杂，...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 【补题】大毛数蚂蚁

大毛数蚂蚁 题干 大毛家的后花园有两个蚂蚁王国：A国和B国。现在两个王国即将开战，大毛前去观战。大毛以非人的动态视力分别数出了两个王国的蚂蚁士兵数量，记为a和b。定义双方的实力对比为a:b。大毛虽然得到了双方蚂蚁士兵的精确数量，但由于a和b数值太大，难以一眼看出它们的关系。大毛正想着怎么把蚂蚁塞进饲养员的被窝里，并没有心思去理解这么复杂的比例。因此大毛希望你能用两个不超过L的数字a’和b...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 [数据结构复习]二叉树

树和二叉树 [TOC] 树的基本术语 节点的度：节点所拥有的子树的个数。 树的度：树中各节点度的最大值。 叶子节点：度为0的节点，也称为终端节点。 分支节点：度不为0的节点，也称为非终端节点。 孩子、双亲：树中某节点子树的根节点称为这个节点的孩子节点，这个节点称为它孩子节点的双亲节点； 兄弟：具有同一个双亲的孩子节点互称为兄弟。 路径：如果树的节点...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 Trie树

Trie 树 参考资料 介绍 Trie树是一种高级数据结构,用于解决多模式串匹配问题(KMP算法是用以解决单模式串匹配),其主要思想是利用树形结构,(树上除根节点外,每一个节点都对应着一个字符),使得前缀相同的单词共用前缀部分的节点.加快匹配速度. 模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 SparseTable问题

SparseTable RMQ问题 RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。 算法 朴素（即搜索），O(n)-O(qn) online。 线段树，O(n)...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 SPFA

SPFA 简介 SPFA算法是一种求单源最短路的算法，其BFS写法是基于Ford的队列优化。但是尤其其经常被卡，所以一般不用于正权图，而是用于负权图来求最短路或者判断负环。 算法思想 主要思路是动态逼近法，也就是不断优化，直到无法优化路径。 我们设置一个队列，用于存储待优化的节点。 每次将队首节点出队，然后用其松弛邻接的结点，如果能松弛，则将可松...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 POJ1651(Multiplication Puzzle)(区间dp)

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 N数码问题

N数码问题 简介 我们先引入一个简单的问题. 首先，这里的拼图游戏是滑块拼图，类似于华容道，游戏者通过移动拼图块将拼图还原为初始形状。关于拼图，常见的有3x3，4x4，多的以至于有16x16不等。一般块数越多拼图越复杂。 如图所示,我们可以用空格与其上下左右相邻的位置的方块进行交换.给你两个局面,问这两个局面能不能互相转化. 分析 这个就是著名的N数码问题,我们为了严...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 MR素性探测

MR素性探测 简介 MR算法全称是Miller-Rabin测试,是一个非确定的算法,用于判断一个数是否是质数.虽然是一个非确定的算法,但是只要巧妙地选取参数,在一定范围内就是一个确定性的算法. 前置条件:费马小定理 1 ≡ a^(p-1) (mod p) Miller和Rabin两个人的工作让Fermat素性测试迈出了革命性的一步，建立了传说中的Miller-Rabin素性测试...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 HDU3466

HDU3466 [TOC] 中文题意 给出n个商品,以及自己的钱数m,然后以下n行,每一行给出p,q,v三个数,表示第i个商品的价格,以及最少需要多少钱才能进行购买,和收益 求最大价值 思路 根据HDU2546(饭卡)的经验,我们也不难发现这个题的产品应该也是需要排序的,但是每个商品有两个变量,这个就带来了排序的困难. 如果仅凭直觉,到底是以哪个参数排序为主,哪个参...

Posted by Dawn-K's Blog on August 6, 2019

FEATURED TAGS
CodeNote Web开发 软件工程 SpringBoot 互联网架构 垃圾回收的算法和实现 设计模式 android DAO 数据库 Python Vue Linux Unity VSCode学习 操作系统 版本控制 C++ View Java Kotlin Missing-Semester
ABOUT ME

Dawnk | 计算机本科生 | 退役ACMer | Vocaloid 爱好者

FRIENDS