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

算法训练营day46

一、单词拆分

元素无重可复选

  1. base case i==s.length return true,遍历到了最后,
    1. 因为i+len = s.length,len初始值为1,那么i+1 = s.length,那么i = s.lenth -1 也就是最后一个字符位置
  2. dp(s,i)函数定义:返回 s[i…] 是否能够被拼出
  3. 判断字符串S的前缀[0,k]是否存在于WordDict,存在就递归dp(s, i+len)
class Solution {// 用哈希集合方便快速判断是否存在HashSet<String> wordDict;// 备忘录,-1 代表未计算,0 代表无法凑出,1 代表可以凑出int[] memo;// 主函数public boolean wordBreak(String s, List<String> wordDict) {// 转化为哈希集合,快速判断元素是否存在this.wordDict = new HashSet<>(wordDict);// 备忘录初始化为 -1this.memo = new int[s.length()];Arrays.fill(memo, -1);return dp(s, 0);}// 定义:s[i..] 是否能够被拼出boolean dp(String s, int i) {// base caseif (i == s.length()) {return true;}// 防止冗余计算if (memo[i] != -1) {return memo[i] == 0 ? false : true;}// 遍历 s[i..] 的所有前缀for (int len = 1; i + len <= s.length(); len++) {// 看看哪些前缀存在 wordDict 中String prefix = s.substring(i, i + len);if (wordDict.contains(prefix)) {// 找到一个单词匹配 s[i..i+len)// 只要 s[i+len..] 可以被拼出,s[i..] 就能被拼出boolean subProblem = dp(s, i + len);if (subProblem == true) {memo[i] = 1;return true;}}}// s[i..] 无法被拼出memo[i] = 0;return false;}
}
二、单词拆分2
class Solution {HashSet<String> wordDict;// 备忘录List<String>[] memo;public List<String> wordBreak(String s, List<String> wordDict) {this.wordDict = new HashSet<>(wordDict);memo = new List[s.length()];return dp(s, 0);}// 定义:返回用 wordDict 构成 s[i..] 的所有可能List<String> dp(String s, int i) {List<String> res = new LinkedList<>();if (i == s.length()) {res.add("");return res;}// 防止冗余计算if (memo[i] != null) {return memo[i];}// 遍历 s[i..] 的所有前缀for (int len = 1; i + len <= s.length(); len++) {// 看看哪些前缀存在 wordDict 中String prefix = s.substring(i, i + len);if (wordDict.contains(prefix)) {// 找到一个单词匹配 s[i..i+len)List<String> subProblem = dp(s, i + len);// 构成 s[i+len..] 的所有组合加上 prefix // 就是构成构成 s[i] 的所有组合for (String sub : subProblem) {if (sub.isEmpty()) {// 防止多余的空格res.add(prefix);} else {res.add(prefix + " " + sub);}}}}// 存入备忘录memo[i] = res;return res;}
}

相关文章:

算法训练营day46

一、单词拆分 元素无重可复选 base case is.length return true&#xff0c;遍历到了最后, 因为ilen s.length&#xff0c;len初始值为1&#xff0c;那么i1 s.length&#xff0c;那么i s.lenth -1 也就是最后一个字符位置 dp(s,i)函数定义&#xff1a;返回 s[i…] 是否能够…...

推荐五个线上兼职,在家也能轻松日入百元,适合上班族和全职宝妈

在这个瞬息万变的时代&#xff0c;你是否也曾考虑过在繁忙的工作之外&#xff0c;寻找一份兼职副业来补贴家用&#xff0c;同时保持生活的多样性&#xff1f;别急&#xff0c;现在就让我为你揭秘五个可靠的日结线上兼职岗位&#xff0c;助你轻松迈向财务自由之路&#xff01; 一…...

Python_文件操作_学习

目录 一、关于文件的打开和关闭 1. 文件的打开 2.文件的关闭 二、文件的读取 1. 文件的读_r 2. 使用readline 3.使用readlines 三、文件的写入 1. 文本的新建写入 2.文本的追加写入 四、文件的删除和重命名 1.文件的重命名 2.文件的删除 五、文件的定位读写 1.t…...

