文章目录
- 题目
- 解
- ① 找规律
题目
将一个给定字符串 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){
//保证数组不越界,并且没使用过就加入到str
use[j-i]=1;
str.append(s.charAt(j-i));
}
if(j+i<len && use[j+i]!=1){
//保证数组不越界,并且没使用过就加入到str
use[j+i]=1;
str.append(s.charAt(j+i));
}
}
}
return str.toString();//转换成字符串返回
}
}