星光与路人

前言 ​ 这篇文章是我学习二叉树的总结。希望本文章能给那么带来一些帮助。有错的地方也请指出，我会更正的。 二叉树简介 百度百科 我理解的概念 ​ 所谓的二叉树也就是树结构的一种，只是二叉树中的任意一个点最多只能指向两个点，并且这个指向是有方向性的也就是我们所说的“左孩子”和“右孩子”。这个方向性是很重要的，因为你在之后使用二叉树需要区别数的时候就要用到。比如堆排序和编码等。如果你不明白什么是堆排序或者编码也没关系。你只要知道二叉树每个点的“孩子”最多两个且是它是有方向性的。 树的相关术语 树的节点（node）：包含一个数据元素及若干指向子树的分支； 孩子节点（child node）：节点的子树的根称为该节点的孩子； 双亲节点：B 节点是A 节点的孩子，则A节点是B 节点的双亲； 兄弟节点：同一双亲的孩子节点； 堂兄节点：也就是同一层上的节点但是双亲不同； 祖先节点: 从根到该节点的所经分支上的所有节点 子孙节点：以某节点为根的子树中任一节点都称为该节点的子孙 节点层：根节点的层定义为1；根的孩子为第二层节点，依此类推； 树的深度：树中最大的节点层 ...

前言： ​ 本篇文章是对我学习广度优先时所刷部分题目的总结。 什么是广度优先搜索 ​ 我理解的广度优先搜索是在横向进行搜索的时候使用的方法。具体说明参照百度百科就好了。 算法应用场景 ​ 最简单明了的需要用到广度优先的题目一般是让你在一个图上找到从某点到另外一点最短的距离。这样的题目出来了就是用广度优先，虽然有时候深度优先也可以但是一般广度优先会更好。 ​ 广度优先搜索的题目意思都是 说从某点开始以特定的步骤进行移动最终到达符合条件的点。这里并不仅仅局限于图论，还可以用于其他的地方。 ​ 总而言之，凡是需要进行横向查询某一个事物的时候都可以使用广度优先搜索。 具体题目 这里我展示一些经典的题目来具体说明。 POJ 3699 1234567891011121314151617181920212223242526272829303132DescriptionBessie hears that an extraordinary meteor shower is coming; reports say that these meteors will crash i ...

前言 ​ 这篇文章我将介绍两个最大公约数的算法并讲解一些题目。有错的地方，请大家多多包涵。 介绍 ​ 最大公约数（最大公因数）指的就是可以同时被整数a和b整除的最大数（百度百科链接）。用代码来求最大公约数一般用这两种思想。 辗转相除法：也称欧几里德算法。 更相减损法：也称更向减损术。 算法实现 辗转相除法 ​ 设两个整数a和b（这里默认a>b）。a%b得到整数c，然后a=c如果换完后a<b那么a b互换后再进行上面的操作直到出现整数a被整数b整除。这时候的整数b就是最大的公约数。它的证明太复杂了，我感觉这个链接中的证明就很好了。所以我这里就不证明了。 辗转相除发的算法实现 12345678910111213141516171819int __gcd(int a, int b){ if (a%b==0)//如果可以a可以被b整除就意味着b就是最大公约数 { return b; } else { a = a % b; if (a>b)//如果a小于b那么a%b会一直为a，函数就会进行死 ...

前言 ​ 有时候我们做题会出现WA，RE，PE等错误。这可能是因为我们在细节上出错。这里我就罗列一些我在做题时常见的错误。希望可以给你一点借鉴。 Presentation Error 中文意思：输出格式错误。顾名思义，它就表示你输出结果的格式错误。 出错情况： ​ (1) 有时候题目虽然没有要求最后一个数子不带空格但是它给出的结果却会是这样。 ​ (2) 你忘记了输出空格或者换行。 解决方法： ​ 检查你的输出是否符合题意，再检查一下题目的输出样式，查明是否最后一个不带空格。 Compilation Error 中文意思：编译错误。这个错误就是表示你的代码编译不通过。 出错情况： ​ (1) 你的代码有语法错误。 ​ (2) 你的编译器和oj上的编译器不一样。因此某些你编译器上支持的语法在oj上的编译器上不支持，最终导致了CE错。 解决方法： ​ 一般oj上都有提示你错在哪里，你只要按照oj的提示修改就好了。 ​ 如果oj上面没有提示。那你只能先去你本地的编译器上调试一下，有错就修改。否则就是oj上的编译器和你的编译器支持的语 ...

前言 ​ 这篇文章是我对于自己学习拓扑排序的一个总结，如果有错的地方请大家见谅。 什么是拓扑排序 ​ 这里我就简单的说明一下。拓扑排序就是在有向图中只有出的没有进的点先排除掉。你只要遇到这类的题只要记住这个思想接下来就是空间和时间复杂度的考虑了。（如果你要在深度了解或是看我这个说明不明白的话可以自行百度，百度百科链接） ​ 在一个图中如果你要想排出所有的点，那么只有无环的有向图才可以把所有的点排出去。而且当我们进行拓扑排序的时候，由于大家想法不一样每一个人排出来的顺序都有可能不同。题目就会在这两个方面来进行设题。题目有时不一定会给你有向无环图，而且为了保证答案的唯一性题目会给你一个排序的规则。这时候你必须要看清题目的需求来进行做题。 如何实现拓扑排序 ​ 首先我们要先建立有向图。那么我们肯定要有两个数据：一个表示点，另一个表示点的指向。在这里举一些本人常用的方法，当然具体使用的时候要按照实际的需求来。 方法一：二维数组。 ​ 用行来表示图上的点，用列表示点的指向。一开始我们用0来填充这个表示图的二维数组。假设点1指向点2那么我们就可以让a[1][2]= ...

原题链接 # 青蛙公主比数字 ## 描述 青蛙公主和青蛙王子在进行一场比数字的游戏。游戏的规则如下： 1、双方在游戏开始的时候会分别得到同样数量的卡牌，每张卡牌上都会有一个整数。 2、每轮比赛中，双方各自拿出一张卡牌，然后比大小，大的那一方取胜；如果相等，则打平，双方都不算获胜。不论胜负或者平，使用的卡牌立即丢弃，不可再次使用。 3、所有卡牌用完后，游戏宣告结束。 问：青蛙公主最多可以获得多少轮比赛的胜利？最少可以获得多少轮比赛的胜利？ 输入 一个正整数n，表示案例的数量。 每组案例中，首先是一个正整数m，表示分到每个人手上的卡牌数量。然后是m个整数，表示发到青蛙公主手上的每张卡牌上的数字；接下来还有m个整数，表示发到青蛙王子手上的每张卡牌上的数字。（m<=10000） 输出 针对每组案例，输出两个整数，第一个整数表示青蛙公主最多可以获得多少轮比赛的胜利，第二个整数表示青蛙公主最少可以获得多少轮比赛的胜利。 两个整数之间有一个空格。每组案例输出完都要换行。 样例输入 1 2 50 -10 90 10 样例输出 1 0 想法： 最多 ...