LeetCode剑指offer题目记录4

leetcode刷题开始啦, 每天记录几道题.

目录

• 剑指offer 07. 重建二叉树
• • 题目描述
  • 示例
  • 思路
  • • python
    • 改进
• 剑指offer 09. 用两个栈实现队列
• • 题目描述
  • 示例
  • 思路
  • • python
• 剑指offer 10-1. 斐波那契数列
• • 题目描述
  • 思路
  • • python
    • C++
• 剑指offer 10-2. 青蛙跳台阶问题
• • 问题描述
  • 思路
  • • C++

剑指offer 07. 重建二叉树 题目描述

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

思路

前序遍历是中左右, 中序遍历是左中右, 所以前序遍历的第一个节点是整个二叉树的根节点. 因为没有重复, 我们在中序遍历结果里去找这个根节点, 它的前面就应该是中序遍历的左子树, 算一下这个左子树有多长, 再去前序遍历结果里从第一个节点之后取等长的一截, 就是这个左子树在前序遍历下的结果. 两个数组剩下的部分就是前序遍历的右子树和中序遍历的右子树. 两组子树, 就可以用递归的方式找根节点左子树右子树, 直到找到基线条件, 就是这个子树只有一个节点或者没有节点.

python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder:
            return None
        result = TreeNode(preorder[0], None, None)
        if len(preorder) == 1:
            return result
        for i, num in enumerate(inorder):
            if num == preorder[0]:
                in_left_tree = inorder[0:i]
                pre_left_tree = preorder[1:i+1]
                in_right_tree = inorder[i+1:]
                pre_right_tree = preorder[i+1:]
                break

        result.left = self.buildTree(pre_left_tree, in_left_tree)
        result.right = self.buildTree(pre_right_tree, in_right_tree)
        return result

改进

思路是这个思路, 写也可以这么写. 但是这样要耗费巨大的空间. 改进一下. 我们不直接传整个子数组了, 我们完全可以只传递索引. 整个递归过程的查找判断, 都只使用最初的inorder数组.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def idxBuildTree(pre_left: int, pre_right: int, in_left: int, in_right: int):
            if pre_left > pre_right:
                return None
            root = TreeNode(preorder[pre_left], None, None)
            if pre_left == pre_right:
                return root
            
            idx = in_left
            while inorder[idx] != preorder[pre_left]:
                idx += 1
            size_left_tree = idx - in_left

            root.left = idxBuildTree(pre_left+1, pre_left+size_left_tree, in_left, idx-1)
            root.right = idxBuildTree(pre_left+size_left_tree+1, pre_right, idx+1, in_right)

            return root
        
        n = len(preorder)
        return idxBuildTree(0, n-1, 0, n-1)

但还是有个巨大的问题, 就是每一次递归都要遍历一次inorder, 非常费时. 完全可以在最开始就遍历一次, 用哈希表存起来. 再改进一下.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def idxBuildTree(pre_left: int, pre_right: int, in_left: int, in_right: int):
            if pre_left > pre_right:
                return None
            root = TreeNode(preorder[pre_left], None, None)
            if pre_left == pre_right:
                return root
            
            idx = inorder_idx[preorder[pre_left]]
            size_left_tree = idx - in_left
            root.left = idxBuildTree(pre_left+1, pre_left+size_left_tree, in_left, idx-1)
            root.right = idxBuildTree(pre_left+size_left_tree+1, pre_right, idx+1, in_right)

            return root
        
        n = len(preorder)
        inorder_idx = {num:i for i, num in enumerate(inorder)}
        return idxBuildTree(0, n-1, 0, n-1)

剑指offer 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]

思路

两个栈, 我用一个来作这个队列的主体. 队尾添加元素很容易, 直接压入这个栈即可. 返回队列的头意味着要返回最先进栈的元素, 那就用另一个栈, 把主体栈的栈顶一个个d出到这个中转栈, 这个中转栈的元素顺序就和主体栈相反, 它的栈顶就是第一个进入主体栈的元素, 把它d出即可, 然后再把中转栈的栈顶一个个d出到主体栈, 回到原来的队列里.

python

class CQueue:

    def __init__(self):
        self.main = []
        self.trans = []

    def appendTail(self, value: int) -> None:
        self.main.append(value)

    def deleteHead(self) -> int:
        if not self.main:
            return -1
        self.trans = self.main[::-1]
        result = self.trans.pop()
        self.main = self.trans[::-1]
        return result

剑指offer 10-1. 斐波那契数列 题目描述

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。

斐波那契数列的定义如下

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

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

思路

转移的思路很清晰. 照着写就可以.

python

class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        
        f0, f1 = 0, 1
        for i in range(2, n + 1):
            f2 = f0 + f1
            f0 = f1
            f1 = f2
        return f2 % 1000000007 if f2 > 1000000007 else f2

C++

这个题目还需要注意数据的范围. 带符号int型存储范围是 − 2 31 -2^{31} −231至 2 31 − 1 2^{31}-1 231−1, 即-2147483648至2147483647. 保险的做法, 就是每一次都取模. 因为取模运算在加减下保持相等.

class Solution {
public:
    int fib(int n) {
        if (n < 2){
            return n;
        }
        int f0 = 0;
        int f1 = 1;
        int f2;
        int tol = 1000000007;
        for (int i = 2; i < n + 1; i ++){
            f2 = (f0 % tol) + (f1 % tol);
            f0 = f1 % tol;
            f1 = f2 % tol;
        }
        return f2 % 1000000007;
    }
};

剑指offer 10-2. 青蛙跳台阶问题 问题描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。

求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

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

思路

和上一个一模一样. 跳上n级的跳法, 等于先跳上n-1级再跳一级或者先跳上n-2级再跳一级的种数的和.

C++

class Solution {
public:
    int numWays(int n) {
        if (n < 2){
            return 1;
        }
        int f0 = 1; 
        int f1 = 1;
        int f2;
        int tol = 1000000007;
        for (int i = 2; i < n + 1; i++){
            f2 = f0 % tol + f1 % tol;
            f0 = f1 % tol;
            f1 = f2 % tol;
        }
        return f2 % tol;
    }
};