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

思路:这个题做起来感觉很绕; 题意要求最后按行输出最终的结果。 我们需要分块进行处理。
举例n=4

| |j = 0| j = 1 | j = 2| j = 3|
|i = 0 | 0 | | | 6 |
|i = 1 | 1 | | 5 | 7 |
|i = 2 | 2 | 4 | | 8 |
|i = 3 | 3 | | | 9 |

rowNum = 4
i = 0 or i = n-1(top or bottom):gap is (rowNum – 1) * 2
i != 0 && i != n-1: gap is j+size-2*i

public class Solution {
    public String convert(String s, int numRows) {
        if (s == null || s.length() == 0 || numRows < 1) 
            return "";
        if (numRows == 1) return s;
        int size = 2* (numRows - 1);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            for (int j = i; j < s.length(); j += size) { 
                sb.append(s.charAt(j));

                if (i != 0 && i != numRows - 1) { // not the first and last row
                    int pos = j + size - 2*i;
                    if (pos < s.length()) {
                        sb.append(s.charAt(pos));
                    }
                }
            }
        }
        return sb.toString();
    }
}

Reference:
http://www.cnblogs.com/springfor/p/3889414.html#3461559

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s