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

模拟算法(3)_Z字形变换

个人主页:C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

模拟算法(3)_Z字形变换

收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记,欢迎大家在评论区交流讨论💌

目录

1. 题目链接 :

2. 题目描述 :

3. 解法(模拟) :

   解法一(模拟 + 暴力):

    题目分析 :

    算法思路 :

    示例展示: 

    代码展示 :

    结果分析 :

   解法二(模拟 + 规律) : 

算法思路:

代码展示:

结果分析:

 


1. 题目链接 :

OJ链接 : Z字形变换

2. 题目描述 :

将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:

P   A   H   N
A P L S I I G
Y   I   R

之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"PAHNAPLSIIGYIR"

请你实现这个将字符串进行指定行数变换的函数:

string convert(string s, int numRows);

示例 1:

输入:s = "PAYPALISHIRING", numRows = 3
输出:"PAHNAPLSIIGYIR"

示例 2:

输入:s = "PAYPALISHIRING", numRows = 4
输出:"PINALSIGYAHRPI"
解释:
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3:

输入:s = "A", numRows = 1
输出:"A"

提示:

  • 1 <= s.length <= 1000
  • s 由英文字母(小写和大写)、',' 和 '.' 组成
  • 1 <= numRows <= 1000

3. 解法(模拟) :

   解法一(模拟 + 暴力):

    题目分析 :

假如题目给我们这样的字符串s : a. b. c. d. e. f. g. h. i. j. k. l. m. n numRows = 4

从上往下进行Z字形排列,然后从左往右逐行读取,产生出一个新的字符串: agmbfhlnceikdj

如下图所示: 

    算法思路 :

1. 输入判断:

首先,算法检查 numRows 是否小于等于 1 或大于等于字符串 s 的长度。如果是,则直接返回原字符串 s,因为在这些情况下,不需要进行任何转换。
2. 初始化:

创建一个字符串向量 rows 来存储每一行的内容。这个向量的大小是 min(numRows, (int)s.size()),以防字符串长度小于行数。
curRow 用于跟踪当前字符应该放入的行,初始值为 0。
goingDown 是一个布尔值,用于指示当前的遍历方向(向下或向上)。
3. 遍历字符串:

使用一个循环遍历字符串 s 中的每个字符。
将当前字符 ch 添加到对应的行 rows[curRow]。
判断是否到达了第一行(curRow == 0)或最后一行(curRow == numRows - 1)。如果到达了这些边界,就反转方向,即将 goingDown 的值取反。
根据当前方向更新 curRow 的值。如果 goingDown 为 true,则 curRow 加 1;否则减 1。
4. 组合结果:

最后,创建一个字符串 ret,将 rows 向量中的所有行连接在一起,形成最终结果。

    示例展示: 

假设输入字符串 s = "PAYPALISHIRING",并且 numRows = 3,算法的执行步骤如下:

初始化:

rows = ["", "", ""](三个空字符串)
curRow = 0
goingDown = false

遍历字符:

添加 P → rows = ["P", "", ""], curRow = 1
添加 A → rows = ["P", "A", ""], curRow = 2
添加 Y → rows = ["P", "A", "Y"], curRow = 1
添加 P → rows = ["P", "AP", "Y"], curRow = 0
添加 A → rows = ["PA", "AP", "Y"], curRow = 1
添加 L → rows = ["PA", "AP", "YL"], curRow = 2
添加 I → rows = ["PA", "API", "YL"], curRow = 1
添加 S → rows = ["PA", "APIS", "YL"], curRow = 0
添加 H → rows = ["PAH", "APIS", "YL"], curRow = 1
添加 I → rows = ["PAH", "APISI", "YL"], curRow = 2
添加 R → rows = ["PAH", "APISIR", "YL"], curRow = 1
添加 I → rows = ["PAH", "APISIRI", "YL"], curRow = 0
添加 N → rows = ["PAHN", "APISIRI", "YL"], curRow = 1
添加 G → rows = ["PAHN", "APISIRIG", "YL"], curRow = 2

    代码展示 :

class Solution {
public:string convert(string s, int numRows) {//如果行数小于等于或大于等于字符串长度,直接返回原字符串if(numRows <= 1 || numRows >= s.size()) return s;//创建一个字符串向量来存储每一行vector<string> rows(min(numRows, (int)s.size()));int curRow = 0; //当前索引bool goingDown = false;//方向标志,false表示向上,true表示向下//遍历字符串中的每个字符for(char ch : s){rows[curRow] += ch;//将字符添加到当前行//当到达第一行或最后一行时,改变方向if(curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;//切换方向//更新当前索引curRow += goingDown ? 1 : -1;}//组合所有行string ret;for(auto ch : rows)ret += ch;return ret;}
};

    结果分析 :

时间复杂度
该算法的时间复杂度是 O(n),其中 n 是输入字符串的长度,因为每个字符都会被遍历一次。
空间复杂度
空间复杂度是 O(n),用于存储结果行数和结果字符串。 