Leetcode 3154. Find Number of Ways to Reach the K-th Stair

Leetcode 3154. Find Number of Ways to Reach the K-th Stair 1. 解题思路2. 代码实现 题目链接&#xff1a;3154. Find Number of Ways to Reach the K-th Stair 1. 解题思路 这一题思路上就是一个动态规划&#xff0c;我们只需要确定一下运行的终止条件&#xff0c;然后写…...

Vue3/Vite引入EasyPlayer.js播放H265视频错误的问题

一、引入EasyPlayer.js github链接:GitHub - EasyDarwin/EasyPlayer.js: EasyPlayer.js H5播放器 将demo/html目录下的 EasyPlayer-element.min.js、EasyPlayer-lib.min.js、EasyPlayer.wasm、jquery.min.js 复制到vue3工程的public目录下,注意,vue3 vite的index.html文件…...

CentOS 7安装alertmanager

说明&#xff1a;本文介绍如何在CentOS 7安装alertmanager&#xff1b; Step1&#xff1a;下载安装包 访问Github仓库&#xff0c;下载对应版本的alertmanager安装包 https://github.com/prometheus/alertmanager/releases 如何查看自己系统的信息&#xff0c;可参考下图中的…...

YOLOv10详细解读 | 一文带你深入了解yolov10的创新点(附网络结构图 + 举例说明)

前言 Hello大家好&#xff0c;我是Snu77&#xff0c;继YOLOv9发布时间没有多久&#xff0c;YOLOv10就紧接着发布于2024.5.23号&#xff08;不得不感叹YOLO系列的发展速度&#xff0c;但要纠正大家的观点就是不是最新的就一定最好&#xff09;&#xff01; 本文给大家带来的是…...

【openlayers系统学习】3.5colormap详解(颜色映射)

五、colormap详解&#xff08;颜色映射&#xff09; ​colormap​ 包是一个很好的实用程序库&#xff0c;用于创建颜色图。该库已作为项目的依赖项添加&#xff08;1.7美化&#xff08;设置style&#xff09;&#xff09;。要导入它&#xff0c;请编辑 main.js​ 以包含以下行…...

Redis教程(十五):Redis的哨兵模式搭建

一、搭建Redis一主二从 分别复制三份Redis工作文件夹&#xff0c;里面内容一致 接着修改7002的配置文件&#xff0c;【redis.windows-service.conf】 port 7002 改成 port 7002 slaveof 127.0.0.1 7001 7003也同样修改 port 7003 slaveof 127.0.0.1 7001 这样就指定了700…...

【C语言】8.C语言操作符详解(3)

文章目录 10.操作符的属性&#xff1a;优先级、结合性10.1 优先级10.2 结合性 11.表达式求值11.1 整型提升11.2 算术转换11.3 问题表达式解析11.3.1 表达式111.3.2 表达式211.3.3 表达式311.3.4 表达式411.3.5 表达式5: 11.4 总结 10.操作符的属性&#xff1a;优先级、结合性 …...

离线初始化k8s

导出和导入所有必要的 Kubernetes 镜像&#xff0c;使用阿里云作为源。 在能访问外网的机器上拉取镜像 首先&#xff0c;在有外网访问的机器上运行以下命令来拉取所有 Kubernetes v1.29.5 版本需要的镜像&#xff1a; kubeadm config images pull --image-repository regist…...

C++字符编码 cppp-reiconv库使用详解

经常写一些控制台小程序&#xff0c;常常会遇到输出中文乱码的问题&#xff0c;在windwos下可以使用MultiByteToWideChar转换字符编码&#xff0c;但跨平台就需要cppp-reiconv这样的第三方字符编码处理库&#xff0c;且开源。 一、下载cppp-reiconv库的源码和静/动态库 GitHu…...

通过继承React.Component创建React组件-5

