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

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

news 来源：原创 2025/5/15 12:55:29
  • 类似于回溯算法中的拆分回文串
  • 题目是要求拆分字符串，问这些字符串是否出现在字典里。但这道题可以反着来考虑，从字典中的单词能不能组成所给定的字符串
    • 如果这样考虑， 这个字符串就背包，容器
    • 字典中的单词就是一个一个物品
    • 问题就转化成这些物品能不能正好装满这个背包，而且这些物品可以使用多次
    • 因此这是一个完全背包类问题
  • 动规五部曲
    • 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;容器字典中的单词就是一个一个物品问题就转…...

编程日记 2025/5/15 12:55:29

selenium clear（）方法清除文本框内容

在使用Selenium进行Web自动化测试时&#xff0c;清除文本框内容是一个常见的需求。这可以通过多种方式实现&#xff0c;取决于你使用的是哪种编程语言&#xff08;如Python、Java等&#xff09;以及你的具体需求。以下是一些常见的方法&#xff1a; 1. 使用clear()方法 clear…...

编程日记 2025/5/13 5:17:00

新增文章功能

总说 过程参考黑马程序员SpringBoot3Vue3全套视频教程&#xff0c;springbootvue企业级全栈开发从基础、实战到面试一套通关_哔哩哔哩_bilibili 之前又偷懒几天。回老家没事干&#xff0c;玩也玩不好&#xff0c;一玩老是被家里人说。写代码吧还是&#xff0c;他们都看不懂&a…...

编程日记 2025/5/15 10:00:33

【设计测试用例自动化测试性能测试 实战篇】

&#x1f308;个人主页&#xff1a;努力学编程’ ⛅个人推荐&#xff1a; c语言从初阶到进阶 JavaEE详解 数据结构 ⚡学好数据结构&#xff0c;刷题刻不容缓&#xff1a;点击一起刷题 &#x1f319;心灵鸡汤&#xff1a;总有人要赢&#xff0c;为什么不能是我呢 设计测试用例…...

编程日记 2025/5/14 17:15:07

【算法与数据结构】动态规划

目录 基本概念 最长递增子序列&#xff08;中等&#xff09; 最大子数组和&#xff08;中等&#xff09; 基本概念 重叠子问题 一个问题可以被分解为多个子问题&#xff0c;并且这些子问题在求解过程中会被多次重复计算。例如&#xff0c;在计算斐波那契数列时&#xff0c;…...

编程日记 2025/5/15 5:25:52

扣子平台音频功能：让声音也能“智能”起来。扣子免费系列教程（14）

在数字化时代&#xff0c;音频内容的重要性不言而喻。无论是在线课程、有声读物&#xff0c;还是各种多媒体应用&#xff0c;音频都是传递信息、增强体验的关键元素。扣子平台的音频功能&#xff0c;为开发者和内容创作者提供了一个强大而灵活的工具&#xff0c;让音频的使用和…...

编程日记 2025/5/15 11:59:32

【CS61A 2024秋】Python入门课，全过程记录P4（Week7 Generators开始，更新于2025/1/29）

文章目录 关于基本介绍&#x1f44b;新的问题更好的解决方案Week7Mon Generators阅读材料Lab 05: Iterators, MutabilityQ1: WWPD: List-MutationQ2: Insert Items 关于 个人博客&#xff0c;里面偶尔更新&#xff0c;最近比较忙。发一些总结的帖子和思考。 江湖有缘相见&…...

编程日记 2025/5/14 18:01:05

JUC--ConcurrentHashMap底层原理

ConcurrentHashMap底层原理 ConcurrentHashMapJDK1.7底层结构线程安全底层具体实现 JDK1.8底层结构线程安全底层具体实现 总结JDK 1.7 和 JDK 1.8实现有什么不同&#xff1f;ConcurrentHashMap 中的 CAS 应用 ConcurrentHashMap ConcurrentHashMap 是一种线程安全的高效Map集合…...

编程日记 2025/5/14 15:42:46

【Linux网络编程】网络层说明

目录 前言&#xff1a; 1&#xff0c;网络层介绍 2&#xff0c;IP协议 3&#xff0c;IP协议的格式 4&#xff0c;网段划分 5&#xff0c;特殊的IP地址 6&#xff0c;私有IP地址和公网IP地址 前言&#xff1a; 网络层对于程序员来说不太重要&#xff0c;这方面知识大致了…...

编程日记 2025/5/15 12:14:33

002-基于Halcon的图像几何变换

