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计算出每个元素所在的位置,以节省空间。

 

上一篇:6. Z 字形变换


下一篇:每日算法-杨辉三角