目录
1.数组中重复的数字
拓展：不修改数组找出重复数字
2.二维数组中的查找
3.替换空格
4.从尾到头打印链表
5.重建二叉树
6.二叉树的下一个节点（！！）
7.用两个栈实现队列
拓展：用两个队列实现一个栈
1.数组中重复的数字
题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
分析：从头到尾依次扫描该数组，当扫描到下标为 i 的数字时，首先比较这个数字是否等于 i 。若等于，直接扫描下一个；不等于则将其与第a[i]个数字比较，如果相等则找出了第一个重复数字，不相等则交换两者的位置。时间复杂度：O（n）
public boolean duplicate(int[] numbers,int length,int [] duplication) {if(numbers == null || numbers.length == 0)return false;for(int i = 0;i < numbers.length;i++){if(numbers[i] != i){if(numbers[numbers[i]] == numbers[i]){duplication[0] = numbers[i];return true;}int temp = numbers[i];numbers[i] = numbers[temp];numbers[temp] = temp;}}return false;}
拓展：不修改数组找出重复数字
题目：在一个长度为n+1的数组里的所有数字都在1到n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字2或者3.
分析：数组长度为n+1，而数字只从1到n，说明必定有重复数字。可以由二分查找法拓展：把1~n的数字从中间数字m分成两部分，若前一半1~m的数字数目超过m个，说明重复数字在前一半区间，否则，在后半区间m+1~n。每次在区间中都一分为二，直到找到重复数字。时间复杂度：O（nlogn）
public int getDuplication(int[] numbers) {if(numbers == null || numbers.length == 0)return -1;int low = 1,high = numbers.length - 1;while(low <= high){int mid = (low + high) / 2;int count = countRange(numbers,low,mid);if(low == high){if(count > 1)return low;elsereturn -1;}if(count > mid - low + 1)high = mid;elselow = mid + 1;}return -1;}private int countRange(int[] numbers, int low, int high) {int count = 0;for(int i = 0;i < numbers.length;i++){if(numbers[i] >= low && numbers[i] <= high)count++;}return count;}
2.二维数组中的查找
题目：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
分析：首先选取数组中右上角的数字。如果该数字等于要查找的数字，则结束；如果该数字大于要查找的数字，则剔除这个数字所在的列；否则剔除这个数字所在的行。选取数组左下角的数字也可。
public boolean Find(int target, int [][] array) {if(array == null || array.length == 0)return false;int col = array[0].length - 1;int row = 0;while(col >= 0 && row < array.length){if(array[row][col] == target)return true;if(array[row][col] > target)col--;elserow++;}return false;}
3.替换空格
题目：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
分析：先遍历一次字符串，统计出字符串中空格的总数。然后从字符串的后面开始替换和复制，准备两个指针，一个指向原始字符串的末尾，一个指向替换之后的字符串末尾。
public String replaceSpace(StringBuffer str) {if(str == null)return "";int count = 0;for(int i = 0;i < str.length();i++){if(str.charAt(i) == ' ')count++;}int i = str.length() - 1;int j = str.length() + count * 2;str.setLength(j);j--;while(i != j){if(str.charAt(i) == ' '){str.setCharAt(j--,'0');str.setCharAt(j--,'2');str.setCharAt(j--,'%');}elsestr.setCharAt(j--,str.charAt(i));i--;}return String.valueOf(str);}
4.从尾到头打印链表
题目：输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
分析：典型的“后进先出”，可以用栈来实现。
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {ArrayList<Integer> list = new ArrayList<>();Stack<Integer> stack = new Stack();if(listNode == null)return list;ListNode cur = listNode;while(cur != null){stack.push(cur.val);cur = cur.next;}while(! stack.empty()){list.add(stack.pop());}return list;}
5.重建二叉树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
分析：前序遍历的第一个结点为二叉树的根结点，然后在中序遍历中找出根结点的位置即可确定左、右子树节点的数量，递归构造即可。
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {if(pre.length != in.length|| pre.length == 0)return null;return constructCore(pre,0,pre.length-1,in,0,in.length-1);}private TreeNode constructCore(int[] pre, int ps, int pend, int[] in, int ins, int inend) {if(ps > pend || ins > inend)return null;TreeNode root = new TreeNode(pre[ps]);int size = 0;for(int i = ins;i <= inend;i++){if(in[i] == pre[ps])break;size++;}root.left = constructCore(pre,ps + 1,ps + size,in,ins,ins + size - 1);root.right = constructCore(pre,ps + size + 1,pend,in,ins + size + 1,inend);return root;}
6.二叉树的下一个节点（！！）
题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
分析：若该节点有右子树，那么下一个节点就是它的右子树的最左子节点；若没有右子树，再分两种情况。如果它是父节点的左子节点，那么下一个节点就是它的父节点；如果它是父节点的右子节点，则需一直向上遍历找到一个是它父节点的左子节点的结点，这个结点的父节点就是要找的下一个节点。
public TreeLinkNode GetNext(TreeLinkNode pNode){if(pNode == null)return null;TreeLinkNode node = null;if(pNode.right != null){ //有右子树node = pNode.right;while(node.left != null){node = node.left;}}else if(pNode.next != null){ //无右子树if(pNode.next.left == pNode)//为父节点的左子树node = pNode.next;else{//为父节点的右子树node = pNode;while(node.next != null && node.next.left != node)node = node.next;node = node.next;}}return node;}
7.用两个栈实现队列
题目：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
分析：进队列每次都压入stack1。出队列：若stack2不为空，直接出栈即可；否则将stack1的元素依次出栈并压入stack2中。
Stack<Integer> stack1 = new Stack<Integer>();Stack<Integer> stack2 = new Stack<Integer>();public void push(int node) {stack1.push(node);}public int pop() {if(stack2.empty()){while(! stack1.empty()){stack2.push(stack1.pop());}}return stack2.pop();}
拓展：用两个队列实现一个栈
题目：用两个队列来实现一个栈，完成栈的Push和Pop操作。 栈中的元素为int类型。
分析：始终保持一个队列为空，进行“互倒”即可。
Queue<Integer> queue1 = new ArrayDeque();Queue<Integer> queue2 = new ArrayDeque();public void push(int node) {if(queue1.isEmpty())queue2.add(node);elsequeue1.add(node);}public int pop() {if(queue1.isEmpty() && queue2.isEmpty())return (Integer)null;//如果queue1为空，queue2有元素， 将queue2的元素依次放入queue1中，直到最后一个元素才弹出。if(queue1.isEmpty()){while(queue2.size() > 1)queue1.add(queue2.poll());return queue2.poll();}if(queue2.isEmpty()){while(queue1.size() > 1)queue2.add(queue1.poll());return queue1.poll();}return (Integer)null;}