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

《剑指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

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114700.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号