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

【算法挨揍日记】day29——139. 单词拆分、467. 环绕字符串中唯一的子字符串

139. 单词拆分

139. 单词拆分

题目描述:

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

 解题思路:

算法思路:
1. 状态表⽰:
对于线性 dp ,我们可以⽤「经验 + 题⽬要求」来定义状态表⽰:
i. 以某个位置为结尾,巴拉巴拉;
ii. 以某个位置为起点,巴拉巴拉。
这⾥我们选择⽐较常⽤的⽅式,以某个位置为结尾,结合题⽬要求,定义⼀个状态表⽰:
dp[i] 表⽰: [0, i] 区间内的字符串,能否被字典中的单词拼接⽽成。
2. 状态转移⽅程:
对于 dp[i] ,为了确定当前的字符串能否由字典⾥⾯的单词构成,根据最后⼀个单词的起始位
j ,我们可以将其分解为前后两部分:
i. 前⾯⼀部分 [0, j - 1] 区间的字符串;
ii. 后⾯⼀部分 [j, i] 区间的字符串。
其中前⾯部分我们可以在 dp[j - 1] 中找到答案,后⾯部分的⼦串可以在字典⾥⾯找到。
因此,我们得出⼀个结论:当我们在从 0 ~ i 枚举 j 的时候,只要 dp[j - 1] = true
并且后⾯部分的⼦串 s.substr(j, i - j + 1) 能够在字典中找到,那么 dp[i] =
true
3. 初始化:
可以在最前⾯加上⼀个「辅助结点」,帮助我们初始化。使⽤这种技巧要注意两个点:
i. 辅助结点⾥⾯的值要「保证后续填表是正确的」;
ii. 「下标的映射关系」。
在本题中,最前⾯加上⼀个格⼦,并且让 dp[0] = true ,可以理解为空串能够拼接⽽成。
其中为了⽅便处理下标的映射关系,我们可以将字符串前⾯加上⼀个占位符 s = ' ' + s ,这
样就没有下标的映射关系的问题了,同时还能处理「空串」的情况。
4. 填表顺序:
显⽽易⻅,填表顺序「从左往右」。
5. 返回值:
由「状态表⽰」可得:返回 dp[n] 位置的布尔值。

解题代码:

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> hash;for(auto& s : wordDict) hash.insert(s);int n=s.size();vector<bool>dp(n+1);dp[0]=true;s=' '+s;for(int i=1;i<=n;i++){for(int j=i;j>=1;j--){if(dp[j-1]==true&&hash.count(s.substr(j,i-j+1))){dp[i]=true;break;}}}return dp[n];}
};

467. 环绕字符串中唯一的子字符串

467. 环绕字符串中唯一的子字符串

题目描述:

定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串,所以 base 看起来是这样的:

  • "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

给你一个字符串 s ,请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。

 解题思路:

算法思路:
1. 状态表⽰:
对于线性 dp ,我们可以⽤「经验 + 题⽬要求」来定义状态表⽰:
i. 以某个位置为结尾,巴拉巴拉;
ii. 以某个位置为起点,巴拉巴拉。
这⾥我们选择⽐较常⽤的⽅式,以某个位置为结尾,结合题⽬要求,定义⼀个状态表⽰:
dp[i] 表⽰:以 i 位置的元素为结尾的所有⼦串⾥⾯,有多少个在 base 中出现过。
2. 状态转移⽅程:
对于 dp[i] ,我们可以根据⼦串的「⻓度」划分为两类:
i. ⼦串的⻓度等于 1 :此时这⼀个字符会出现在 base 中;
ii. ⼦串的⻓度⼤于 1 :如果 i 位置的字符和 i - 1 位置上的字符组合后,出现在 base
中的话,那么 dp[i - 1] ⾥⾯的所有⼦串后⾯填上⼀个 s[i] 依旧在 base 中出
现。因此 dp[i] = dp[i - 1]
综上, dp[i] = 1 + dp[i - 1] ,其中 dp[i - 1] 是否加上需要先做⼀下判断。
3. 初始化:
可以根据「实际情况」,将表⾥⾯的值都初始化为 1
4. 填表顺序:
显⽽易⻅,填表顺序「从左往右」。
5. 返回值:
这⾥不能直接返回 dp 表⾥⾯的和,因为会有重复的结果。在返回之前,我们需要先「去重」:
i. 相同字符结尾的 dp 值,我们仅需保留「最⼤」的即可,其余 dp 值对应的⼦串都可以在
最⼤的⾥⾯找到;
ii. 可以创建⼀个⼤⼩为 26 的数组,统计所有字符结尾的最⼤ dp 值。
最后返回「数组中所有元素的和」即可。

