当前位置: 首页 > 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.配合日志包含绕…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

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

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

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...