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

力扣-动态规划-139 单词拆分

思路

  1. dp数组定义:用wordDict数组可以完成不超过j的字符串的可能为dp[j]
  2. 递推公式:
    tmp = s.substr(j - wordDict[i].size(), wordDict[i].size());
    dp[j] = (dp[j - wordDict[i].size()] && wordDict[i] == tmp) || dp[j];
  3. dp数组初始化:dp[0] = true;
  4. 遍历顺序:由于算是排列问题,不同字典语句先后会影响判断,所以先遍历背包再遍历物品,当前容量在前一个容量完成了对所有物品遍历一遍
  5. 时间复杂度:O(n*m)     

代码

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {vector<bool> dp(s.size() + 1, false);dp[0] = true;for (int j = 1; j <= s.size(); j++) {for (int i = 0; i < wordDict.size(); i++) {if (j >= wordDict[i].size()) {string tmp;tmp = s.substr(j - wordDict[i].size(), wordDict[i].size());dp[j] = (dp[j - wordDict[i].size()] && wordDict[i] == tmp) || dp[j];}}}return dp[s.size()];}
};

相关文章:

力扣-动态规划-139 单词拆分

思路 dp数组定义&#xff1a;用wordDict数组可以完成不超过j的字符串的可能为dp[j]递推公式&#xff1a; tmp s.substr(j - wordDict[i].size(), wordDict[i].size()); dp[j] (dp[j - wordDict[i].size()] && wordDict[i] tmp) || dp[j]; dp数组初始化&#xff1a;…...

建筑能耗监测系统数据采集装置 物联网网关功能参数介绍

安科瑞刘鸿鹏 摘要 随着物联网&#xff08;IoT&#xff09;技术的迅猛发展&#xff0c;现代物联网系统的规模和复杂度不断增加&#xff0c;各种智能设备和传感器的广泛应用为数据采集和分析提供了丰富的信息源。然而&#xff0c;面对不同协议、标准和通信方式的设备&#xff…...

vue深拷贝:1、使用JSON.parse()和JSON.stringify();2、使用Lodash库;3、使用深拷贝函数(采用递归的方式)

