原题

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

题目大意

　　输入一个字符串和指定的行数，将字符以Z字型输出。

解题思路

　　计算出字符的最大列数，根据列数和行数创建一个一维数组，再计算每个字符中一维数组中的位置，再对一维数组中的字符进行紧凑操作，返回结果。

【解析】

第一次看到这个题目的人，可能不知道ZigZag是什么意思，简单解释一下，就是把字符串原顺序012345……按下图所示排列：

比较直观的解法是，用一个字符串数组 string[rows] 来存储每一行，最后一拼接就是最终结果。

用一个delta表示正向还是反向，即上图中从第一行到最后一行还是最后一行到第一行。

代码如下所示：

 

[java]

1. public class Solution {  
2.     public String convert(String s, int nRows) {  
3.         int len = s.length();  
4.         if (len == 0 || nRows <= 1) return s;  
5.           
6.         String[] ans = new String[nRows];  
7.         Arrays.fill(ans, "");  
8.         int row = 0, delta = 1;  
9.         for (int i = 0; i < len; i++) {  
10.             ans[row] += s.charAt(i);  
11.             row += delta;  
12.             if (row >= nRows) {  
13.                 row = nRows-2;  
14.                 delta = -1;  
15.             }  
16.             if (row < 0) {  
17.                 row = 1;  
18.                 delta = 1;  
19.             }  
20.         }  
21.           
22.         String ret = "";  
23.         for (int i = 0; i < nRows; i++) {  
24.             ret += ans[i];  
25.         }  
26.         return ret;  
27.     }  
28. }  

【网上解法】

 

如 http://blog.csdn/cshaxu/article/details/12507201 说的最为简洁：

发现所有行的重复周期都是 2 * nRows - 2

对于首行和末行之间的行，还会额外重复一次，重复的这一次距离本周期起始字符的距离是 2 * nRows - 2 - 2 * i

代码如下所示：

 

[java]

1. public class Solution {  
2.     public String convert(String s, int nRows) {  
3.         int len = s.length();  
4.         if (len == 0 || nRows < 2) return s;  
5.           
6.         String ret = "";  
7.         int lag = 2*nRows - 2; //循环周期  
8.         for (int i = 0; i < nRows; i++) {  
9.             for (int j = i; j < len; j += lag) {  
10.                 ret += s.charAt(j);  
11.                   
12.                 //非首行和末行时还要加一个  
13.                 if (i > 0 && i < nRows-1) {  
14.                     int t = j + lag - 2*i;  
15.                     if (t < len) {  
16.                         ret += s.charAt(t);  
17.                     }  
18.                 }  
19.             }  
20.         }  
21.         return ret;  
22.     }  
23. }  

【总结】

 

这道题属于简单题，找规律即可，循环周期可能比较容易找，周期中间的规律 2 * nRows - 2 - 2 * i 可能不大好找。

代码实现

public class Solution {    public String convert(String s, int nRows) {        if (s == null || s.length() <= nRows || nRows == 1) {            return s;        }        int index = s.length();        int rowLength = 0; // 计算行的长度，包括最后换行字符        int slash = nRows - 2; // 一个斜线除去首尾所占用的行数        while (index > 0) {            // 竖形的一列            index -= nRows;            rowLength++;            // 斜着的列数            for (int i = 0; i < slash && index > 0; i++) {                rowLength++;                index--;            }        }        char[] result = new char[nRows * rowLength]; // 保存结果的数组，最后一列用于保存换行符        for (int i = 0; i < result.length; i++) { // 初始化为空格            result[i] = ' ';        }        int curColumn = 0; // 当前处理的行数        index = 0;        while (index < s.length()) {            // 处理竖线            for (int i = 0; i < nRows && index < s.length(); i++) {                result[rowLength * i + curColumn] = s.charAt(index);                index++;            }            curColumn++;            // 处理斜线            for (int i = nRows - 2; i > 0 && index < s.length(); i--) {                result[rowLength * i + curColumn] = s.charAt(index);                curColumn++;                index++;            }        }//        System.out.println(new String(result));        // 对字符数组进行紧凑操作        index = 0;        while (index < s.length() && result[index] != ' ') { // 找第一个是空格的字符位置            index++;        }        int next = index + 1;        while (index < s.length()) {            while (next < result.length && result[next] == ' ') { // 找不是空格的元素                next++;            }            result[index] = result[next];            index++;            next++;        }        System.out.println(s);        System.out.println(new String(result, 0, index));        return new String(result, 0, index);    }}

 

这题的解法也很单一，也没有很难的时间复杂度，大致都是O(n)。

我们想一下思路，这个zigzag有一个性质不知道你们发现了没有。

对于数列123456789来说当nRows＝4的时候第一列肯定是满列，然后第二列的位置＝2%4+1也就是3那么第三列的位置就是3%4+1也就是2

这样我们一个循环就可以完成这个操作了，这里说的操作仅仅是可以放在一个二维数组中了，那么我们可不可以利用这个性质直接输出呢？

首先读取一个字符串从1开始如果＝1或者％4＋（4-2）＋1=0的话则输出，这样一层一层的输出就好了，但是这样我们需要不断的遍历操作，但是如果我们操作数组下标这个时间复杂度增加的问题就解决了。

代码如下：

 

[java]

 

1. public class ZigZagConversion {  
2.     public static void main(String[] args){  
3.         String text = "123456789";  
4.         System.out.println(method(text, 4));  
5.     }  
6.     public static String method(String text ,int nRows){  
7.         StringBuilder result = new StringBuilder();  
8.         char[] string = text.toCharArray();  
9.         for(int i =0;i<nRows;i++){  
10.             for(int j = i;j<string.length;){  
11.                 if(i==0||i==(nRows-1)){//处在第一行和最后一行，不用输出中间数  
12.                     result.append(string[j]);  
13.                     j += nRows*2-2;  
14.                 }else {//处在中间行，要多输出中间数  
15.                       
16.                     if(j>nRows){  
17.                         result.append(string[j-i*2]);  
18.                     }  
19.                     result.append(string[j]);  
20.                     j += nRows*2-2;  
21.                 }  
22.             }  
23.         }  
24.         return result.toString();  
25.     }  
26. }  

这个代码的主要特点就是根据nRows做的时间复杂度，它的时间复杂度经过计算应该是O(n^2/2n-2)当n趋向于无限大的时候O趋向于O(n)，针对String比较长而nRows比较短的情况应该有奇效。