面试题07. 重建二叉树

题目链接：面试题07. 重建二叉树

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

例如，给出

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

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

限制：

0 <= 节点个数 <= 5000

思路

在前序遍历中，第一个数字是根节点。在中序遍历中，左子树的n个节点位于根节点的左边。前序遍历中根节点后面的n个数字就是左子树，后面是右子树。用同样的方法可以构建整个树。

代码

// Java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0)
            return null;
        return buildCore(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode buildCore(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
        // 创建根节点
        TreeNode root = new TreeNode(preorder[preStart]);
        int rootIndex = -1;
        for (int i = 0; i < inorder.length; ++i) {
            if (inorder[i] == root.val) {
                rootIndex = i;
                break;
            }
        }
        int leftLength = rootIndex - inStart;
        int rightLength = inEnd - rootIndex;
        if (leftLength > 0)
            root.left = buildCore(preorder, inorder, preStart + 1, preStart + leftLength, inStart, rootIndex - 1);
        if (rightLength > 0)
            root.right = buildCore(preorder, inorder, preStart + leftLength + 1, preEnd, rootIndex + 1, inEnd);
        return root;
    }
}

面试题09. 用两个栈实现队列

题目链接：面试题09. 用两个栈实现队列

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

示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示：

1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用

思路

用两个“先进后出”的栈实现一个“先进先出”的队列。插入元素是都插入s1，当删除元素时，如果s2为空，把s1的元素逐个弹出并压入到s2中，弹出s2的栈顶即可。如果s2不为空，直接弹出栈顶即可。

代码

// Java
class CQueue {
    Stack<Integer> s1 = new Stack<>();
    Stack<Integer> s2 = new Stack<>();
    public CQueue() {
    }

    public void appendTail(int value) {
        s1.push(value);
    }

    public int deleteHead() {
        if (s1.empty() && s2.empty())
            return -1;
        else if (!s2.empty()) {
            return s2.pop();
        }
        else {
            while (!s1.empty()) {
                s2.push(s1.pop());
            }
            return s2.pop();
        }
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

面试题10- I. 斐波那契数列

题目链接：面试题10- I. 斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：1
示例 2：

输入：n = 5
输出：5

提示：

0 <= n <= 100

思路

递归算法重复计算过多，我们采用从下往上计算，根据$f(0)$和$f(1)$计算$f(2)$，以此类推。

代码

// Java
class Solution {
    public int fib(int n) {
        int[] ans = {0, 1};
        if (n < 2)
            return ans[n];
        long fibFront = 0;
        long fibBack = 1;
        long fibAns = 0;
        for (int i = 2; i <= n; ++i) {
            fibAns = (fibBack + fibFront) % 1000000007;
            fibFront = fibBack;
            fibBack = fibAns;
        }
        return (int) (fibAns);
    }
}

其他解法

递归实现O($n^2$)

// C++
long long Fibonacci(unsigned int n)
{
    if (n <= 0)
        return 0;
    if (n == 1)
        return 1;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

数学公式O($logn$)

见书。

打表O($1$)

int f[]={0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,134903163,836311896,971215059,807526948,778742000,586268941,365010934,951279875,316290802,267570670,583861472,851432142,435293607,286725742,722019349,8745084,730764433,739509517,470273943,209783453,680057396,889840849,569898238,459739080,29637311,489376391,519013702,8390086,527403788,535793874,63197655,598991529,662189184,261180706,923369890,184550589,107920472,292471061,400391533,692862594,93254120,786116714,879370834,665487541,544858368,210345902,755204270,965550172,720754435,686304600,407059028,93363621,500422649,593786270,94208912,687995182};
int fib(int n){
    return f[n];
}

面试题10- II. 青蛙跳台阶问题

题目链接：面试题10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2
示例 2：

输入：n = 7
输出：21

提示：

0 <= n <= 100

思路

和上一题起始条件不一样，其他一样。

代码

// Java
class Solution {
    public int numWays(int n) {
        int[] ans = {1, 1};
        if (n < 2)
            return ans[n];
        long fibFront = 1;
        long fibBack = 1;
        long fibAns = 0;
        for (int i = 2; i <= n; ++i) {
            fibAns = (fibBack + fibFront) % 1000000007;
            fibFront = fibBack;
            fibBack = fibAns;
        }
        return (int) (fibAns);
    }
}

其他

版权属于：moluuser

本文链接：https://archive.moluuser.com/archives/35/

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。