[leetcode] ZigZag Conversion


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 text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

tag: string

9/24/2015 update

Another approach, view the zigzag graph as separated groups.

0-5 belongs to group 1, 6-11 belongs to group 2, etc…

0    6      12
1  5 7   11 13
2 4  8 10   14
3    9      15
*--* *----* *---
(1)    (2)    (3)---

assume there are n rows, gap between the same location element in adjacent groups is 2 * (n – 1)

 

 

class Solution {
public:
    string convert(string s, int numRows) {
        string ans;
        if(numRows == 0) return "";
        if(numRows == 1) return s;
        int gap = 2 * (numRows - 1);
        for(int i = 0; i < numRows; i++){
            if(i == 0){
                //first line
                int j = 0;
                while(j < s.size()){
                   ans.push_back(s[j]);
                   j += gap;
                }
            }
            else if(i == numRows - 1){
                //last line
                int j = i;
                while(j < s.size()){
                    ans.push_back(s[j]);
                    j += gap;
                }
            }
            else{
                //in the middle lines
                int j1 = i;
                int j2 = 2 * (numRows - 1) - j1;
                while(j2 < s.size()){
                    ans.push_back(s[j1]);
                    ans.push_back(s[j2]);
                    j1 += gap;
                    j2 += gap;
                }
                if(j1 < s.size()){
                    ans.push_back(s[j1]);
                }
            }
        }
        return ans;
    }
};

 

觉得是个数学题。我的思路是按zigzag图形的每行进行扫描,找规律计算出每个点对应的string的索引值,将该字符压入re中。

网上的关于zigzag的解释不多,大都是讲另一个zigzag螺旋矩阵。本题指的是并列排列的N字形矩阵。

他有点像: | / | / | / | / |

我们取每个N的左边一竖和中间的斜线作为循环单位“| /”,利用offset进行单位间的偏移。

需要注意的是,我们要把nRow=1的情况单独考虑,否则会导致offset为0,死循环,而内存超界。

class Solution {
public:
    string convert(string s, int nRows) {
        string re;
        if(nRows == 1){
            return s;
        }
        for(int i = 0; i < nRows; i++){//for each row
            int offset = 0;//for each unit
            while(true){
                int index = offset + i;
                if(index >= s.size()){
                    break;
                }
                re.push_back(s[index]);
                if(i == 0 || i == nRows - 1){
                    offset += (nRows - 1) * 2;
                    continue;
                }
                index = offset + i + (nRows - i - 1) * 2;
                if(index >= s.size()){
                    break;
                }
                re.push_back(s[index]);
                offset += (nRows - 1) * 2;
            }
        }
        return re;
    }
};

Selection_012

 

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.