剑指offer题解c++版(三)

二，算法

1，递归

10-1. 斐波那契数列

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

解题方法：

1，记忆化递归
2，迭代法

C++代码：

// 剑指 offer 10-1. 斐波那契数列
class Solution {
private:
    static const int mod = 1e9 + 7;
    int m = 101;
    vector<int> vec = vector<int>(101, -1);  // c++11 之后，类 private成员初始化方式
public:
    // 1，直接递归会超出时间限制，需要使用记忆化递归
    constexpr int fib(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;

        if (vec[n] != -1) return vec[n];
        vec[n] = (fib(n - 1) + fib(n - 2)) % mod;

        return vec[n];
    }
    // 2，迭代求解
    int fib(int n) {
        int arr[101];
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 1;
        for (int i = 2; i < n; i++) {
            arr[i+1] = (arr[i ] + arr[i - 1]) % mod;
        }
        return arr[n];
    }
};

2，二分查找

3，排序

4，贪心

63-股票的最大利润

63-股票的最大利润

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

示例 1:

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

解题方法：

1，贪心法：假设每天的股价都是最低价，每天都计算股票卖出去后的利润。一次 for 循环，时间复杂度：O(n)
2，暴力法：两次 for 循环，时间复杂度 O(n^2)

C++代码：

# include <iostream>
# include <vector>
# include <algorithm>

using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 贪心算法：一次遍历
        int inf = 1e9; // 表示“无穷大”
        int minprice = inf, maxprofit = 0;
        for(int price: prices){
            maxprofit = max(maxprofit, (price-minprice)); // 假设每天都是最低价
            minprice = min(minprice, price);
        }
        return maxprofit;
    }
};

int main(){
    vector<int> prices = {7,1,5,3,6,4};
    Solution s1;
    int max_profit = s1.maxProfit(prices);
    cout << max_profit << endl;
    return 0;
}

5，分治

6，回溯

7，动态规划

10.2-青蛙跳台阶问题

剑指offer 10.2-青蛙跳台阶问题

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

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

解题方法：

1，动态规划法：以斐波那契数列性质 $f(n + 1) = f(n) + f(n - 1)$ 为转移方程。

• 状态定义： 设 $dp$ 为一维数组，其中 $dp[i]$ 的值代表斐波那契数列第 $i$ 个数字 。
• 转移方程： $dp[i + 1] = dp[i] + dp[i - 1]$ ，即对应数列定义 $f(n + 1) = f(n) + f(n - 1)$；
• 初始状态： $dp[0] = 1, dp[1] = 1$，即初始化前两个数字；
• 返回值： $dp[n]$，即斐波那契数列的第 $n$ 个数字。

C++代码：

class Solution {
private:
    static const int mod = 1e9 + 7;
public:
    // 动态规划法 
    int numWays(int n) {
        int dp[n+1];
        if( n == 0 || n == 1) return 1;
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2; i<=n; i++){
            dp[i] = (dp[i-1] + dp[i-2]) % mod;
        }
        return dp[n];
    }
    // 递归法
    int numWays2(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        return numWays2(n-1) + numWays2(n-2);
    }
};

42-连续子数组的最大和

剑指offer 42-连续子数组的最大和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

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

解题思路：

动态规划法。

C++代码：

class Solution {
public:
    //1, 动态规划算法
    int maxSubArray2(vector<int>& nums) {
        int* dp = new int[nums.size()];
        dp[0] = nums[0];
        int maxSum = dp[0];
        for(int i=1; i < nums.size(); i++){
            dp[i] = max(dp[i-1], 0) + nums[i];
            maxSum = max(dp[i], maxSum);
        }
        return maxSum;
    }
    //1, 动态规划，优化空间
    int maxSubArray(vector<int>& nums) {
        int sum = nums[0];
        int maxSum = nums[0];
        for(int i=1; i < nums.size(); i++){
            sum = max(sum, 0) + nums[i];
            maxSum = max(sum, maxSum);
        }
        return maxSum;
    }
};

47-礼物的最大价值

剑指offer 47-礼物的最大价值

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

示例 1:

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

解题方法：

动态规划-状态转移方程法。

C++代码：

class Solution {  // 状态转移方程法
private:
    int minDist(int i, int j, vector<vector<int> >& matrix, vector<vector<int> >& mem) { // 调用minDist(n-1, n-1);
        if (i == 0 && j == 0) return matrix[0][0];
        if (mem[i][j] > 0) return mem[i][j];

        int minUp = -10000;
        if (i - 1 >= 0) minUp = minDist(i - 1, j, matrix, mem);
        int minLeft = -10000;
        if (j - 1 >= 0) minLeft = minDist(i, j - 1, matrix, mem);
        int currMinDist = matrix[i][j] + std::max(minUp, minLeft);

        mem[i][j] = currMinDist;

        return currMinDist;
    }
public:
    int maxValue(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int> > mem(m, vector<int>(n, -1));

        return minDist(m - 1, n - 1, grid, mem);
    }
};

48-最长不含重复字符的子字符串

剑指offer 42-最长不含重复字符的子字符串

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

示例 1:

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

解题思路：

1. 动态规划。参考这里。
2. 滑动窗口法 + 哈希表结构。

C++代码：

class Solution {
public:
    // 动态规划+线性遍历
    int lengthOfLongestSubstring(string s) {
        int res=0, tmp = 0, i=0;
        for(int j=0; j < s.size(); j++){
            i = j-1;
            while(i>=0 && s[i] != s[j]) i-= 1;
            if(tmp < j-i) tmp += 1;
            else tmp = j - i;
            res = max(res, tmp);
        }
        return res;
    }
    // 滑动窗口法 +  哈希表保存字符出现的位置
    int lengthOfLongestSubstring2(string s) {
        unordered_map<char, int> seen;
        int maxLength = 0, l = 0;
        for(int r=0; r<s.size(); r++){
            // 更新滑动窗口左侧位置
            if(seen.count(s[r]) > 0) {
                int last_pos = seen[s[r]];
                // 位置判断不可少，重复字符的位置必须是在滑动窗口内！
                if(last_pos >= l) l = last_pos + 1;  // last_pos <= r
            }
            maxLength = max(maxLength, r-l+1);
            seen[s[r]] = r;
        }
        return maxLength;
    }
};
```分享常见的数据结构包括：数组、链表、栈和队列等，以及常见的算法：排序、分治、回溯、递归、贪心、动态规划等。