题目描述

原题

Description:

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)

1
2
3
4
> 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:

Example 1:

Input: s = “PAYPALISHIRING”, numRows = 3
Output: “PAHNAPLSIIGYIR”

Example 2:

Input: s = “PAYPALISHIRING”, numRows = 4
Output: “PINALSIGYAHRPI”
Explanation:

1
2
3
4
5
> > > P     I     N
> > > A   L S   I G
> > > Y A   H R
> > > P     I
> > >

原题翻译

描述：

字符串“PAYPALISHIRING”以Z字形图案写在给定数量的行上，如下所示:
(您可能希望以固定字体显示此图案以获得更好的易读性） 

1
2
3
4
> P     A     H     N
> A  P  L  S  I  I  G
> Y     I     R
>

然后逐行读取得到：“PAHNAPLSIIGYIR”。

编写将给定字符串转化的代码：

Example 1:

Input: s = “PAYPALISHIRING”, numRows = 3
Output: “PAHNAPLSIIGYIR”

Example 2:

Input: s = “PAYPALISHIRING”, numRows = 4
Output: “PINALSIGYAHRPI”
Explanation:

1
2
3
4
5
> > > P     I     N
> > > A   L S   I G
> > > Y A   H R
> > > P     I
> > >

解法一(mine)

打败了5.54%的回答…

主要思想

把每个$|/$形状作为一个分组（如：例子中的PAYPAL）。

用一个二维数组保存过程中的图形，然后遍历这个数组。

运行速度：超过了7.39%的解答。

内存使用：超过了84.04%的解答。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Solution {
    public String convert(String s, int numRows) {
        int len = s.length();
        if (len < 2 || numRows == 1) {
            return s;
        }
        StringBuffer result = new StringBuffer("");
        int last = len % (numRows + numRows - 2);
        int nums = len / (numRows + numRows - 2); //分组数
        int m = nums * (1 + numRows - 2);
        if (last > numRows) {
            m += 1 + (last - numRows);
        } else {
            m += 1;
        }
        char[][] temp = new char[m][numRows];
        boolean flag = true;
        int a = 0, b = 0;
        for (int i = 0; i < len; i++) {
            temp[a][b] = s.charAt(i);
            if (flag) {
                ++b;
            } else {
                ++a;
                --b;
            }
            if (b == (numRows - 1)) {
                flag = false;
            } else if (b == 0) {
                flag = true;
            }
        }

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < m; j++) {
                String ss = String.valueOf(temp[j][i]);
                if (!ss.equals("\u0000")) {
                    result.append(ss);
                }
            }
        }
        return result.toString();
    }
}

解法二

主要思想

通过从左往右迭代字符串，可以得到每个字符位于”Z”图案的第几行。

用一个list保存每一行。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;

        List<StringBuilder> rows = new ArrayList<>();
        for (int i = 0; i < Math.min(numRows, s.length()); i++)
            rows.add(new StringBuilder());

        int curRow = 0;
        boolean goingDown = false;

        for (char c : s.toCharArray()) {
            rows.get(curRow).append(c);
            if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
            curRow += goingDown ? 1 : -1;
        }

        StringBuilder ret = new StringBuilder();
        for (StringBuilder row : rows) ret.append(row);
        return ret.toString();
    }
}

解法三

第一名的答案。

运行速度：超过了100%的解答。

内存使用：超过了100%的解答。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
public class Solution {
    public String convert(String s, int numRows) {
        if (s == null || s.length() == 0) {
            return "";
        }
        if (s.length() == 1) { 
            return s;
        }
        if (numRows <= 1) { 
            return s;
        }
        int stringLength = s.length();
        char[] chars = s.toCharArray();
        char[] output = new char[stringLength];
        int outputIndex = 0;

        for (int offset = 0; offset < numRows; offset++) {
            int index = offset;

            // Add the first letter
            if (index >= stringLength) {
                break;
            }
            output[outputIndex++] = chars[index];

            while (index < stringLength) {
                // Skip this for the last row, since it will
                // output the same spot
                if (offset < numRows - 1) {
                    index += 2 * (numRows - 1 - offset);
                    if (index >= stringLength) break;
                    output[outputIndex++] = chars[index];
                }

                // Skip this for the first row, since it will 
                // always output the same spot
                if (offset > 0) {
                    index += 2 * offset;
                    if (index >= stringLength) break;
                    output[outputIndex++] = chars[index];
                }
            }
        }
        return new String(output);
        // rows = 4
        // 0 (2 * rows - 1)     
        // 6
        // 12

        // offset = 1
        // 1 (2 * (rows - offset - 1))
        // 5 (2 * (offset))
        // 7
        // 11
        // 13

        // offset = 2
        // 2 (2 * (rows - offset - 1))
        // 4 (2 * offset)
        // 8
        // 10
        // 14

        // offset = 3
        // 3
        // 3
        // 9
    }
}