本节将简要介绍Halcon中有关图像几何变换的基本算子及其应用&#xff0c;主要涉及五种常见的二维几何变换形式&#xff1a;平移、镜像、旋转、错切和放缩。这几种变换可归结为一类更高级更抽象的空间变换类型&#xff0c;即仿射变换&#xff08;Affine transformation&#xff…...

编程日记 2025/5/15 12:27:00

unity学习22：Application类其他功能

目录 1 是否允许后台运行 1.1 Application.runInBackground&#xff0c;显示是否允许后台运行 1.2 设置的地方 2 打开URL 2.1 Application.OpenURL("") 打开超链接 3 退出游戏 3.1 Application.Quit() 退出游戏 4 场景相关 5 返回游戏状态 6 控制游戏的行…...

编程日记 2025/5/15 12:49:27

配置cursor进行Java springboot项目开发

本文用于记录如何配置cursor进行Java SpringBoot项目开发&#xff0c;因为项目团队同事基本都是在使用idea开发工具&#xff0c;所以在尝试cursor新ide的时候发现还是有一些小坑要处理一下的。 首先为了后续在多个不同的java项目之间进行切换的时候不想翻来覆去的总配置指定jdk…...

编程日记 2025/5/15 2:38:07

ChirpIoT技术的优势以及局限性

ChirpIoT是一种由上海磐启微电子开发的国产无线射频通讯技术&#xff0c;ChirpIoT技术基于磐启多年对雷达等线性扩频信号的深入研究&#xff0c;并在此基础上对线性扩频信号的变化进行了改进&#xff0c;实现了远距离传输的一种无线通信技术。相关产品型号有E29-400T22D、E290-…...

编程日记 2025/5/15 12:51:53

ODP(OBProxy)路由初探

OBProxy路由策略 Primary Zone 路由 官方声明默认情况&#xff0c;会将租户请求发送到租户的 primary zone 所在的机器上&#xff0c;通过 Primary Zone 路由可以尽量发往主副本&#xff0c;方便快速寻找 Leader 副本。另外&#xff0c;设置primary zone 也会在一定成都上减少…...

编程日记 2025/5/15 12:11:19

【25考研】人大计算机考研复试该怎么准备？有哪些注意事项？

人大毕竟是老牌985&#xff0c;复试难度不会太低&#xff01;建议同学认真复习&#xff01;没有机试还是轻松一些的&#xff01; 一、复试内容 由公告可见&#xff0c;复试包含笔试及面试&#xff0c;没有机试&#xff01; 二、参考书目 官方无给出参考书目&#xff0c;可参照…...

编程日记 2025/5/15 11:54:36

阿里云域名备案

一、下载阿里云App 手机应用商店搜索"阿里云"，点击安装。 二、登录阿里云账号 三、打开"ICP备案" 点击"运维"页面的"ICP备案"。 四、点击"新增网站/App" 若无备案信息，则先新增备案信息。 五、开始备案...

编程日记 2025/5/15 11:41:13

实现基础的shell程序

1. 实现一个基础的 shell 程序&#xff0c;主要完成两个命令的功能 cp 和 ls 1.1.1. cp 命令主要实现&#xff1a; ⽂件复制⽬录复制 1.1.2. ls 命令主要实现&#xff1a; ls -l 命令的功能 1.1. 在框架设计上&#xff0c;采⽤模块化设计思想&#xff0c;并具备⼀定的可扩…...

编程日记 2025/5/15 11:28:46

yolov5错误更改与相关参数详解（train.py）

1.错误更改 main中相关参数 if __name__ __main__:parser argparse.ArgumentParser()parser.add_argument(--weights, typestr, default, helpinitial weights path)parser.add_argument(--cfg, typestr, defaultmodels/yolov5s.yaml, helpmodel.yaml path)parser.add_arg…...

编程日记 2025/5/15 12:41:45

（详细）Springboot 整合动态多数据源 这里有mysql（分为master 和 slave） 和oracle,根据不同路径适配不同数据源

文章目录 Springboot 整合多动态数据源 这里有mysql&#xff08;分为master 和 slave&#xff09; 和oracle1. 引入相关的依赖2. 创建相关配置文件3. 在相关目录下进行编码&#xff0c;不同路径会使用不同数据源 Springboot 整合多动态数据源 这里有mysql&#xff08;分为maste…...

编程日记 2025/5/15 11:30:57

20.Word：小谢-病毒知识的科普文章❗【38】

