Leetcode 2851. String Transformation
- Leetcode 2851. String Transformation
- 0. 吐槽
- 1. 算法思路
- 1. 整体思路
- 2. 字符串匹配优化
- 2. 代码实现
- 题目链接:2851. String Transformation
0. 吐槽
这道题多少有点坑爹,题目本身挺有意思的,是一道数组题目,其实用数学方法直接可以写出结果的数学表达式,因此做的时候成就感非常强。
但是,坑爹的来了,谁会想到这道题最终卡人的是数组匹配算法,真心晕菜!!!
举个不太恰当的例子,就像是你去复原一个魔方,你想了n久,终于想到了魔方的复原方法,然后到了考场上面,面试官给了你一块木头和一把锯子,让你先做个魔方然后再复原,还限时2h……
就尼玛坑爹啊!!!
不过万幸,总算是搞定了,顺道也优化了一下字符串的匹配算法,虽然非我所愿,但多少也有点成就感吧……
1. 算法思路
1. 整体思路
这一题整体思路上可以视为一道数组题目。
显然的,对于一个长度为 n n n的字符串s
,我们经过 k k k此操作之后可能的操作方式总数有 ( n − 1 ) k (n-1)^{k} (n−1)k种。
我们假设第 k k k次操作之后字符串s
恰好变为t
的操作方式总数为 a k a_k ak,那么显然我们有如下递推公式:
a k = a k − 1 × ( m − 1 ) + ( ( n − 1 ) k − 1 − a k − 1 ) × m = m ⋅ ( n − 1 ) k − 1 − a k − 1 \begin{aligned} a_k &= a_{k-1} \times (m-1) + ((n-1)^{k-1} - a_{k-1}) \times m \\ &= m \cdot (n-1)^{k-1} - a_{k-1} \end{aligned} ak=ak−1×(m−1)+((n−1)k−1−ak−1)×m=m⋅(n−1)k−1−ak−1
其中, m m m表示s
的所有循环字符串(至多经过一次操作之后得到的字符串)当中t
的个数,亦即,s
可以通过 m m m种旋转方式直接变为t
。
此时,我们由上述递推公式,不难迭代写出:
a k = m ⋅ ( n − 1 ) k − 1 − a k − 1 a k − 1 = m ⋅ ( n − 1 ) k − 2 − a k − 2 ⋯ a 1 = m ⋅ ( n − 1 ) 0 − a 0 \begin{aligned} a_k &= m \cdot (n-1)^{k-1} - a_{k-1} \\ a_{k-1} &= m \cdot (n-1)^{k-2} - a_{k-2} \\ \cdots \\ a_1 &= m \cdot (n-1)^{0} - a_{0} \end{aligned} akak−1⋯a1=m⋅(n−1)k−1−ak−1=m⋅(n−1)k−2−ak−2=m⋅(n−1)0−a0
我们分别带入之后即可得到 a k a_k ak的表达式如下:
a k = ( − 1 ) k a 0 + m ∑ i = 0 k − 1 ( − 1 ) k − 1 − i ⋅ ( n − 1 ) i = ( − 1 ) k a 0 + m ⋅ ( n − 1 ) k − ( − 1 ) k n \begin{aligned} a_{k} &= (-1)^{k} a_0 + m \sum\limits_{i=0}^{k-1} (-1)^{k-1-i} \cdot (n-1)^i \\ &= (-1)^{k} a_0 + m \cdot \frac{(n-1)^k - (-1)^k}{n} \end{aligned} ak=(−1)ka0+mi=0∑k−1(−1)k−1−i⋅(n−1)i=(−1)ka0+m⋅n(n−1)k−(−1)k
因此,事实上这道题我们可以通过 n , m , k n,m,k n,m,k的值直接算出我们的最终答案。
剩下的问题就是 n , m n,m n,m的求解了,其中 n n n是显然的,剩下的就是 m m m的求解了,本来其实就是将s
再拼接一份然后看一下新组成的这个字符串当中t
一共出现的次数就行了,用伪代码表示就是:
n = len(s)
ns = s + s[:-1]
m = len([i for i in range(n) if ns[i:i+n] == t])
结果没想到这里居然一直超时,最后这道题大部分的时候居然都集中在了解决这个问题上面,也是醉了……
下面,我们就来看一下我们具体对于这个问题的优化。
2. 字符串匹配优化
如前所述,这里事实上我们可以将问题抽象为如下问题:
已知两个字符串
s
和t
,问s
当中t
一共出现过多少次。
因此这里其实就是一个字符串匹配的问题,不过我们可以对其进行一下优化:
- 如果
s
当中的某一段已经和t
匹配上了(假设起始坐标为i
),此时我们就可以通过t
本身的特性,找到t
当中最接近头部的某个位置idx
,满足t[idx:] == t[:n-idx]
,此时我们可以直接跳转到这个位置,然后比较子串t[n-idx:]
与s[i+n:i+n+idx]
是否一致即可判断新的这个子串s[i+idx:i+idx+n]
是否等于t
,而无需判断中间的位置以及完整地判断这两个子串是否相同。
此时,问题就简化到了如何求得t
当中最接近头部的某个位置idx
,满足t[idx:] == t[:n-idx]
,而这个可以通过z-algorithm来进行快速实现,关于这部分的内容,我们之前已经写过了一个博客(经典算法:Z算法(z algorithm))对其进行过整理了,这里我们就不再展开赘述了。
2. 代码实现
综上,我们就可以给出我们最终的python代码实现如下:
def z_algorithm(s):n = len(s)z = [0 for _ in range(n)]l, r = -1, -1for i in range(1, n):if i > r:l, r = i, iwhile r < n and s[r-l] == s[r]:r += 1z[i] = r-lr -= 1else:k = i - lif z[k] < r - i + 1:z[i] = z[k]else:l = iwhile r < n and s[r-l] == s[r]:r += 1z[i] = r-lr -= 1z[0] = nreturn zdef find_all(s, t):l, n = len(s), len(t)prefix = z_algorithm(t)nxt, m = n, 0for i in range(1, n):if i + prefix[i] == n:nxt = im = prefix[i]breakidx = 0cnt = 0while idx < l:idx = s.find(t, idx)if idx == -1:breakcnt += 1if nxt < n:while idx+n < l and t[m:] == s[idx+n:idx+n+nxt]:idx = idx+nxtcnt += 1idx += 1return cntclass Solution:def numberOfWays(self, s: str, t: str, k: int) -> int:MOD = 10**9+7n = len(s)m = find_all(s+s[:-1], t)f0 = 0 if s != t else 1fk = f0 * pow(-1, k) + m * pow(n, -1, MOD) * (pow(n-1, k, MOD) - pow(-1, k))return fk % MOD
提交代码评测得到:耗时801ms,占用内存41.1MB。
值得一提的是,截至23.9.10晚间,当前这个执行效率远远高于其他python提交的算法执行效率(其他实现当中最快的执行时间为3167ms),多少也是让我感觉挺有成就感的……
相关文章:
Leetcode 2851. String Transformation
Leetcode 2851. String Transformation 0. 吐槽1. 算法思路 1. 整体思路2. 字符串匹配优化 2. 代码实现 题目链接:2851. String Transformation 0. 吐槽 这道题多少有点坑爹,题目本身挺有意思的,是一道数组题目,其实用数学方法…...

