当前位置: 首页 > 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对应的是相机公司&…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...

Xcode 16 集成 cocoapods 报错

基于 Xcode 16 新建工程项目&#xff0c;集成 cocoapods 执行 pod init 报错 ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchro…...