目录 题目​ NO1.2.3文档格式 NO4.5 NO6.7目录/图表目录/书目 NO8.9.10 NO11索引 NO12.13.14 每一步操作完&#xff0c;确定之后记得保存最后所有操作完记得再次删除空行 题目 NO1.2.3文档格式 样式的应用 选中应用段落段落→开始→选择→→检查→应用一个一个应用ctr…...

编程日记 2025/5/12 16:33:15

arkui-x跨平台与android java联合开发

华为鸿蒙系统采用的是arkts&#xff0c;支持跨平台crossplatform 即前端为arkts&#xff0c;arkui-x框架&#xff0c;后端为其他的语言框架。 本篇示例后端采用的是java&#xff0c;android studio工程。 主要方式是前端鸿蒙完成界面元素、布局等效果&#xff0c;后面androi…...

编程日记 2025/5/15 3:20:14

G. Rudolf and CodeVid-23

题目链接&#xff1a;Problem - G - Codeforces 题目大意&#xff1a; 一种病有 n≤10 种症状。 一种病情可以用一个长度为 n 的01 串表示&#xff0c;其中第 i 个字符表示是否出现该种症状。 现有 m(∑m≤103) 种药&#xff0c;每种药用两个无交集的 01 串表示。第一个 01…...

编程日记 2025/5/14 11:55:23

基于STM32的智能宠物喂食器设计

目录 引言系统设计 硬件设计软件设计 系统功能模块 定时喂食模块远程控制与视频监控模块食物存量检测与报警模块语音互动与用户交互模块数据记录与智能分析模块 控制算法 定时与手动投喂算法食物存量检测与低存量提醒算法数据记录与远程反馈算法 代码实现 喂食控制代码存量检测…...

编程日记 2025/5/15 12:18:47

css中的animation

css的animation animation是一个综合属性,是animation-name, animation-duration, animation-timing-function, animation-delay, animation-iteration-count, animation-direction, animation-fill-mode, animation-play-state, and animation-timeline这些属性的简写 不过在…...

编程日记 2025/5/15 12:29:43

[内网安全] 内网渗透 - 学习手册

这是一篇专栏的目录文档&#xff0c;方便读者系统性的学习&#xff0c;笔者后续会持续更新文档内容。 如果没有特殊情况的话&#xff0c;大概是一天两篇的速度。&#xff08;实验多或者节假日&#xff0c;可能会放缓&#xff09; 笔者也是一边学习一边记录笔记&#xff0c;如果…...

编程日记 2025/5/15 12:12:22

VMware 中Ubuntu无网络连接/无网络标识解决方法【已解决】

参考文档 Ubuntu无网络连接/无网络标识解决方法_ubuntu没网-CSDN博客 再我们正常使用VMware时&#xff0c;就以Ubuntu举例可能有时候出现无网络连接&#xff0c;甚至出现无网络标识的情况&#xff0c;那么废话不多说直接上教程 环境&#xff1a;无网络 解决方案&#…...

编程日记 2025/5/15 12:01:42

区块链在能源行业的创新

技术创新 1. 智能合约与自动化交易 智能合约是区块链技术的核心组件之一&#xff0c;它允许在没有中介的情况下自动执行合同条款。在能源行业&#xff0c;这可以用于自动化电力交易、支付流程以及管理复杂的供应链。例如&#xff0c;当太阳能板产生的电量达到预设值时&#x…...

编程日记 2025/5/15 5:28:21

skynet 源码阅读 -- 核心概念服务 skynet_context

本文从 Skynet 源码层面深入解读 服务&#xff08;Service&#xff09; 的创建流程。从最基础的概念出发&#xff0c;逐步深入 skynet_context_new 函数、相关数据结构&#xff08;skynet_context, skynet_module, message_queue 等&#xff09;&#xff0c;并通过流程图、结构…...

编程日记 2025/5/13 6:45:05

前端react后端java实现提交antd form表单成功即导出压缩包

前端&#xff08;React Ant Design&#xff09; 1. 创建表单&#xff1a;使用<Form>组件来创建你的表单。 2. 处理表单提交&#xff1a;在onFinish回调中发起请求到后端API&#xff0c;并处理响应。 import React from react; import { Form, Input, Button } from ant…...

编程日记 2025/5/15 11:03:45

2025 = 1^3 + 2^3 + 3^3 + 4^3 + 5^3 + 6^3 + 7^3 + 8^3 + 9^3

