算法练习-递归

1 解题技巧

1.1 如何发现问题可以用递归来做

• 规模更小的问题和规模更大的问题，解题思路相同，规模不同
• 利用子问题可以组合得到原问题的解
• 存在最小子问题，可以直接返回结果(存在递归终止条件)

1.2编写递归的正确姿势

可以假设子问题B、C已经解决，在此基础上再思考如何解决问题A

2 爬楼梯

链接：https://leetcode.cn/problems/climbing-stairs

2.1 题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶
   示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

2.2 题解

class Solution {private int[] m;public int climbStairs(int n) {m = new int[n + 1];return f(n);}private int f(int n) {if (n == 1) {return 1;}if (n == 2) {return 2;}if (m[n] != 0) {return m[n];}m[n] = f(n - 1) + f(n - 2);return m[n];}
}

3 细胞分裂

3.1 题目

一个细胞的生命周期是3小时，1小时分裂一次，求n小时后容器内有多少个细胞。

细胞会在每个小时的开始分裂、死亡，并且先分裂后死亡

3.2 题解

当前时间细胞总数 = 分裂后的个数 - 死亡个数

f(n) = 2 * f(n - 1) - f(n - 4)

当前时间点，死亡的细胞个数，为三个小时前分裂出的净细胞个数，

而一个时间点分裂出来的净细胞个数等于前一个时间点的细胞个数

所以死亡个数为f(n - 4)

public int f(int n) {if (n == 0) return 1;if (n == 1) return 2;if (n == 2) return 4;if (n == 3) return 8;return 2 * f(n - 1) - f(n - 4);
}

4 从尾到头打印链表

链接：剑指 Offer 06. 从尾到头打印链表 - 力扣（LeetCode）

4.1 题目

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

4.2 题解

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {List<Integer> result = new ArrayList<>();public int[] reversePrint(ListNode head) {reverse(head);int[] resultArr = new int[result.size()];int i = 0;for (Integer j : result) {resultArr[i++] = j;}return resultArr;}public void reverse(ListNode head) {if (head == null) {return;}reverse(head.next);result.add(head.val);}
}

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

链接：https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof

5.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。

示例 1：

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

输入：n = 5
输出：5

5.2 题解

class Solution {int mod = 1000000007;int[] m;public int fib(int n) {m = new int[n + 1];return f(n);}private int f(int n) {if (n == 0) return 0;if (n == 1) return 1;if (m[n] != 0) return m[n];m[n] = (f(n - 1) + f(n - 2)) % mod;return m[n];}
}

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

链接：https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof

6.1 题目

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

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

示例 1：

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

输入：n = 7
输出：21
示例 3：

输入：n = 0
输出：1
提示：

0 <= n <= 100

6.2 题解

class Solution {private int mod = 1000000007;private Map<Integer, Integer> memo = new HashMap<>();public int numWays(int n) {if (n == 0) return 1;if (n == 1) return 1;if (memo.containsKey(n)) {return memo.get(n);}int ret = (numWays(n-1)+numWays(n-2))%mod;memo.put(n, ret);return ret;}
}

7 三步问题

链接：https://leetcode.cn/problems/three-steps-problem-lcci

7.1 题目

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

示例1:

输入：n = 3
输出：4
说明: 有四种走法
示例2:

输入：n = 5
输出：13

7.2 题解

7.2.1 递归(可能会超时)

class Solution {private int mod = 1000000007;private Map<Integer, Integer> m = new HashMap<>();public int waysToStep(int n) {if (n == 1) return 1;if (n == 2) return 2;if (n == 3) return 4;if (m.containsKey(n)) return m.get(n);int ret = ((waysToStep(n - 1) + waysToStep(n - 2)) % mod + waysToStep(n - 3)) % mod;m.put(n, ret);return ret; }
}

7.2.2 非递归

class Solution {public int  waysToStep(int n) {int mod = 1000000007;if (n == 1) return 1;if (n == 2) return 2;if (n == 3) return 4;int[] dp = new int[n + 1];dp[1] = 1;dp[2] = 2;dp[3] = 4;for (int i = 4; i <= n; i++) {dp[i] = ((dp[i - 1] + dp[i - 2]) % mod + dp[i - 3]) % mod;}return dp[n];}
}

7.2.3 非递归+优化（内存优化）

class Solution {public int  waysToStep(int n) {int mod = 1000000007;if (n == 1) return 1;if (n == 2) return 2;if (n == 3) return 4;int a = 1;int b = 2;int c = 4;int d = 0;for (int i = 4; i <= n; i++) {d = ((c + b) % mod + a) % mod;a = b;b = c;c = d;}   return d;}
}

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

链接：https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof

8.1 题目

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：

输入：x = 2.10000, n = 3
输出：9.26100
示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

8.2 题解

class Solution {public double myPow(double x, int n) {if (n == 0) return 1;if (n == 1) return x;if (n == -1) return 1/x;double h = myPow(x, n / 2);double mod = myPow(x, n % 2);return h * h * mod;}
}

9 递归乘法

链接：https://leetcode.cn/problems/recursive-mulitply-lcci

9.1 题目

递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。

示例1:

输入：A = 1, B = 10
输出：10
示例2:

输入：A = 3, B = 4
输出：12

9.2 题解

class Solution {public int multiply(int A, int B) {if (B == 0) return 0;return A + multiply(A, B - 1);}
}

class Solution {public int multiply(int A, int B) {int n = Math.min(A, B);int k = Math.max(A, B);if (n == 1) {return k;}int h = multiply(n / 2, k);if (n % 2 == 1) {return h + h + k;} else {return h + h;}}
}