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

【动态规划刷题 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 ,我们可以将其分解为前后两部分:

  1. i. 前⾯⼀部分 [0, j - 1] 区间的字符串;
  2. 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] ,我们可以根据⼦串的「⻓度」划分为两类:

  1. i. ⼦串的⻓度等于 1 :此时这⼀个字符会出现在 base 中;

  2. . ⼦串的⻓度⼤于 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 表⾥⾯的和,因为会有重复的结果。在返回之前,我们需要先「去重」:

  1. i. 相同字符结尾的 dp 值,我们仅需保留「最⼤」的即可,其余 dp 值对应的⼦串都可以在 最⼤的⾥⾯找到;
  2. 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 。 注意&#xff1a;不要求字典中出现的单词全部都使用&#xff0c;并且字典中的单词可以重复使用。 示例 1&#xff1a; 输入: …...

react-redux 的使用

react-redux React Redux 是 Redux 的官方 React UI 绑定库。它使得你的 React 组件能够从 Redux store 中读取到数据&#xff0c;并且你可以通过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属性用来设置元素的堆叠顺序&#xff0c;使用z-index有一个大的前提&#xff1a;z-index所作用元素的样式列表中必须有position属性并且属性值为absolute、relative或fixed中的一个&#xff0c;否则z-index无效。 层叠上下文 MDN讲解 我们给元素设置的z-index都是有一…...

系统架构设计师(第二版)学习笔记----多媒体技术

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

【面试经典150 | 数组】合并两个有序数组

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

系统架构设计专业技能 ·操作系统

现在的一切都是为将来的梦想编织翅膀&#xff0c;让梦想在现实中展翅高飞。 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里面输入下面那命令&#xff0c;启用“适用于 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语言的同学&#xff0c;应该都见过typedef&#xff0c;但可能对typedef的用法并不是真的了解。本文介绍几种typedef的用法&#xff0c;相信会有所帮助 基础用法 一般typedef用来声明一个…...

Linux中安装MySQL5.7.42

1. 首先&#xff0c;下载mysql5.7.42的安装包&#xff08;下方是下载地址&#xff09;&#xff0c;选择红色框框的下载&#xff08;注意的是&#xff0c;这个链接只提供5.7的版本下载&#xff0c;可能还会更新&#xff0c;不一定打开就是5.7.42的版本&#xff0c;后续可能会有4…...

网络基础--1.网络纵横

网络的发展历程 计算机由原来的只能单一处理信息&#xff08;单用户批处理&#xff09;逐步发展为多用户批处理&#xff0c;可以实现一台计算机连接多个终端同时使用一台计算机&#xff08;分时系统&#xff09;&#xff0c;但是多个终端之间不能相互通信&#xff0c;再发展成为…...

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仓库&#xff0c;含有教程&#xff1a;https://github.com/go-delve/delve golang的debugging教程&#xff1a;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&#xff0c;这个问题可能会让我们感到困扰。mfc140u.dll 是 Microsoft Foundation Classes&#xff08;MFC&#xff09;库的一部分&#xff0c;它是一个 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 基金会已发起了一份请愿书&#xff0c;旨在阻止法国政府强迫 Mozilla Firefox 等浏览器审查网站。 据悉&#xff0c;法国政府正在制定一项旨在打击网络欺诈的 SREN 法案 (“Projet de loi Visant scuriser et reguler lespace numrique”)&#xff0c;包含大约 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 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; 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篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;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"…...

无人机侦测与反制技术的进展与应用

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

力扣热题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的应用开发模型中&#xff0c;featureAbility是旧版FA模型&#xff08;Feature Ability&#xff09;的用法&#xff0c;Stage模型已采用全新的应用架构&#xff0c;推荐使用组件化的上下文获取方式&#xff0c;而非依赖featureAbility。 FA大概是API7之…...