首页 > 代码库 > LeetCode: ZigZag Conversion 解题报告

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

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

 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代表第几个BLOCK20             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 }
View Code

 

请至主页君的GIT HUB:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/string/Convert.java

 

LeetCode: ZigZag Conversion 解题报告