面试题07. 重建二叉树(难度:中等)

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树:
3
/
9 20
/
15 7

思路

前序遍历的顺序是:根节点,左子树,右子树。中序遍历的顺序是:左子树,根节点,右子树。每个子树同样具有对应特点。
前序遍历的第一个节点是根节点,只要找到根节点在中序遍历中的位置,就可以将左右子树进行一个划分:根节点之前的节点位于左子树,
根节点之后的节点位于右子树。左右子树同样具有相应特点,可根据前序遍历和中序遍历进一步划分左右子树。因此可以通过递归的方式,重建左子树和右子树,然后重建整个二叉树。

代码实现

class Solution {
    HashMap<Integer, Integer> dic = new HashMap<>();
    int[] po;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        po = preorder;
        for (int i = 0; i < inorder.length; i++)
            dic.put(inorder[i], i);
        return recur(0, 0, inorder.length - 1);
    }

    public TreeNode recur(int pre_root, int in_left, int in_right) {
        if (in_left > in_right) return null;
        TreeNode root = new TreeNode(po[pre_root]);
        int i = dic.get(po[pre_root]);
        root.left = recur(pre_root + 1, in_left, i - 1);
        root.right = recur(pre_root + i - in_left + 1, i + 1, in_right);
        return root;
    }
    public void preOrder(TreeNode T)
    {
        if(T!=null)
        {
            System.out.print(T.val+" ");
            preOrder(T.left);
            preOrder(T.right);
        }
    }
    public void inOrder(TreeNode T)
    {
        if(T!=null)
        {
            inOrder(T.left);
            System.out.print(T.val+" ");
            inOrder(T.right);
        }
    }
    public void posOrder(TreeNode T)
    {
        if(T!=null)
        {
            posOrder(T.left);
            posOrder(T.right);
            System.out.print(T.val+" ");
        }
    }
}

面试题09. 用两个栈实现队列(难度:简单)

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead操作返回-1)

示例

输入:
[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[3],[],[]]
输出:[null,null,3,-1]

输入:
[“CQueue”,”deleteHead”,”appendTail”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[],[5],[2],[],[]]
输出:[null,-1,null,null,5,2]

思路

栈的特点是先入后出,队列的特点是先入先出。为了保持队列的特点,每次插入的元素应该在主栈的栈底。因此每次插入元素时,若主栈内已经有元素,应将已有的全部元素依次弹出并压入辅助栈,然后将新元素压入主栈,最后将第二个栈内的全部元素依次弹出并压入主栈。这样就保证了新插入元素在主栈栈底,其余元素顺序保持不变。删除元素时,若第主栈非空,则直接从主栈内弹出一个元素并返回,若主栈为空,则返回-1。

代码实现

public class CQueue {
    //定义主栈、辅助栈以及队列大小
    Stack<Integer> stackMajor, stackMinor;
    int size;

    //构造方法初始化
    public CQueue() {
        stackMajor = new Stack<>();
        stackMinor = new Stack<>();
        size = 0;
    }

    public void appendTail(int value) {

        //如果主栈不为空,则把主栈全部元素依次弹出并压入副栈
        while (!stackMajor.isEmpty()) {
            stackMinor.push(stackMajor.pop());
        }

        //压入副栈完成则把新元素压入主栈底部
        stackMajor.push(value);

        //如果副栈不为空,则把副栈全部元素依次弹出并压入主栈
        while (!stackMinor.isEmpty()) {
            stackMajor.push(stackMinor.pop());
        }
        //队列元素个数加一
        size++;
    }

    public int deleteHead() {
        //如果队列为空,则返回-1
        if(size==0){
            return -1;
        }
        //如果size大于0,则队列非空,将size的值减1,从stack1弹出一个元素并返回
        size--;
        return stackMajor.pop();
    }
}

面试题10-II. 青蛙跳台阶问题(难度:简单)

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例

输入:n = 2
输出:2

输入:n = 7
输出:21

思路

  • 设跳上n级台阶有f(n)种跳法。在所有跳法中,青蛙的最后一步只有两种情况:跳上1级或2级台阶。
    1. 当为1级台阶:剩n-1个台阶,此情况共有f(n-1)种跳法;
    2. 当为2级台阶:剩n-2个台阶,此情况共有f(n-2)种跳法。
  • f(n)为以上两种情况之和,即f(n)=f(n-1)+f(n-2),以上递推性质为斐波那契数列。本题可转化为 求斐波那契数列第n项的值,与面试题10-I. 斐波那契数列等价,唯一的不同在于起始数字不同。
    1. 青蛙跳台阶问题:f(0)=1, f(1)=1, f(2)=2;
    2. 斐波那契数列问题:f(0)=0, f(1)=1, f(2)=1。

代码实现

public class Solution {
    //动态规划
    public int numWays(int n) {
        int a = 1, b = 1, sum;
        for (int i = 0; i < n; i++) {
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
    //递归实现
    public int numWays2(int n) {
        if (n < 2)
            return 1;
        return numWays2(n - 1) + numWays2(n - 2);
    }
}

评论