LeetCode: ZigZag Conversion 解题报告

- 日理万妓 2022-03-28 15:44 205阅读 0赞

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

![231613168128190.jpg][]

SOLUTION 1:

使用以下算法会比较简单。

两个规律：

1 两个zigzag之间间距为2\*nRows-2

2 每个zigzag中间（在j和j+interval之间）位置为j+interval-2\*i

注意：当Rows = 1时，此方法不适用，因为size = 0,会造成死循环。所以Rows = 1时，需要独立处理。

引自：[http://blog.csdn.net/fightforyourdream/article/details/16881517][http_blog.csdn.net_fightforyourdream_article_details_16881517]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 public class Solution {
     2     public String convert(String s, int nRows) {
     3         if (s == null) {
     4             return null;
     5         }
     6         
     7         // 第一个小部分的大小        
     8         int size = 2 * nRows - 2;
     9         
    10         // 当行数为1的时候，不需要折叠。
    11         if (nRows <= 1) {
    12             return s;
    13         }
    14         
    15         StringBuilder ret = new StringBuilder();
    16         
    17         int len = s.length();
    18         for (int i = 0; i < nRows; i++) {
    19             // j代表第几个BLOCK
    20             for (int j = i; j < len; j += size) {
    21                 ret.append(s.charAt(j));
    22                 
    23                 // 即不是第一行，也不是最后一行，还需要加上中间的节点
    24                 int mid = j + size - i * 2;
    25                 if (i != 0 && i != nRows - 1 && mid < len) {
    26                     char c = s.charAt(mid);
    27                     ret.append(c);
    28                 }
    29             }
    30         }
    31         
    32         return ret.toString();
    33     }
    34 }

2015.1.4 redo:

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 public class Solution {
     2     public String convert(String s, int nRows) {
     3         if (s == null) {
     4             return null;
     5         }
     6         
     7         // corner case;
     8         if (nRows == 1) {
     9             return s;
    10         }
    11         
    12         // The number of elements in a section.
    13         int section = 2 * nRows - 2;
    14         StringBuilder sb = new StringBuilder();
    15         
    16         int len = s.length();
    17         for (int i = 0; i < nRows; i++) {
    18             for (int j = i; j < len; j += section) {
    19                 char c = s.charAt(j);
    20                 sb.append(c);
    21                 
    22                 // The middle rows.
    23                 int mid = j + section - 2 * i;
    24                 // bug 2: the mid is out of range.
    25                 if (i != 0 && i != nRows - 1 && mid < len) {
    26                     // bug 1: forget a ')'
    27                     sb.append(s.charAt(mid));
    28                 }
    29             }
    30         }
    31         
    32         return sb.toString();
    33     }
    34 }

请至主页君的GIT HUB:

[https://github.com/yuzhangcmu/LeetCode\_algorithm/blob/master/string/Convert.java][https_github.com_yuzhangcmu_LeetCode_algorithm_blob_master_string_Convert.java]

[231613168128190.jpg]: /images/20220328/7615761d4a304800a93a6e45588480c6.png
[http_blog.csdn.net_fightforyourdream_article_details_16881517]: http://blog.csdn.net/fightforyourdream/article/details/16881517
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220328/305e2928d28644f1aee6681c4f57ffd9.png
[https_github.com_yuzhangcmu_LeetCode_algorithm_blob_master_string_Convert.java]: https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/string/Convert.java