[LeetCode 题解]: ZigZag Conversion

前言

【LeetCode 题解】系列传送门： http://www.cnblogs.com/double-win/category/573499.html

1.题目描述

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

2. 相关题目

ZigZag again:

在本人之前的博客中，曾列出过另一个ZigZag数组的例子http://www.cnblogs.com/double-win/p/3641657.html

与上一篇不同的是,本题对于ZigZag的规则则有所不同。

图一

图二

3. 思路

如果我们将数组分成矩形框中的部分，那么可以看到有如下的规律：

（1）在矩形框图一中的子结构中，设行号为i （i=1~nRows）每次都是行号先增加，后减小：在矩形框中的数据的个数为：A = 2*(nRows-1).

1) 若用 string temp[nRows]来存储每一行的数据

2) 子结构可以分成两个部分，一个是行号从1~nRows, 另一个是行号从nRow-1~2

（2）矩形框之外的结构的数据个数B为： s.size()% A.

1) 若 B<nRows，那么多出来的字符只能依次填多出来的一列；如图二中的 NG

2) 若 B >nRows, 那么必然可以将某一列都填满，多出来的数据有B-=nRows, 行号的变化范围为 nRow-1 : nRow-B

4. 解法

 1 class Solution {
 2 public:
 3     string convert(string s,int nRows)
 4     {
 5            if(nRows==1) return s;
 6            int i=0,j=0,Count=0;
 7            string a[nRows],b;
 8            for(i=0;i<nRows;i++)
 9               a[i].clear();
10            b.clear();
11            int time = s.size()/2/(nRows-1);  //完整子结构出现的次数
12            int remain = s.size()%(2*(nRows-1)); // 剩余不足一个子结构的数据长度
13 
14            while(time--)
15            {
16               for(i=0;i<nRows;i++)
17                  a[i]+=s[Count++];
18               for(i=nRows-2;i>=1;i--)
19                  a[i]+=s[Count++];
20             }
21 
22             if(remain<=nRows)  // 剩余的数据不足nRows
23             {
24                for(i=0;i<remain;i++)
25                  a[i]+=s[Count++];
26             }
27             else                        //剩余的数据在nRows~ 2*(nRow-1)-1 之间
28             {
29                 for(i=0;i<nRows;i++)
30                   a[i]+=s[Count++];
31                 remain-=nRows;
32                 i=nRows-2;
33                 for(j=0;j<remain;j++)
34                    a[i--] += s[Count++];
35             }
36             for(i=0;i<nRows;i++)
37                b+=a[i];
38             return b;
39     }
40 };

作者：Double_Win

出处: http://www.cnblogs.com/double-win/p/3687749.html

声明：由于本人水平有限，文章在表述和代码方面如有不妥之处，欢迎批评指正~