【leetcode】6. 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 s, int numRows);

思路：

实际上蕴含着一些规律。把所有answer矩阵中元素的(r,c)坐标（r是行号，c是列号）与对应原字符串s中的位置index（index从0开始）都列出来，你就会发现一个规律：index=r+2*c。是不是很神奇！哈哈哈！

具体分析如下：

注：n就是题目中的numRows。

例如，n为4，字符串s长度为15（具体内容不重要）。其(r,c)与index映射关系如下：

矩阵中的位置(r,c)	原数组中的位置index
(0,0)
(0,3)	6
(0,6)	12
(1,0)	1
(1,2)	5
(1,3)	7
(1,5)	11
(1,6)	13
(2,0)	2
(2,1)	4
(2,3)	8
(2,4)	10
(2,6)	14
(3,0)	3
(3,3)	9

我们可以发现一个规律：index=r+2*c。这样我们就可以知道answer矩阵中每个位置应该输出的元素是什么。

=========================================================================

接下来就要分析矩阵元素的分布规律了。通过画个图就能发现其中的规律。例如，n为7，字符串s长度为31时，分析如下：

规律已经很明显了 。按照图上规律，按行遍历矩阵中所有元素的坐标（不存在就不要遍历），然后将(r,c)转化成index，然后输出元素即可。

代码实现如下，时间复杂度应该为   O ( n ) \ O(n)  O(n)：

class Solution {
public:
    string convert(string s, int numRows) {
        if (s.length() == 0 || numRows <= 1){
            return s;
        }
        
        int r = 0, c = 0;
        int n = numRows;
        string ans;
        
        while (ans.length() < s.length() && r < n){
            c = 0;
            int swh = 1;
            int step1 = n - 1 - r;
            int step2 = n - 1 - step1;
            
            if (step1 == 0 || step2 == 0){
                while (r+2*c < s.length()){
                    ans.append(1,s[r+2*c]);
                    c += n-1;
                }
            }else {
                while (r+2*c < s.length()){
                    ans.append(1,s[r+2*c]);
                    if (swh){
                        c += step1;
                        swh = 1 - swh;
                    }else{
                        c += step2;
                        swh = 1 - swh;
                    }
                }
            }
            ++r;
        }
        
        return ans;
    }
};
           

discuss，比我的思路简介，似乎我想复杂了。直接看代码注释：

class Solution {
public:
    string convert(string s, int numRows) {
        vector<string> vs(numRows, ""); // Z字型矩阵
        int i = 0;
        
        while (i < s.length()){
            for (int j = 0; j < numRows && i < s.length(); j++){ //从上到下遍历（包含首行和尾行）
                vs[j].push_back(s[i++]);
            }
            for (int j = numRows - 2; j >= 1 && i < s.length(); --j){ // 从下到上遍历（不包含首行和尾行）
                vs[j].push_back(s[i++]);
            } 
        }
        
        string zigzag;
        for (string &v : vs){ // 最后将vs中每个字符串拼接起来即可
            zigzag += v;
        }
        
        return zigzag;
    }
};