力扣139.单词拆分
思路:动态规划,设dp[]记录当前字符能不能通过字典里的单词到达,双层循环,外层循环遍历字符串每一个字符,内层遍历当前i字符之前的所有以i字符结尾的子串
例如字符串:leetcode
i遍历到了t
那么内层循环就会遍历:leet、eet、et、t
然后判断这些子串中有没有与字典里的单词匹配,若匹配且当前dp[j]为真,则dp[i]为真
判断dp[j] 是因为若dp[j]为真,则代表j字符可以到达,那么当前字符子串以j为起始并且字典里存在此子串,所以当前子串的结尾处也可以到达(dp[i] = true)
dp[0] 赋初值true,因为若子串起始字符为第一个字符,那么从第一个字符出发的子串当然是可以的
最后判断dp[]最后一个位置是否为真,若为真则说明此字符串可以通过字典里的单词拼凑到达最后一个字符
一开始的笨办法,虽然笨且慢,不过可能更便于理解:
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int len = s.size();auto dp = vector<bool> (len + 1); dp[0] = true; //dp[0]赋值for(int i = 1; i <= len; i++){ //外层循环遍历字符串int sw = true; //开关,若内层循环确定当前字符可到达则进行下一个字符for(int j = 0; j < i && sw; j++){ //内层循环遍历i字符前每一个以i字符结尾的子串for(auto word:wordDict){ //在字典里面找有没有此子串if(dp[j] && (word.compare(s.substr(j, i - j)) == 0)){ dp[i] = true; //如果子串存在可到达则i字符后一个字符也可到达sw = false; //如果当前字符可到达则无需继续遍历子串}}}}return dp[len];}
};
加入unordered_set之后快了很多
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int len = s.size();auto dp = vector<bool> (len + 1);dp[0] = true;auto wordset = unordered_set <string> ();for(auto word : wordDict){wordset.insert(word);}for(int i = 1; i <= len; i++){for(int j = 0; j < i; j++){if(dp[j] && wordset.find(s.substr(j, i - j)) != wordset.end()){dp[i] = true;break;}}}return dp[len];}
};
思路不变,unordered_set就是一个key为值的字典,并且unordered_set中find()若找不到对应元素,会返回.end()
相关文章:
力扣139.单词拆分
思路:动态规划,设dp[]记录当前字符能不能通过字典里的单词到达,双层循环,外层循环遍历字符串每一个字符,内层遍历当前i字符之前的所有以i字符结尾的子串 例如字符串:leetcode i遍历到了t 那么内层循环就…...
Docker 镜像命令总汇
目录 1、查看镜像列表 2、搜索镜像 3、拉取镜像 4、删除镜像 5、显示镜像详细信息 6、显示镜像历史 7、导出镜像 8、导入镜像 9、清理未使用的镜像 10、强制删除镜像 1、查看镜像列表 docker images 这个命令列出了你系统中的所有 Docker 镜像,包括镜像名…...
客户服务:助力企业抵御经济衰退的关键要素与策略
目前经济仍悬而未决是否陷入衰退。当前情况下,尽管通胀率高企,消费者支出良好,就业率也在上升,表明就业市场强劲。然而,有人认为衰退可能会在2024年第一季度发生。经济环境的不确定性可能会让人望而却步,但…...
第八周:AIPM面试准备
以下为从开始准备转行到拿到offer期间每天需要准备的10个面试题目以及相关知识补充!来源广泛,从各个地方收集,只提供题目,我自己的尝试回答也会陆续放在我的喜马拉雅,基于我粗浅的认知,分享我粗浅的作答思路…...
阿里云2核2G3M服务器能放几个网站?有限制吗?
阿里云2核2g3m服务器可以放几个网站?12个网站,阿里云服务器网的2核2G服务器上安装了12个网站,甚至还可以更多,具体放几个网站取决于网站的访客数量,像阿里云服务器网aliyunfuwuqi.com小编的网站日访问量都很少…...
Baumer工业相机堡盟工业相机如何通过NEOAPI SDK设置相机本身的数据保存(CustomData)功能(C#)
Baumer工业相机堡盟工业相机如何通过NEOAPI SDK设置相机本身的数据保存(CustomData)功能(C#) Baumer工业相机Baumer工业相机的数据保存(CustomData)功能的技术背景CameraExplorer如何使用图像剪切ÿ…...
从零开始配置kali2023环境:镜像保存和导入
对原始的镜像做了一些改动,然后把当前容器状态打包为新的镜像,这样以后可以部署到其他地方了,而不用再安装软件等改动等等 1.查看容器id ┌──(holyeyes㉿kali2023)-[~] └─$ sudo docker ps ┌──(holyeyes㉿kali2023)-[~] └─$ s…...
Transformer梳理与总结
其实transformer的成功也是源于对注意力机制的应用,其本质上还是可以归因于注意力机制,首先我们先来了解一下什么是注意力机制。在注意力机制的背景下,自主性提示被称为查询(query),给定任何查询,注意力机制…...
php之 校验多个时间段是否重复
参考网址 https://www.kancloud.cn/xiaobaoxuetp/mywork/3069416 https://segmentfault.com/a/1190000020487996 PHP判断多个时间段是否存在跨天或重复叠加的场景 /*** PHP计算两个时间段是否有交集(边界重叠不算)** param string $beginTime1 开始时间…...
atoi函数的模拟实现
这里强力推荐一篇文章 http://t.csdnimg.cn/kWuAm 详细解析了atoi函数以及其模拟实现,我这里就不说了。 这里作者先把自己模拟的代码给大家看一下。 int add(char* arr) {char* arr2 arr;while (*arr!-48){arr;}arr--;int sum 0;int n 0;while (arr ! (arr2-…...
编程笔记 html5cssjs 009 HTML链接
编程笔记 html5&css&js 009 HTML链接 一、HTML 链接二、文本链接三、图片链接四、HTML 链接- id 属性五、锚点链接六、HTML 链接 - target 属性七、属性downloadhrefpingreferrerpolicyreltargettype 八、操作小结 网页有了链接,就可根据需要进行跳转。纸质…...
Vue实现导出Excel表格,提示“文件已损坏,无法打开”的解决方法
一、vue实现导出excel 1、前端实现 xlsx是一个用于读取、解析和写入Excel文件的JavaScript库。它提供了一系列的API来处理Excel文件。使用该库,你可以将数据转换为Excel文件并下载到本地。这种方法适用于在前端直接生成Excel文件的场景。 安装xlsx依赖 npm inst…...
分发糖果,Java经典算法编程实战。
🏆作者简介,普修罗双战士,一直追求不断学习和成长,在技术的道路上持续探索和实践。 🏆多年互联网行业从业经验,历任核心研发工程师,项目技术负责人。 🎉欢迎 👍点赞✍评论…...
鸿蒙原生应用再添新丁!中国移动 入局鸿蒙
鸿蒙原生应用再添新丁!中国移动 入局鸿蒙 来自 HarmonyOS 微博1月2日消息,#中国移动APP启动鸿蒙原生应用开发#,拥有超3亿用户的中国移动APP宣布,正式基于HarmonyOS NEXT启动#鸿蒙原生应用#及元服务开发。#HarmonyOS#系统的分布式…...
一个人能不能快速搭建一套微服务环境
一、背景 大型软件系统的开发现在往往需要多人的协助,特别是前后端分离的情况下下,分工越来越细,那么一个人是否也能快速搭建一套微服务系统呢? 答案是能的。看我是怎么操作的吧。 二、搭建过程 1、首先需要一套逆向代码生成工…...
计算机毕业设计------经贸车协小程序
项目介绍 本项目分为三种用户类型,分别是租赁者,车主,管理员用户; 管理员用户包含以下功能: 管理员登录,个人中心,租赁者管理,车主管理,赛事活动管理,车类别管理,租车管理,租车订单管理,车辆出售管理,购买订单管理,…...
数据结构OJ实验11-拓扑排序与最短路径
A. DS图—图的最短路径(无框架) 题目描述 给出一个图的邻接矩阵,输入顶点v,用迪杰斯特拉算法求顶点v到其它顶点的最短路径。 输入 第一行输入t,表示有t个测试实例 第二行输入顶点数n和n个顶点信息 第三行起&…...
你的第一个JavaScript程序
JavaScript,即JS,JavaScript是一种具有函数优先的轻量级,解释型或即时编译型的编程语言。虽然它是作为开发Web页面的脚本语言而出名,但是它也被用到了很多非浏览器环境中,JavaScript基于原型编程、多范式的动态脚本语言…...
CMake入门教程【基础篇】列表操作(list)
文章目录 1. 定义列表2. 获取列表长度3. 获取列表元素4. 追加元素到列表末尾5. 插入元素到指定位置6. 移除指定位置的元素7. 移除指定值的元素8. 替换指定位置的元素9. 迭代列表元素 #mermaid-svg-IAjFPWI6IXEGYmuU {font-family:"trebuchet ms",verdana,arial,sans-…...
普中STM32-PZ6806L开发板(HAL库函数实现-读取内部温度)
简介 主芯片STM32F103ZET6,读取内部温度其他知识 内部温度所在ADC通道 温度计算公式 V25跟Avg_Slope值 参考文档 stm32f103ze.pdf 电压计算公式 Vout Vref * (D / 2^n) 其中Vref代表参考电压, n为ADC的位数, D为ADC输入的数字信号。 实现…...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
群晖NAS如何在虚拟机创建飞牛NAS
套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...
