6-Z字形变换
@Author：CSU张扬
@Email：csuzhangyang@gmail.com or csuzhangyang@qq.com
1. 题目
将一个给定字符串根据给定的行数，以从上往下、从左到右进行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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zigzag-conversion
2. 解法
2.1 解法一
按每行从左到右依次输出。
以示例2为例，
L D R
E O E I I
E C I H N
T S G
对应的下标如下：
0 6 12
1 5 7 11 13
2 4 8 10 14
3 9 15
我们的任务是找出每一行的下标。
- 对于第一行和最后一行来说，它只有3个数，而其他行是它的二倍，有6个数。
- 我们以下标0-5为第一组，6-11为第二组，以此类推，每6个数一组，不足6个数的也算作一组。
- 6是怎么求的呢？
k = 2 * (numRows - 1) = 2*(4-1) = 6 - 一共有多少组呢？
loopNum = (n + k - 1) / k;(n为s的长度)，注意：不足k个的也算作一组。 - 对于第一行和最后一行来说，初值为i（
start1 = i），我们只需要每次循环加上k即可。 - 对于其他行，我们每组有两个数。前一个数和步骤5中一样，初值为i（
start1 = i）；第二个数的初值是关键，start2 = start1 + (numRows-(i+1))*2；每次循环都加上k即可，循环总次数为numRows。
执行用时 :8 ms, 在所有 cpp 提交中击败了97.82%的用户
内存消耗 :10.3 MB, 在所有 cpp 提交中击败了88.53%的用户
class Solution {
public:
string convert(string s, int numRows) {
int n = s.size();
if (numRows == 1)
return s;
int k = 2 * (numRows - 1);
string str = "";
int loopNum = (n + k - 1) / k;
for (auto i = 0; i < numRows; ++ i) {
int start1 = i;
int start2 = 0;
if (i != 0 && i != (numRows -1))
start2 = start1 + (numRows-(i+1))*2;
for (auto j = 0; j < loopNum; ++ j) {
if (start1 < n) {
str += s[start1];
start1 += k;
}
if (i != 0 && i != (numRows -1)) {
if (start2 < n) {
str += s[start2];
start2 += k;
}
}
if (start1 >= n && start2 >= n)
break;
}
}
return str;
}
};
2.2 解法二
参考：麓山南路飞行员
主要思想就是：一共有numRows行，找出每个字符所在的行数，依次添加到该行。
关键代码int row = i % k < numRows ? i % k : k - i % k;
以示例2为例，
L D R
E O E I I
E C I H N
T S G
对应的下标如下： 行数：
0 6 12 0
1 5 7 11 13 1
2 4 8 10 14 2
3 9 15 3
易知k = 6, numsRows = 4，我们以下标0-5为例。第一种情况是下标0-3，第二种情况是下标4-5，这两种情况区分的标志是i % k < numRows。
很容易知道第一种情况的行数为i % k；第二种情况，对于5来说，row = 1 = 6 - 5；对于11来说，row = 1 = 6 - 11...，11怎么才能变成5呢，当然是对6取余啦。所以第二种情况行数为k - i % k。
执行用时 :20 ms, 在所有 cpp 提交中击败了58.47%的用户
内存消耗 :12.7 MB, 在所有 cpp 提交中击败了78.71%的用户
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1)
return s;
int n = s.size();
int k = 2 * (numRows - 1);
string str;
vector<string> res(numRows);
for (auto i = 0; i < n; ++ i) {
int row = i % k < numRows ? i % k : k - i % k;
res[row] += s[i];
}
for (auto i : res)
str += i;
return str;
}
};