LeetCode-Java:6.Z字形变换

文章目录

    • 题目
      • ① 找规律

题目

将一个给定字符串 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"

① 找规律

2ms,超过98.63%

43.69MB,超过86.85%

这道题还是有点难度在,一开始想要设置一个二维数组,遍历整个字符串,按照变换的规则将字符串存入到二维数组当中,最后将二维数组按照从左向右顺序读取转换成字符串。

写了一半,感觉这个思路写起来太麻烦了,想走个捷径,就按照下图的方式把原‘s’、排列情况、输出情况都列出来,想要得到一个‘函数’,可以使得输入转变为输出。

题目已经给定了numRows,按照规律排列能够找到第一行元素彼此之间间隔多少,后几行输出则根据第一行的输出±i (i=1,2,3…)即可

但在这种情况下,仍旧存在一些特殊情况需要考虑,比如如果numRows<2,那无论如何排列都是原本的‘s’,按照代码的情况的话,容易造成数组越界,所以numRows<2,直接返回s。

在这里插入图片描述

问题:为什么要设置use[]数组?

**答:**use[]数组主要用于记录字符串当中哪些元素已经被使用过,防止元素重复使用。具体在例子当中可以看为‘P A Y R A’,假设第一行是"P A",第二行是“A R”,第三行应该是‘Y’,如果按照代码的逻辑,在‘p’下标基础上+2输出一次,在‘A’下标基础上-2输出一次,那么‘Y’会被输出两次,有了use[]数组就可以保证只输出一次。当然也有其他的方法,不设置use[]数组也可以防止多输出情况,能够节省一些空间,但实现更复杂,更不易懂,感觉没必要。

问题:为什么第二个for循环当中的for循环设置j<len+numRows?

**答:**主要是因为用例“ABCD”,numRows=3无法通过。第一个for循环是用来确定第一行的情况的,第二个for循环是根据第一行情况找到第一行元素左右两侧±i的位置进行保存。用例“ABCD”,第一行只有‘A’,第二行应当为‘B D’,假设j<len的话,则第二行只有‘B’,因为‘D’是根据s[4](该元素不存在)的左右两侧进行确定的,所以理论上j一定得比len多出一个(2*numRows-2)/2,里面的判断只需要看j±i是否会超过数组范围就可保证不会越界。

那为什么是j<len+numRows,而不是j<len+numRows-1?主要原因是加上-1也可以,就是运行速度略微慢了一点,所以呐,这里去掉了,影响不大~

