leecode6:Z字形变换

1.题目描述

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

2.示例

示例1：输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

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

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

示例2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：

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

3.分析

（1）此题难度不大，看似题目描述复杂，结构变换，实则找规律即可。

（2）将Z字形的上面和中间的连接作为一个周期处理，分别处理头部和中间的连接部分。设置一个二维数组/vector保存改变顺序后每行的字符集合。

4.代码

class Solution {
public:
    string convert(string s, int numRows) {

        vector<vector<char>> *total = new vector<vector<char>>();//存储改变顺序后的总字符集合
        for(int i=0;i<numRows;i++){//初始化numRows行字符集合
            vector<char> *temp = new vector<char>();
            total->push_back(*temp);
        }

        int pos =0;
        while(pos<s.length()){//按Z规律重排字符集合  O(s.length())
            for(int i=0;i<numRows;i++){//处理Z的头
                (total->at(i)).push_back(s.at(pos));
                pos++;
                if(pos>=s.length()) goto A;
            }
            for(int i=numRows-2;i>0;i--){//处理Z的连接处
                (total->at(i)).push_back(s.at(pos));
                pos++;
                if(pos>=s.length()) goto A;
            }
        }
        A:string *result = new string();
        for(int i=0;i<numRows;i++){
            for(int j=0;j<(total->at(i)).size();j++){
               *result+=(total->at(i)).at(j);

            }
        }
        return *result;
    }
};

5.总结

（1）算法时间效率合格，仅需遍历字符串的全部元素即可。

（2）编写时注意中间连接部分的顺序是从后往前排，也要注意处理头部和中间连接部分的一个周期尚未结束时，元素的字符串已经遍历结束，这时注意要跳出循环避免越界。

（3）该算法的空间效率不好，原因在于没有对元素改变位置后的位置没有计算。采用了暴力的设numRows个vector的方式。

（4）改进算法的话，即直接计算每个元素改变后的位置。根据周期循环的次数，和numRows计算出每个元素所在的位置，以节省空间。