剑指offer -- 动态规划

发表于 | 分类于
字数统计: 4k | 阅读时长 ≈ 18
夜晚下的大阪市中心 -- 日本

剑指offer – 动态规划

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

Difficulty: 简单

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

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

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

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

示例 1：

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

示例 2：

1
2
输入：n = 5
输出：5

提示：

  • 0 <= n <= 100

Solution

方法一：递归写法

1
2
3
4
5
6
7
class Solution {
public:
    int fib(int n) {
        if (n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }
};

时间复杂度：$O(2^N)$，指数级别。

空间复杂度：$O(N)$，每一层运算所占用的空间为1，一共要递归 n-1 次；也就是约等于n。

方法二：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int fib(int n) {
        if (n <= 1) return n;
        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        return dp[n];
    }
};

时间复杂度：$O(N)$，N 为数组长度，一次遍历

空间复杂度：$O(N )$，dp 数组所需要的额外空间

方法二：动态规划，滚动数组，空间优化

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int fib(int n) {
        if (n <= 1) return n;
        int p = 0, q = 0, r = 1;
        for (int i = 1; i < n; i++) {
            p = q;
            q = r;
            r = (p + q) % 1000000007;
        }
        return r;
    }
};

时间复杂度：$O(N)$，N 为数组长度，一次遍历

空间复杂度：$O(1)$，p,q,r 所需的额外常数空间

方法三：矩阵快速幂

斐波那契数_官方题解__方法二：矩阵快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int fib(int n) {
        if (n < 2) {
            return n;
        }
        vector<vector<int>> q{{1, 1}, {1, 0}};
        vector<vector<int>> res = matrix_pow(q, n - 1);
        return res[0][0];
    }
	// 求矩阵的 n 次幂
    vector<vector<int>> matrix_pow(vector<vector<int>>& a, int n) {
        vector<vector<int>> ret{{1, 0}, {0, 1}}; // 初始化单位矩阵
        while (n > 0) {
            // n 存在奇数和偶数两种情况，整个思路同:剑指offer16 数值的整数次方
            // 奇数情况要多乘一次 a
            // a^n = a * (a^(n/2) * a^(n/2))
            if (n & 1) {
                ret = matrix_multiply(ret, a);
            }
            // 偶数：a^n = a^(n/2) * a^(n/2)
            a = matrix_multiply(a, a);
            n >>= 1;
        }
        return ret;
    }
	// 二维矩阵乘法公式
    vector<vector<int>> matrix_multiply(vector<vector<int>>& a, vector<vector<int>>& b) {
        vector<vector<int>> c{{0, 0}, {0, 0}};
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }
};

注意：此题使用的快速幂算法与 数值的整数次方 相同。

时间复杂度：$O(\log N)$，二分的时间复杂度为对数级别。

空间复杂度：$O(1)$，res , q, a, ret 等变量都有明确的大小，仅占用常数大小额外空间。

方法四：通项公式

斐波那契数_官方题解__方法三：通项公式
$$
F(n) = \frac{1}{\sqrt{5}}[(\frac{1 + \sqrt{5}}{2})^n - (\frac{1 - \sqrt{5}}{2})^n]
$$

1
2
3
4
5
6
7
8
class Solution {
public:
    int fib(int n) {
        double sqrt5 = sqrt(5);
        double fibN = pow((1 + sqrt5) / 2, n) - pow((1 - sqrt5) / 2, n);
        return round(fibN / sqrt5);
    }
};

时间复杂度，空间复杂度皆为 $O(1)$。

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

Difficulty: 简单

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

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

示例 1：

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

示例 2：

1
2
输入：n = 7
输出：21

示例 3：

1
2
输入：n = 0
输出：1

提示：

  • 0 <= n <= 100

Solution

与斐波那契数列本质相同，更多解法同上。以下是一个常规的动态规划+滚动数组优化空间解法。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int numWays(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 0; i < n; i++) {
            p = q;
            q = r;
            r = (p + q) % 1000000007;
        }
        return r;
    }
};

时间复杂度：$O(N)$，N 为数组长度，一次遍历

空间复杂度：$O(1)$，p,q,r 所需的额外常数空间

剑指 Offer 19. 正则表达式匹配

Difficulty: 困难

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

示例 1:

1
2
3
4
5
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

1
2
3
4
5
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

1
2
3
4
5
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

1
2
3
4
5
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

1
2
3
4
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size() + 1, n = p.size() + 1;
        vector<vector<bool>> dp(m, vector<bool>(n, false));
        dp[0][0] = true;
        // 初始化首行
        for(int j = 2; j < n; j += 2)
            dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';
        // 状态转移
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 模式串是否为 *
                if (p[j - 1] == '*') {
                    if (dp[i][j - 2]) dp[i][j] = true;  
                    // 当前模式串字符前一位与当前匹配串字符相同，或者为 . 则取决于正上方情况                            
                    else if (s[i - 1] == p[j - 2] || p[j - 2] == '.') dp[i][j] = dp[i - 1][j]; 
                } else {
                    // // 当前模式串字符与当前匹配串字符相同，或者为 . 则取决于左斜上方情况
                    if (p[j - 1] == '.' || s[i - 1] == p[j - 1]) dp[i][j] = dp[i - 1][j - 1];  
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};

时间复杂度：$O(MN)$，其中 M 为匹配串的长度，N 为模式串的长度。

