LeetCode 面试题 01.09. 字符串轮转
文章目录
- 一、题目
- 二、C# 题解
一、题目
字符串轮转。给定两个字符串 s1 和 s2,请编写代码检查 s2 是否为 s1 旋转而成(比如,waterbottle 是 erbottlewat 旋转后的字符串)。
点击此处跳转题目。
示例1:
输入:s1 = “waterbottle”, s2 = “erbottlewat”
输出:True
示例2:
输入:s1 = “aa”, s2 = “aba”
输出:False
提示:
- 字符串长度在[0, 100000]范围内。
说明:
- 你能只调用一次检查子串的方法吗?
二、C# 题解
可以将题目理解为从字符串内部切一刀换序重组,判断是否能变为原字符串。但按照该思路写复杂度为 O ( n 2 ) O(n^2) O(n2),不是很理想,因此还是从字符入手。
使用双指针 i,j 从左向右分别指向 s1,s2。i 的任务是遍历 s1,查找 s2 在 s1 中的前缀;j 的任务是标识 s2 中前缀的位置,即 s2[0]~s2[j - 1] 为 s2 与 s1 相同的部分。
以 s1:bunana, s2:nabuna 为例,可以看出,s1:buna | na,s2:na | buna,s1 的后缀和 s2 的前缀想同,均为 na,算法的具体流程如下:
b u n a n a ( s 1 ) i : ↑ n a b u n a ( s 2 ) j : ↑ ⇓ b u n a n a ( s 1 ) i : ↑ n a b u n a ( s 2 ) j : ↑ ⇓ b u n a n a ( s 1 ) i : ↑ n a b u n a ( s 2 ) j : ↑ ⇓ b u n a n a ( s 1 ) i : ↑ n a b u n a ( s 2 ) j : ↑ ⇓ b u n a n a ( s 1 ) i : ↑ n a b u n a ( s 2 ) j : ↑ ⇓ b u n a n a ( s 1 ) i : ↑ n a b u n a ( s 2 ) j : ↑ ⇓ b u n a n a ( s 1 ) i : ↑ n a b u n a ( s 2 ) j : ↑ \begin{array}{l} & b & u & n & a & n & a & (s1)\\ i:& \uparrow & & & & \\ & n & a & b & u & n & a & (s2)\\ j:& \uparrow & & & & \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} & b & u & n & a & n & a & (s1)\\ i:& & \uparrow & & & \\ & n & a & b & u & n & a & (s2)\\ j:& \uparrow & & & & \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} & b & u & n & a & n & a & (s1)\\ i:& & & \uparrow & & \\ & n & a & b & u & n & a & (s2)\\ j:& \uparrow & & & & \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} & b & u & n & a & n & a & (s1)\\ i:& & & & \uparrow & \\ & n & a & b & u & n & a & (s2)\\ j:& & \uparrow & & & \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} & b & u & n & a & n & a & (s1)\\ i:& & & & & \uparrow \\ & n & a & b & u & n & a & (s2)\\ j:& \uparrow & & & & \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} & b & u & n & a & n & a & (s1)\\ i:& & & & & & \uparrow \\ & n & a & b & u & n & a & (s2)\\ j:& & \uparrow & & & \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} & b & u & n & a & n & a & (s1)\\ i:& & & & & & & \uparrow \\ & n & a & b & u & n & a & (s2)\\ j:& & & \uparrow & & \end{array}\\ i:j:b↑n↑uanbaunnaa(s1)(s2) ⇓ i:j:bn↑u↑anbaunnaa(s1)(s2) ⇓ i:j:bn↑uan↑baunnaa(s1)(s2) ⇓ i:j:bnua↑nba↑unnaa(s1)(s2) ⇓ i:j:bn↑uanbaun↑naa(s1)(s2) ⇓ i:j:bnua↑nbaunna↑a(s1)(s2) ⇓ i:j:bnuanb↑aunnaa(s1)↑(s2)
最终,i 指向 s1 的末尾,j 指向 s2 前缀的后一字符,即 s2 后缀的起始位置。
public class Solution {public bool IsFlipedString(string s1, string s2) {int l1 = s1.Length, l2 = s2.Length;if (l1 != l2) return false; // 长度不相等直接否掉int i = 0, j = 0; // 双指针,i 指 s1,j 指 s2while (i < l1) { // 遍历 s1,寻找 s2 的前缀if (s1[i] == s2[j]) j++; // 如果字符相同,则 j 后移else { // 字符不同,则 i、j 回退i -= j;j = 0;}i++; // i 始终前进}i = 0;while (j < l2) { // 检查 s2 后缀是否为 s1 前缀if (s1[i++] != s2[j++]) return false;}return true;}
}
- 时间复杂度:一般情况下为 O ( n ) O(n) O(n),但波动较大。最坏情况为 O ( n 2 ) O(n^2) O(n2),即字符串包含大部分重复字符。可以使用 KMP 算法优化,懒了没必要。
- 空间复杂度: O ( 1 ) O(1) O(1)。
相关文章:
LeetCode 面试题 01.09. 字符串轮转
文章目录 一、题目二、C# 题解 一、题目 字符串轮转。给定两个字符串 s1 和 s2,请编写代码检查 s2 是否为 s1 旋转而成(比如,waterbottle 是 erbottlewat 旋转后的字符串)。 点击此处跳转题目。 示例1: 输入:s1 “wa…...
系统上线安全测评需要做哪些内容?
电力信息系统、航空航天、交通运输、银行金融、地图绘画、政府官网等系统再正式上线前需要做安全测试。避免造成数据泄露从而引起的各种严重问题。 那么系统上线前需要做哪些测试内容呢?下面由我给大家介绍 1、安全机制检测-应用安全 身份鉴别 登录控制模块 应提供…...
vue 中 axios 的安装及使用
vue 中 axios 的安装及使用 1. axios 安装2. axios使用 1. axios 安装 首先,打开当前的项目终端,输入 npm install axios --save-dev验证是否安装成功,检查项目根目录下的 package.json,其中的 devDependencies 里面会多出一个axios及其版本…...
数据结构——线性数据结构(数组,链表,栈,队列)
文章目录 1. 数组2. 链表2.1. 链表简介2.2. 链表分类2.2.1. 单链表2.2.2. 循环链表2.2.3. 双向链表2.2.4. 双向循环链表 2.3. 应用场景2.4. 数组 vs 链表 3. 栈3.1. 栈简介3.2. 栈的常见应用常见应用场景3.2.1. 实现浏览器的回退和前进功能3.2.2. 检查符号是否成对出现3.2.3. 反…...
多态(C++)
多态 一、初识多态概念“登场”1>. 多态的构成条件2>. 虚函数3>. 虚函数重写(覆盖)4>. 虚函数重写的两个例外1. 协变 一 基类和派生类虚函数返回值类型不同2. 析构函数重写(基类和派生类析构函数名不同) 小结 二、延伸…...
算法leetcode|73. 矩阵置零(rust重拳出击)
文章目录 73. 矩阵置零:样例 1:样例 2:提示:进阶: 分析:题解:rust:go:c:python:java: 73. 矩阵置零: 给定一个 m x n 的矩…...
axios 二次封装
axios 二次封装 基本上每一个项目开发,都必须要二次封装 axios。主要是为了减少重复性工作,不可能每一次发起新请求时,都要重新配置请求域名、请求头 Content-Type、Token 等信息。所以需要把公用的部分都封装成一个函数,每次调用…...
Rust安全之数值
文章目录 数值溢出 数值溢出 编译通过,运行失败 cargo run 1 fn main() {let mut arg std::env::args().skip(1).map(|x| x.parse::<i32>().unwrap()).next().unwrap();let m_i i32::MAX - 1;let a m_i arg;println!("{:?}", a); }thread main panicked…...
4种方法实现html 页面内锚点定位及跳转
使用scrollIntoView进行锚点定位效果 不知道你有没有遇到这样的需求:锚点定位?进入页面某个元素需要出现在可视区?…这一类的需求归根结底就是处理元素与可视区域的关系。我接触了很多前端小伙伴,实现的方式有各种各样的ÿ…...
gitlab配置备忘
版本 gitlab 14.6.2 gitlab备份上传到阿里云oss ### Backup Settings ###! Docs: https://docs.gitlab.com/omnibus/settings/backups.html# gitlab_rails[manage_backup_path] true # gitlab_rails[backup_path] "/var/opt/gitlab/backups"###! Docs: https://…...
基于Centos搭建k8s仓库
系统环境: Red Hat Enterprise Linux 9.1 (Plow) Kernel: Linux 5.14.0-162.6.1.el9_1.x86_64 主机名地址master192.168.19.128node01192.168.19.129node02192.168.19.130 目录 1、关闭防火墙,关闭SElinxu ,开启时间同步服务 2、关…...
浅谈泛在电力物联网发展形态与技术挑战
安科瑞 华楠 摘 要:泛在电力物联网是当前智能电网发展的一个方向。首先,总结了泛在电力物联网的主要作用和价值体现;其次,从智能电网各个环节概述了物联网技术在电力领域的已有研究和应用基础;进而,构思并…...
git reset --soft 用法
git reset --soft 是 Git 命令中的一个选项,它用于取消之前的提交,并将取消的更改保留在暂存区。这允许您重新组织提交历史或将更改合并到一个新的提交中,而不影响暂存区和工作目录中的更改。 这个命令的语法是: git reset --so…...
哪些测试仪器可以用于检测静电中和设备的性能
静电设备性能测试通常需要使用一些专门的仪器来进行。以下是一些常见的静电设备性能测试仪器: 1. 静电电压测试仪:用于测量物体表面的静电电压。它通常可以测量正负电压,并具有高精度和快速响应的特点。 2. 静电电荷仪:用于测量物…...
浅析 GlusterFS 与 JuiceFS 的架构异同
在进行分布式文件存储解决方案的选型时,GlusterFS 无疑是一个不可忽视的考虑对象。作为一款开源的软件定义分布式存储解决方案,GlusterFS 能够在单个集群中支持高达 PiB 级别的数据存储。自从首次发布以来,已经有超过十年的发展历程。目前&am…...
ARM开发,stm32mp157a-A7核PWM实验(驱动蜂鸣器,风扇,马达工作)
1.分析框图; 2.比较捕获寄存器(产生PWM方波); 工作原理: 1、系统提供一个时钟源209MHZ,需要通过分频器进行分频,设置分频器值为209分频; 2、当定时器启动之后,自动重载…...
群狼调研(长沙眼镜店神秘顾客)|消费者需求研究方案
本文由群狼调研(长沙品牌调研)出品,欢迎转载,请注明出处。消费者需求研究方案是在开展研究之前制定的计划,用于指导研究的设计、实施和分析。以下是一个可能的消费者需求研究方案的大致框架: 1. 研究目标和问题: • …...
电脑入门:宽带路由器常见故障排除技巧
宽带路由器在企业网络中的应用是相当广泛的,在运行的过程中出现故障是在所难免的,虽然故障现象多种多样,引起故障发生的原因也不尽相同,但从大体上可以把这些故障分为硬件故障和软件故障,具体来说就是一些网络连接性问题、配置文件选项问题以及网络协议问题等。 由于路由器…...
基于云原生网关的流量防护实践
作者:涂鸦 背景 在分布式系统架构中,每个请求都会经过很多层处理,比如从入口网关再到 Web Server 再到服务之间的调用,再到服务访问缓存或 DB 等存储。在下图流量防护体系中,我们通常遵循流量漏斗原则进行流量防护。…...
开源与云计算:新的合作模式
🌷🍁 博主猫头虎 带您 Go to New World.✨🍁 🦄 博客首页——猫头虎的博客🎐 🐳《面试题大全专栏》 文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~🌺 &a…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
k8s从入门到放弃之HPA控制器
k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率(或其他自定义指标)来调整这些对象的规模,从而帮助应用程序在负…...
从实验室到产业:IndexTTS 在六大核心场景的落地实践
一、内容创作:重构数字内容生产范式 在短视频创作领域,IndexTTS 的语音克隆技术彻底改变了配音流程。B 站 UP 主通过 5 秒参考音频即可克隆出郭老师音色,生成的 “各位吴彦祖们大家好” 语音相似度达 97%,单条视频播放量突破百万…...