class Solution {public String convert(String s, int numRows) {if (numRows<2) return s;//如果numRows=1,则s不需要变换直接返回StringBuilder str=new StringBuilder();//StringBuilder比String运算速度要快int len=s.length();int[] use=new int[len];//记录s的元素是否使用过//变换后的第一行for(int i=0;i<len;i=i+2*numRows-2){use[i]=1;str.append(s.charAt(i));}//变换后的2~numRows行for(int i=1;i<numRows;i++){for(int j=0;j<len+numRows;j=j+2*numRows-2){//为什么设置j<len+numRows看上面//先j-1,后j+1,符合s的从左到右顺序if(j-i>=0 && j-i<len && use[j-i]!=1){//保证数组不越界,并且没使用过就加入到struse[j-i]=1;str.append(s.charAt(j-i));}if(j+i<len && use[j+i]!=1){//保证数组不越界,并且没使用过就加入到struse[j+i]=1;str.append(s.charAt(j+i));}}}return str.toString();//转换成字符串返回}
}

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

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

相关文章

独家原创 | Matlab实现INFO-BiTCN-BiGRU-Attention多输入单输出回归预测

独家原创 | Matlab实现INFO-BiTCN-BiGRU-Attention多输入单输出回归预测 目录 独家原创 | Matlab实现INFO-BiTCN-BiGRU-Attention多输入单输出回归预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.Matlab实现INFO-BiTCN-BiGRU-Attention向量加权算法优化双向时间卷积…

【无人机/平衡车/机器人】详解STM32+MPU6050姿态解算—卡尔曼滤波+四元数法+互补滤波——附3个算法源码

效果&#xff1a; MPU6050姿态解算-卡尔曼滤波四元数互补滤波 目录 基础知识详解 欧拉角 加速度计(Accelerometer)与姿态测量 陀螺仪(Gyroscope)与姿态测量 姿态解算算法1-互补滤波 姿态解算算法2-四元数法 姿态解算算法3-卡尔曼滤波 组成 1.预测状态方程 2. 预测协方…

10:00面试,10:08就出来了,问的问题有点变态。。。

从小厂出来&#xff0c;没想到在另一家公司又寄了。 到这家公司开始上班&#xff0c;加班是每天必不可少的&#xff0c;看在钱给的比较多的份上&#xff0c;就不太计较了。没想到8月一纸通知&#xff0c;所有人不准加班&#xff0c;加班费不仅没有了&#xff0c;薪资还要降40%…

浅谈网络安全威胁与防御策略

企业网络安全威胁概述 外部威胁&#xff1a;来自网络安全威胁&#xff0c;比如DDOS攻击&#xff0c;病毒&#xff0c;sql注入&#xff0c;木马&#xff0c;蠕虫&#xff0c;等网络入侵&#xff0c;网络扫描&#xff0c;垃圾邮件&#xff0c;钓鱼邮件&#xff0c;针对web的攻击…

计算机网络——NAT技术

目录 前言 前篇 引言 SNAT&#xff08;Source Network Address Translation&#xff09;源网络地址转换 SNAT流程 确定性标记 DNAT&#xff08;Destination Network Address Translation&#xff0c;目标网络地址转换&#xff09; NAT技术重要性 前言 本博客是博主用于…

科技论文和会议录制高质量Presentation Video视频方法

一、背景 机器人领域&#xff0c;许多高质量的期刊和会议&#xff08;如IEEE旗下的TRO&#xff0c;RAL&#xff0c;IROS&#xff0c;ICRA等&#xff09;在你的论文收录后&#xff0c;需要上传一个Presentation Video材料&#xff0c;且对设备兼容性和视频质量有较高要求&#…

Vue3基础语法

在这个章节中&#xff0c;简单的看下Vue3的基础语法&#xff0c;有了这些基础后&#xff0c;对写vue3单页也就没有什么问题了。 模板语法 在写html时&#xff0c;我们希望在某个节点绑定一个动态值时&#xff0c;是使用dom操作执行的&#xff0c;如下&#xff1a; <!DOCT…

Linux:动态库加载、编址

目录 一、库的概念 二、动静态库的加载 2.1绝对编址与相对编址 2.1一般程序的加载 三、动态库的加载 一、库的概念 库默认就是一个磁盘级文件&#xff0c;所以在执行代码时&#xff0c;库和可执行程序都会被加载到内存中&#xff0c;从原理上&#xff0c;库函数的调用依旧…

多态【C/C++复习版】

目录 一、多态是什么&#xff1f;如何实现&#xff1f; 二、 什么是重写&#xff1f;有什么特点&#xff1f; 三、什么是协变&#xff1f; 四、析构函数能实现多态吗&#xff1f;为什么要实现&#xff1f; 五、override和final的作用是什么&#xff1f; 六、 多态的原理是…

从 SQLite 3.4.2 迁移到 3.5.0(二十)

返回&#xff1a;SQLite—系列文章目录 上一篇:SQLite---调试提示&#xff08;十九&#xff09; 下一篇&#xff1a;SQLite—系列文章目录 ​ SQLite 版本 3.5.0 &#xff08;2007-09-04&#xff09; 引入了一个新的操作系统接口层&#xff0c; 与所有先前版本的 SQLi…

ELK 日志分析系统(一)

一、概念 二、详解 2.1 Elasticsearch 核心概念 2.1.1 接近实时(NRT) 2.1.2 cluster集群 2.1.3 Node节点 2.1.4 index索引 2.1.5 类型&#xff08;type&#xff09; 2.1.6 文档&#xff08;document) 2.1.7 分片和副本(shards & replicas) 2.2 Logstash主要组件 …

个人博客系统项目(SpringBoot+Linux部署上线)

在学完SpringBoot框架、MyBatis后&#xff0c;直接开始做第一个项目&#xff1a;博客系统 首先&#xff0c;该博客系统包含核心功能有&#xff1a; 一、登录、注册、退出登录功能。 二、没有登陆前可以查看博客首页以及博客展示的分页处理&#xff0c;以及点击查看博客可以…

windows下pycharm中配置conda虚拟环境

目录 一&#xff1a;背景 二&#xff1a;安装conda环境 三&#xff1a;pycharm配置环境 四&#xff1a;注意问题 一&#xff1a;背景 在使用python的过程中&#xff0c;我们可能需要在一个windows环境中创建多个版本的python和安装不同的库去做一些开发任务。 使用conda&a…

IDEA2023 开发环境配置

目录 1. 关闭IDEA自动更新1.2 IDEA 新版样式切换 2. Maven配置2.1本地仓库优先加载2.2 maven.config配置文件中 3. 全局配置JDK4. 配置文件编码:UTF-85. 开启自动编译&#xff08;全局配置&#xff09;6. 开启自动导包7. 开启鼠标悬浮&#xff08;提示文档信息&#xff09;8. 设…

10分钟1000台虚机 云安全效能双升 亚信安全新信舱无代理云平台快速适配版正式发布

新信舱 亚信安全新信舱无代理云平台快速适配版正式发布。在云平台依赖性、无代理部署速度、宿主机无代理AV防护和虚拟机缓存扫描性能等方面&#xff0c;新信舱无代理版本提供了无缝的可扩展性、低资源消耗并降低管理复杂性&#xff0c;让安全防护真正做到了 多快好省&#xff…

Rust语言入门第二篇-Cargo教程

文章目录 Rust语言入门第二篇-Cargo教程一&#xff0c;Cargo 是什么二&#xff0c;Cargo教程Cargo.toml文件src/main.rs 文件构建并运行Cargo项目 Rust语言入门第二篇-Cargo教程 本节提供对cargo命令行工具的快速了解。我们演示了它为我们生成新包的能力&#xff0c;它在包内编…

基于Leaflet.js的Marker闪烁特效的实现-模拟预警

目录 前言 一、闪烁组件 1、关于leaflet-icon-pulse 2、 使用leaflet-icon-pulse 3、方法及参数简介 二、闪烁实例开发 1、创建网页 2、Marker闪烁设置 3、实际效果 三、总结 前言 在一些地质灾害或者应急情况当中&#xff0c;或者热门预测当中。我们需要基于时空位置来…

ActiveMQ + MQTT 集群搭建(虚机版本) + Springboot使用配置

文章目录 前言一、ActiveMQ、 MQTT是什么&#xff1f;1.ActiveMQ介绍2.MQTT介绍 二、集群搭建步骤1.下载apache-activemq-5.15.12-bin.tar.gz2.上传apache-activemq-5.15.12-bin.tar.gz到服务器并解压文件到文件夹clusters、master、slave三个文件夹下面形成三个节点&#xff0…

C++ stl容器string的底层模拟实现

目录 前言&#xff1a; 1.成员变量 2.构造函数与拷贝构造函数 3.析构函数 4.赋值重载 5.[]重载 6.比较关系重载 7.reserve 8.resize 9.push_back,append和重载 10.insert 11.erase 12.find 14.迭代器 15.流插入&#xff0c;流提取重载 16.swap 17.c_str 18.完…

信道延迟的计算方法

目录 1.信道延迟影响的因素 2.计算公式 3.实践理解 4.基础知识 1.信道延迟影响的因素 因素1&#xff1a;与源端和宿端距离&#xff1b; 因素2&#xff1a;具体信道中的信号传播速率有关&#xff1b; 2.计算公式 总延迟 T发送延迟T1&#xff08;信号传播速率&#xff09; 线路…