题003 二维数组中的查找
题目内容
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
如果在一个二维数组中找到数字7，则返回true，如果没有找到，则返回false。
思路
就是从右上角开始遍历，假设要查找的数为A，当前遍历的数为B，B的特点是B所在行里面最大的数，也是B所在列最小的数，如果遍历的数B<A，那么B所在的行可以排除（比B都小)，如果遍历的数B>A，那么B所在的列可以排除(比B都大)。
代码：
static boolean find(int target, int [][] array) { int rowLength = array.length;//总行数 int colLength = array[0].length;//总列数 int currentRow = 0;//起始遍历位置是右上角，行号为0 int currentCol = colLength - 1;//起始遍历位置是右上角，列号为最大值 while (currentRow <rowLength && currentCol >= 0) {//防止超出边界 if (array[currentRow][currentCol] == target) { return true; } else if (array[currentRow][currentCol] > target) {//比要找的数大，那么排除更大的数，也就是排除这一列 currentCol--; } else {//比要找的数小，那么排除更小的数，也就是排除这一行 currentRow++; } } return false; }点击复制代码复制出错复制成功
总结
注意这个currentRow <rowLength && currentCol >= 0判断条件，防止越界。
题004 替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为 We%20Are%20Happy。
最暴力的方法就是从头开始对字符数组进行遍历，碰到空格，就进行替换，然后让后面的元素向后移动2位，但是这样每个空格都需要让后面的元素移动，复杂度会是O（n^2）。
优化的方法是先遍历一编字符串，知道字符串的空格数，然后计算得到替换后的长度=原来长度+2*空格数，然后从字符串的末尾进行遍历，每次把元素移动到计算后的数组下标的位置，并且对空格进行替换。
String replaceSpace(StringBuffer str) { int number = 0;//空格数目 for (int i = 0; i < str.length(); i++) { if (str.charAt(i) == ' ') { number++; } } int oldLength = str.length(); int newLength = str.length()+ 2*number; str.setLength(newLength); int tempIndex = newLength - 1;//新字符串正在的位置 for (int i = oldLength-1; i >=0; i--) {//遍历 if (str.charAt(i) != ' ') { str.setCharAt(tempIndex, str.charAt(i)); tempIndex--; } else { str.setCharAt(tempIndex, '0'); str.setCharAt(tempIndex-1, '2'); str.setCharAt(tempIndex-2, '%'); tempIndex = tempIndex - 3; } } return str.toString(); }点击复制代码复制出错复制成功
题005 从尾到头打印链表
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
总结：
首先通过开始的判断，来排除链表为空的情况，直接返回空数组，链表不为空，取下一个节点，判断下一个节点是否为空，
- 不为空，那么递归调用printListFromTailToHead方法来获取后面的节点反序生成的ArrayList，然后添加当前的节点的值，然后返回arrayList。
- 为空，那么说明当前节点是链表尾部节点，直接创建一个ArrayList，然后添加当前节点的值，然后返回arrayList。
其实原理就是先递归遍历，然后再打印，这样链表打印的顺序就是逆序的了。
ArrayList<Integer> list = new ArrayList<Integer>(); public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { if(listNode == null ){ return list; } printListFromTailToHead(listNode.next); list.add(listNode.val); return list; }点击复制代码复制出错复制成功
题006重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
前序遍历结果和中序遍历结果：
前序遍历结果分布是二叉树根节点，左子树，右子树。
中序遍历结果分布是左子树，二叉树根节点，右子树。
所以根据前序遍历结果的第一个元素获取到根节点，然后根据根节点把中序遍历结果分为两半，得到左子树的中序遍历结果，然后根据左子树的长度可以去前序遍历结果中分离出左子树的前序遍历结果，右子树也是如此，所以可以递归得构造出整个二叉树。
public static TreeNode reConstructBinaryTree(int[] pre, int[] in) { return reConstructBinaryTree(pre, 0, pre.length-1, in, 0, in.length-1); } public static TreeNode reConstructBinaryTree(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) { if (preStart > preEnd || inStart > inEnd) { return null; } TreeNode treeNode = new TreeNode(pre[preStart]); for (int i = inStart; i <= inEnd; i++) { if (in[i] == pre[preStart]) { int leftLength = i - inStart;//左子树长度 treeNode.left = reConstructBinaryTree(pre, preStart + 1, preStart+leftLength, in, inStart, i-1); treeNode.right = reConstructBinaryTree(pre, preStart +leftLength+1, preEnd, in, i+1, inEnd); break; } } return treeNode; }
