《剑指offer》–二维数组中的查找、从头到尾打印链表、重建二叉树、旋转数组的最小数字

一、二维数值中的查找：

1、题目：

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

2、解题思路：

通过分析可以很简单的找出一个规律，二维数组的最左下角的的点，该点的所在列上边的点都是减少的，该点所在行右边的点都是增加的。因此，我们以该点作为切入点，如果目标数比左下角的数大，则往右边移动；如果目标数比左下角的数小，则往上边移动；之后以此类推，如果匹配到目标数，则返回true；如果当移动到最右上角的点仍然没有匹配到目标数，则返回false。

3、代码示例：

public boolean Find(int target, int[][] array) {
		int rowCount = array.length;
		int colCount = array[0].length;

		int x, y;

		for (y = rowCount - 1, x = 0; y >= 0 && x < colCount;) {
			if (target == array[y][x]) {
				return true;
			} else if (target > array[y][x]) {
				x++;
				continue;
			} else if (target < array[y][x]) {
				y--;
				continue;
			}
		}
		return false;
	}

二、从头到尾打印链表：

1、题目：

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

2、代码实现：

public class Solution{

	//第二种方式:递归实现：
	ArrayList<Integer> resultList = new ArrayList<Integer>();
	public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
		
		if(listNode!=null){
			this.printListFromTailToHead2(listNode.next);
			resultList.add(listNode.val);
		}
		
		return resultList;
	}
	
	
	//第一种方式，使用堆栈结构
	public ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
		
		 Stack<Integer> stack = new Stack<Integer>();
		 while(listNode != null){
			 stack.push(listNode.val);
			 listNode = listNode.next;
		 }
        
		 ArrayList<Integer> resultList = new ArrayList<Integer>();
		 while(!stack.isEmpty()){
			resultList.add(stack.pop());
		}
		
		return resultList;
	}
}

三、重建二叉树：

1、题目：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

2、思路：

通过分析前序遍历和中序遍历的规律，前序遍历的第一个节点就是二叉树的根节点，中序遍历中，位于根节点前面的所有节点都位于左子树上，位于根节点后面的所有节点都位于右子树上面。通过这个规律，我们可以使用递归方法来重建二叉树。

3、代码实现：

class TreeNode{
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x){
		val=x;
	}
}

public class Test1 {

	public TreeNode reConstructBinaryTree(int[] pre,int[] in){
		//前序的第一个数是根节点
		TreeNode root = new TreeNode(pre[0]);
		
		int len=pre.length;
		if(len==1){
			root.left=null;
			root.right=null;
			
			return root;
		}
		
		//找出中序中的根节点位置
		int rootVal=root.val;
		int i;
		for(i=0;i<len;i++){
			if(rootVal==in[i])
				break;
		}
		
		//构建左子树
		if(i>0){
			int[] pr = new int[i];
			int[] ino = new int[i];
			
			for(int j=0;j<i;j++){
				pr[j]=pre[j+1];
				ino[j]=in[j];
			}
			
			root.left=reConstructBinaryTree(pr,ino);
		}else{
			root.left=null;
		}
		
		//构建右子树
		if(len-i-1>0){
			int[] pr =new int[len-i-1];
			int[] ino = new int[len-i-1];
			
			for(int j=i+1;j<len;j++){
				pr[j-i-1]=pre[j];
				ino[j-i-1]=in[j];
			}
			
			root.right=reConstructBinaryTree(pr,ino);
		}else{
			root.right=null;
		}
		
		return root;
	}
	
}

4、第二种写法：

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
        return root;
    }
    //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
    private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
         
        if(startPre>endPre||startIn>endIn)
            return null;
        TreeNode root=new TreeNode(pre[startPre]);
         
        for(int i=startIn;i<=endIn;i++)
            if(in[i]==pre[startPre]){
                root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
                root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
                      break;
            }
                 
        return root;
    }
}

四、旋转数组的最小数字：

1、题目:

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

2、思路：

采用二分查询的方法，但是需要处理两种特殊情况：

即{1 0 1 1 1} 以及{1 1 1 0 1}这两种类型的排序。

3、代码实现：

public class Solution {
    public int minNumberInRotateArray(int [] array) {
       if(array.length==0){
           return 0;
       }
        
        int leftIndex=0;
        int rightIndex=array.length-1;
        int midIndex=0;
        
       while(array[leftIndex]>=array[rightIndex]){
           //当左右两个指针相互接触，则说明已经找到最小值，即右边的指针的元素
            if(rightIndex-leftIndex<=1){
                midIndex=rightIndex;
                break;
            }
           
           midIndex=(leftIndex+rightIndex)/2;
           
           //这里是处理特殊情况，即当左中右三个指针的值都是一样的时候，我们不能判断最小元素位于哪个位置，只能通过遍历的方法找出最小元素
           //特殊情况：{1 0 1 1 1} 以及{1 1 1 0 1}这两种类型的排序
           if(array[rightIndex]==array[leftIndex] && array[leftIndex]==array[midIndex]){
               return MinInOrder(array,leftIndex,rightIndex);
           }
           
           //如果中间元素大于末尾元素，那么表明最小元素在后半段数组中，修改leftIndex指针位置
           if(array[midIndex]>=array[leftIndex]){
               leftIndex=midIndex;
           }else if(array[midIndex]<=array[rightIndex]){
               //如果中间元素小于末尾元素，那么表明最小元素在前半段部分中，修改rightIndex指针位置
               rightIndex=midIndex;
           }
        }
        return array[midIndex];
        
    }
    
    public int MinInOrder(int[] array,int leftIndex,int rightIndex){
        int result=array[leftIndex];
        for(int i=leftIndex+1;i<rightIndex;i++){
            if(result>array[i]){
                result=array[i];
            }
        }
        return result;
    }
    
}

4、代码实现2：

public class Solution {
	 public int minNumberInRotateArray(int [] array) {
		 int low=0;int high = array.length-1;
		 
		 while(low<high){
			int mid = low + ((high - low) >> 2);
		 	if(array[mid] > array[high]){
		 		low = mid+1;
		 	}else if(array[mid] == array[high]){
		 		high--;
		 	}else{
		 		high =mid;
		 	}
		 }
		 
		 return array[low];
    }
}

注意这里有个坑：如果待查询的范围最后只剩两个数，那么mid 一定会指向下标靠前的数字

比如 array = [4,6]

array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;

如果high = mid – 1，就会产生错误， 因此high = mid