   解法二(模拟 + 规律) : 

算法思路:

 

不难发现,数据是以 2row - 2 为⼀个周期进⾏规律变换的。将所有数替换成用周期来表示的变量:
第⼀行的数是:0, 2row - 2, 4row - 4;
第⼆行的数是:1, (2row - 2) - 1, (2row - 2) + 1, (4row - 4) - 1, (4row - 4) + 1;
第三行的数是:2, (2row - 2) - 2, (2row - 2) + 2, (4row - 4) - 2, (4row - 4) + 2;
第四行的数是:3, (2row - 2) + 3, (4row - 4) + 3。
可以观察到,第⼀行、第四行为差为 2row - 2 的等差数列;第二行、第三行除了第⼀个数取值为行
数,每组下标为(2n - 1, 2n)的数围绕(2row - 2)的倍数左右取值。
以此规律,我们可以写出迭代算法。

再进一步抽象成序号:

 

代码展示:

class Solution {
public:string convert(string s, int numRows) {string ret;if(numRows <= 1 || numRows >= s.size()) return s;//求出公差int d = 2 * numRows - 2;//处理第一行for(int i = 0; i < s.size(); i += d)ret += s[i];//处理中间k行for(int i = 1; i < numRows - 1; i++)for(int j = i; j < s.size(); j += d){ret += s[j];if(j + d - 2 * i < s.size()) ret += s[j + d - 2 * i]; }//处理最后一行for(int i = numRows - 1; i < s.size(); i += d)ret += s[i];return ret;}
};

 

结果分析:

综合
时间复杂度 : O(n)
空间复杂度 : O(n)

相关文章:

模拟算法(3)_Z字形变换

个人主页&#xff1a;C忠实粉丝 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 C忠实粉丝 原创 模拟算法(3)_Z字形变换 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记&#xff0c;欢迎大家在评论区交流讨论&#x1f48c; 目录 1. 题目链…...

Go语言实现长连接并发框架 - 任务执行流路由模块

文章目录 前言接口结构体接口实现项目地址最后 前言 你好&#xff0c;我是醉墨居士&#xff0c;上篇博客中我们实现了任务执行流上下文部分&#xff0c;接下来我们实现一下任务执行流的路由模块&#xff0c;基于该模块可以实现将消息转发到相应注册的任务执行流中进行处理 接…...

Windows 编译 FFmpeg 源码详细教程

FFmpeg FFmpeg 是一个开源的多媒体框架,它包括了一整套工具和库,可以用来处理(转码、转换、录制、流式传输等)音频和视频。FFmpeg 支持广泛的音视频格式,并且可以在多种操作系统上运行,包括 Windows、Linux 和 macOS。 FFmpeg 的主要组件包括: ffmpeg:这是一个命令行工…...

JavaCV 实现视频链接截取封面工具

引入必要依赖 <!--JavaCV--> <dependency><groupId>org.bytedeco</groupId><artifactId>javacv-platform</artifactId><version>1.5.7</version> </dependency> <dependency><groupId>cn.hutool</groupI…...

初识Linux · 进程替换

目录 前言&#xff1a; 1 直接看代码和现象 2 解释原理 3 将代码改成多进程版本 4 认识所有函数并使用 前言&#xff1a; 由前面的章节学习&#xff0c;我们已经了解了进程状态&#xff0c;进程终止以及进程等待&#xff0c;今天&#xff0c;我们学习进程替换。进程替换我…...

项目-坦克大战学习-人机ai

我们要知道&#xff0c;人机的移动和玩家的移动方式是一样的&#xff0c;所以我们可以将玩家移动代码以及检测碰撞代码移过来&#xff0c;唯一不同的就是人机检测到碰撞后会改变方向继续移动而不是停止 所以我们需要一个随机数使人机检测到碰撞后随机修改方向 Random rd new …...

YOLOv11改进 | Conv篇 | YOLOv11引入SKConv

1. SKConv介绍 1.1 摘要:在标准卷积神经网络(CNN)中,每层中阿尔蒂神经元的感受野被设计为共享相同的大小。在神经科学界众所周知,视觉皮层神经元的感受野大小受到刺激的调制,这在构建CNN时很少考虑。我们在CNN中提出了一种动态选择机制,允许每个神经元根据输入信息的多…...

招联2025校招内推

【投递方式】 直接扫下方二维码&#xff0c;或点击内推官网https://wecruit.hotjob.cn/SU61025e262f9d247b98e0a2c2/mc/position/campus&#xff0c;使用内推码 igcefb 投递&#xff09; 【招聘岗位】 后台开发 前端开发 数据开发 数据运营 算法开发 技术运维 软件测试 产品策…...

美容院管理创新:SpringBoot系统设计与开发

摘 要 如今的信息时代&#xff0c;对信息的共享性&#xff0c;信息的流通性有着较高要求&#xff0c;因此传统管理方式就不适合。为了让美容院信息的管理模式进行升级&#xff0c;也为了更好的维护美容院信息&#xff0c;美容院管理系统的开发运用就显得很有必要。并且通过开发…...

文心一言 VS 讯飞星火 VS chatgpt (361)-- 算法导论24.3 3题

三、假定将 Dijkstra 算法的第4行改为&#xff1a; 4 while |Q|>1 这种改变将让 while 循环的执行次数从 ∣ V ∣ |V| ∣V∣ 次降低到 ∣ V ∣ − 1 |V|-1 ∣V∣−1 次。这样修改后的算法正确吗? 如果要写代码&#xff0c;请用go语言。 文心一言&#xff1a; 将 Dijkst…...

ArkTS 开发中,有两种网络请求

在鸿蒙开发中&#xff0c;ArkTS&#xff08;Ark TypeScript&#xff09;是用于构建鸿蒙应用的一种开发语言&#xff0c;它基于TypeScript&#xff0c;并提供了丰富的API和工具集来简化开发过程。其中&#xff0c;网络请求是开发应用时经常需要用到的一个功能。 ArkTS 网络请求…...

记录一次病毒启动脚本

在第一次下载软件时&#xff0c;目录中配了一个使用说明&#xff0c;说是需要通过start.bat 这个文件来启动程序&#xff0c;而这个 start.bat 就是始作俑者&#xff1a; 病毒作者比较狡猾&#xff0c;其中start.bat 用记事本打开是乱码&#xff0c;但是可以通过将这个批处理…...

2019~2023博文汇总目录

2023 大厂实践 - 哈啰&#xff1a;记录一次ElasticSearch的查询性能优化-CSDN博客 Shiro安全框架-CSDN博客 MQ知识点汇总-CSDN博客 工作学习记录-CSDN博客 后端架构师技术图谱-CSDN博客 2020 Elasticsearch相关技术点_elasticsearch技术点-CSDN博客 Kafka相关技术点_kafka…...

springboot项目配置部分依赖从私服拉取,部分从阿里云拉取

在Java项目中&#xff0c;配置部分依赖从私服拉取&#xff0c;部分从阿里云拉取&#xff0c;可以在Maven的配置文件settings.xml中设置多个镜像&#xff0c;Maven会根据镜像的顺序尝试下载依赖。 ‌配置私服镜像‌&#xff1a;首先配置你的私服镜像&#xff0c;例如Nexus私服&…...

返回索引对象中各元素的数据类型 pandas.Index.dtype

【小白从小学Python、C、Java】 【考研初试复试毕业设计】 【Python基础AI数据分析】 返回索引对象中 各元素的数据类型 pandas.Index.dtype [太阳]选择题 根据题目代码&#xff0c;执行idx3.dtype的结果是&#xff1f; import pandas as pd idx1 pd.Index([1, 2, 3, 4, 5])…...

通过freepbx搭建小型电话系统的过程

领导说公司的客服电话需要实现语音导航和非工作时间自动接听播放语音提示的功能。任务自然落到了伟大的程序员的头上&#xff0c;本着为公司节约成本原则遂百度了一番&#xff0c;找到了asterisk 和freeswitch两个比较流行的电话系统。经过对比和考虑公司的情况选择了asterisk系…...

pdf处理1

处理PDF文件以构建数据索引是一个复杂但关键的步骤&#xff0c;尤其是因为PDF格式的文件通常包含多种元素&#xff0c;如文本、图片、表格、标题等。以下是一个通俗易懂的详细解释&#xff0c;帮助你理解PDF文件是如何被处理和解析的&#xff1a; 1. PDF文件的基本结构 PDF&a…...

区间覆盖(贪心)

给定 NN 个闭区间 [ai,bi][ai,bi] 以及一个线段区间 [s,t][s,t]&#xff0c;请你选择尽量少的区间&#xff0c;将指定线段区间完全覆盖。 输出最少区间数&#xff0c;如果无法完全覆盖则输出 −1−1。 输入格式 第一行包含两个整数 ss 和 tt&#xff0c;表示给定线段区间的两…...

[rk3588 debain]cpu死锁问题解决

1 问题 rk3588机器上运行客户如下程序程序发生“BUG: spinlock recursion on CPU#0” ./rtsp RtspWrapper.xml 应用程序功能是&#xff1a;ip摄像头推流&#xff0c;通过rtsp协议拉流&#xff0c;对视频流做裁剪&#xff0c;缩放工作。首先&#xff0c;根据视频帧率每秒钟处理…...

CMU 10423 Generative AI:lec18(大模型的分布式训练)

这个文档主要讲解了分布式训练&#xff08;Distributed Training&#xff09;&#xff0c;特别是如何在多GPU上训练大规模的语言模型。以下是主要内容的概述&#xff1a; 1. 问题背景 训练大规模语言模型的主要挑战是内存消耗。 训练过程中&#xff0c;内存消耗主要来源于两个…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...