【算法代码】 #include <bits/stdc.h> using namespace std;int year2025; int main() {cout<<year<<" ";int i1;while(year) {cout<<i<<"^3";if(i<9) cout<<" ";year-pow(i,3);i;}return 0; }/* 202…...

编程日记 2025/5/15 10:51:18

程序代码篇---C++常量引用

文章目录 前言第一部分&#xff1a;C常量常量变量const与指针1.指向常量的指针2.常量指针3.指向常量的常量指针 常量成员函数const_cast运算符总结 第二部分&#xff1a;C引用引用的基本概念引用的声明引用的使用引用的特性1.不可变性2.无需解引用3.内存地址 引用的用途1.函数参…...

编程日记 2025/5/14 12:15:26

DeepSeek-R1本地部署笔记

文章目录 效果概要下载 ollama终端下载模型【可选】浏览器插件 UIQ: 内存占用高&#xff0c;显存占用不高&#xff0c;正常吗 效果 我的配置如下 E5 2666 V3 AMD 590Gme 可以说是慢的一批了&#xff0c;内存和显卡都太垃圾了&#xff0c;回去用我的新设备再试试 概要 安装…...

编程日记 2025/5/15 10:36:02

golang通过AutoMigrate方法自动创建table详解

一.AutoMigrate介绍 1.介绍 在 Go 语言中&#xff0c;GORM支持Migration特性&#xff0c;支持根据Go Struct结构自动生成对应的表结构,使用 GORM ORM 库的 AutoMigrate 方法可以自动创建数据库表&#xff0c;确保数据库结构与定义的模型结构一致。AutoMigrate 方法非常方便&am…...

编程日记 2025/5/14 11:34:37

如何看待 OpenAI 的12天“shipmas”发布计划？

openAI的“Shipmas”并非单纯的营销活动，而是在用户增长、技术创新和市场竞争中的综合布局和战略体现。 史上最寒酸的发布会？继十月马斯克在好莱坞电影城高调发布特斯拉三款最新产品（无人出租车、无人巴士、人形机器人）后，十二月，OpenAI CEO 奥特曼宣布 OpenAI 将连续12…...

编程日记 2025/5/15 11:17:58

Vue 3 30天精进之旅：Day 07 - Vue Router

引言 在前几天的学习中&#xff0c;我们深入探讨了Vue的表单输入绑定及其处理机制。今天&#xff0c;我们将学习Vue Router&#xff0c;这是Vue.js官方提供的路由管理器&#xff0c;用于构建单页面应用&#xff08;SPA&#xff09;。通过使用Vue Router&#xff0c;你可以轻松…...

编程日记 2025/5/15 12:16:42

Redis学习之哨兵二

一、API 1.sentinel masters:展示被监控的主节点状态及相关的统计信息 2.sentinel master <master name>:展示指定的主节点的状态以及相关的统计信息 3.sentinel slaves <master name>:展示指定主节点的从节点状态以及相关的统计信息 4.sentinel sentinels <mas…...

编程日记 2025/5/15 10:12:25

本地部署AI大模型（deepseek r1）说明

1、硬件环境和操作系统 win11intel i5 8C16G deepseek-1.5B和7B**&#xff1a;选择RTX 3060或其他 Pascal架构显卡&#xff0c;搭配至少8GB的内存。 deepseek-70B**&#xff1a;推荐使用RTX 40系列 APU 或更高世代显卡&#xff0c;…...

编程日记 2025/5/14 11:05:59

幸运数字——蓝桥杯

1.问题描述 哈沙德数是指在某个固定的进位制当中&#xff0c;可以被各位数字之和整除的正整数。例如 126126 是十进制下的一个哈沙德数&#xff0c;因为 (126)10mod(126)0&#xff1b;126 也是八进制下的哈沙德数&#xff0c;因为 (126)10(176)8&#xff0c;(126)10​mod(176)…...

编程日记 2025/5/15 10:58:40

[250129] Archinstall 3.0.2 发布 | Wolfram 语言与 Mathematica 14.2 版本发布

目录 Archinstall 3.0.2 版本发布Wolfram 语言与 Mathematica 14.2 版本发布&#x1f31f; 主要亮点 Archinstall 3.0.2 版本发布 Archlinux 的自动化安装程序 Archinstall 发布了 3.0.2 版本&#xff0c;该版本带来了大量的改进和修复&#xff0c;以及一些新功能和贡献者。 …...

编程日记 2025/5/15 10:11:20

ios swift画中画技术尝试

