当前位置: 首页 > news >正文

代码随想录算法训练营29期|day54 任务以及具体安排

第九章 动态规划part11

  •  123.买卖股票的最佳时机III  
    // 版本一
    class Solution {public int maxProfit(int[] prices) {int len = prices.length;// 边界判断, 题目中 length >= 1, 所以可省去if (prices.length == 0) return 0;/** 定义 5 种状态:* 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出*/int[][] dp = new int[len][5];dp[0][1] = -prices[0];// 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润dp[0][3] = -prices[0];for (int i = 1; i < len; i++) {dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);}return dp[len - 1][4];}
    }

    思路:于上两个股票买卖问题的区别在于这道题限制了买卖次数,需要定义五种状态:0、1、2、3、4来代表不同的状态。然后使用递推公式对dp数组进行更新。

  •  188.买卖股票的最佳时机IV 
    // 版本一: 三维 dp数组
    class Solution {public int maxProfit(int k, int[] prices) {if (prices.length == 0) return 0;// [天数][交易次数][是否持有股票]int len = prices.length;int[][][] dp = new int[len][k + 1][2];// dp数组初始化// 初始化所有的交易次数是为确保 最后结果是最多 k 次买卖的最大利润for (int i = 0; i <= k; i++) {dp[0][i][1] = -prices[0];}for (int i = 1; i < len; i++) {for (int j = 1; j <= k; j++) {// dp方程, 0表示不持有/卖出, 1表示持有/买入dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);}}return dp[len - 1][k][0];}
    }// 版本二: 二维 dp数组
    class Solution {public int maxProfit(int k, int[] prices) {if (prices.length == 0) return 0;// [天数][股票状态]// 股票状态: 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作int len = prices.length;int[][] dp = new int[len][k*2 + 1];// dp数组的初始化, 与版本一同理for (int i = 1; i < k*2; i += 2) {dp[0][i] = -prices[0];}for (int i = 1; i < len; i++) {for (int j = 0; j < k*2 - 1; j += 2) {dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);}}return dp[len - 1][k*2];}
    }

    思路:该题与上题的区别在于该题是至多能k次,所以二维数组需要2*k+1的维度,1、3、5等奇数代表持有股票,2、4、6等偶数代表不持有股票。然后根据递推公式进行遍历递推。再进行dp数组的初始化。

相关文章:

代码随想录算法训练营29期|day54 任务以及具体安排

第九章 动态规划part11 123.买卖股票的最佳时机III // 版本一 class Solution {public int maxProfit(int[] prices) {int len prices.length;// 边界判断, 题目中 length > 1, 所以可省去if (prices.length 0) return 0;/** 定义 5 种状态:* 0: 没有操作, 1: 第一次买入…...

文件操作相关工具类

目录 1. 文件上传工具类 -- FileUploadUtils 2. 文件处理工具类 -- FileUtils 3. 媒体类型工具类 -- MimeTypeUtils 1. 文件上传工具类 -- FileUploadUtils /*** 文件上传工具类**/ public class FileUploadUtils {private static final Logger log LoggerFactory.ge…...

Spring源码:手写SpringIOC

文章目录 一、分析二、实现1、版本1&#xff1a;实现Bean注入IOC容器&#xff0c;并从容器中获取1&#xff09;定义BeanDefinition2&#xff09;定义BeanDefinition实现类3&#xff09;定义BeanDefinitionRegistry4&#xff09;定义Beanfactory5&#xff09;定义默认Beanfactor…...

【软件设计师】程序猿需掌握的技能——数据流图

作为一个程序员&#xff0c;不仅要具备高水平的程序编码能力&#xff0c;还要是熟练掌握软件设计的方法和技术&#xff0c;具有一定的软件设计能力&#xff0c;一般包括软件分析设计图&#xff08;常见的有数据流图&#xff0c;程序流程图&#xff0c;系统流程图&#xff0c;E-…...

17.3.1 像素处理

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 17.3.1 像素处理 C#处理图像&#xff0c;主要使用到Bitmap 类的 GetPixel方法和SetPixel方法。 Bitmap.GetPixel 方法&#xff1a…...

白话微机:8.解释FPGA以及一些考研面试问题

一. 前言&#xff08;更新世界观&#xff09; 在“微机世界”&#xff0c;普通的城市(单片机)里&#xff0c;人又有一个别的名字叫做“数据”&#xff0c;人有0有1&#xff1b;人们也有住房&#xff0c;这些住房在这个世界叫做“存储器”&#xff1b;地上有路&#xff0c;这些路…...

Kubernetes基础(十八)-k8s存储对象Persistent Volume

1 什么是Persistent Volume&#xff1f; 在容器化应用中&#xff0c;Pod的生命周期是短暂的&#xff0c;当Pod终止时&#xff0c;其中的数据通常也会被销毁。为了解决这个问题&#xff0c;Kubernetes引入了Persistent Volume&#xff08;PV&#xff09;的概念。PV是集群中的一…...

用linux命令将文本格式文件转换为csv文件

文章目录 前言例: 总结 前言 用到linux命令awk 使用 awk 命令来将文本文件转换为 CSV 格式。假设你有一个以空格或制表符分隔的文本文件&#xff0c;以下是将其转换为 CSV 格式的命令&#xff1a; awk BEGIN { OFS"," } { print $1, $2, $3 } input.txt > outpu…...

C++中的binary_search函数详解

C中的std::binary_search函数详解 在C标准模板库&#xff08;STL&#xff09;中&#xff0c;std::binary_search是一个非常有用的函数&#xff0c;它可以在一个已排序的序列中查找一个特定的元素。这个函数的使用非常直观&#xff0c;但是了解其工作原理和一些注意事项可以帮助…...

程序员为什么不喜欢关电脑?我来回答

程序员为什么不喜欢关电脑&#xff1f; 主题&#xff1a; 你是否注意到&#xff0c;程序员们似乎从不关电脑&#xff1f;别以为他们是电脑上瘾&#xff0c;实则是有他们自己的原因&#xff01;让我们一起揭秘背后的原因&#xff0c;看看程序员们真正的“英雄”本色&#xff01…...

波奇学Linux:动静态库

创建静态库 Makefile文件 mymath.c文件 mymath.h文件 编译main.c文件 gcc 编译时会把在系统目录中寻找头文件和库文件&#xff0c;文件不在系统目录中用参数 -I 头文件所在文件夹/ -L 库的地址文件夹 -l除去lib和后缀。 拷贝文件到系统目录即可不用参数 库的安装类似于把头文件…...

1723. 完成所有工作的最短时间

文章目录 题意思路代码 题意 题目链接 K个工人&#xff0c;一共jobs个任务&#xff0c;问怎样分配任务&#xff0c;最短的最长工人完成任务完成时间。 思路 DFS剪枝&#xff08;最大单个工人jobs时间超过ans时间&#xff1b;有限空闲工人拿任务&#xff09;模拟退火dp 代码…...

初始HTTP协议

一、http协议 1、http相关概念 互联网&#xff1a;是网络的网络&#xff0c;是所有类型网络的母集因特网&#xff1a;世界上最大的互联网网络。即因特网概念从属于互联网概念。习惯上&#xff0c;大家把连接在因特网上的计算机都成为主机。万维网&#xff1a;WWW&#xff08;…...

C++ 位运算常用操作 二进制中1的个数

给定一个长度为 n 的数列&#xff0c;请你求出数列中每个数的二进制表示中 1 的个数。 输入格式 第一行包含整数 n 。 第二行包含 n 个整数&#xff0c;表示整个数列。 输出格式 共一行&#xff0c;包含 n 个整数&#xff0c;其中的第 i 个数表示数列中的第 i 个数的二进制表…...

大数据领域的数据仓库

在大数据领域&#xff0c;数据仓库&#xff08;Data Warehouse&#xff09;是一个用于存储、管理和分析大量数据的集中式系统。它从多个异构数据源收集数据&#xff0c;对数据进行清洗、转换和整合&#xff0c;然后将其存储在一个集中的位置&#xff0c;以支持复杂的查询、报告…...

sentinel的资源数据指标是如何采集

资源数据采集 之前的NodeSelectorSlot和ClusterBuilderSlot已经完成了对资源调用树的构建, 现在则是要对资源进行收集, 核心点就是这些资源数据是如何统计 LogSlot 作用: 记录异常请求日志, 用于故障排查 public class LogSlot extends AbstractLinkedProcessorSlot<Def…...

算法刷题:找到字符串中所有的字母异位词

找到字符串中所有的字母异位词 .题目链接题目详情题目解析算法原理滑动窗口流程图定义指针及变量进窗口判断出窗口更新结果 我的答案 . 题目链接 找到字符串中所有的字母异位词 题目详情 题目解析 所谓的异位词,就是一个单词中的字母,打乱顺序,重新排列得到的单词 如:abc-&g…...

【Java EE初阶十九】网络原理(四)

4. 数据链路层 数据链路层也有很多种协议&#xff0c;其中一个比较常见常用的,就是“以太网协议”&#xff08;通过网线/光纤, 来通信所使用的协议叫做以太网协议&#xff0c;以太网是横跨数据链路层 物理层&#xff09;&#xff1b; 4.1 以太网数据帧格式 帧头 载荷(IP 数据…...

12.23 校招 实习 内推 面经

绿*泡*泡VX&#xff1a; neituijunsir 交流*裙 &#xff0c;内推/实习/校招汇总表格 1、社招&校招 | 轻舟智航 社招 & 2024校招 社招&校招 | 轻舟智航 社招 & 2024校招 2、校招 | 成都精灵云科技2024校园招聘补录 校招 | 成都精灵云科技2024校园招聘补录 …...

FPGA转行ISP的探索之一:行业概览

ISP的行业位置 最近看到一个分析&#xff0c;说FPGA的从业者将来转向ISP&#xff08;Image Signal Process图像信号处理&#xff09;是个不错的选择&#xff0c;可以适应智能汽车、AI等领域。故而我查了一下ISP&#xff0c;对它大致有个概念。 传统的ISP对应的是相机公司&…...

新手避坑指南:PX4飞控连接TFmini、LIDAR Lite V3等定高雷达的完整接线与参数配置(QGC实操)

PX4飞控与定高雷达实战&#xff1a;从接线到参数配置的避坑指南 刚拿到PX4飞控和一堆传感器的新手们&#xff0c;面对密密麻麻的接口和参数设置&#xff0c;是不是有种无从下手的感觉&#xff1f;特别是当你需要连接定高雷达时&#xff0c;不同品牌&#xff08;北醒TFmini、LID…...

从零开始玩转translategemma-27b-it:Ollama环境搭建与提示词详解

从零开始玩转translategemma-27b-it&#xff1a;Ollama环境搭建与提示词详解 1. 环境准备与快速部署 想要体验强大的图文翻译能力&#xff0c;首先需要搭建好运行环境。translategemma-27b-it是一个基于Ollama部署的翻译模型&#xff0c;支持文本和图片的翻译功能。 1.1 系统…...

Starry Night Art Gallery效果展示:黄金渐变按钮交互+实时生成反馈

Starry Night Art Gallery效果展示&#xff1a;黄金渐变按钮交互实时生成反馈 1. 沉浸式艺术体验&#xff1a;当AI遇见文艺复兴 想象一下&#xff0c;你走进的不是一个冰冷的AI工具界面&#xff0c;而是一座数字艺术殿堂。四周是深邃的墨蓝色背景&#xff0c;如同梵高笔下的夜…...

无需本地安装,用快马平台5分钟搭建git操作可视化原型

最近在准备一个Git入门教学项目时&#xff0c;发现很多新手卡在环境配置这一步。传统方式需要先安装Git客户端、配置SSH密钥、设置全局参数&#xff0c;光是这些前置操作就能劝退不少人。于是尝试用InsCode(快马)平台的云端开发环境&#xff0c;意外发现能跳过所有安装步骤直接…...

浅谈MIKE URBAN转SWMM的方法

01 前言近期有群友咨询MIKE URBAN怎么转换成SWMM的INP文件格式&#xff0c;其实这个是很简单的&#xff0c;前提是你对两个软件格式足够熟悉&#xff0c;另一方面&#xff0c;很多年前SWMM就开发了inpPNS软件。可以利用这个软件便可实现转换&#xff0c;小编抽时间给大家分享下…...

Qt网络编程实战:基于QTcpSocket构建带进度反馈的可靠文件传输系统

1. 为什么需要带进度反馈的文件传输系统 在开发桌面应用时&#xff0c;文件传输是个绕不开的刚需功能。特别是传输大文件时&#xff0c;用户最怕的就是看着界面发呆——不知道传输进行到哪一步了&#xff0c;也不知道还要等多久。我做过一个医疗影像传输系统&#xff0c;医生们…...

物理引擎核心原理拆解:GJK算法如何用Support函数取代SAT检测

物理引擎核心原理拆解&#xff1a;GJK算法如何用Support函数取代SAT检测 在实时物理模拟的世界里&#xff0c;碰撞检测算法的效率直接决定了虚拟世界的真实感与流畅度。当两个刚体在三维空间中高速运动时&#xff0c;传统分离轴定理&#xff08;SAT&#xff09;需要检测多达15组…...

用STM32和示波器搞定美的/格力空调红外遥控(附完整C代码)

STM32实战&#xff1a;从示波器捕获到空调红外协议逆向全解析 红外遥控技术看似简单&#xff0c;却蕴含着精妙的时序设计和协议逻辑。作为一名长期混迹于硬件开发领域的工程师&#xff0c;我经常遇到需要逆向控制家电的场景。最近在智能家居项目中&#xff0c;就遇到了需要通过…...

新手避坑指南:用Altium Designer打开嘉立创PCB文件,这3个设置不改布线全乱

Altium Designer导入嘉立创PCB文件的三大核心设置解析 刚接触硬件设计的新手工程师们&#xff0c;当你们第一次尝试用Altium Designer打开从嘉立创EDA导出的PCB文件时&#xff0c;是否遇到过这样的场景&#xff1a;板框莫名其妙错位、网络连接全部丢失、设计规则一片混乱&#…...

CST仿真EIT电磁诱导透明:石墨烯建模与案例分析

CST仿真eit电磁诱导透明(包括石墨烯的建模) EIT石墨烯电磁诱导透明案例搞EIT仿真的都知道&#xff0c;传统金属结构虽然经典&#xff0c;但石墨烯的可调性才是现在的香饽饽——靠栅压就能调费米能级&#xff0c;相当于给器件装了个电控遥控器&#xff0c;在传感器、慢光器件里简…...