wy的leetcode刷题记录_Day16

902. 最大为 N 的数字组合

今天的每日一题是：902. 最大为 N 的数字组合

题目介绍

给定一个按非递减顺序排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = [‘1’,‘3’,‘5’]，我们可以写数字，如 ‘13’, ‘551’, 和 ‘1351315’。
返回可以生成的小于或等于给定整数 n 的正整数的个数。

示例 1：
输入：digits = [“1”,“3”,“5”,“7”], n = 100
输出：20
解释：可写出的 20 个数字是： 1, 3,5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

示例 2：
输入：digits = [“1”,“4”,“9”], n = 1000000000
输出：29523
解释：我们可以写 3 个一位数字，9个两位数字，27 个三位数字， 81 个四位数字，243 个五位数字，729 个六位数字， 2187 个七位数字，6561 个八位数字和19683 个九位数字。总共，可以使用D中的数字写出 29523 个整数。

思路

数位DP：
1.dp数组含义：dp[i][0]表示小于n的前i位并且包含digits的数的个数，dp[i][1]表示等于n的前i位并且包含digits的数的个数。
2.dp数组递推公式：
设 digits 中的字符数目为 m 个，数字 n 的前 j 位构成的数字为 num[j]，数字 n 的第 j 个字符为 s[j]，当遍历到 n 的第 i 位时：
本题的递推分3部分：

1）首先对于i>1时不论digit中为多少都是小于num[i]，所以所有digit都可以加入dp[i][0]也就是，dp[i][0]+=digits.size()
2）其次设数字 a <num[i?1]，则此时在 a 的末尾追加一个数字 d 构成的数为 a×10+d，此时可以知道 d取 0，1,?,9
中任意数字均满足小于a×10+d<num[i]=num[i?1]×10+s[i]，所以dp[i][0]+=dp[i-1][0]*digits.size()
3）而设数字 a=<num[i?1]，则此时在 a 的末尾追加一个数字 d 构成的数为 a×10+d，此时可以知道
d<s[i]时满足小于a×10+d<num[i]=num[i?1]×10+s[i]，所以dp[i][0]+=dp[i-1][1]*C[I]

3.初始化dp[0][1]=1

代码

class Solution {
public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        string s = to_string(n);
        int m = digits.size(), k = s.size();
        vector<vector<int>> dp(k + 1, vector<int>(2));
        dp[0][1] = 1;
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j < m; j++) {
                if (digits[j][0] == s[i - 1]) {
                    dp[i][1] = dp[i - 1][1];
                } else if (digits[j][0] < s[i - 1]) {
                    dp[i][0] += dp[i - 1][1];
                } else {
                    break;
                }
            }
            if (i > 1) {
                dp[i][0] += m + dp[i - 1][0] * m;
            }
        }
        return dp[k][0] + dp[k][1];
    }
};

收获

第一次做数位DP，看题解写的，还是挺蒙的，还有一种数学解法看不懂。。多做多练吧。

122. 买卖股票的最佳时机 II

题目介绍

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在 同一天 出售。
返回你能获得的最大利润。

示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 =5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。总利润为 4 + 3 = 7 。

示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 =5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。总利润为 4 。

思路

方法一：
贪心算法：本题只要求求最大利润，我们可以分部计算每天的最大利润然后相加得到总体最大利润。
方法二：
动态规划：
1.确定dp数组的含义：与之前的I相同dp[i][0]表示第i天持有股票时所拥有的的资金（包括第i-1天已持有股票或者第i天刚购入股票），dp[i][1]表示第i天不持有股票时所拥有的的资金（包括第i-1天未持有股票或者第i天刚卖出股票）
2.确定dp数组的递推公式：由于不限制交易次数那么相比于第一题只有dp[i][0]有变化。

            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

3.初始化：由dp数组含义得知，dp[0][0]=-price[0],dp[i][1]=0

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if (len < 2) {
            return 0;
        }

        int res = 0;
        for (int i = 1; i < len; i++) {
            int diff = prices[i] - prices[i - 1];
            if (diff > 0) {
                res += diff;
            }
        }
        return res;
    }
};


```cpp
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int dp[n][2];
        dp[0][0] = 0, dp[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }
};