【算法刷题】Day26

文章目录

  • 1. 买卖股票的最佳时机含冷冻期
    • 题干:
    • 算法原理:
      • 1. 状态表示:
      • 2. 状态转移方程
      • 3. 初始化
      • 4. 填表顺序
      • 5. 返回值
    • 代码:
  • 2. 替换所有的问号
    • 题干:
    • 算法原理:
    • 代码:

1. 买卖股票的最佳时机含冷冻期

在这里插入图片描述

原题链接


题干:

整数数组prices
prices[i] 表示第 i 天的股票价格
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)
不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)


算法原理:

在这里插入图片描述

1. 状态表示:

在这里插入图片描述
在这里插入图片描述
dp[i][0] 表示:第 i 天结束之后,处于“买入”状态,此时最大利润
dp[i][1] 表示:第 i 天结束之后,处于“可交易”状态,此时最大利润
dp[i][2] 表示:第 i 天结束之后,处于“冷冻期”状态,此时最大利润

2. 状态转移方程

圆圈表示前一天
箭头所指的是当前的状态
在这里插入图片描述
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - p[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][2])
dp[i][2] = dp[i-1][0] + p[i]

3. 初始化

dp[0][0] = -p[0]
dp[0][1] = 0
dp[0][2] = 0

4. 填表顺序

从左往右
三个表一起填

5. 返回值

max(dp[n-1][1], dp[n-1][2])


代码:

class Solution {public int maxProfit(int[] prices) {int n = prices.length;int[][] dp = new int[n + 1][3];dp[0][0] = -prices[0];for(int i = 1; i < n; i++) {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);dp[i][2] = dp[i - 1][0] + prices[i];}return Math.max(dp[n - 1][1], dp[n - 1][2]);}
}

在这里插入图片描述


2. 替换所有的问号

在这里插入图片描述
原题链接


题干:

包含小写英文字母和 ‘?’ 字符的字符串 s
将所有的 ‘?’ 转换为若干小写字母
最终的字符串不包含任何 连续重复 的字符


算法原理:

在这里插入图片描述


代码:

class Solution {public int maxProfit(int[] prices) {int n = prices.length;int[][] dp = new int[n + 1][3];dp[0][0] = -prices[0];for(int i = 1; i < n; i++) {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);dp[i][2] = dp[i - 1][0] + prices[i];}return Math.max(dp[n - 1][1], dp[n - 1][2]);}
}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2659764.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

组件间的值传递:改进若依框架中的BarChart.vue组件

改进前的BarChart 如下是若依(Ruoyi)框架中的BarChart.vue文件&#xff0c;该BarChart.vue无法实现组件间的值传递。到这里您不妨可以试试该如何去传值。如果您不想思考&#xff0c;请看改进后的BarChart。直接拿走使用&#xff01; <template><div :class"cla…

大量数据的渲染优化-分页渲染方案

文章目录 直接渲染数据的拆分使用定时器分页渲染 相信有一道耳熟能详的题目&#xff0c;如果前端获取到了 10w 条数据&#xff0c;应该怎么渲染&#xff1f;本文就以此为例&#xff0c;来进行切入&#xff0c;解析大量数据渲染的方案 直接渲染 样式代码比较简单&#xff0c;我就…

Android原生实现单选

六年前写的一个控件&#xff0c;一直没有时间总结&#xff0c;趁年底不怎么忙&#xff0c;整理一下之前写过的组件。供大家一起参考学习。废话不多说&#xff0c;先上图。 一、效果图 实现思路使用的是radioGroup加radiobutton组合方式。原理就是通过修改RadioButton 的backgr…

vue3-富文本编辑器(vue-quill)

官网&#xff1a;VueQuill | Rich Text Editor Component for Vue 3 安装 pnpm add vueup/vue-quilllatest 使用 局部使用 先导包 import { QuillEditor } from vueup/vue-quill import vueup/vue-quill/dist/vue-quill.snow.css; 再使用 <QuillEditor theme"snow…

想要快速搭建知识付费平台?找明理信息科技!

明理信息科技知识付费saas租户平台 一、确定目标群体 首先&#xff0c;你需要明确你的知识付费平台的目标用户是谁。这将帮助你确定所需的内容和功能&#xff0c;以及如何吸引和留住这些用户。例如&#xff0c;如果你的目标群体是职场新人&#xff0c;你的平台可能需要提供…

MFC工程中无法使用cygwin64的库

文章目录 MFC工程中无法使用cygwin64的库概述在MFC中使用cygwin64的静态库在MFC中使用cygwin64的DLL进行静态包含在MFC中使用cygwin64的DLL进行动态调用唯一可以使用cygwin64的方法是进程隔离来通讯cygwin64的官方用途修正后的启动进程隐藏dos窗口的函数动态载入DLL的实现 - La…

代码随想录27期|Python|Day29|回溯算法|491.递增子序列|46.全排列|47.全排列 II

491. 非递减子序列 本题不是单纯的去重题目&#xff0c;而是需要保持数字在原数组的顺序。 比如&#xff1a;[4,5,6,7]和[4,6,5,7]相比&#xff0c;后者就不能选择[5,6,7]这个排列&#xff0c;因为违反了设置的顺序。所以去重的方法就只有哈希表。 需要在每一层设置一个哈希表…

