当前位置: 首页 > 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…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...