空间复杂度：$O(MN)$，dp 矩阵所需要的额外空间消耗。

剑指 Offer 42. 连续子数组的最大和

Difficulty: 简单

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

1
2
3
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：

  • 1 <= arr.length <= 10^5
  • -100 <= arr[i] <= 100

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> dp(n);
        dp[0] = nums[0];
        int result = dp[0];
        for (int i = 1; i < n; ++i) {
            // dp[i - 1] < 0 的情况,dp[i] = nums[i],也就是重新从nums[i]开始遍历
            // dp[i - 1] > 0 的情况,dp[i] = dp[i - 1] + nums[i],考虑前者仍然对其有增益效果
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            if (dp[i] > result) result = dp[i]; // 每轮更新最大值
        }
        return result;
    }
};

时间复杂度：$O(N)$，N 为数组 nums 的长度。

空间复杂度：$O(N)$，dp 所需要的额外空间消耗。

剑指 Offer 46. 把数字翻译成字符串

Difficulty: 中等

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

1
2
3
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

提示：

  • 0 <= num < 2^31

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int translateNum(int num) {
        int a = 1, b = 1, x = 0, y = 0;
        // num 大于两位数
        while(num > 9) {
            y = num % 10; // 倒数第一位
            num /= 10;
            x = num % 10; // 倒数第二位
            int tmp = 10 * x + y;  // 最后两位构成的数字
            // 如果该数字满足构成字母的要求，也即是符合 10 <= tmp <= 25
            int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
            b = a;
            a = c;
            y = x;
        }
        return a;
    }
};

时间复杂度：$O(log_{10}N)$，即 num 的位数。

空间复杂度：$O(1)$，a, b, c, x, y, tmp, 常数个变量所需的额外空间。

剑指 Offer 47. 礼物的最大价值

Difficulty: 中等

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:

1
2
3
4
5
6
7
8
输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

提示：

  • 0 < grid.length <= 200
  • 0 < grid[0].length <= 200

Solution

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        vector<vector<int>> dp(m, vector<int>(n));
        dp[0][0] = grid[0][0];
		// 初始化第一行
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        // 初始化第一列
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        // 动态规划
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 当前元素取值由其上方和左方元素决定
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
};

时间复杂度：$O(M \times N)$，M 为行数，N 为列数。

空间复杂度：$O(M \times N)$ ，dp 所占用的额外空间。

动态规划，空间优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for(int j = 1; j < n; j++) // 初始化第一行
            grid[0][j] += grid[0][j - 1];
        for(int i = 1; i < m; i++) // 初始化第一列
            grid[i][0] += grid[i - 1][0];
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++)
                grid[i][j] += max(grid[i][j - 1], grid[i - 1][j]);
        return grid[m - 1][n - 1];
    }
};

时间复杂度：$O(M \times N)$，M 为行数，N 为列数。

空间复杂度：$O(1)$ ，原地操作。

剑指 Offer 48. 最长不含重复字符的子字符串

Difficulty: 中等

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

1
2
3
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • s.length <= 40000

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<int, int> mp;
        int len = s.size();
        int i = -1, res = 0; // i = -1，从边界外开始
        for (int j = 0; j < len; j++) {
            if (mp.find(s[j]) != mp.end()) {
                // i 为最接近 j 时，重复的位置
                i = max(mp[s[j]], i);
            }
            mp[s[j]] = j; // 更新字母的位置信息
            res = max(res, j - i);  // 更新最大长度
        }
        return res;
    }
};

时间复杂度：$O(N)$，N 为字符串长度，一次遍历即可

空间复杂度：$O(1)$，哈希表最多存26个字母，因此是仅需要常数额外空间。

剑指 Offer 49. 丑数

Difficulty: 中等

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

1
2
3
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

**说明: **

  1. 1 是丑数。
  2. n 不超过1690。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int nthUglyNumber(int n) {
        int a = 0, b = 0, c = 0;
        vector<int> dp(n);
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = min(min(n1, n2), n3);
            if (dp[i] == n2) a++;
            if (dp[i] == n3) b++;
            if (dp[i] == n5) c++;
        }
        return dp[n - 1];
    }
};

时间复杂度：$O(n)$

空间复杂度：$O(n)$，dp 额外所需的空间复杂度

剑指 Offer 60. n个骰子的点数

Difficulty: 中等

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

示例 1:

1
2
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

示例 2:

1
2
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

限制：

1 <= n <= 11

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<double> dp(6, 1.0 / 6.0);
        for (int i = 2; i <= n; i++) {
            vector<double> tmp(5 * i + 1, 0);
            for (int j = 0; j < dp.size(); j++) {
                for (int k = 0; k < 6; k++) {
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }
};

参考: 图解算法数据结构 - 剑指offer60)

剑指 Offer 63. 股票的最大利润

Difficulty: 中等

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:

1
2
3
4
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

1
2
3
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

限制：

0 <= 数组长度 <= 10^5

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX;
        int maxPro = 0;
        for (int i = 0; i < prices.size(); ++i) {
            // 找到当前最低值
            minPrice = min(minPrice, prices[i]);
            maxPro = max(maxPro, prices[i] - minPrice);
        }
        return maxPro;
    }
};

时间复杂度：$O(N )$，N 为 prices 长度，一次遍历

空间复杂度：$O(1 )$，minPrice 和 maxPro 所需的

参考资料

图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com) 官方题解



----------- 本文结束 -----------




0%