当前位置: 首页 > 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;也为用户提供…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...