【动态规划】子数组系列(下)


1. 等差数列划分
413. 等差数列划分

状态表示:以 i 位置为结尾时的等差数列的个数
状态转移方程:由于至少需要三个元素才符合题目中等差数列的要求,所以需要判断 i - 2,i - 1,i 三个元素,当这三个元素符合等差数列时,那么以 i - 1 为结尾的等差数列再加上 i 也是等差数列,等差数列的个数就 + 1,如果说这三个元素不符合等差数列,那么以 i 为结尾的等差数列个数就是 0

初始化:由于三个元素才能进行等差数列的判断,所以 dp[0],dp[1] 初始化为 0
返回值:如果数组长度小于 3 直接返回 0,大于等于 3 就返回 dp 数组的和
class Solution {public int numberOfArithmeticSlices(int[] nums) {int n = nums.length;int[] dp = new int[n];int ret = 0;if(n < 3) return 0;for(int i = 2;i < n;i++){dp[i] = (nums[i] - nums[i - 1]) == (nums[i - 1] - nums[i - 2]) ? dp[i - 1] + 1:0; ret += dp[i];}return ret;}
}
2. 最长湍流子数组
978. 最长湍流子数组

状态表示:先用 dp[i] 来表示以第 i 个位置为结尾时的最长湍流数组的长度
f[i]:表示以第 i 个位置为结尾时表示上升状态的最长湍流数组的长度
f[i]:表示以第 i 个位置为结尾时表示下降状态的最长湍流数组的长度
状态转移方程:

第 i - 1 和 i 位置的状态可能会有下降,上升,相等三种状态,所以定义一个 dp 状态就不够了,需要定义一个上升状态和一个下降状态,当 i - 1 到 i 处于下降状态时,之前应该是处于上升状态的,也就是 f[i - 1],再加上 1 就是以第 i 个位置为结尾时处于下降状态的最长数组长度,上升也是一样的道理,需要在第 i - 1 位置处于下降状态,就是 g[i - 1] + 1,相等时等于 1 即可
初始化:由于 1 个元素也可以称为湍急子数组,所以可以把 0 下标初始化为 1,又因为状态转移方程中的其他情况是 1 ,为了方便,可以把初始的两个 dp 表都初始化为 1
填表顺序:从左到右
返回值:下降和上升状态的最大值
class Solution {public int maxTurbulenceSize(int[] arr) {int n = arr.length;int[] f = new int[n];int[] g = new int[n];for(int i = 0;i < n;i++){f[i] = g[i] = 1;}int ret = 1;for(int i = 1;i < n;i++){if(arr[i] > arr[i - 1]){g[i] = f[i - 1] + 1;}else if(arr[i] < arr[i - 1]){f[i] = g[i - 1] + 1;}ret = Math.max(Math.max(ret,g[i]),f[i]);}return ret;}
}
3. 单词拆分
139. 单词拆分

状态表示:dp[i] 表示以 i 为结尾时,区间 [0 , i] 之间内能否被字典中的单词拼接而成
状态转移方程:

