剑指Offer题解——递归和堆

不念不忘少年蓝@ 2022-11-26 02:59 71阅读 0赞

### 文章目录 ###

*  递归
 *   *  剑指 Offer 10- I. 斐波那契数列
     *   *  迭代
     *  剑指 Offer 10- II. 青蛙跳台阶问题
     *   *  迭代
     *  剑指 Offer 16. 数值的整数次方
     *   *  快速幂
 *  堆排序
 *   *  剑指 Offer 41. 数据流中的中位数
     *   *  堆
         *   *  推荐阅读

# 递归 #

## 剑指 Offer 10- I. 斐波那契数列 ##

[剑指 Offer 10- I. 斐波那契数列][Offer 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

### 迭代 ###

class Solution {
        
        public int fib(int n) {
        
            int first = 0, second = 1, sum;
            for (int i = 0; i < n; i++) {
        
                sum = (first + second) % 1000000007;
                first = second;
                second = sum;
            }
            return first;
        }
    }

## 剑指 Offer 10- II. 青蛙跳台阶问题 ##

[剑指 Offer 10- II. 青蛙跳台阶问题][Offer 10- II.]

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

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

示例 1：
    
    输入：n = 2
    输出：2
    示例 2：
    
    输入：n = 7
    输出：21
    示例 3：
    
    输入：n = 0
    输出：1
    提示：
    
    0 <= n <= 100

### 迭代 ###

我们用 f(x) 表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：

f ( x ) = f ( x − 1 ) + f ( x − 2 ) f(x) = f(x - 1) + f(x - 2) f(x)=f(x−1)\+f(x−2)

class Solution {
        
        public int numWays(int n) {
        
            int p = 0, q = 0, sum = 1;
            for (int i = 1; i <= n; ++i) {
        
                p = q; 
                q = sum; 
                sum = (p + q) % 1000000007;
            }
            return sum;
        }
    }

## 剑指 Offer 16. 数值的整数次方 ##

[剑指 Offer 16. 数值的整数次方][Offer 16.]

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例 1:
    
    输入: 2.00000, 10
    输出: 1024.00000
    示例 2:
    
    输入: 2.10000, 3
    输出: 9.26100
    示例 3:
    
    输入: 2.00000, -2
    输出: 0.25000
    解释: 2-2 = 1/22 = 1/4 = 0.25
     
    
    说明:
    
    -100.0 < x < 100.0
    n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

### 快速幂 ###

class Solution {
        
        public double myPow(double x, int n) {
        
            if (x == 0) {
        
                return 0;
            }
            long b = n;
            double res = 1.0;
            if (b < 0) {
        
                x = 1 / x;
                b = -b;
            }
            while (b > 0) {
        
                if ((b & 1) == 1) {
        
                    res *= x;
                }
                x *= x;
                b >>= 1;
            }
            return res;
        }
    }

# 堆排序 #

## 剑指 Offer 41. 数据流中的中位数 ##

[剑指 Offer 41. 数据流中的中位数][Offer 41.]

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

\[2,3,4\] 的中位数是 3

\[2,3\] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。  
double findMedian() - 返回目前所有元素的中位数。

示例 1：
    
    输入：
    ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
    [[],[1],[2],[],[3],[]]
    输出：[null,null,null,1.50000,null,2.00000]
    示例 2：
    
    输入：
    ["MedianFinder","addNum","findMedian","addNum","findMedian"]
    [[],[2],[],[3],[]]
    输出：[null,null,2.00000,null,2.50000]
     
    
    限制：
    
    最多会对 addNum、findMedia进行 50000 次调用。

### 堆 ###

class MedianFinder {
        
        Queue<Integer> q1, q2;
        /** initialize your data structure here. */
        public MedianFinder() {
        
            q1 = new PriorityQueue<>(); // 小顶堆，保存较大的一半
            q2 = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
        }
        
        public void addNum(int num) {
        
            if (q1.size() != q2.size()) {
         // 数据流为奇数，先将num插入q1, 然后取q1里面最小的数，放入q2
                q1.add(num);
                q2.add(q1.poll());
            } else {
        
                q2.add(num);
                q1.add(q2.poll());
            }
        }
        
        public double findMedian() {
        
            return q1.size() != q2.size() ? q1.peek() : (q1.peek() + q2.peek()) / 2.0;
        }
    }
    
    /**
     * Your MedianFinder object will be instantiated and called as such:
     * MedianFinder obj = new MedianFinder();
     * obj.addNum(num);
     * double param_2 = obj.findMedian();
     */

--------------------

#### 推荐阅读 ####

*  [机器学习资料汇总][Link 1]
 *  [吴恩达《机器学习》视频、作业、源码][Link 2]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 3]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]

--------------------

![format_png][]

[Offer 10- I.]: https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
[Offer 10- II.]: https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
[Offer 16.]: https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
[Offer 41.]: https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
[Link 1]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 2]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 3]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[format_png]: /images/20221124/a4284ba458a6480c866008a6f217eefc.png