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

代码随想录算法训练营第三十八天-动态规划-完全背包-139.单词拆分

  • 类似于回溯算法中的拆分回文串
  • 题目是要求拆分字符串,问这些字符串是否出现在字典里。但这道题可以反着来考虑,从字典中的单词能不能组成所给定的字符串
    • 如果这样考虑, 这个字符串就背包,容器
    • 字典中的单词就是一个一个物品
    • 问题就转化成这些物品能不能正好装满这个背包,而且这些物品可以使用多次
    • 因此这是一个完全背包类问题
  • 动规五部曲
    • dp[j]数组含义:把题目给定的字符串能不能用字典字符串来添满。字符串长度为j时,能被字典字符串来组成,就返回true,否则为false
    • 递推公式:道德字符串中[i, j]内容正好字典中,而且dp[i]也为true的话,dp[j]也就是true
    • 初始化值:dp[0]必须为true,否则递推出来的内容都会是false
      • 非0下标都要初始化为false
    • 遍历顺序:给定字符串的内容是确定的,也就是说字典中内容是一种排列效果来生成字符串,而不是组合出多种效果来组成字符串(也根本组不成)
      • 所以要先遍历背包,再遍历物品
class Solution {
public:bool wordBreak(std::string s, std::vector<std::string>& wordDict) {std::unordered_set<std::string> wordSet(wordDict.begin(), wordDict.end());std::vector<bool> dp(s.size() + 1, false);dp[0] = true;for (int i = 1; i <= s.size(); ++i) {for (int j = 0; j < i; ++j) {std::string word = s.substr(j, i - j);if (wordSet.find(word) != wordSet.end() && dp[j])dp[i] = true;}}return dp.at(s.size());}
};
  • 汇总

相关文章:

代码随想录算法训练营第三十八天-动态规划-完全背包-139.单词拆分

类似于回溯算法中的拆分回文串题目是要求拆分字符串&#xff0c;问这些字符串是否出现在字典里。但这道题可以反着来考虑&#xff0c;从字典中的单词能不能组成所给定的字符串 如果这样考虑&#xff0c; 这个字符串就背包&#xff0c;容器字典中的单词就是一个一个物品问题就转…...

ML基础-Jupyter notebook中的魔法命令

在 Jupyter Notebook 或 IPython 环境中&#xff0c;“魔法命令”&#xff08;Magic Commands&#xff09;是一些以百分号&#xff08;%&#xff09;或惊叹号&#xff08;!)开头的特殊命令&#xff0c;用于执行一些与代码运行环境相关的操作&#xff0c;而不仅仅是执行普通的 P…...

Zookeeper入门部署(单点与集群)

本篇文章基于docker方式部署zookeeper集群&#xff0c;请先安装docker 目录 1. docker初期准备 2.启动zookeeper 2.1 单点部署 2.2 集群部署 3. Linux脚本实现快速切换启动关闭 1. docker初期准备 拉取zookeeper镜像 docker pull zookeeper:3.5.6 如果拉取时间过长&#xf…...

Kafa分区策略实现

引言 Kafka 的分区策略决定了生产者发送的消息会被分配到哪个分区中&#xff0c;合理的分区策略有助于实现负载均衡、提高消息处理效率以及满足特定的业务需求。 轮询策略&#xff08;默认&#xff09; 轮询策略是 Kafka 默认的分区策略&#xff08;当消息没有指定键时&…...

Pyside/Pyqt中QWebEngineView和QWebEnginePage的区别

在 PySide/Qt 的 WebEngine 模块中&#xff0c;QWebEngineView 和 QWebEnginePage 是两个紧密相关但职责不同的类。以下是它们的核心区别和关系&#xff1a; 1. 职责区分 类名核心职责模块归属QWebEngineView作为可视化的窗口部件&#xff08;Widget&#xff09;&#xff0c;负…...

Kafka的内部通信协议

引言 kafka内部用到的常见协议和优缺点可以看看原文 Kafka用到的协议 本文奖详细探究kafka核心通信协议和高性能的关键 网络层通信的实现 基于 Java NIO&#xff1a;Kafka 的网络通信层主要基于 Java NIO 来实现&#xff0c;这使得它能够高效地处理大量的连接和数据传输。…...

强大到工业层面的软件

电脑数据删不干净&#xff0c;简直是一种让人抓狂的折磨&#xff01;明明已经把文件扔进了回收站&#xff0c;清空了&#xff0c;可那些残留的数据就像牛皮癣一样&#xff0c;怎么也除不掉。这种烦恼简直无处不在&#xff0c;让人从头到脚都感到无比烦躁。 首先&#xff0c;心…...

数据分析和AI丨应对AI实施挑战,工程领域AI应用的五大方法