在PHP8中对数组进行计算-PHP8知识详解
在php8中,提供了丰富的计算函数,可以对数组进行计算操作。常见的计算函数如下几个:array_sum()函数、array_merge()函数、array_diff()函数、array_diff_assoc()函数、array_intersect()函数、array_intersect_assoc()函数。 1、array_sum()函…...
Android BottomSheetDialog最大展开高度问题
修改界面的时候遇到了这个问题,这个问题比较简单,网上解决方案也很多,这是 peekHeight 半展开高度,毕竟只是 dialog,全铺满就我们不必考虑 dialog 了 方法是在DialogFragment初始化dialog时处理 companion object {/*** 设置弹窗高度 默认展开无折叠情况 */ const val …...
记录Linux部署人脸修复GFPGAN项目Docker Python 使用
记录Linux 服务器使用人脸修复GFPGAN 项目 1:阿里云安装docker,用docker 是隔离环境,Python环境还真是麻烦… https://help.aliyun.com/zh/ecs/use-cases/deploy-and-use-docker-on-alibaba-cloud-linux-2-instances 2:关于docker 镜像,想找个好的镜像也是很难,百度吧,很多Li…...
如何编写可重入的函数?
编写可重入(reentrant)的函数是在多线程环境或并发编程中非常重要的任务。可重入函数是一种可以安全地被多个线程同时调用的函数,而不会导致数据竞争或不一致性的函数。在C语言中,编写可重入函数需要遵循一些特定的规则和技巧。本…...

使用纯C语言定义通用型数据结构的方法和示例
文章目录 前言以实现优先队列来描述实现思想基本类型的包装类型比较函数演示总结 前言 最近一段时间在复习数据结构和算法,用的C语言,不得不说,不学个高级语言再回头看C语言根本不知道C语言的强大和完美,不过相比之下也有许多不便…...

数据结构基础8:二叉树oj+层序遍历。
二叉树oj层序遍历 题目一:二叉树的销毁:方法一:前序遍历:方法二:后序遍历: 题目二:二叉树查找值为x的节点方法一:方法二:方法三: 题目三:层序遍历…...

Spring注解家族介绍:@RestController
前言: Spring Boot可以说是当前JAVA最为重要的一个框架,而Spring Boot的基石Spring中有着丰富的注解,因此我们会利用几篇文章来讲解我目前学到的各种注解,因此本类型文章的篇幅会比较短,主要着重于介绍各个注解。 目录…...

rocketmq
🍓代码仓库 https://gitee.com/xuhx615/rocket-mqdemo.git 🍓基本概念 ⭐生产者(Producer):消息发布者⭐主题(Topic):topic用于标识同一类业务类型的消息⭐消息队列(MessageQueue)…...

JAVA成员变量首字母小写,第二个字母大写报错问题(原因:Lombok与Spring冲突)
1、问题现象: JAVA类里定义成员变量使用首字母小写,第二个字母大写 Getter Setter public class BrandQueryObject extends QueryObject{private String pName; }结果页面报错,无法找到类型为 cn.wolfcode.ssm.query.BrandQueryObject 的对象…...

Python入门教程 |Python 错误和异常
Python3 错误和异常 作为 Python 初学者,在刚学习 Python 编程时,经常会看到一些报错信息,在前面我们没有提及,这章节我们会专门介绍。 Python 有两种错误很容易辨认:语法错误和异常。 Python assert(断…...
API商品接口对接使用:从理论到实践
随着电子商务的飞速发展,API商品接口已成为现代电子商务应用程序不可或缺的一部分。通过API商品接口,开发者可以轻松地从其他应用程序或服务中获取商品信息,实现快速、高效的电子商务功能。本文将探讨API商品接口的概念、对接使用的方法以及一…...

解决stable diffusion webui1.6 wd1.4 tagger加载失败的问题
由于webui源码的变化,需要修改两个地方的import 1.tagger/ui.py # 第十行 # from webui import wrap_gradio_gpu_call # 原代码 from modules.call_queue import wrap_gradio_gpu_call1.preload.py # 第4行开始 # from modules.shared import models_path # 原…...
Python学习-实现简单的http服务
基于Python实现一个简单的HttpServer,当用户在浏览器中输入IP地址:8000时,则会返回index.html页面内容,访问其它信息,则会返回错误信息(404) """ httpserver v1.0 1.获取来自浏览器的请求, 2.判断如果请求内容是 …...
#循循渐进学51单片机#变量进阶与点阵LED#not.6
1、掌握变量的作用域及存储类别。 局部变量 函数内部声明的变量,只在函数内部有效,在本函数以外是不能使用的,叫局部变量。 全局变量 在函数外部声明的变量就是全局变量,一个源程序可以包含一个或多个函数,全局变量…...

访问者模式
图片转载自 #include<iostream> using namespace std; #include<list> /*模板工厂单例化,所有的商品被注册进工厂中*/ /*访问者模式(行为型模式) 访问者,被访问者 visit accept 让访问变成一种操作,不同…...

epoll 的实现
epoll 这么好,为什么迟至 2.6 版本的 kernel 才支持(epoll manual: The epoll API was introduced in Linux kernel 2.5.44.)?2.4 版本的 kernel 不支持 epoll? 原因很简单,epoll 没什么神奇的。在早期没有太多的并发连接要处理&…...

怎么用excel管理固定资产
在当今的数字时代,我们已经习惯了使用各种电子工具来提高我们的生产力。其中,Excel无疑是一个强大的工具,它不仅可以帮助我们处理数据,还可以用来进行复杂的计算和分析。然而,你可能不知道的是,Excel也可以…...

记录crack某IDE插件过程
声明:本文仅记录学习过程,已对关键位置脱敏处理,未提供任何工具,请支持正版。 反编译jar包 使用cfr进行对插件核心jar包MyBxxxxxx-obfuss.jar进行反编译,在本地生成a.txt。 java -jar cfr-0.152.jar MyBxxxx-obfuss.…...
Android DEX相关,ART加载OAT文件
android .dex文件,对于Android DEX文件详细说明 Android dex、odex、oat、vdex、art区别 Android下的DEX文件和SO文件梳理总结 Android[art]-Android dex,odex,oat,vdex,art文件结构学习总结 第四章 常见的 Android 文件格式&…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...