【数据结构与算法】之深入解析“Z字形变换”的求解思路和算法示例
【摘要】
一、题目要求
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：
P A...
一、题目要求
- 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
- 比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
- 1
- 2
- 3
- 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。
- 请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
- 1
- 示例 1：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
- 1
- 2
- 示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P I N
A L S I G
Y A H R
P I
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 示例 3：
输入：s = "A", numRows = 1
输出："A"
- 1
- 2
- 提示：
-
- 1 <= s.length <= 1000；
-
- s 由英文字母（小写和大写）、’,’ 和 ‘.’ 组成；
-
- 1 <= numRows <= 1000。
二、求解算法
① 按行寻找规律
- 这个 Z 字型其实是这样的：
- 对于前面的 3 行的 示例1，它的字符数分布是这样的：
- 对于前面的 4 行的 示例2，它的字符数分布是这样的：
- 那么对于 n 行的字符数分布是这样的：
- 可以发现：
-
- 当前行 curRow 为 0 或 n-1 时，箭头发生反向转折
-
-
- 从左到右按箭头方向迭代 s ，将每个字符添加到合适的行，之后从上到下遍历行即可。
-
-
-
- 假定 n=numRows，C++ 示例如下：
-
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s;
vector<string> rows(min(numRows, int(s.size()))); // 防止s的长度小于行数
int curRow = 0;
bool goingDown = false;
for (char c : s) {
rows[curRow] += c;
if (curRow == 0 || curRow == numRows - 1) {// 当前行curRow为0或numRows -1时，箭头发生反向转折
goingDown = !goingDown;
}
curRow += goingDown ? 1 : -1;
}
string ret;
for (string row : rows) {// 从上到下遍历行
ret += row;
}
return ret;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
-
-
- 比如对于 s = “LEETCODEISHIRING” ，得到的四行就是：
-
-
- 每一行字母的所有下标其实是有规则的
-
-
- 先假定有 numRows=4 行来推导下，其中 2numRows-2 = 6 , 我们可以假定为 step=2numRows-2 ，先来推导下规则：
-
-
-
-
- 第 0 行： 0 - 6 - 12 - 18：==> 下标间距 6 - 6 - 6 ==> 下标间距 step - step - step
-
-
-
-
-
- 第 1 行： 1 - 5 - 7 - 11 - 13：==> 下标间距 4 - 2 - 4 - 2 ==> 下标间距step-21(行)-21(行)-step-21(行)-21(行)
-
-
-
-
-
- 第 2 行： 2 - 4 - 8 - 10 - 14：==> 下标间距 2 - 4 - 2 - 4 ==> 下标间距step-22(行)-22(行)-step-22(行)-22(行)
-
-
-
-
-
- 第 3 行：3 - 9 - 15 - 21：==> 下标间距间距 6 - 6 - 6 ==>下标间距step - step - step
-
-
-
-
- 可以得出以下结论：
-
-
-
-
- 起始下标都是行号；
-
-
-
-
-
- 第 0 层和第 numRows-1 层的下标间距总是 step；
-
-
-
-
-
- 中间层的下标间距总是 step-2行数，2行数交替；
-
-
-
-
-
- 下标不能超过 len(s)-1。
-
-
-
-
- C++ 示例：
-
string convert(string s, int numRows) {
if (numRows == 1) return s;
int step = numRows * 2 - 2; // 间距
int index = 0;// 记录s的下标
int len = s.length();
int add = 0; // 真实的间距
string ret;
for (int i = 0; i < numRows; i++) // i表示行号
{
index = i;
add = i * 2;
while (index < len)//超出字符串长度计算下一层
{
ret += s[index]; // 当前行的第一个字母
add = step - add;// 第一次间距是step -2*i，第二次是2*i,
index += (i == 0 || i == numRows-1) ? step : add; // 0行和最后一行使用step间距，其余使用add间距
}
}
return ret;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
② 按行排序（LeetCode 官方解法）
- 通过从左向右迭代字符串，可以轻松地确定字符位于 Z 字形图案中的哪一行。
- 我们可以使用 min(numRows,len(s)) 个列表来表示 Z 字形图案中的非空行。
- 从左到右迭代 s，将每个字符添加到合适的行。可以使用当前行和当前方向这两个变量对合适的行进行跟踪。
- 只有当我们向上移动到最上面的行或向下移动到最下面的行时，当前方向才会发生改变。
- C++ 示例：
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s;
vector<string> rows(min(numRows, int(s.size())));
int curRow = 0;
bool goingDown = false;
for (char c : s) {
rows[curRow] += c;
if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
curRow += goingDown ? 1 : -1;
}
string ret;
for (string row : rows) ret += row;
return ret;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- Java 示例：
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) return s;
List<StringBuilder> rows = new ArrayList<>();
for (int i = 0; i < Math.min(numRows, s.length()); i++)
rows.add(new StringBuilder());
int curRow = 0;
boolean goingDown = false;
for (char c : s.toCharArray()) {
rows.get(curRow).append(c);
if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
curRow += goingDown ? 1 : -1;
}
StringBuilder ret = new StringBuilder();
for (StringBuilder row : rows) ret.append(row);
return ret.toString();
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 复杂度分析：
-
- 时间复杂度：O(n)，其中 n==len(s)；
-
- 空间复杂度：O(n)。
③ 按行访问（LeetCode 官方解法）
- 按照与逐行读取 Z 字形图案相同的顺序访问字符串。
- 首先访问 行 0 中的所有字符，接着访问 行 1，然后 行 2，依此类推…
- 对于所有整数 k：
-
- 行 0 中的字符位于索引 k(2⋅numRows−2) 处；
-
- 行 numRows−1 中的字符位于索引 k(2⋅numRows−2)+numRows−1 处；
-
- 内部的行 i 中的字符位于索引 k(2⋅numRows−2)+i 以及 (k+1)(2⋅numRows−2)−I 处；
- C++ 示例：
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s;
string ret;
int n = s.size();
int cycleLen = 2 * numRows - 2;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < n; j += cycleLen) {
ret += s[j + i];
if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
ret += s[j + cycleLen - i];
}
}
return ret;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- Java 示例：
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) return s;
StringBuilder ret = new StringBuilder();
int n = s.length();
int cycleLen = 2 * numRows - 2;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < n; j += cycleLen) {
ret.append(s.charAt(j + i));
if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
ret.append(s.charAt(j + cycleLen - i));
}
}
return ret.toString();
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 复杂度分析：
-
- 时间复杂度：O(n)，其中 n==len(s)。每个索引被访问一次。
-
- 空间复杂度：O(n)，对于 C++ 实现，如果返回字符串不被视为额外空间，则复杂度为 O(1)。
文章来源: blog.csdn.net，作者：Serendipity·y，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/Forever_wj/article/details/122473690
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）