力扣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输入的数字信号。 实现…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...
Python 实现 Web 静态服务器(HTTP 协议)
目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...
