6. ZigZag Conversion

Medium

9022823FavoriteShare

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);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

先记录一下悲剧的代码（下面是没有AC的）：

class Solution {
public:
    string convert(string s, int numRows) {
        //思路1是一列为一个vector，然后往右填数字，然后把空的填“ ”，最后转置数组输出
        //思路2是按照打印顺序一排一排找数字，先确定第一排（顶点数字，再往下找），悲剧从这里开始
        //提交时输入“” 1报错，需要加入特殊情况
        //提交时输入"A" 1报错……
        //提交时输入"AB" 1报错……
        //提交时输入"ABCD" 3报错……感觉要重写了，算法覆盖不了这种情况

        if(s.length()==0)return "";
        if(s.length()<=numRows)return s;
        if(numRows==1)return s;
        string ans="";
        //先算有几个顶点
        int p=numRows*2-2;
        int nd=(s.length()-1)/p;
        //打印顶点进ans
        ans+=s[0];
        int dnums=1;//顶点的数量
            for(int i=1;i<nd+1;i++)
            {
                ans+=s[p*i];
                dnums++;
            }
        //打印顶点以下的层
        
        for(int i=1;i<numRows-1;i++)//打印的层数
        {
            //每层打印的内容
            ans+=s[i];//先打印第一列
            for(int j=1;j<dnums;j++)//打印后面需要重复的列数
            {
                //int e=p-i;
                //int f=p+i;
                ans+=s[p*j-i];
                if((p*j+i)>=s.length()){}
                else ans+=s[p*j+i];
            } 
            
        }
        //打印最后一层
        //计算有几个顶点
        ans+=s[numRows-1];//先写入第一个顶点
        int q=(s.length()-numRows)/p;
        for(int i=0;i<q;i++)
        {
            ans+=s[(numRows-1)+p*(i+1)];
        }
        return ans;
    }
};

重写后的代码如下。要提一下复制代码容易出现这种错误：error: stray '\302' in program，这个是因为在复制过程中格式变了，只需要重抄一遍代码就ok了。

另外需要注意的是string二维数组的定义方式和赋值方式，如下定义在赋值时如果使用anss[x][y]会读不到x,y，赋值失败，最后运行出来是空的""，然后leetcode中不会有语法报错，但是输出一直为空，放到VS里调试就能看到这个问题了。

class Solution {
public:
    string convert(string s, int numRows) {
        //思路：先确定有几行，每行做一个string，最后再加起来
        if (s.length() == 0)return "";
        if (s.length() <= numRows)return s;
        if (numRows == 1)return s;
        vector<string> anss;
        anss.clear();
        for (int i = 0; i < numRows; i++)
        {
            anss.push_back("");
        }

        int r = 0;
        //int c = 0;
        bool direction = false;//false向下，true向上
        for (int i = 0; i < s.length(); i++)
        {
            if (!direction)
            {
                anss.at(r) += s[i];
                //anss[r][c] += s[i];
                r++;
                if (r == numRows)
                {
                    direction = true;
                    r = r - 2;
                    //c++;
                }
            }
            else
            {
                anss.at(r) += s[i];
                //anss[r][c] += s[i];
                //c++;
                r--;
                if (r == -1)
                {
                    direction = false;
                    r = r + 2;
                    //c--;
                }
            }

        }

        string ans = "";
        for (int i = 0; i < numRows; i++)
        {
            ans += anss[i];
        }
        return ans;
    }
};