【教3妹学编程-算法题】3008. 找出数组中的美丽下标 II

烦死了
3妹:呜呜,烦死了, 脸上长了一个痘
2哥 : 不要在意这些细节嘛,不用管它,过两天自然不就好了。
3妹:切,你不懂,影响这两天的心情哇。
2哥 : 我看你是不急着找工作了啊, 工作那么辛苦,哪还有时间想这些啊。
3妹:说到找工作,我又要去刷题了。
2哥:我给你出一道关于美丽的题吧,让你的心情美丽美丽~

题目:

给你一个下标从 0 开始的字符串 s 、字符串 a 、字符串 b 和一个整数 k 。

如果下标 i 满足以下条件,则认为它是一个 美丽下标 :

0 <= i <= s.length - a.length
s[i…(i + a.length - 1)] == a
存在下标 j 使得:
0 <= j <= s.length - b.length
s[j…(j + b.length - 1)] == b
|j - i| <= k
以数组形式按 从小到大排序 返回美丽下标。

示例 1:

输入:s = “isawsquirrelnearmysquirrelhouseohmy”, a = “my”, b = “squirrel”, k = 15
输出:[16,33]
解释:存在 2 个美丽下标:[16,33]。

  • 下标 16 是美丽下标,因为 s[16…17] == “my” ,且存在下标 4 ,满足 s[4…11] == “squirrel” 且 |16 - 4| <= 15 。
  • 下标 33 是美丽下标,因为 s[33…34] == “my” ,且存在下标 18 ,满足 s[18…25] == “squirrel” 且 |33 - 18| <= 15 。
    因此返回 [16,33] 作为结果。
    示例 2:

输入:s = “abcd”, a = “a”, b = “a”, k = 4
输出:[0]
解释:存在 1 个美丽下标:[0]。

  • 下标 0 是美丽下标,因为 s[0…0] == “a” ,且存在下标 0 ,满足 s[0…0] == “a” 且 |0 - 0| <= 4 。
    因此返回 [0] 作为结果。

提示:

1 <= k <= s.length <= 5 * 10^5
1 <= a.length, b.length <= 5 * 10^5
s、a、和 b 只包含小写英文字母。

思路:

思考

KMP+二分查找,
用 KMP 求出 a 在 s 中的所有出现位置,记作 posA。
用 KMP 求出 b 在 s 中的所有出现位置,记作 posB。
遍历 posA中的下标 i,在 posB中二分查找离 iii 最近的 j。如果 ∣i−j∣≤k,则把 i 加入答案。

java代码:

class Solution {public List<Integer> beautifulIndices(String s, String a, String b, int k) {char[] text = s.toCharArray();List<Integer> posA = kmp(text, a.toCharArray());List<Integer> posB = kmp(text, b.toCharArray());List<Integer> ans = new ArrayList<>();for (int i : posA) {int bi = lowerBound(posB, i);if (bi < posB.size() && posB.get(bi) - i <= k ||bi > 0 && i - posB.get(bi - 1) <= k) {ans.add(i);}}return ans;}private List<Integer> kmp(char[] text, char[] pattern) {int m = pattern.length;int[] pi = new int[m];int c = 0;for (int i = 1; i < m; i++) {char v = pattern[i];while (c > 0 && pattern[c] != v) {c = pi[c - 1];}if (pattern[c] == v) {c++;}pi[i] = c;}List<Integer> res = new ArrayList<>();c = 0;for (int i = 0; i < text.length; i++) {char v = text[i];while (c > 0 && pattern[c] != v) {c = pi[c - 1];}if (pattern[c] == v) {c++;}if (c == m) {res.add(i - m + 1);c = pi[c - 1];}}return res;}// 开区间写法// 请看 https://www.bilibili.com/video/BV1AP41137w7/private int lowerBound(List<Integer> nums, int target) {int left = -1, right = nums.size(); // 开区间 (left, right)while (left + 1 < right) { // 区间不为空// 循环不变量:// nums[left] < target// nums[right] >= targetint mid = (left + right) >>> 1;if (nums.get(mid) < target) {left = mid; // 范围缩小到 (mid, right)} else {right = mid; // 范围缩小到 (left, mid)}}return right;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/239002.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

rke2 Offline Deploy Rancher v2.8.0 latest (helm 离线部署 rancher v2.8.0)

文章目录 1. 预备条件2. 为什么是三个节点&#xff1f;​3. 配置私有仓库4. 介质清单5. 安装 helm6. 安装 cert-manager6.1 下载介质6.2 镜像入库6.3 helm 部署6.4 cert-manager 卸载 7. 安装 rancher7.1 镜像入库7.2 helm 安装 8. 验证9. 界面预览10. 卸载 1. 预备条件 所有支…

k8s中的基础概念

k8s可以从硬件和软件两方面来理解&#xff1a; 硬件&#xff1a; 1、节点&#xff08;Node&#xff09;&#xff1a;类似于手机、平板、电脑 2、集群&#xff08;Cluster&#xff09;&#xff1a;多个节点组合到一起 3、持久卷&#xff08;Persistent Volumes&#xff09;&…

Ubuntu20.04安装配置OpenCV-Python库并首次执行读图

一、选择三方提供的预编译包安装&#xff1a; 可以从官网下载 OpenCV 的安装包&#xff0c;编译后使用&#xff1b;也可以直接使用第三方提供的预编译包 安装。显然后者不需要执行编译步骤&#xff0c;更便捷。选择由 PyPI 提供的 OpenCV 安装包&#xff0c;可以在 https://py…

k8s源码阅读环境配置

源码阅读环境配置 k8s代码的阅读可以让我们更加深刻的理解k8s各组件的工作原理&#xff0c;同时提升我们Go编程能力。 IDE使用Goland&#xff0c;代码阅读环境需要进行如下配置&#xff1a; 从github上下载代码&#xff1a;https://github.com/kubernetes/kubernetes在GOPATH目…

git切换到另一分支更改也会随之过去

一次的修改如果没有 commit如果切换到另一分支就会把修改带到另一个分支 这时可以使用 git stash 其他使用场景 切换分支&#xff1a;当正在一个分支上工作&#xff0c;但需要临时切换到另一个分支处理一些紧急任务时&#xff0c;可以使用 git stash 保存当前的工作进度。完成…

【GitHub】如何上传文件夹到GitHub上(配图详解)

一、如果没有账号要先创建账号&#xff08;有账号跳过此步骤&#xff09;二、建立一个仓库&#xff08;有仓库跳过此步骤&#xff09;三、复制仓库地址四、以下为本地操作 1、在本地新建一个空文件夹2、上传文件 2.1、在空文件夹内&#xff0c;右键选择Git Bash Here2.2、弹出G…

Python - 深夜数据结构与算法之 LRUCache

目录 一.引言 二.LRU Cache 简介 1.实现特性 2.工作流程 三.LRU Cache 实战 1.HashMap ListNode 2.OrderedDict 四.总结 一.引言 LRU 即 Least Recently Used 意为最近使用&#xff0c;它是一种局部 Cache 的缓存方法&#xff0c;用于存储最近使用的元素&#xff0c;…

记一个有关 Vuetify 组件遇到的一些问题

Vuetify 官网地址 所有Vuetify 组件 — Vuetify 1、Combobox使用对象数组 Combobox 组合框 — Vuetify items数据使用对象数组时&#xff0c;默认选中的是整个对象&#xff0c;要对数据进行处理 <v-comboboxv-model"defaultInfo.variableKey":rules"rules…

Python3 索引下标及切片完全指南

介绍 Python 字符串数据类型是由一个或多个字符组成的序列&#xff0c;可以包含字母、数字、空格字符或符号。由于字符串是一个序列&#xff0c;我们可以通过索引和切片的方式访问它&#xff0c;就像访问其他基于序列的数据类型一样。 本教程将指导您通过索引访问字符串&…

23111 网络编程 day2

思维导图 重打代码 #include<myhead.h> #define SER_IP "192.168.122.150" //服务器ip #define SER_PORT 8888 //服务器端口int main(int argc, const char *argv[]) {//1.创建用于连接的套接字int sfdsocket(AF_INET,SOCK_STREAM,0);if(sfd-1){perror("…

pytorch集智-5手写数字识别器-卷积神经网络

1 简介 简称&#xff1a;CNN&#xff0c;convolutional neural network 应用场景&#xff1a;图像识别与分类&#xff08;CNN&#xff09;&#xff0c;看图说话&#xff08;CNNRNN&#xff09;等 优越性&#xff1a;和多层感知机相比&#xff0c;cnn可以识别独特的模式&…

前端框架前置课Node.js学习(1) fs,path,模块化,CommonJS标准,ECMAScript标准,包

目录 什么是Node.js 定义 作用: 什么是前端工程化 Node.js为何能执行Js fs模块-读写文件 模块 语法: 1.加载fs模块对象 2.写入文件内容 3.读取文件内容 Path模块-路径处理 为什么要使用path模块 语法 URL中的端口号 http模块-创建Web服务 需求 步骤: 案例:浏…

[笔记]深度学习入门 基于Python的理论与实现(二)

2. 感知机 感知机(perceptron)是由美国学者 Frank Rosenblatt 在 1957 年提出的。它作为神经网络&#xff08;深度学习&#xff09;的起源的算法&#xff0c;是学习神经网络和深度学习的重要一环 严格地说&#xff0c;本章所说的感知机应该称为‘人工神经元’或‘朴素感知机’&…

Qt6入门教程 6:Qt元对象系统

目录 一.什么是Qt元对象系统&#xff1f; 二.编译时Qt Creator偷摸做了哪些事情&#xff1f; 1.uic 2.rcc 3.moc 一.什么是Qt元对象系统&#xff1f; Qt中的元对象系统&#xff08;Meta-Object System&#xff09;提供了对象间通信的信号和槽机制、运行时类型信息和动态属…

ArcGIS Pro 拓扑编辑和常见一些拓扑错误处理

7.4 拓扑编辑 拓扑编辑也叫共享编辑&#xff0c;多个数据修改时&#xff0c;一块修改&#xff0c;如使用数据&#xff1a;chp7\拓扑检查.gdb,数据集DS下JZX、JZD和DK&#xff0c;加载地图框中&#xff0c;在“地图”选项卡下选择“地图拓扑”或“ds_Topology(地理数据库)”&…

基于Redis+Lua的分布式限流

本文已收录至我的个人网站&#xff1a;程序员波特&#xff0c;主要记录Java相关技术系列教程&#xff0c;共享电子书、Java学习路线、视频教程、简历模板和面试题等学习资源&#xff0c;让想要学习的你&#xff0c;不再迷茫。 前面我们了解了如何利用Nginx做网关层限流&#xf…

SpringAMQP的使用

1. 简介&#xff1a; SpringAMQP是基于RabbitMQ封装的一套模板&#xff0c;并且还利用SpringBoot对其实现了自动装配&#xff0c;使用起来非常方便。 SpringAmqp的官方地址&#xff1a;https://spring.io/projects/spring-amqp SpringAMQP提供了三个功能&#xff1a; 自动声…

【C语言】指针知识点笔记(2)

目录 一、野指针 二、assert断言 三、指针的使用和传址调用 四、数组名的理解 五、使用指针访问数组 一、野指针 二、assert断言 三、指针的使用和传址调用 四、数组名的理解 五、使用指针访问数组

Java中的异常处理

目录 前言&#xff1a; 异常简介&#xff1a; Error类&#xff1a; Exception类&#xff1a; Exception异常&#xff1a; 运行异常&#xff1a; 编译异常&#xff1a; throw和throws关键字&#xff1a; throw: throws: try-catch关键字&#xff1a; finally: 为…

编译 FastDFS 时报错 fatal error: sf/sf_global.h: No such file or directory 解决办法

编译 FastDFS 时&#xff0c;报错如下 gcc -Wall -D_FILE_OFFSET_BITS64 -D_GNU_SOURCE -g -O1 -DDEBUG_FLAG -c -o ../common/fdfs_global.o ../common/fdfs_global.c -I../common -I/usr/local/include In file included from ../common/fdfs_global.c:21:0: ../common/fdf…