[LeetCode] ZigZag Conversion
ZigZag Conversion
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".
解题思路：
1、一般这种矩形的变换，直接想到的办法是按照它的规则模拟一遍即可。下面是相关代码，其时间复杂度和空间复杂度均为O(n*nRows)
class Solution {
public:
string convert(string s, int nRows) {
if(nRows<2){
return s;
}
int len=s.length();
char matrix[nRows][len];
for(int i=0; i
2、看来我发现规律的能力有些欠缺。其实每一竖一提的字符个数为2*nRows-2，其中-2是第一层和最后一层只有一个元素。对于非第一行和非最后一行，元素在s中的下标为j+2*nRows-2-2*i，其中i是当前行，j是当前列。下面是代码。时间复杂度为O(n*nRows)，空间复杂度为O(1)。
class Solution {
public:
string convert(string s, int nRows) {
if(nRows<2){
return s;
}
int len=s.length();
int step = 2*nRows-2;
string result="";
for(int i=0; i
二次刷题（2015-07-28）：
n行，主列相邻的两个下标相距2*（numRows - 1）。除了第0行和第n-1行，每两个主列之间有且仅有一个元素，该元素的下标为前一个主列下标+2*（n- i - 1）。
比如：
0 6 12
1 5 7 11 13
2 4 8 10
3 9
共有4行，0到6下标相距2*(4-1)=6,1到7下标相距2*(4-1)=6,等等。1到5下标相距2*(4-1-1)=4，2到4下标相距2*(4-2-1)=2,等等。
知道这个规律，我们就能很容易得到下面的代码：
class Solution {
public:
string convert(string s, int numRows) {
if(numRows<=1){
return s;
}
int len = s.length();
string result = "";
for(int i=0; i
转载请注明： » [LeetCode] ZigZag Conversion
<!--
-->
原文作者：；如有侵权，请联系管理员删除。
