Leetcode(6) - Z字形变换 -java版 - 全解
2019-07-30 本文已影响0人
nailiang97
Leetcode(6) - Z字形变换 -java版 - 全解
题目
难度: 中等
将一个给定字符串根据给定的行数,以从上往下、从左到右进行 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
一.按行排序
具体思路:
此方法与定义最为贴切,也最为巧妙.
通过从左向右迭代字符串,我们可以轻松地确定字符位于 Z 字形图案中的哪一行。
我们可以使用Math.min(numRows,s.length()个列表来表示 Z 字形图案中的非空行。
从左到右迭代 s,将每个字符添加到合适的行。可以使用当前行和当前方向这两个变量对合适的行进行跟踪。
只有当我们向上移动到最上面的行或向下移动到最下面的行时,当前方向才会发生改变。
实现:
class Solution {
public String convert(String s, int numRows) {
if(numRows == 1) return s;
// 定义一个存储每一行字符串的集合
List<StringBuilder> rowList = new ArrayList<>();
// 将集合中Z形图案的非空行赋初值
for(int i=1;i<=Math.min(numRows,s.length());i++)
rowList.add(new StringBuilder());
boolean goingDown = false;// 上下移动的标记变量
int curRow = 0;// 当前行
for(char c: s.toCharArray()){// 迭代s,将每个字符添加到合适的行
rowList.get(curRow).append(c);
if(curRow == 0 || curRow == numRows-1) goingDown = !goingDown;
curRow += goingDown ?1:-1;
}
StringBuilder ans = new StringBuilder();
for(StringBuilder row : rowList)// 拼接每一行
ans.append(row);
return ans.toString();
}
}
二.按行访问
具体思路:
按照与逐行读取 Z 字形图案相同的顺序访问字符串。
关键是找到numRows,当前行,插入的是当前行的第几个数,字符串的对应索引这四者之间的关系.
实现:
class Solution {
public String convert(String s, int numRows) {
if(numRows ==1) return s;
StringBuilder ans = new StringBuilder();
// cycleLen为第一行相邻的两个元素在原字符串中的对应索引的差值
int n =s.length(),cycleLen = 2*numRows-2;
for(int i =0;i<numRows; i++){// 逐行插入数据
for(int j =0; j+i<n;j+=cycleLen){//以cycleLen为间隔插入数据
ans.append(s.charAt(i+j));
if(i!=0&&i!=numRows-1&&j-i+cycleLen <n){//对于不是第一行或是最后一行的元素,单独考虑
ans.append(s.charAt(j-i+cycleLen))// 注意这里的对应关系
}
}
}
return ans.toString();
}
}