继上篇&#xff1a;iOS swift 后台运行应用尝试失败-CSDN博客 为什么想到画中画&#xff0c;起初是看到后台模式里有一个picture in picture&#xff0c;去了解了后发现这个就是小窗口视频播放&#xff0c;方便用户执行多任务。看小窗口视频的同时&#xff0c;可以作其他的事情…...

编程日记 2025/5/15 10:29:09

第21节课：前端构建工具—自动化与模块化的利器

目录 前端构建工具的重要性任务运行器&#xff1a;Gulp与GruntGulpGulp的工作原理安装与使用Gulp GruntGrunt的工作原理安装与使用Grunt 模块打包器&#xff1a;WebpackWebpack简介Webpack的工作原理安装与使用Webpack 实践&#xff1a;使用Gulp和Webpack构建前端项目示例&…...

编程日记 2025/5/14 16:47:42

python3+TensorFlow 2.x 基础学习（一）

目录 TensorFlow 2.x基础 1、安装 TensorFlow 2.x 2、TensorFlow 2.x 基础概念 2、1 Eager Execution 2、2 TensorFlow 张量&#xff08;Tensor&#xff09; 3、使用Keras构建神经网络模型 3、1 构建 Sequential 模型 3、2 编译模型 1、Optimizer&#xff08;优化器&a…...

编程日记 2025/5/15 11:20:06

在sortablejs的拖拽排序情况下阻止input拖拽事件

如题 问题 在vue3的elementPlus的table中&#xff0c;通过sortablejs添加了行拖拽功能&#xff0c;但是在行内会有输入框&#xff0c;此时拖拽输入框会触发sortablejs的拖拽功能 解决 基于这个现象&#xff0c;我怀疑是由于拖拽事件未绑定而冒泡到后面的行上从而导致的拖拽…...

编程日记 2025/5/15 11:05:08

doris:异常数据处理

在导入过程中&#xff0c;源数据列与目标列的数据类型可能存在不一致的情况。导入过程会对这些类型不一致的数据进行转换&#xff0c;但在转换过程中可能会出现字段类型不匹配、字段超长、精度不匹配等问题&#xff0c;从而导致转换失败。 为了处理这些异常情况&#xff0c;Do…...

编程日记 2025/5/14 19:04:13

汇编基础语法及其示例

1.汇编指令 1.1汇编指令的基本格式 <opcode>{<cond>}{s} <Rd> , <Rn> , <shifter_operand> <功能码>{<条件码>}{cpsr影响位} <目标寄存器> , <第一操作寄存器> , <第二操作数> 注&#xff1a;第一操作寄存器…...

编程日记 2025/5/15 4:36:08

使用python调用JIRA6 进行OAuth1认证获取AccessToken

Jira配置应用程序链接 1) 创建应用程序链接 登录 JIRA 管理后台。转到 Administration > Applications > Application Links。在输入框中输入外部应用程序的 URL&#xff08;例如 GitLab 或自定义应用&#xff09;&#xff0c;然后点击 Create new link。 2) 配置 Con…...

编程日记 2025/5/12 14:53:38

关于el-table翻页后序号列递增的组件封装

需求说明&#xff1a; 项目中经常会用到的一个场景&#xff0c;表格第一列显示序号&#xff08;1、2、3...&#xff09;&#xff0c;但是在翻页后要递增显示序号&#xff0c;例如10、11、12&#xff08;假设一页显示10条数据&#xff09;&#xff0c;针对这种情况&#xff0c;封…...

编程日记 2025/5/12 1:12:16

Android createScaledBitmap与Canvas通过RectF drawBitmap生成马赛克/高斯模糊（毛玻璃）对比，Kotlin

Android createScaledBitmap与Canvas通过RectF drawBitmap生成马赛克/高斯模糊&#xff08;毛玻璃&#xff09;对比&#xff0c;Kotlin import android.graphics.Bitmap import android.graphics.BitmapFactory import android.graphics.Canvas import android.graphics.RectF …...

编程日记 2025/5/12 14:53:36

Linux 进程概念

目录 一、前言 二、概念实例&#xff0c;正在执行的程序等 三、描述进程-PCB 四、组织进程 五、查看进程 ​编辑六、通过系统调用获取进程标示符 七、进程切换和上下文数据 1.进程切换 2.上下文数据 一、前言 在Linux中&#xff0c;每个执行的程序叫做进程&#xff…...

编程日记 2025/5/11 17:46:08

Kafa分区策略实现

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

编程日记 2025/5/12 22:08:41