LeetCode-Java:6.Z字形变换

2024-04-12 14:12
文章标签 java leetcode 变换 字形

本文主要是介绍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();//转换成字符串返回}
}

这篇关于LeetCode-Java:6.Z字形变换的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/897358

相关文章

Spring Boot中的路径变量示例详解

《SpringBoot中的路径变量示例详解》SpringBoot中PathVariable通过@PathVariable注解实现URL参数与方法参数绑定,支持多参数接收、类型转换、可选参数、默认值及... 目录一. 基本用法与参数映射1.路径定义2.参数绑定&nhttp://www.chinasem.cnbs

JAVA中安装多个JDK的方法

《JAVA中安装多个JDK的方法》文章介绍了在Windows系统上安装多个JDK版本的方法,包括下载、安装路径修改、环境变量配置(JAVA_HOME和Path),并说明如何通过调整JAVA_HOME在... 首先去oracle官网下载好两个版本不同的jdk(需要登录Oracle账号,没有可以免费注册)下载完

Spring StateMachine实现状态机使用示例详解

《SpringStateMachine实现状态机使用示例详解》本文介绍SpringStateMachine实现状态机的步骤,包括依赖导入、枚举定义、状态转移规则配置、上下文管理及服务调用示例,重点解... 目录什么是状态机使用示例什么是状态机状态机是计算机科学中的​​核心建模工具​​,用于描述对象在其生命

Spring Boot 结合 WxJava 实现文章上传微信公众号草稿箱与群发

《SpringBoot结合WxJava实现文章上传微信公众号草稿箱与群发》本文将详细介绍如何使用SpringBoot框架结合WxJava开发工具包,实现文章上传到微信公众号草稿箱以及群发功能,... 目录一、项目环境准备1.1 开发环境1.2 微信公众号准备二、Spring Boot 项目搭建2.1 创建

Java中Integer128陷阱

《Java中Integer128陷阱》本文主要介绍了Java中Integer与int的区别及装箱拆箱机制,重点指出-128至127范围内的Integer值会复用缓存对象,导致==比较结果为true,下... 目录一、Integer和int的联系1.1 Integer和int的区别1.2 Integer和in

SpringSecurity整合redission序列化问题小结(最新整理)

《SpringSecurity整合redission序列化问题小结(最新整理)》文章详解SpringSecurity整合Redisson时的序列化问题,指出需排除官方Jackson依赖,通过自定义反序... 目录1. 前言2. Redission配置2.1 RedissonProperties2.2 Red

IntelliJ IDEA2025创建SpringBoot项目的实现步骤

《IntelliJIDEA2025创建SpringBoot项目的实现步骤》本文主要介绍了IntelliJIDEA2025创建SpringBoot项目的实现步骤,文中通过示例代码介绍的非常详细,对大家... 目录一、创建 Spring Boot 项目1. 新建项目2. 基础配置3. 选择依赖4. 生成项目5.

JSONArray在Java中的应用操作实例

《JSONArray在Java中的应用操作实例》JSONArray是org.json库用于处理JSON数组的类,可将Java对象(Map/List)转换为JSON格式,提供增删改查等操作,适用于前后端... 目录1. jsONArray定义与功能1.1 JSONArray概念阐释1.1.1 什么是JSONA

Java JDK1.8 安装和环境配置教程详解

《JavaJDK1.8安装和环境配置教程详解》文章简要介绍了JDK1.8的安装流程,包括官网下载对应系统版本、安装时选择非系统盘路径、配置JAVA_HOME、CLASSPATH和Path环境变量,... 目录1.下载JDK2.安装JDK3.配置环境变量4.检验JDK官网下载地址:Java Downloads

Spring boot整合dubbo+zookeeper的详细过程

《Springboot整合dubbo+zookeeper的详细过程》本文讲解SpringBoot整合Dubbo与Zookeeper实现API、Provider、Consumer模式,包含依赖配置、... 目录Spring boot整合dubbo+zookeeper1.创建父工程2.父工程引入依赖3.创建ap