题目描述:
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 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
思路1：
找到每一行的元素在原字符串中的下标位置映射规律，一行一行的获取,每一行的元素直接计算出来。
代码：
1 class Solution {
2 public:
3 string convert(string s, int nrows)
4 {
5 if(s.length() == 0)
6 return "";
7 if(nrows <= 1)
8 return s;
9 string ret = "";
10 int len = s.length();
11 for(int i = 0; i < nrows; i++)
12 {
13 int cur = i;//初始化为这一行的第一个元素位置下标
14 if(i == 0 || i == nrows-1)
15 {
16 while(cur < len)
17 {
18 ret += s[cur];
19 //以“竖线的末端元素”为中间媒介比较对象
20 cur += 2*(nrows-1);//位移(行下标与行下标之间的位移)不变性的应用
21 }
22 }
23 else
24 {
25 int flag = 0;
26 while(cur < len)
27 {
28 ret += s[cur];
29 if(flag == 0)
30 cur += 2 * (nrows-1-i);
31 else
32 cur += 2 * i;
33 flag = 1-flag;
34 }
35 }
36 }
37
38 return ret;
39 }
40 };
思路2：
需要一个额外的辅助空间，按照题目的意思，将原字符串中的字符按照z字型写入这个辅助空间中，然后按照拼接即得出要求的字符串行数为nRows的时候 周期cycle= 2*nRows-2(一个周期有这么多个数)[0，nRows-1]向下, [nRows,cycle)向上初始化一个nRows行的vector,依次将string中的每一个元素放入，再一行一行的合并。
代码：
1 class Solution {
2 public:
3 string convert(string s, int nRows) {
4
5 if(s.length() == 0)
6 return "";
7 if(nRows <= 1)
8 return s;
9 int cycle = nRows + nRows - 2; //求出循环周期
10 vector<string> temp(nRows,"");
11 for(int i = 0; i < s.length(); i++)//流式处理，一个一个的放
12 {
13 //i这里的含义是下标，除以周期，得到的是一个周期中以0为起始下标的下标
14 //如果i的含义为以1为起始点的第几个数，除以周期，得到的是还剩几个数(从计数意义上说)
15 int index = i%cycle;
16 if(index < nRows)
17 temp[index]+=s[i];//往下走
18 else//位移不变性
19 temp[(nRows-1)-(index-(nRows-1))]+=s[i];//往上走
20 }
21
22 string ret="";
23 for(int i = 0; i < nRows; i++)
24 ret += temp[i]; //合并
25 return ret;
26 }
27 };
和上面的思路一样，但使用了不同的实现：
1 class Solution {
2 public:
3 string convert(string s, int nRows)
4 {
5
6 if(s.length() == 0)
7 return "";
8 if(nRows <= 1)
9 return s;
10 vector<string> temp(nRows,"");
11 int len=s.length();
12 int i=0;
13 while(i<len)//这里外面的循环是如果还有元素时就一个周期一个周期的添加
14 { //(上面的实现是一个元素一个元素的添加)
15 for(int j=0;j<nRows && i<len;j++)
16 temp[j]+=s[i++];
17 for(int j=nRows-2;j>0 && i<len;j--)
18 temp[j]+=s[i++];
19 }
20 string ret="";
21 for(int i=0;i < nRows;i++)
22 ret+=temp[i];
23 return ret;
24 }
25 };