剑指offer三五题-1

题目描述

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

题解

前序的一个值必为根节点,对应于中序则其左边序列为左子树,右边序列为右子树,对左右子树重复上述过程,当从中序序列找到所有根节点(遍历)后,递归调用结束。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

import java.util.Arrays;

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length == 0 || in.length == 0){
            return null;
        }

        TreeNode root = new TreeNode(pre[0]);
        //在中序中找到前序的根
        for(int i = 0; i < in.length; i++){
            if(in[i] == pre[0]){
                //左子树,注意copyOfRange 函数,左闭右开
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
                //右子树,注意 copyOfRange 函数,左闭右开
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length));
                break;
            }
        }
        return root;
    }
}

题目描述

用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

题解

队列:队尾进,队头出,两端操作,先进先出。

栈:栈顶进,栈顶出,单端操作,先进后出。

两个栈则可满足两端操作,当把入栈的元素,弹出再依次压入另一个栈,则先入栈的元素在另一个栈的顶端可以先出,此时满足先进先出。

import java.util.Stack;

public class Solution {
    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.size() == 0){
            while(stack1.size() != 0 ){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

题目描述

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

题解

二分查找的变种,该数组分为非递减排序、有间断的两段,只要到达这两段的邻接值,返回靠后的值即可。

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int start=0;
        int end=array.length-1;
        while(start<=end)
        {
            int mid=(start+end)/2;
            if(end-start==1)
                return array[end];
            if(array[mid]>=array[start])
                start=mid;
            if(array[mid]<=array[end])
                end=mid;
        }
        return -1;

    }
}

题目描述

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第1项是1)。

n<=39

题解

递归,直接套公式

public class Solution {
    public int Fibonacci(int n) {
        if(n<=1){
            return n;
        }
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}

非递归,用数组存储依次计算的值。

public class Solution {
    public int Fibonacci(int n) {
        int ans[] = new int[40];
        ans[0] = 0;
        ans[1] = 1;

        for(int i = 2; i<=n; i++){
            ans[i] = ans[i-1] + ans[i-2];
        }
        return ans[n];
    }
}

非递归,用两个变量存储最新计算的两个值。

public class Solution {
    public int Fibonacci(int n) {
        if(n == 0){
            return 0;
        }else if(n == 1){
            return 1;
        }
        int sum = 0;
        int two = 0;
        int one = 1;
        for(int i=2;i<=n;i++){
            sum = two + one;
            two = one;
            one = sum;
        }
        return sum;
    }
}

   转载规则


《剑指offer三五题-1》 帅张 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录