leaflet学习笔记-初始化vue项目(一)

leaflet简介 Leaflet是一款开源的轻量级交互式地图可视化JavaScript库&#xff0c;能够满足大多数开发者的地图可视化需求&#xff0c;其最早的版本大小仅仅38 KB。Leaflet能够在主流的计算机或移动设备上高效运行&#xff0c;其功能可通过插件进行扩展&#xff0c;拥有易于使用…

【Linux】指令(本人使用比较少的)——笔记(持续更新)

文章目录 ps -axj&#xff1a;查看进程ps -aL&#xff1a;查看线程echo $?&#xff1a;查看最近程序的退出码jobs&#xff1a;查看后台运行的线程组fd 任务号&#xff1a;将后台任务提到前台bg 任务号&#xff1a;将暂停的后台程序重启netstat -nltp&#xff1a;查看服务及监听…

C#中的Attribute详解(下)

C#中的Attribute详解&#xff08;下&#xff09; 一、Attribute本质二、Attribute实例化三、Attribute实例化的独特之处四、元数据的作用五、自定义Attribute实例六、Attribute的附着目标七、附加问题 一、Attribute本质 从上篇里我们可以看到&#xff0c;Attribute似乎总跟pu…

SAP VA01 创建带wbs号的销售订单包 CJ067的错误

接口错误提示如下 SAP官方 CJ067 124177 - VA01: CJ067 during WBS acct assgmt with a different business area S4的core 刚好能用上 实施 这个note后成功

nestjs入门教程系列(一):让项目先跑起来

nestjs启动基本步骤 Nest (NestJS) 是一个用于构建高效、可扩展的 Node.js 服务器端应用的框架。 它使用渐进式 JavaScript&#xff0c;构建并完全支持 TypeScript&#xff08;但仍然允许开发者使用纯 JavaScript 进行编码&#xff09;并结合了 OOP&#xff08;面向对象编程&am…

第二节-数据封装+传输介质

数据传输的形式&#xff1a; 1.电路交换 2.报文交换&#xff1a; 在数据之外&#xff0c;加上能够标识接收者以及发送者的信息 3.分组交换&#xff1a; 依然进行报文交换&#xff0c;不过讲每个数据的大小进行定义 应用层&#xff08;数据data&#xff09;->传输层&am…

K8S部署Harbor仓库实战

K8S部署Harbor仓库实战 K8S部署Harbor仓库实战 - 简书 创建文件目录 chartmuseum目录: /var/nfs/data/harbor/chartmuseumdatabase目录: /var/nfs/data/harbor/databasejobservice目录: /var/nfs/data/harbor/jobserviceredis目录: /var/nfs/data/harbor/redisregistry目录:…

深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第五节 引用类型复制问题及用克隆接口ICloneable修复

深入浅出图解C#堆与栈 C# Heaping VS Stacking 第五节 引用类型复制问题及用克隆接口ICloneable修复 [深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第一节 理解堆与栈](https://mp.csdn.net/mdeditor/101021023)[深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第二节…

【头歌实训】kafka-入门篇

文章目录 第1关&#xff1a;kafka - 初体验任务描述相关知识Kafka 简述Kafka 应用场景Kafka 架构组件kafka 常用命令 编程要求测试说明答案代码 第2关&#xff1a;生产者 &#xff08;Producer &#xff09; - 简单模式任务描述相关知识Producer 简单模式Producer 的开发步骤Ka…

Python跳动的爱心完整代码

文章目录 环境需求完整代码详细分析环境需求 python3.11.4PyCharm Community Edition 2023.2.5pyinstaller6.2.0(可选,这个库用于打包,使程序没有python环境也可以运行,如果想发给好朋友的话需要这个库哦~)【注】 python环境搭建请见:https://want595.blog.csdn.net/arti…

深入理解Mysql MHA高可用集群搭建:从实验到实战

1. 简介 MHA&#xff08;Master High Availability&#xff09;是一个高效的开源MySQL高可用性解决方案。由日本开发者yoshinorim&#xff08;前DeNA员工&#xff0c;现在Facebook&#xff09;创建&#xff0c;MHA支持MySQL的主从复制架构&#xff0c;自动化主节点故障转移。当…

支付宝 v3 验签如何实现

上次给大家介绍了 支付宝 v3 自签名如何实现&#xff0c;这次顺便再把验签也写一下。 为什么要验签 说起为什么要验签&#xff0c;如果要详细一点解释的话&#xff0c;可以写很多很多...... 我们就简单一点来解释&#xff1a;验签可以证明接收到的信息是支付宝给我的&#xf…

【信息安全原理】——拒绝服务攻击及防御(学习笔记)

&#x1f4d6; 前言&#xff1a;拒绝服务攻击&#xff08;Denial of Service, DoS&#xff09;是一种应用广泛、难以防范、严重威胁网络安全&#xff08;破坏可用性&#xff09;的攻击方式。本章主要介绍DoS的基本概念、攻击原理及防御措施。 目录 &#x1f552; 1. 定义&#…