可以把区间分为两段,设 j 为最后一个单词的起始位置的下标,如果 [0 , j - 1] 区间内能够被字典中的单词拼接而成,也就是 dp[j - 1],再加上 j ~ i 区间的单词在数组中,那么就说明 0 ~ i 区间可以被字典中的单词拼接而成
初始化:为了方便表示 ,dp 数组还是开 n + 1(n 为所给字符串的长度),此时 dp[0] 需要设置为 true 才能不影响后续的判断,如果是 false 的话,那么后面区间就一直都不可以被拼接,dp 数组长度 + 1 之后,为了更方便的表示下标的映射关系,可以把原来的字符串 s 最前面加一个长度为 1 的占位符,这样字符串的下标也对应着 dp 表的下标
填表顺序:从左到右
返回值:dp[n]
为了便于查找 j ~ i 的字符串是否在字典中,可以把题中的字典映射到哈希表中
class Solution {public boolean wordBreak(String s, List<String> wordDict) {int n = s.length();boolean[] dp = new boolean[n + 1];dp[0] = true;s = " " + s;Set<String> hash = new HashSet(wordDict);for(int i = 1;i <= n;i++){//字符串长度 + 1,对应的 j 最小就是 1 下标for(int j = i;j >= 1;j--){//substring 前闭后开 ,所以 i + 1if(dp[j - 1] && hash.contains(s.substring(j,i + 1))){dp[i] = true;//如果找到一种再往前就不用找了break;}} }return dp[n];}
}
4. 环绕字符串中唯一的子字符串
467. 环绕字符串中唯一的子字符串

状态表示:dp[i] 表示以 i 位置为结尾时,有多少子串出现
状态转移方程:

和上一题其实差不多,可以分为长度为 1 和长度大于 1 的,只需要判断是否是连续的,前一个是“z”后一个是 "a" 也算是连续的
初始化:由于长度为 1 时可以算出现一次,长度大于 1 就是找到以 i - 1 为结尾的子串再加上 s[i] ,整体的数量还是 dp[i - 1],dp[i] 就是把长度为 1 和长度大于 1 的两种情况加起来,所以可以把整个 dp 表初始化为 1 ,然后就只需要判断长度大于 1 时的情况直接相加就行
填表顺序:从左到右
返回值:由于 dp[i] 中存储的是以 i 为结尾时的子串出现的次数,这就可能出现多次,例如“cac”

相同的子串只能统计一次,并且可以发现,以同一个字符结尾的子串只需要统计最长的即可,短的情况就包含在了长的情况,所以可以额外定义一个 hash 表来存储最终的答案,最后只需返回 hash 表中的所有和即可
class Solution {public int findSubstringInWraproundString(String s) {int n = s.length();int[] dp = new int[n];Arrays.fill(dp, 1);//表示 26 个字母int[] hash = new int[26];char[] chars = s.toCharArray();for(int i = 1;i < n;i++){if((chars[i] == (chars[i - 1] + 1)) || (chars[i] == 'a'&&chars[i - 1] == 'z')){dp[i] += dp[i - 1];}}int ret = 0;for(int i = 0;i < n;i++){//更新为以当前字符为结尾最长子串的数量hash[chars[i] - 'a'] = Math.max(hash[chars[i] - 'a'],dp[i]);}for(int x : hash) ret += x;return ret;}
}

相关文章:
【动态规划】子数组系列(下)
1. 等差数列划分 413. 等差数列划分 状态表示:以 i 位置为结尾时的等差数列的个数 状态转移方程:由于至少需要三个元素才符合题目中等差数列的要求,所以需要判断 i - 2,i - 1,i 三个元素,当这三个元素符合…...
macos mendeley Unable to install the Microsoft Word Plugin 解决
windows也是相似的原理,这里主要说macos, 本质是 找到mendeley的插件启动项,放在word启动目录下, GPT-o1的解决方案: 3. Manual Installation (If Automatic Installation Fails) If the automatic installation doe…...
【Linux进程间通信】Linux信号机制深度解析:保存与处理技巧
📝个人主页🌹:Eternity._ ⏩收录专栏⏪:Linux “ 登神长阶 ” 🌹🌹期待您的关注 🌹🌹 ❀Linux进程间通信 📒1. 信号的保存🌊在内核中的表示🍂sigs…...
常见开源组件的详解
文章目录 RPCRPC架构和工作流程为什么有了HTTP还要用RPC底层协议数据格式连接管理错误处理 使用场景常见的RPC框架 Web应用框架主要功能常见的Web应用框架Spring Boot (Java)Django (Python)Express.js (Node.js) Redis主要特点应用场景缓存问题Redis集群架构主从复制Redis Clu…...
rust使用教程详解
欢迎来到 Rustlings。该项目包含一些小练习,让您习惯阅读和编写 Rust 代码。这包括阅读和响应编译器消息! 建议在阅读Rust 官方书籍(学习 Rust 最全面的资源)的同时做 Rustlings 练习 📚️ Rust By Example是另一个推…...
并查集的实现(朴素版)
这是C算法基础-数据结构专栏的第二十九篇文章,专栏详情请见此处。 由于作者即将参加CSP,所以到比赛结束前将不再发表文章! 引入 并查集是一种可以快速合并查找集合的一种数据结构,这次我们将通过三道题来详细讲解并查集ÿ…...
WPF 为button动态设置不同的模板
有时候需要动态的设置一些按钮的状态模板。使一个button显示不同的内容,比如Button未点击安装显示: 安装后显示: 可以通过设置button的content,通过content来设置不同的模板来实现功能,以下是代码: MainWi…...
【C++贪心 DFS】2673. 使二叉树所有路径值相等的最小代价|1917
本文涉及知识点 C贪心 反证法 决策包容性 CDFS LeetCode2673. 使二叉树所有路径值相等的最小代价 给你一个整数 n 表示一棵 满二叉树 里面节点的数目,节点编号从 1 到 n 。根节点编号为 1 ,树中每个非叶子节点 i 都有两个孩子,分别是左孩子…...
虚幻引擎GAS入门学习笔记(一)
虚幻引擎GAS入门(一) Gameplay Ability System(GAS) 是一个模块化且强大的框架,用于管理虚幻引擎中的游戏玩法逻辑。它的核心组成部分包括 Gameplay Ability(定义和执行能力)、Gameplay Effect(应用和管理…...
Excel:vba实现合并工作表(表头相同)
这个代码应该也适用于一些表头相同的工作表的汇总,只需要修改想要遍历的表,适用于处理大量表头相同的表的合并 这里的汇总合并表 total 是我事先创建的,我觉得比用vba代码创建要容易一下,如果不事先创建汇总表就用下面的代码&…...
Redis:分布式 - 主从复制
Redis:分布式 - 主从复制 概念配置主从模式info replicationslave-read-onlytcp-nodelay 命令slaveof 主从结构一主一从一主多从 主从复制流程数据同步命令全量同步部分同步实时同步 节点晋升 概念 Redis的最佳应用,还是要在分布式系统中。对于非分布式…...
el-date-picker设置只有某些日期可选
示例图: <el-date-pickerv-model"topFormObj.upTime"type"date"value-format"timestamp"format"dd/MM/yyyy":picker-options"pickerOptions" /> 固定限制每周的周末周三不可选 data() {return {pickerOp…...
java数据库操作-cnblog
创建lib目录,填入jar包 选择 libraries添加lib目录 package nb;import java.sql.Connection; import java.sql.DriverManager; import java.sql.SQLException;public class JDBCtest {private static final String url "jdbc:mysql://localhost:3306/test?c…...
HCIP-HarmonyOS Application Developer 习题(九)
(多选) 1、HarmonyOS多窗口交互能力提供了以下哪几种交互方式? A. 全局消息通知 B.平行视界 C.悬浮窗 D.分屏 答案:BCD 分析:系统提供了悬浮窗、分屏、平行视界三种多窗口交互,为用户在大屏幕设备上的多任务并行、便捷的临时任务…...
redis集成到spring boot中使用
(一)添加依赖 redis服务器在官网中公开了自己使用的协议--RESP,所以我们可以使用这个协议来访问redis服务器,但是如果我们要自己实现库,那肯定是非常麻烦的,所以我们可以使用网上的库,我们直接调…...
Spring Boot、Spring MVC和Spring有什么区别
人要长大,就要学会不断接受事件的变化 —— 24.10.14 spring是一个IOC容器,用来管理Bean,使用依赖注入实现控制反转,可以很方便的整合各种框架,提供AOP机制弥补OOP的代码重复问题、更方便将不同类不同方法中的共同处理…...
Flip动画
前言 最近在做复图标库功能时,感觉这个功能在使用上有些“生硬”。如随机删除一个图标,后面的元素在视觉上是“瞬间移动”过来补位的。想着做个小优化,简单加个动画效果吧。 看起来确实“花里胡哨”了,实现也很简单, …...
Java通过RAG构建专属知识问答机器人_超详细
RAG:融合检索与生成的文本精准生成技术 检索增强生成(RAG)是一种技术,它通过结合检索模型和生成模型来提高文本生成的准确性。具体来说,RAG首先利用检索模型从私有或专有的数据源中搜索相关信息,然后将这些…...
2.1 使用点对点信道的数据链路层
欢迎大家订阅【计算机网络】学习专栏,开启你的计算机网络学习之旅! 文章目录 前言1 通信信道类型2 数据链路3 帧4 透明传输5 差错检测 前言 在计算机网络通信中,数据链路层起着关键作用。它为直接相连的网络设备之间提供可靠的数据传输服务。…...
台式机来电自启动设置
在前司时,由于有些工作需要用到台式机,且一到节假日或者突然停电等情况,电脑每次都需要自己手动开机,后来研究了一下,发现可以在BIOS里面更改设置,从而变成关机的情况下,只要来电就能自动开机&a…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

