2017年12月1日23:54:17，日常泡吧。

慢慢的我就喜欢上了这样天天记录我的学习状态情况。

老师强制让我每天交记录，然而我却爱上了这样的生活。

下面内容可能排版什么的可能不好，我的东西都是写在word文档里的，用了一个插件，把word里的内容转成网页的内容，可能会导致排版问题。

一步步按顺序来，今天首先做得一道题

Acm题：

爬楼梯

描述

树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数
例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级
也可以第一次走两级，第二次走一级，一共3种方法。

输入

输入包含若干行，每行包含一个正整数N，代表楼梯级数，1 <= N <= 30

输出

不同的走法数，每一行输入对应一行输出

样例输入

5

8

10

样例输出

8

34

89

按着顺序做哪知道后面还有这种简单题，很明显这题就是找顺序，把只有1级的时候有几种，2级的时候有几种，3级的时候情况有几种，知道5级。找出了一个公式fn=f（n-1）+f（n-2）。

一下两种方法实现

Java非递归实现：

此段代码执行情况：

/*

*memory: 24608kB

*time: 357ms

*codeSize:433 B

*/

Java递归实现：

执行情况：

/*

* memory:24212kB

* time:404ms

* codeSize:351 B

*/

两代码比较发现非递归实现优势明显。这个结果是oj提交后给出的结果。

Bfs和dfs

Bfs是广度优先搜索，按我目前的理解就是搜索算法。

Dfs是深度优先搜索。

Bfs

Bfs是用队里来完成搜索，bfs是先访问一个节点，然后在访问他节点相邻的节点。如果符合节点依次忘后访问。直到访问完所有的节点。

比如bfs搜索从A点开始，它有两个节点，B,C。然后A出队列。队列里就只有【B,C】了，然后找B，B里面有3个节点【D,E,F】然后B出队列，队列就有【C,D,E,F】。然后找C。C有【G,H】两个节点，然后C出列。队列里就有【D,E,F,G,H】。然后找D，有一个节点【I】，D出列。队列就有【D,E,F,G,H,I】。依次这样搜索。

Bfs的代码嘛。还不会写，现在看得到明白不明白的，主要是把这个算法弄懂了

下图是dfs的伪代码 。

Dfs

Dfs的搜索形式是栈的形式，比如A开始，A压栈顶，A开始寻找，从左边开始，A>B>D>I>K，找到K之后不条件不满足，它就会回溯，K>I>D>B，回到B节点没找完，B又开始B>E>J。就这样知道找完所有的元素为止。

以上就是我理解的中广度优先搜索和深度优先搜索。

Queue队列

队列是一种数据结构．它有两个基本操作：在队列尾部加人一个元素，和从队列头部移除一个元素就是说，队列以一种先进先出的方式管理数据，如果你试图向一个 已经满了的阻塞队列中添加一个元素或者是从一个空的阻塞队列中移除一个元索，将导致线程阻塞．在多线程进行合作时，阻塞队列是很有用的工具。工作者线程可 以定期地把中间结果存到阻塞队列中而其他工作者线线程把中间结果取出并在将来修改它们。队列会自动平衡负载。如果第一个线程集运行得比第二个慢，则第二个 线程集在等待结果时就会阻塞。如果第一个线程集运行得快，那么它将等待第二个线程集赶上来。：

主要方法

add        增加一个元索                     如果队列已满，则抛出一个IIIegaISlabEepeplian异常
remove   移除并返回队列头部的元素    如果队列为空，则抛出一个NoSuchElementException异常
element  返回队列头部的元素             如果队列为空，则抛出一个NoSuchElementException异常
offer       添加一个元素并返回true       如果队列已满，则返回false
poll         移除并返问队列头部的元素    如果队列为空，则返回null
peek       返回队列头部的元素             如果队列为空，则返回null
put         添加一个元素                      如果队列满，则阻塞
take        移除并返回队列头部的元素     如果队列为空，则阻塞

示例代码：

System.out.println("poll="+queue.poll()); //返回第一个元素，并在队列中删除

System.out.println("element="+queue.element()); //返回第一个元素

System.out.println("peek="+queue.peek()); //返回第一个元素

集合map

主要有：HashMap,TreeMap,Hashtable以及LinkedHashMap等

HashMap：我们最常用的Map，它根据key的HashCode 值来存储数据,根据key可以直接获取它的Value，同时它具有很快的访问速度。HashMap最多只允许一条记录的key值为Null(多条会覆盖);允许多条记录的Value为 Null。非同步的。

TreeMap: 能够把它保存的记录根据key排序,默认是按升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的。TreeMap不允许key的值为null。非同步的。

Hashtable: 与 HashMap类似,不同的是:key和value的值均不允许为null;它支持线程的同步，即任一时刻只有一个线程能写Hashtable,因此也导致了Hashtale在写入时会比较慢。

LinkedHashMap: 保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的.在遍历的时候会比HashMap慢。key和value均允许为空，非同步的。

把以上这些东西找出来，看了个遍，主要是给bfs和dfs用的。看完后主要记到treemap和hashmap。

Acm题：

班级排名

描述

信息科学技术学院年终评定讲学金，需要对整个年级的学生按照平均分数进行排名.
要求:根据输入的学号和平均成绩，按照平均成绩降序输出学号
如果平均成绩相同，按照输入的顺序输出。

输入

第一行为N,表示输入N位学生的信息，接着的N行输入学生信息，1<=N<=500
学生信息的格式为：学号 平均成绩
学号的长度小于10，平均成绩在1-100之间.

输出

按照平均成绩降序输出学号，如果平均成绩相同，按照输入顺序输出

样例输入

5

10948001 80

10948004 90

10948101 95

10948102 80

10948209 90

样例输出

10948101

10948004

10948209

10948001

10948102

这道题需要用到一些技巧了，参考网上C语言的代码用到了集合，在java里面就是一个类的形式。然后找了一个java代码，好好分析了一下。用到了比较器和集合。然后把网上的代码调试和分析，我也依样画葫芦写了一个。

Java实现：

比较器：

写完以上的题就好好分析了一下Comparable和Collections

发现Comparable还有一个兄弟，Compartor。

Comparable与Comparator的区别

Comparable和Comparator都是用来实现集合中元素的比较、排序的。
Comparable是在集合内部定义的方法实现的排序，位于java.util下。
Comparator是在集合外部实现的排序，位于java.lang下。

Comparator在集合（即你要实现比较的类）外进行定义的实现，而Comparable接口则是在你要比较的类内进行方法的实现。这样看来Comparator更像是一个专用的比较器。

Comparator实现了算法和数据的分离，从代码也可以看出，其实这和第一点是相辅相成的，因为Comparable依赖于某一个需要比较的类来实现。

Comparable支持自比较，自比较是指比如String等类里面本身就有CompareTo()方法，直接就可以进行String类对象的比较，这也可以从较之Comparator,Comparable中Arrays.sort()方法中只带数组参数的形式与书上例子更相似这点看出。

实现Comparable

重写方法public int compareTo(Object o)

实现Compartor

重写方法public int compareTo(Object1 o，Object2 o2)

对象排序：

Collections.sort(Object，new【排序方式的类】);这种方式是Compartor用的。

如果是Comparable可以直接Collections.sort(Object);就会根据自身类的compareTo的方式排序。

Comparable没有使用sort的话就是根据自然排序。

今日花了很多时间去看搜索，结果功力不够，真苦。