工程领域的人工智能 &#xff08;AI&#xff09; 已经开始发挥价值&#xff0c;低代码和无代码工具正在使曾经仅属于专业数据科学家的 AI 能力变得大众化。 然而&#xff0c;并非工程领域的每个人都能从中受益&#xff0c;使用新的便捷的 AI 工具提高工作效率并不难&#xff0c…...

54. UDP协议

UDP协议 UDP&#xff08;User Datagram Protocol&#xff0c;用户数据报协议&#xff09;是一个无连接的传输层协议&#xff0c;它提供简单的、不可靠的信息传送服务。与TCP&#xff08;传输控制协议&#xff09;不同&#xff0c;UDP不提供数据包的排序、错误检查&#xff08;仅…...

AJAX笔记入门篇

黑马程序员视频地址&#xff1a; 黑马程序员前端AJAX入门到实战全套教程https://www.bilibili.com/video/BV1MN411y7pw?vd_source0a2d366696f87e241adc64419bf12cab&spm_id_from333.788.videopod.episodes&p2https://www.bilibili.com/video/BV1MN411y7pw?vd_source…...

深入解析Java集合框架:春招面试要点

在上一篇文章中&#xff0c;我们深入探讨了Java核心基础&#xff0c;这是学习Java的基石。而在实际的Java开发中&#xff0c;集合框架的使用频率极高&#xff0c;它为我们提供了丰富的数据结构和算法实现&#xff0c;极大地提高了开发效率。对于春招面试来说&#xff0c;集合框…...

【Elasticsearch】Elasticsearch的查询

Elasticsearch的查询 DSL查询基础语句叶子查询全文检索查询matchmulti_match 精确查询termrange 复合查询算分函数查询bool查询 排序分页基础分页深度分页 高亮高亮原理实现高亮 RestClient查询基础查询叶子查询复合查询排序和分页高亮 数据聚合DSL实现聚合Bucket聚合带条件聚合…...

STM32 PWM驱动直流电机

接线图&#xff1a; 代码配置&#xff1a; 根据驱动舵机的代码来写&#xff0c;与舵机不同的是&#xff0c;这次的引脚接到了PA2上&#xff0c;所以需要改一下引脚以及改为OC3通道。 另外还需在配置两个GPIO引脚&#xff0c;来控制电机的旋转方向&#xff0c;这里连接到了PA4与…...

系统思考—心智模式

“我们的大脑对连贯性的渴望远胜于对准确性的追求。”—诺贝尔经济学得主丹尼尔卡尼曼 在面对复杂的决策时&#xff0c;我们往往更倾向于寻找那些能够迅速串联起来的信息&#xff0c;而非深入挖掘每一个细节的真实性。这种倾向在日常生活中或许能帮助我们迅速作出决策&#xf…...

JavaScript_02 表单

表单常用演示: 1.图片 结果失真了... 2.切换图片 切换结果 3.表单:...

【Qt】06-对话框

对话框 前言一、模态和非模态对话框1.1 概念1.2 模态对话框1.2.1 代码QAction类 1.2.2 模态对话框运行分析 1.3 非模态对话框1.3.1 代码局部变量和成员变量setAttribute 类 1.3.2 现象解释 二、标准对话框2.1 提示对话框 QMessageBox2.1.1 现象及解释 2.2 问题对话框2.2.1 现象…...

AI学习指南Ollama篇-使用Ollama构建自己的私有化知识库

一、引言 (一)背景介绍 随着企业对数据隐私和效率的重视,私有化知识库的需求日益增长。私有化知识库不仅可以保护企业数据的安全性,还能提供高效的知识管理和问答系统,提升企业内部的工作效率和创新能力。 (二)Ollama和AnythingLLM的结合 Ollama和AnythingLLM的结合…...

2.策略模式(Strategy)

定义 定义一系列算法&#xff0c;把它们一个个封装起来&#xff0c;并且使他们可互相替换&#xff08;变化&#xff09;。该模式使算法可独立于使用它的客户程序&#xff08;稳定&#xff09;而变化&#xff08;拓展&#xff0c;子类化&#xff09;。 动机&#xff08;Motiva…...

Python里的小整数问题挺有意思的

简单来说&#xff0c;Python为了优化性能&#xff0c;会把一些常用的整数&#xff08;通常是-5到256&#xff09;提前创建好&#xff0c;放到一个“缓存池”里。这样&#xff0c;当你用到这些小整数时&#xff0c;Python就不用每次都重新创建对象了&#xff0c;直接从缓存池里拿…...

开源智慧园区管理系统对比五款主流产品探索智能运营新模式

内容概要 在这个数字化迅速发展的时代&#xff0c;园区管理也迎来了全新的机遇和挑战。众所周知&#xff0c;开源智慧园区管理系统作为一种创新解决方案&#xff0c;正逐步打破传统管理的局限性。它的开放性不仅使得系统可以根据具体需求进行灵活调整&#xff0c;也为用户提供…...

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

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

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...