Leetcode: ZigZag Conversion
Leetcode: ZigZag Conversion
最近在改论文，不喜欢写论文，但是为了毕业也没有办法！尽自己最大的努力做到最好吧！
这道题目做完貌似所有的Easy级别的题目就做完了，开始Medium的题目！加油吧！
题目：
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return"PAHNAPLSIIGYIR".
思路分析：
我们先来探索N字型排列以后下标的规律(为了方便规律探索，我们这里下标从1开始，行数从1开始，程序中从0开始)：
nRows = 2时，
1 | 4 |
|---|---|
2 | 3 |
nRows = 3时，
1 | 5 | |
|---|---|---|
2 | 4 | 6 |
3 | 7 |
nRows = 4时，
1 | 7 | ||
|---|---|---|---|
2 | 6 | 8 | |
3 | 5 | 9 | |
4 | 10 |
nRows = 5时，
1 | 9 | |||
|---|---|---|---|---|
2 | 8 | 10 | ||
3 | 7 | 11 | ||
4 | 6 | 12 | ||
5 | 13 |
有没有发现什么规律?
每i行的第一个下标是i
没一个N型中间都会包含一个数（第一行和最后一行除外），我们可以看做是第一个数+一个间距，得到第二个数；第二个数+一个间距，得到第三个数。第一行和最后一行也符合这个规律，只不过可以看做两个间距中的一个间距是0.
下面看看这两个间距的规律：
我总结出的是：
第一个间距是2 * （nRows - i），
第二个间距是2 * （i- 1）
看看是不是？
拿nRows=5看：
第一行1+2*(5-1)=9
第二行2+2*（5-2）=8，8+2*（2-1）=10，
第三行3+2*（5-3）=7，7+2*（3-1）=11，
第四行4+2*（5-4）=6，6+2*（4-1）=12
最后一行5+2*（5-1）=13
OK，分析出了这个规律，下面开始写程序。
C++参考代码：
class Solution
{
public:
string convert(string s, int nRows)
{
int length = s.length();
if (length <= 1 || nRows <= 1 || nRows >= length) return s;
string result = "";
//current记录当前元素下标，next记录当前元素到下一个元素下标的间距，nnext记录current到下下一个元素下标的间距
int current, next, nnext;
//一行一行的循环计算
for (int i = 0; i < nRows; i++)
{
result += s[i];//第i列的第一个元素
current = i;//记录下标
while (true)
{
next = 2 * (nRows - i - 1);//计算到下一个元素下标之间的距离2*（nRow-1）
nnext = 2 * i;//计算到下下一个元素下标之间的额距离2*(i-1)
if (next != 0)
{
current += next;
if (current < length) result += s[current];
else break;
}
if (nnext != 0)
{
current += nnext;
if (current < length) result += s[current];
else break;
}
}
}
return result;
}
};C#参考代码：
public class Solution
{
public string Convert(String s, int nRows)
{
if (s.Length <= 1 || nRows <= 1 || s.Length <= nRows) return s;
String result = String.Empty;
int current, next, nnext;
for (int i = 0; i < nRows; i++)
{
current = i;
result += s[current ];
while (true)
{
next = 2 * (nRows - i - 1);
nnext = 2 * i;
if (next != 0)
{
current += next;
if (current < s.Length) result += s[current];
else break;
}
if (nnext != 0)
{
current += nnext;
if (current < s.Length) result += s[current];
else break;
}
}
}
return result;
}
}Python参考代码：
class Solution:
# @return a string
def convert(self, s, nRows):
length = len(s)
if length <= 1 or nRows <= 1 or nRows >= length:
return s
result = ""
for i in range(nRows):
current = i
result = result + s[current]
while True:
next = 2 * (nRows - i -1)
nnext = 2 * i
if next > 0:
current = current + next
if current < length:
result = result + s[current]
else:
break
if nnext > 0:
current = current + nnext
if current < length:
result = result + s[current]
else:
break
return result