笔试面试题【1-10】
1.输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向解法：中序遍历二叉平衡树，先遍历左子树，然后遍历根节点，然后遍历右子树。所以指针需要这样调整即可：
每次需要记录他的刚刚访问过的节点pre,以及正在访问的节点now
preNodenext=nowNode
nowNodepre=preNode
2.定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)想得到最小元素那么就需要比较或者排序，很显然如果排序的话，除了天才排序算法，其他的算法时间复杂度不可能是O(1)，那么我们就得想想在push与pop的时候进行比较即可。我的思路是这样的：在栈里面的对象中添加一个属性min，记录的是：如果此对象是栈顶的话，栈里面最小的值。
举个例子就明白了：
比如说：5，6，4，2，3，8，6
5进栈，min为5
6进栈，min为5
4进栈，min为4
2进栈，min为2
3进栈，min为2
8进栈，min为2
6进栈，min为2
意思就是：对象默认的min值为自身，A进栈的时候，A的min值必须与栈顶的对象B的min值比较，如果比B的min小，A的min值不变，如果A的min值比B的min值大，更新A的min值为B的min值。
示例代码如下：
package 闭区间;import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Problem {public static final boolean START = true;public static final boolean END = false;public static void main(String[] args) {Internal internal1 = new Internal(1, 6);Internal internal2 = new Internal(2, 4);Internal internal3 = new Internal(5, 7);Internal internal4 = new Internal(5, 6);Internal internal5 = new Internal(8, 10);List<Internal> allInternal = new ArrayList<Internal>();allInternal = Arrays.asList(internal1, internal2, internal3, internal4, internal5);// 测试二testProblem1And2(allInternal);// 测试三Internal[] internals = (Internal[]) allInternal.toArray();Arrays.sort(internals);getMax(internals, 0);System.out.println("最大时间为：" + max);}/************** 华丽的分割线：下面是测试问题三 *******************/public static int current = 0;// 当前的总时长public static int max = 0;// 最大总时长private static void getMax(Internal[] internals, int index) {for (int i = index; i < internals.length; i++) {current += internals[i].getLength();max = max > current ? max : current;int next = getNextBegin(i, internals);getMax(internals, next);current -= internals[i].getLength();}}private static int getNextBegin(int i, Internal[] internals) {int j = 0;for (j = i + 1; j < internals.length; j++) {if (internals[j].getStart() > internals[i].getEnd()) {return j;}}return j;}/************** 华丽的分割线：下面是测试问题一与问题二 *******************/private static void testProblem1And2(List<Internal> allInternal) {Point[] points = new Point[allInternal.size() * 2];for (int i = 0; i < allInternal.size(); i++) {Point pointBegin = new Point(START, allInternal.get(i).getStart());Point pointEnd = new Point(END, allInternal.get(i).getEnd());points[i * 2] = pointBegin;points[i * 2 + 1] = pointEnd;}Arrays.sort(points);Point[] stack = new Point[allInternal.size() * 2];int max = -1;int stackTop = -1;// 栈顶游标for (int i = 0; i < points.length; i++) {if (points[i].flag) {stack[++stackTop] = points[i];// 进栈if (stackTop > max) {max = stackTop;}} else {Point pop = stack[stackTop--];// 出栈if (stackTop < 0) {// 如果栈为空System.out.println("合并的区间为：[" + pop.location + "," + points[i].location + "]");}}}System.out.println("最大次数为" + (max + 1));}// 坐标类static class Point implements Comparable<Point> {public boolean flag;// 是start还是endpublic int location;// 坐标public Point(boolean flag, int location) {this.flag = flag;this.location = location;}/** * 为了数组排序 */@Overridepublic int compareTo(Point o) {if (this.location > o.location) {return 1;} else if (this.location < o.location) {return -1;} else {return 0;}}@Overridepublic String toString() {return "Point [flag=" + flag + ", location=" + location + "]";}}}10.一个单链表中，如何求出倒数第n个数据？如何求出中间的数据？这是特别常见特别简单的一类问题常规做法：遍历一遍，存入数组中，直接找到第n个数据