【动态规划刷题 12】等差数列划分 最长湍流子数组
139. 单词拆分
链接: 139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例 1:
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。
示例 2:
输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。
注意,你可以重复使用字典中的单词。
示例 3:
输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false
1.状态表示*
这⾥我们选择⽐较常⽤的⽅式,以某个位置为结尾,结合题⽬要求,定义⼀个状态表⽰:
dp[i] 表⽰: [0, i] 区间内的字符串,能否被字典中的单词拼接⽽成
2.状态转移方程
对于 dp[i] ,为了确定当前的字符串能否由字典⾥⾯的单词构成,根据最后⼀个单词的起始位1置 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].
代码:
bool wordBreak(string s, vector<string>& wordDict) {int n=s.size();if(n==0) return false;vector<bool> dp(n+1);s=" "+s;dp[0]=true;unordered_set<string> hash;for(auto e:wordDict){hash.insert(e);}for(int i=1;i<=n;i++){for(int j=i;j>0;j--){if(dp[j-1]==true&&hash.count(s.substr(j,i-j+1))){//cout<<i<<" "<<j<<endl;cout<<i<<endl;dp[i]=true;break;}}//cout<<dp[i]<<endl;} return dp[n];}
467. 环绕字符串中唯一的子字符串
链接: 467. 环绕字符串中唯一的子字符串
定义字符串 base 为一个 “abcdefghijklmnopqrstuvwxyz” 无限环绕的字符串,所以 base 看起来是这样的:
“…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…”.
给你一个字符串 s ,请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。
示例 1:
输入:s = “a”
输出:1
解释:字符串 s 的子字符串 “a” 在 base 中出现。
示例 2:
输入:s = “cac”
输出:2
解释:字符串 s 有两个子字符串 (“a”, “c”) 在 base 中出现。
示例 3:
输入:s = “zab”
输出:6
解释:字符串 s 有六个子字符串 (“z”, “a”, “b”, “za”, “ab”, and “zab”) 在 base 中出现。
1.状态表示*
dp[i] 表⽰:以 i 位置的元素为结尾的所有⼦串⾥⾯,有多少个在 base 中出现过。
2.状态转移方程
对于 dp[i] ,我们可以根据⼦串的「⻓度」划分为两类:
-
i. ⼦串的⻓度等于 1 :此时这⼀个字符会出现在 base 中;
-
. ⼦串的⻓度⼤于 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 值。
最后返回「数组中所有元素的和」即可。
代码:
int findSubstringInWraproundString(string s) {int n=s.size();vector<int> dp(n,1);for(int i=1;i<n;i++){//还需要去重if(s[i]==s[i-1]+1||(s[i]=='a'&&s[i-1]=='z'))dp[i]=dp[i-1]+1;}// 计算每⼀个字符结尾的最⻓连续⼦数组的⻓度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;}
相关文章:

【动态规划刷题 12】等差数列划分 最长湍流子数组
139. 单词拆分 链接: 139. 单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 示例 1: 输入: …...
react-redux 的使用
react-redux React Redux 是 Redux 的官方 React UI 绑定库。它使得你的 React 组件能够从 Redux store 中读取到数据,并且你可以通过dispatch actions去更新 store 中的 state 安装 npm install --save react-reduxProvider React Redux 包含一个 <Provider…...

77 # koa 中间件的应用
调用 next() 表示执行下一个中间件 const Koa require("koa");const app new Koa();app.use(async (ctx, next) > {console.log(1);next();console.log(2); });app.use(async (ctx, next) > {console.log(3);next();console.log(4); });app.use(async (ctx,…...

【css】z-index与层叠上下文
z-index属性用来设置元素的堆叠顺序,使用z-index有一个大的前提:z-index所作用元素的样式列表中必须有position属性并且属性值为absolute、relative或fixed中的一个,否则z-index无效。 层叠上下文 MDN讲解 我们给元素设置的z-index都是有一…...

系统架构设计师(第二版)学习笔记----多媒体技术
【原文链接】系统架构设计师(第二版)学习笔记----多媒体技术 文章目录 一、多媒体概述1.1 媒体的分类1.2 多媒体的特征1.3 多媒体系统的基本组成 二、多媒体系统的关键技术2.1 多媒体系统的关键技术2.2 视频技术的内容2.3 音频技术的内容2.4 数据压缩算法…...

【面试经典150 | 数组】合并两个有序数组
文章目录 写在前面Tag题目来源题目解读解题思路方法一:合并排序方法二:双指针方法三:原地操作-从前往后方法四:原地操作-从后往前 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章…...

系统架构设计专业技能 ·操作系统
现在的一切都是为将来的梦想编织翅膀,让梦想在现实中展翅高飞。 Now everything is for the future of dream weaving wings, let the dream fly in reality. 点击进入系列文章目录 系统架构设计高级技能 操作系统 一、操作系统概述二、进程管理2.1 进程概念2.2 进…...

CSP 202209-1 如此编码
答题 题目就是字多 #include<iostream>using namespace std;int main() {int n,m;cin>>n>>m;int a[n],c[n1];c[0]1;for(int i0;i<n;i){cin>>a[i];c[i1]c[i]*a[i];}for(int i0;i<n;i){cout<<(m%c[i1]-m%c[i])/c[i]<< ;} }...

windows安装向量数据库milvus
本文介绍windows下安装milvus的方法。 一.Docker安装 1.1docker下载 首先到Docker官网上下载docker:Docker中文网 官网 1.2.安装前前期准备 先使用管理员权限打开windows powershell 然后在powershell里面输入下面那命令,启用“适用于 Linux 的 Windows 子系统”…...
Qt中,QScript对JavaScript的内置接口支持情况
支持 JSON.parse()/stringify() Object.keys() 不支持 console.info()/debug()/warn()/error() window setTimeout() clearTimeout() setInterval() clearInterval() 后续添加更多接口支持情况~...
C语言基础-typedef的用法
文章目录 前言基础用法高阶用法typedef作用于数组typedef作用于函数指针 总结 前言 熟悉C语言的同学,应该都见过typedef,但可能对typedef的用法并不是真的了解。本文介绍几种typedef的用法,相信会有所帮助 基础用法 一般typedef用来声明一个…...

Linux中安装MySQL5.7.42
1. 首先,下载mysql5.7.42的安装包(下方是下载地址),选择红色框框的下载(注意的是,这个链接只提供5.7的版本下载,可能还会更新,不一定打开就是5.7.42的版本,后续可能会有4…...
网络基础--1.网络纵横
网络的发展历程 计算机由原来的只能单一处理信息(单用户批处理)逐步发展为多用户批处理,可以实现一台计算机连接多个终端同时使用一台计算机(分时系统),但是多个终端之间不能相互通信,再发展成为…...
Django TypeError: Abstract models cannot be instantiated.错误解决方案
问题 [2023-09-05 10:23:41][dvadmin.utils.exception.CustomExceptionHandler():64] [ERROR] Traceback (most recent call last): File “D:\InstallSpace\Anaconda3\envs\py39\lib\site-packages\rest_framework\views.py”, line 506, in dispatch response handler(requ…...

vscode使用delve调试golang程序
环境配置 delve仓库,含有教程:https://github.com/go-delve/delve golang的debugging教程:https://github.com/golang/vscode-go/wiki/debugging > go version go version go1.20 windows/amd64> go install github.com/go-delve/de…...

如何从任何苹果、Windows或安卓设备访问iCloud照片
本文介绍了如何在各种设备上访问iCloud照片库,包括iPhone和iPad、Mac、Windows PC和Android设备。说明适用于iOS 13及以上版本、iPadOS 13及以上、macOS Big Sur(10.16)和Catalina(10.15)、Windows 10或11以及Android 10。 从iPhone、iPod Touch和iPad访问iCloud照片 照…...

关于“找不到mfc140u.dll,无法继续执行代码”问题的分析处理方法
我想和大家分享一个在编程过程中经常会遇到的问题——找不到mfc140u.dll,无法继续执行代码。找不到 mfc140u.dll,这个问题可能会让我们感到困扰。mfc140u.dll 是 Microsoft Foundation Classes(MFC)库的一部分,它是一个 Windows 系…...
用 TripletLoss 优化bert ranking
下面是 用 TripletLoss 优化bert ranking 的demo import torch from torch.utils.data import DataLoader, Dataset from transformers import BertModel, BertTokenizer from sklearn.metrics.pairwise import pairwise_distancesclass TripletRankingDataset(Dataset):def __…...
Tomcat安装及使用
这里写目录标题 Tomcat一.java基础1.java历史2.java组成3.实现动态网页功能serveltjsp 4.jdkJDK 和 JRE 关系安装openjdk安装oracle官方JDK 二.tomcat基础功能1.Tomcat介绍2.安装tomcat二进制安装Tomcat 3.配置文件介绍及核心组件配置文件组件 4.状态页5.常见的配置详解6.tomca…...

法国新法案强迫 Firefox 等浏览器审查网站
导读Mozilla 基金会已发起了一份请愿书,旨在阻止法国政府强迫 Mozilla Firefox 等浏览器审查网站。 据悉,法国政府正在制定一项旨在打击网络欺诈的 SREN 法案 (“Projet de loi Visant scuriser et reguler lespace numrique”),包含大约 2…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...

力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
【HarmonyOS 5】鸿蒙中Stage模型与FA模型详解
一、前言 在HarmonyOS 5的应用开发模型中,featureAbility是旧版FA模型(Feature Ability)的用法,Stage模型已采用全新的应用架构,推荐使用组件化的上下文获取方式,而非依赖featureAbility。 FA大概是API7之…...