在React中&#xff0c;V16版本之前有三种方式创建组件&#xff08;createClass() 被删除了)&#xff0c;之后只有两种方式创建组件。这两种方式的组件创建方式效果基本相同&#xff0c;但还是有一些区别&#xff0c;这两种方法在体如下&#xff1a; 本节先了解下用extnds Reac…...

PgSQL内核机制 - 算子执行统计元组个数

PgSQL内核机制 - 算子执行统计元组个数 我们在执行explain analyze观察执行计划执行情况时&#xff0c;时常通过每个算子实际执行结果来分析SQL的执行&#xff0c;其中有一项“rows XXX”表示执行的行数&#xff08;这里姑且先认为是执行的真实行数&#xff09;。但有些场景下…...

Ubuntu/Linux 安装Paraview

文章目录 0. 卸载已有ParaView1. 安装ParaView1.1 下载后安装 2.进入opt文件夹改名3. 更改启动项4. 创建硬链接5. 添加桌面启动方式6. 即可使用 0. 卸载已有ParaView YUT 1. 安装ParaView https://www.paraview.org/ 1.1 下载后安装 找到下载的文件夹&#xff0c;文件夹内…...

内存泄漏及其解决方法

1. 系统崩溃前的现象 垃圾回收时间延长&#xff1a;从原本的约10ms增长至50ms&#xff0c;Full GC时间也由0.5s增加至4-5s。Full GC频率增加&#xff1a;最短间隔可缩短至1分钟内发生一次。年老代内存持续增长&#xff1a;即使经过Full GC&#xff0c;年老代内存未见明显释放。…...

Java进阶学习笔记13——抽象类

认识抽象类&#xff1a; 当我们在做子类共性功能抽取的时候&#xff0c;有些方法在父类中并没有具体的体现&#xff0c;这个时候就需要抽象类了。在Java中&#xff0c;一个没有方法体的方法应该定义为抽象方法&#xff0c;而类中如果有抽象方法&#xff0c;该类就定义为抽象类…...

【Docker学习】深入研究命令docker exec

使用docker的过程中&#xff0c;我们会有多重情况需要访问容器。比如希望直接进入MySql容器执行命令&#xff0c;或是希望查看容器环境&#xff0c;进行某些操作或访问。这时就会用到这个命令&#xff1a;docker exec。 命令&#xff1a; docker container exec 描述&#x…...

C语言中的文件操作

前言 嗨&#xff0c;我是firdawn&#xff0c;在本章中我们将介绍&#xff0c;文件的概念&#xff0c;文件的打开和关闭&#xff0c;在篇末我们将介绍文件缓冲区的作用&#xff0c;下面是本章的思维导图&#xff0c;接下来&#xff0c;让我们开始今天的学习吧&#xff01; 一…...

python使用xlrd读取excel的时候把字符串读成了数字

xlrd 是一个 Python 库&#xff0c;用于读取 Excel 文件&#xff08;.xls 和 .xlsx&#xff0c;但 .xlsx 需要 openpyxl 或 xlrd 的较新版本&#xff09;。然而&#xff0c;xlrd 在读取 Excel 文件时通常会将单元格的内容按其原始数据类型&#xff08;如字符串、数字、日期等&a…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

简约商务通用宣传年终总结12套PPT模版分享

IOS风格企业宣传PPT模版&#xff0c;年终工作总结PPT模版&#xff0c;简约精致扁平化商务通用动画PPT模版&#xff0c;素雅商务PPT模版 简约商务通用宣传年终总结12套PPT模版分享:商务通用年终总结类PPT模版https://pan.quark.cn/s/ece1e252d7df...

【Ragflow】26.RagflowPlus(v0.4.0):完善解析逻辑/文档撰写模式全新升级

概述 在历经半个月的间歇性开发后&#xff0c;RagflowPlus再次迎来一轮升级&#xff0c;正式发布v0.4.0。 开源地址&#xff1a;https://github.com/zstar1003/ragflow-plus 更新方法 下载仓库最新代码&#xff1a; git clone https://github.com/zstar1003/ragflow-plus.…...