解题代码:

class Solution {
public:int findSubstringInWraproundString(string s) {int n=s.size();vector<int>dp(n,1);for(int i=1;i<n;i++){if(s[i]-1==s[i-1]||(s[i-1]=='z'&&s[i]=='a'))dp[i]=dp[i-1]+1;}// 2. 计算每⼀个字符结尾的最⻓连续⼦数组的⻓度int hash[26] = { 0 };for(int i = 0 ; i < n; i++)hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);// 3. 将结果累加起来int sum = 0;for(auto x : hash) sum += x;return sum;}
};

相关文章:

【算法挨揍日记】day29——139. 单词拆分、467. 环绕字符串中唯一的子字符串

139. 单词拆分 139. 单词拆分 题目描述&#xff1a; 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意&#xff1a;不要求字典中出现的单词全部都使用&#xff0c;并且字典中的单词可以重复使用。 解题思路&am…...

YOLOv8-Seg改进:轻量级Backbone改进 | VanillaNet极简神经网络模型 | 华为诺亚2023

🚀🚀🚀本文改进:一种极简的神经网络模型 VanillaNet,支持vanillanet_5, vanillanet_6, vanillanet_7, vanillanet_8, vanillanet_9, vanillanet_10, vanillanet_11等版本,相比较yolov8-seg各个版本如下: layersparametersgradientsGFLOPsvanillanet_521230017523...

解决Requests中使用httpbin服务器问题:自定义URL的实现与验证

问题背景 在使用Python的Requests模块进行单元测试时&#xff0c;可能会遇到无法使用本地运行的httpbin服务器进行测试的问题。这是因为测试脚本允许通过环境变量HTTPBIN_URL指定用于测试的本地httpbin实例&#xff0c;但在某些测试用例中&#xff0c;URL是硬编码为httpbin.or…...

​软考-高级-系统架构设计师教程(清华第2版)【第17章 通信系统架构设计理论与实践(P614~646)-思维导图】​

软考-高级-系统架构设计师教程&#xff08;清华第2版&#xff09;【第17章 通信系统架构设计理论与实践&#xff08;P614~646&#xff09;-思维导图】 课本里章节里所有蓝色字体的思维导图...

【MATLAB源码-第82期】基于matlab的OFDM系统载波频移偏差(CFO)估计,对比三种不同的方法。

操作环境&#xff1a; MATLAB 2013b 1、算法描述 正交频分复用&#xff08;OFDM&#xff09;系统中的载波频率偏移&#xff08;CFO&#xff09;估计是一项关键技术&#xff0c;用于确保数据传输的准确性和效率。CFO通常由于振荡器频率不匹配和多普勒频移引起。不同的CFO估计…...

Docker Swarm: 容器编排的力量和优势深度解析

文章目录 Docker Swarm的核心概念1. 节点&#xff08;Node&#xff09;2. 服务&#xff08;Service&#xff09;3. 栈&#xff08;Stack&#xff09; 使用Docker Swarm1. 初始化Swarm2. 加入节点3. 创建服务4. 扩展和缩减服务5. 管理栈6. 管理服务更新 Docker Swarm的优势深度解…...

调整Windows键盘上只能看到拼音而无法看到实际的文本以及关闭输入法悬浮窗方法

一、输入法设置 如果您在键盘上只能看到拼音而无法看到实际的文本&#xff0c;这可能是因为您的输入法设置为中文拼音输入法或其他仅显示拼音的输入法。 要解决这个问题&#xff0c;您可以尝试以下方法&#xff1a; 1. 切换输入法&#xff1a;按下 Shift Alt 组合键或 Wind…...

【微软技术栈】C#.NET 中的管道操作

C#.NET 管道为进程间通信提供了平台。 管道分为两种类型&#xff1a; 匿名管道。 匿名管道在本地计算机上提供进程间通信。 与命名管道相比&#xff0c;虽然匿名管道需要的开销更少&#xff0c;但提供的服务有限。 匿名管道是单向的&#xff0c;不能通过网络使用。 仅支持一个服…...

Python学习笔记--进程

进程 Python 中的多线程其实并不是真正的多线程,如果想要充分地使用多核 CPU 的资源,在 Python 中大部分情况需要使用多进程。 Python 提供了非常好用的多进程包 multiprocessing,只需要定义一个函数,Python 会完成其他所有事情。 借助这个包,可以轻松完成从单进程到并…...

比亚迪刀片电池与特斯拉4680电池比较

1 电池材料 比亚迪刀片电池采用的磷酸铁锂LFP&#xff08;LiFePO4&#xff09;&#xff0c;特斯拉的4680电池采用的三元锂。 磷酸铁锂&#xff1a;循环寿命长&#xff0c;安全性能好&#xff0c;价格低廉&#xff0c;但是能量密度低&#xff0c;导电性能差&#xff0c;低温表现…...

在写windows C++代码的时候,从代码安全角度考虑,我们应该注意什么?

在写windows C代码的时候&#xff0c;从代码安全角度考虑&#xff0c;我们应该注意什么&#xff1f;分别是&#xff1a;输入验证、内存管理、错误处理、并发和线程安全、使用安全的API、避免使用不安全的函数、最小权限原则。 一、输入验证 1. 用户输入验证 #include <io…...

【草料】uni-app ts vue 小程序 如何如何通过草料生成对应的模块化二维码

一、查看uni-app项目 1、找到路径 可以看到项目从 src-race-pages-group 这个使我们目标的查询页面 下面我们将这个路径copy到草料内 2、找到进入页面入参 一般我们都会选择 onload() 函数下的入参 这里我们参数的是 id 二、草料 建议看完这里的教程文档 十分清晰&#xff01…...

CMS与FullGC

JVM中的CMS&#xff08;Concurrent Mark Sweep&#xff09;GC和Full GC&#xff08;Full Garbage Collection&#xff09;是两种不同的垃圾回收算法。 CMS GC&#xff1a;CMS GC是一种并发的垃圾回收算法&#xff0c;它在运行期间与应用程序线程并发工作&#xff0c;尽可能减少…...

一款.NET开源的小巧、智能、免费的Windows内存清理工具 - WinMemoryCleaner

前言 我们在使用Windows系统的时候经常会遇到一些程序不会释放已分配的内存&#xff0c;从而导致电脑变得缓慢。今天给大家推荐一款.NET开源的小巧、智能、免费的Windows内存清理工具&#xff1a;WinMemoryCleaner。 使用Windows内存清理工具来优化内存&#xff0c;这样不必浪…...

iptables详解:链、表、表链关系、规则的基本使用

目录 防火墙基本概念 什么是防火墙&#xff1f; Netfilter与iptables的关系 链的概念 表的概念 表链关系 规则的概念 查询规则 添加规则 删除iptables中的记录 修改规则 更详细的命令&#xff08;5链4表&#xff09; 防火墙基本概念 什么是防火墙&#xff1f; 在…...

安全管理中心(设备和技术注解)

网络安全等级保护相关标准参考《GB/T 22239-2019 网络安全等级保护基本要求》和《GB/T 28448-2019 网络安全等级保护测评要求》 密码应用安全性相关标准参考《GB/T 39786-2021 信息系统密码应用基本要求》和《GM/T 0115-2021 信息系统密码应用测评要求》 1系统管理 1.1对系统管…...

Failed to execute org.scala-tools:maven-scala-plugin:2.15.2解决

原因也不是很清楚&#xff0c;查看一个博主文章(net.alchim31.maven:scala-maven-plugin&#xff1a;maven依赖无法下载或无法编译)得到的解决方案&#xff1a; 在idea的terminal执行以下语句即可实现maven对scala代码的编译&#xff1a; mvn clean scala:compile compile pac…...

C#中委托和事件的使用总结

委托&#xff08;delegate&#xff09;特别用于实现事件和回调方法。所有的委托&#xff08;Delegate&#xff09;都派生自 System.Delegate 类。事件是一种特殊的多播委托&#xff0c;仅可以从声明事件的类或结构中对其进行调用。类或对象可以通过事件向其他类或对象通知发生的…...

基于STM32的外部中断(EXTI)在嵌入式系统中的应用

外部中断&#xff08;External Interrupt&#xff0c;EXTI&#xff09;是STM32嵌入式系统中常见且重要的功能之一。它允许外部事件&#xff08;例如按键按下、传感器触发等&#xff09;通过适当的引脚触发中断&#xff0c;从而应用于各种嵌入式系统中。在STM32微控制器中&#…...

【心得】PHP的文件上传个人笔记

目录 1 php的文件上传绕过 黑名单绕过 2 php文件上传的00截断 3 iconv字符转换异常后造成了字符截断 4 文件后缀是白名单的时候的绕过 web服务器的解析漏洞绕过 5.高级文件上传绕过 1 .htaccess nginx.htaccess 2 服务端内容检测 3 配合伪协议来绕过 4.配合日志包含绕…...

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; 左…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...