04题解–重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路解析
这里我们首先需要知道前序遍历和中序遍历的规则
前序遍历（根左右）
中序遍历（左根右）
我们是通过前序序列的第一个节点来划分中序序列，从而找到该节点的左右子树，之后只需要在对相应的序列做递归操作即可。
这里面我们只要注意一下Arrays.copyOfRange(，，)这个函数是左闭右开的就行了
源代码
import java.util.Arrays; public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { if(pre.length==0||in.length==0) return null; TreeNode treeNode=new TreeNode(pre[0]); for(int i=0;i<in.length;i++) { if(in[i]==treeNode.val) { treeNode.left=reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));//左子树重建 treeNode.right=reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in,i+1,in.length));//右子树重建 } } return treeNode; } }
05题解–用两个栈实现队列
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路解析
这里面我们需要懂栈和队列的特性
栈：先进后出
队列：先进先出
通过下面的图来进行讲解
这是栈：
这是队列:
我们的处理逻辑，主要存储还是通过一个栈来实现，但是需要另外一个栈来充当中间件的功能
源代码
import java.util.Stack; public class Solution { static Stack<Integer> stack1 = new Stack<Integer>(); static Stack<Integer> stack2 = new Stack<Integer>(); public static void push(int node) { stack1.push(node); } public static int pop() { stack2.clear();//首先保证stack2中是没有任何元素的 int node; if(stack1==null)//避免栈为空时，pop报错 return (Integer) null; else { while(!stack1.empty()) { stack2.push(stack1.pop()); } node=stack2.pop(); while (!stack2.empty()) { stack1.push(stack2.pop()); } return node; } } }
06题解–旋转数组的最小数字
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路解析
最简单的方法就是通过暴力来解决，也能通过，但是显然这是不可取的。
主要还是通过二分法来进行，但是这又和我们平常的二分有所不同，他的顺序是部分有序但是二分的整体思想还是能够用的，
二分主要的就是怎么比较，和谁比较。
这里我们采取的是和右端点进行比较。
首先必须明白一点，给我们的数组一定是这样的形式
【{升序数组1},{升序数组2}】 中间有一处是断开的，正是因为他翻转的因素。
现在我们举例说明
第一种情况就是mid<last
举例 {4,5,1,2,3},既然mid<last,那么就可以确定mid-last必定是处于升序的数组之中，这里大家可以通过反证法即可验证。那么显然mid+1~last的元素肯定是大于mid的，所以区间范围就处于0-mid之中，这里因为mid可能刚好是最小的那个元素，所以必须将mid这个位置也包括进去。
第二种情况就是mid>last
举例{3,4,5,1,2}，既然mid>last,那么就可以确定0-mid必定是处于升序的数组之中，这里大家也可以通过反证法即可验证。那么显然0-mid的元素都是大于last的，所以区间就确定在了mid+1~last之间了，这里因为mid本身就已经大于last了，所以必定不是最小的元素了，所以排除。
第三种情况就是mid=last
这里面稍微比较复杂，因为=并不能确定我们到底是处于哪一区间的数组之中，所以我们只能慢慢地减少数组中的元素。
举两个例子
{1,2,0,0,0} 这种情况最小值是落在了右边的区间上。
{4,1,2,2,2} 这种情况最小值是落在了左边的区间上。
所以显然我们并不能通过上述的方法进行大幅度的区间减少，只能通过last-1的方式来减少区间范围。
源代码
import java.util.Arrays; public class Solution { public static int minNumberInRotateArray(int [] array) { if(array.length==0) return 0;//这是在空数组时进行输出 if(array.length==1) return array[0];//因为在最后的递归过程中，到最后剩下一个元素时，其实就应该输出了。否则再次进入递归过程那么，就会陷入数组为空的情况，那样就会直接输出0了 //注意边界的取值情况 int first=0; int last=array.length-1; int mid=(last-first)/2; //同时注意Arrays.copyOfRange(，，)这个函数是左闭右开的就行了 if(array[mid]<array[last]) { return minNumberInRotateArray(Arrays.copyOfRange(array,first,mid+1)); } else if(array[mid]>array[last]) { return minNumberInRotateArray(Arrays.copyOfRange(array,mid+1,last+1)); } else { return minNumberInRotateArray(Arrays.copyOfRange(array,first,last)); } } }
