小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. Leetcode
  6. 正文

leetcode题目解析(191029)

2019年10月29日 724点热度 0人点赞 0条评论

Leetcode 309:最佳买卖股票时机含冷冻期

题目描述

给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

  • 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
  • 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

示例

输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

解题思路

这又是一个动态规划问题,我们思考该题的状态图。一共可能有三个状态:

  • Hold:购入股票;
  • Sold:卖出股票;
  • Rest:持有股票什么都不做。

那么如何能得到这三个状态呢?

对于Hold来说:

  • 前一天持有,当日Rest;
  • 前一天Rest,当日买入股票。

对于Sold来说:

  • 前一日Hold股票,当日卖出。

对于Rest来说:

  • 前一日Sold了,当日必须Rest;
  • 也可以前一天Rest,当日继续Rest。

所以说状态转换图如下:

复杂度配图

由上面的状态转换图我们可以得到:
(以下i表示第i天,i-1代表前一天)

sold[i]=hold[i-1]+price[i];
hold[i]=max(hold[i-1],rest[i-1]-price[i]);
rest[i]=max(rest[i-1],sold[i-1]);

那么对于最后一天来说,最大值存在两种情况:什么都不做;卖出股票。所以为max(sold,rest)。

代码实现

int maxProfit(vector<int>& prices) {
        int sold=0,hold=INT_MIN,rest=0;
        for(int price:prices){
            int pre_sold=sold;
            sold=hold+price;
            hold=max(hold,rest-price);
            rest=max(rest,pre_sold);
        }
        return max(sold,rest);
    }

复杂度分析

时间复杂度:O(n)

复杂度配图

LeetCode 312:戳气球

题目描述

n 个气球,编号为0 到 n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。

现在要求你戳破所有的气球。每当你戳破一个气球 i 时,你可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后,气球 left 和气球 right 就变成了相邻的气球。

求所能获得硬币的最大数量。

说明:

你可以假设 nums[-1] = nums[n] = 1,但注意它们不是真实存在的所以并不能被戳破。
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

示例

输入: [3,1,5,8]
输出: 167
解释: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
  coins = 315 + 358 + 138 + 181 = 167

解题思路

这个题类似于游艇租赁问题,游艇租赁问题就是找分隔点,而本题也是类似的。这种动态规划问题和我们前面遇到的是不太一样的。

动态规划问题就是将一个大问题分隔成多个独立的小问题。在这个问题上,就是我们可以将大的区间分隔为独立的小区间,然后先戳爆小区间,也就是先算小区间,再组合出大区间。

对于本题的示例[3,1,5,8]来说,步骤如下:

第一步:计算长度为1的区间,分别戳3,1,5,8。

第二步:计算长度为2的区间,分别算[3,1],[1,5],[5,8]:
对于3,1:3最后戳,1已经算出;同样1最后戳,3也算出;
对于1,5:1最后戳,5已经算出;同样5最后戳,1也算出;
对于5,8:5最后戳,8已经算出;同样8最后戳,5也算出。

第三步,计算长度为3的区间,分别计算[3,1,5]和[1,5,8]:
对于3,1,5来说,3最后戳,1/5已经计算出来;1最后戳,3/5已经计算出来;5最后戳,3,1已经计算出来;
对于1,5,8来说,1最后戳,5/8已经计算出来;5最后戳,1/8已经计算出来;8最后戳,1,5已经计算出来。

第四步,计算长度为4的区间,即[3,1,5,8]:3最后戳,1,5,8已经算出。1最后戳3和5,8已经算出。5最后戳,3,1和8已经算出。8最后戳,3,1,5已经算出。

简单来说,写一个伪代码:
序列为num,[i,j]为区间,dp[i][j]为dp数组;c为区间长度,则

for(c in [1,N]){
    for(i in [1,N-c+1])//区间起始点在[1,N-c+1]这个区间里面
    {
        j=i+c-1;//区间长度为c-1,即代表分别计算1,2,...,N的长度区间
        for(k in [i,j]){
            dp[i][j]=max(num[i-1]*num[k]*num[j+1])+dp[i][k-1]+dp[k+1][j]);
            //当前戳中的值+其左侧戳中的值+其右侧戳中的值
        }
    }
}

解析参考自:
https://leetcode-cn.com/problems/burst-balloons/solution/san-chong-jie-fa-by-jason-2-6/

代码实现

int maxCoins(vector<int>& nums) {
    int N;
    N = nums.size();
    nums.insert(nums.begin(), 1);
    nums.push_back(1);//在开头和结尾插入1,因为题目说-1和最后一个位置当做1
    const int len = nums.size();
    vector<vector<int>> dp(len, vector<int>(len, 0));

    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j + i - 1 <= N; ++j) {
            const int k = j + i - 1;
            int& ans = dp[j][k];
            for (int m = j; m <= k; ++m) {
                ans = max(ans, nums[j - 1] * nums[m] * nums[k + 1] + dp[j][m - 1] + dp[m + 1][k]);
            }
        }
    }

    return dp[1][N];
}

复杂度分析

复杂度配图

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode
最后更新:2019年10月29日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
鸡尾酒排序问题 每日一评0823:现代青少年的“早熟”与“晚熟” 个人日记-091222 安装pygame步骤 iNove新春2010主题[本博客2010新年主题] WebRTC VAD模块分析
标签聚合
linux 生活 学习 鸟哥的linux私房菜 python学习 高中 算法 Python Java leetcode
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号