第六题：Z字形变换
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1:
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:
L D R
E O E I I
E C I H N
T S G
V1版本
最开始看到这题的时候是想弄一个二维数组，根据规律依次将字符串依次填入数组的相应位置，然后遍列输出
可越想越不对劲，因为只需要我们输出最后的变换过后的字符串，根本不需要我们打印Z字形
这下就好办了，只需要去找取字符的规
对于字符串 LEETCODEISHIRING
行数为3的时候：
L C I R
E T O E S I I G
E D H N
下标 中间间隔的步数
0 4 8 12 4 4
1 3 5 7 9 11 13 15 2 2
2 6 10 14 4 4
行数为4的时候：
L D R
E O E I I
E C I H N
T S G
下标 中间间隔的步数
0 6 12 6 6
1 5 7 11 13 4 2
2 4 8 10 14 2 4
3 9 15 6 6
行数为6的时候：
下标 中间间隔的步数
0 10 10 10
1 9 11 8 2
2 8 12 6 4
3 7 13 4 6
4 6 14 2 8
5 15 10 10
规率很好发现，第一列就是 0~numRows，
间隔的步长可以通过 numRows + numRows - 2 获取到
头和尾的步长是一样的，从第二行起，步长就等于 步长 - 2 和 2交替变化，
继续向下走 左边的步长 -= 2，右边步长 += 2
只需要考虑一下边界问题
行数为 1的时候，返回的就是原字符串
行数为 2的时候，本想单独处理的，直接输出 0，2，4，6.....1，3，5.....
代码如下
public String convert(String s, int numRows) {
// 返回本身
if (numRows == 1) {
return s;
}
// 用于记录新字串的char数组
char[] chars = new char[s.length()];
// 间隔的步长
int length = numRows + numRows - 2;
// 新字串的下标
int charIndex = 0;
// 记录应该从什么位置取老字串的值
int index = 0;
// 遍列的行数
int row = 0;
// 左右的间隔数
int intervalLeft = length, intervalRight = length;
// 单行的循环次数
int rowCycleNum = 1;
while (row < numRows) {
if (index < s.length()) {
chars[charIndex++] = s.charAt(index);
index += rowCycleNum++ % 2 == 1? intervalLeft : intervalRight;
} else {
index = ++row;
// 重置单行的循环次数
rowCycleNum = 1;
if (row == 1) {
intervalLeft = length - 2;
intervalRight = 2;
}
if (row == numRows - 1){
intervalLeft = length;
intervalRight = length;
}
if (row != 1 && row != numRows - 1){
intervalLeft -= 2;
intervalRight += 2;
}
}
}
return String.valueOf(chars);
}
image.png
时间还可以，代码还需要优化一下
V2版本
V2版本是参考官方的 ##按行排序##
简单点说就是，遍例字符串时，我能知道每个字符所在的行
我先遍例一次，按顺序将字符分别添加至行，最终在将几个行组合起来成为最终的行
例：
L C I R
E T O E S I I G
E D H N
随着字符串的例，行号的变化为 0 1 2 1 0 1 2
0 0 0
1 1 1 1 1
2 2 2
代码如下
public String convert(String s, int numRows) {
// 返回本身
if (numRows == 1) {
return s;
}
List<StringBuffer> list = new ArrayList<>();
for (int i = 0; i < Math.min(numRows, s.length()); i++) {
list.add(new StringBuffer());
}
// 记录当前行
int cruRow = 0;
boolean isAdd = false;
for (int i = 0; i < s.length(); i++) {
list.get(cruRow).append(s.charAt(i));
// 第次遇到两端就取反
if (cruRow == 0 || cruRow == numRows -1) {
isAdd = !isAdd;
}
cruRow += isAdd? 1 : -1;
}
// 遍历填充完后，逐行整合在一起返回
StringBuffer sb = new StringBuffer(s.length());
for (StringBuffer stringBuffer : list) {
sb.append(stringBuffer);
}
return sb.toString();
}
image.png
不过这种用list保存数据的方式本来就是空间利用不高，执行效率也不是特别的高，算是多了解一种思路吧
V3版本
V3版本参数参考官方的 ##按行访问## 不过官方的是用StringBuilder，我觉得用数组会更好
以4行为例
首先只看整体部分，步长为6
L D R
E O E I I
E C I H N
T S G
下标 步长
0 6 12 6
1 7 13 6
2 8 14 6
3 9 15 6
在看完整的
0 6 12
1 5 7 11 13
2 4 8 10 14
3 9 15
其实只有在非首尾行时，每两个数中间会多夹带一个数，用这个数的步长也是有规律的
按照这种思想自己在实现一下
public String convert(String s, int numRows) {
// 返回本身
if (numRows == 1) {
return s;
}
int strLength = s.length();
// 依旧使用数组保存最终结果
char[] chars = new char[strLength];
int charIndex = 0;
// 步长
int length = numRows + numRows - 2;
// 第一个循环循环行
for (int i = 0; i < numRows; i++) {
// 第二个循环获限当前行的字符
for (int j = 0; i + j < strLength; j += length) {
// 这里获取的是上面整体部分的值
chars[charIndex++] = s.charAt(i + j);
// 首行和尾行没有多余的字符,超过字符长度也过滤
if (i == 0 || i == numRows - 1 || j + length - i >= strLength) {
continue;
}
/**
* 例：像上面所说行数为4时，j总是在 0 6 12中进行变化
* 而中间的值总是相对于在 1 6 12的基础上， -1 -2的值
*/
chars[charIndex++] = s.charAt(j + length - i);
}
}
return String.valueOf(chars);
}
image.png
网友评论