文章目录 引言三种方法的优缺点在Vue中,实现数组的深拷贝I JSON.stringify和 JSON.parse的小技巧深拷贝步骤缺点:案例1:向后端请求路由数据案例2: 表单数据处理时复制用户输入的数据II 使用Lodash库步骤适用于复杂数据结构和需要处理循环引用的场景III 自定义的深拷贝函数(…...

ES 删除index 的curl

以下是使用 `curl` 命令删除 Elasticsearch 索引的格式和示例: ### 基本格式 ```bash curl -XDELETE "http://<node-ip|hostname>:9200/<index-name>" ``` - `<node-ip|hostname>`:Elasticsearch 节点的 IP 地址或主机名。 - `<index-name&g…...

游戏引擎学习第124天

仓库:https://gitee.com/mrxiao_com/2d_game_3 回顾/复习 今天是继续完善和调试多线程的任务队列。之前的几天&#xff0c;我们已经介绍了多线程的一些基础知识&#xff0c;包括如何创建工作队列以及如何在线程中处理任务。今天&#xff0c;重点是解决那些我们之前没有注意到…...

第十四届蓝桥杯Scratch11月stema选拔赛真题——小猫照镜子

编程实现&#xff1a; 小猫照镜子。(背景非源素材) 具体要求&#xff1a; 1). 运行程序&#xff0c;角色、背景如图所示&#xff1b; 完整题目可点击下方链接查看&#xff0c;支持在线编程~ 小猫照镜子_scratch_少儿编程题库学习中心-嗨信奥https://www.hixinao.com/tiku/s…...

使用vscode导出Markdown的PDF无法显示数学公式的问题

我的硬件环境是M2的MacBook air&#xff0c;在vscode中使用了Markdown PDF来导出md文件对应的PDF。但不管导出html还是PDF文件&#xff0c;数学公式都是显示的源代码。 我看了许多教程&#xff0c;给的是这个方法&#xff1a;在md文件对应的html文件中加上以下代码&#xff1a…...

前端系列之:Blob

Blob 与二进制 什么是二进制&#xff1f; 二进制是计算机数据的基本表示形式&#xff0c;只使用 0 和 1 两个数字来表示数值。任何类型的数据&#xff08;无论是文本、图片、音频文件等&#xff09;都可以通过二进制表示。 什么是 Blob&#xff1f; 全称 Binary Large Object&a…...

【项目管理】基于 C 语言的 QQ 聊天室实现(TCP + 多线程 + SQLite3)

基于 C 语言的 QQ 聊天室(TCP + 多线程 + SQLite3) 项目功能基础功能: 登录、注册、添加好友、私聊、创建群聊、群聊扩展功能: 删除好友、注销账号、好友在线状态、群管理(拉人/踢人)、VIP 特权、邮件通知等 功能介绍:模拟QQ聊天客户端:登录界面:1、登录2、注册 //将用…...

Apache Flink:实时数据流处理的终极武器

Apache Flink&#xff1a;实时数据流处理的终极武器 在当今这个数据驱动的世界&#xff0c;实时数据流处理已经成为各行各业的核心需求。从金融风控到电商推荐&#xff0c;从物联网监控到网络安全&#xff0c;毫秒级的响应能力决定了一家公司在市场中的竞争力。而在众多流式计…...

点云处理入门--PointNetPointNet++论文与代码详解

基础知识 点云数据&#xff1a; 点云是一种通过三维扫描设备或计算机图形学技术获取的三维空间数据&#xff0c;通常由一系列点组成&#xff0c;每个点包含其在三维空间中的坐标&#xff08;如 x,y,z&#xff09;&#xff0c;有时还可能包含颜色、强度等附加信息。 介绍几种常…...

通过Nginx负载均衡+Keepalived实现业务高可用

通过Nginx负载均衡和Keepalived可以实现业务的高可用&#xff0c;以下是详细的实现步骤&#xff1a; 环境准备 假设我们有3台服务器&#xff0c;IP地址分别为&#xff1a; 服务器1&#xff08;Nginx Keepalived 主节点&#xff09;&#xff1a;192.168.1.100服务器2&#x…...

Spark技术系列(三):Spark算子全解析——从基础使用到高阶优化

Spark技术系列(三):Spark算子全解析——从基础使用到高阶优化 1. 算子核心概念与分类体系 1.1 算子本质解析 延迟执行机制:转换算子构建DAG,行动算子触发Job执行任务并行度:由RDD分区数决定(可通过spark.default.parallelism全局配置)执行位置优化:基于数据本地性的…...

ES6模块化详解:导入与导出方式

在现代 JavaScript 开发中&#xff0c;模块化是代码管理和组织的重要工具。ES6&#xff08;ECMAScript 2015&#xff09;引入了模块化的概念&#xff0c;通过 import 和 export 来组织代码&#xff0c;使得模块的管理变得更加清晰和简洁。本文将详细介绍 ES6 中的各种模块导入导…...

每日学习Java之一万个为什么?[MySQL面试篇]

分析SQL语句执行流程中遇到的问题 前言1 MySQL是怎么在一台服务器上启动的2 MySQL主库和从库是同时启动保持Alive的吗&#xff1f;3 如果不是主从怎么在启动的时候保证数据一致性4 ACID原则在MySQL上的体现5 数据在MySQL是通过什么DTO实现的6 客户端怎么与MySQL Server建立连接…...

常用空间数据结构对比

空间数据结构是用来组织和查询多维空间数据的算法结构。它们在地理信息系统 (GIS)、计算机图形学、机器人导航、机器学习等领域非常重要。以下是几种常见空间数据结构的对比&#xff1a; 1. 四叉树&#xff08;Quadtree&#xff09; 适用场景&#xff1a;二维空间数据&#x…...

AnythingLLM+LM Studio本地知识库构建

前置操作&#xff1a; 已经安装以下软件&#xff0c;并配置后&#xff1a; DeepSeek-R1-Distill-Llama-8B-Q4_K_M.ggufLM-Studio-0.3.10-6-x64 软件准备&#xff1a; 下载AnythingLLM&#xff1a;AnythingLLM | The all-in-one AI application for everyone 点击"Dow…...

使用 Java 更新 Word 文档中的图表数据-超详细

使用 Java 更新 Word 文档中的图表数据 在日常的工作中&#xff0c;尤其是在数据分析和报告自动化的场景中&#xff0c;可能会遇到需要定期更新 Word 文档中的图表数据的需求。比如&#xff0c;生成数据报告时&#xff0c;我们需要在图表中更新一些动态的数据值。今天&#xf…...

Qt常用控件之下拉框QComboBox

下拉框QComboBox QComboBox 是一个下拉框控件。 1. QComboBox属性 属性说明currentText当前选中的文本。currentIndex当前选中的条目下标&#xff08;从 0 开始&#xff0c;如果没有条目被选中则该值为 -1&#xff09;。editable是否允许被修改。为 true 时&#xff0c;QCom…...

Qt 中集成mqtt协议

一&#xff0c;引入qmqtt 库 我是将整个头文件/源文件都添加到了工程中进行编译&#xff0c;这样 跨平台时 方便&#xff0c;直接编译就行了。 原始仓库路径&#xff1a;https://github.com/emqx/qmqtt/tree/master 二&#xff0c;使用 声明一个单例类&#xff0c;将订阅到…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...