HelloKenLee

Leetcode 6. ZigZag Conversion 解题报告

Posted on By KenLee

题目信息

题目: 6. ZigZag Conversion
难度: Medium
正确率: 26.63%
问题描述:

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”.

问题分析

  该问题的意思是,给出一个字符串,要求把他转换成zigzag样式。

解题思路

  主要难点在于理解Zigzag样式,其要求应该如下:

/*n=numRows
Δ=2n-2    1                           2n-1                         4n-3
Δ=        2                     2n-2  2n                    4n-4   4n-2
Δ=        3               2n-3        2n+1              4n-5       .
Δ=        .           .               .               .            .
Δ=        .       n+2                 .           3n               .
Δ=        n-1 n+1                     3n-3    3n-1                 5n-5
Δ=2n-2    n                           3n-2                         5n-4
*/

  根据上面的规律处理字符串即可。

结果分析

  • 时间复杂度: $ O(N) $。
  • 空间复杂度: $ O(N) $。
  • 通过时间: 16 ms
  • 击败: 94.44%

源代码

class Solution {
public:
    string convert(string s, int numRows) {
        string result="";
        if(numRows==1)
			return s;
        int step1,step2;
        int len=s.size();
        for(int i=0;i<numRows;++i){
            step1=(numRows-i-1)*2;
            step2=(i)*2;
            int pos=i;
            if(pos<len)
                result+=s.at(pos);
            while(1){
                pos+=step1;
                if(pos>=len)
                    break;
				if(step1)
					result+=s.at(pos);
                pos+=step2;
                if(pos>=len)
                    break;
				if(step2)
					result+=s.at(pos);
            }
        }
        return result;
    }
};