[TOC]

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

思路分析

5行

6行

最終結(jié)果就是將上圖中每一行的內(nèi)容去掉中間間隔連接起來(lái)

所以最直觀的方法就是：

• 生成類似上圖的結(jié)構(gòu)(二維數(shù)組？？？)
• 去掉間隔
• 連接每一行

另外：

若使用二維數(shù)組，最終連接的時(shí)候還得去掉空白。所以可以使用特殊的二維數(shù)組--一維字符串?dāng)?shù)組來(lái)保存上述結(jié)構(gòu)的同時(shí)去掉間隔。

代碼

java

import java.util.Arrays;
public class Solution006 {
    public String convert(String s, int numRows) {
        if (s == null || s.length() == 0 || numRows <= 1)
            return s;
        String rows[] = new String[numRows];
        Arrays.fill(rows, "");
        boolean down = true;
        int row = 0;

        for (int i = 0; i < s.length(); i++) {
            rows[row] += s.charAt(i);

            if (down) {
                row++;
            } else {
                row--;
            }

            if (row >= numRows) {
            //不是減一，因?yàn)榈谝恍行凶詈笠恍卸际且粋€(gè)元素
                row = numRows - 2;
                down = false;
            }

            if (row < 0) {
            //不是零,因?yàn)榈谝恍行凶詈笠恍卸际且粋€(gè)元素
                row = 1;
                down = true;
            }

        }

        StringBuilder sb = new StringBuilder();
        for (String r : rows) {
            sb.append(r);
        }
        return sb.toString();
    }
}

python

class Solution006(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if not s or len(s) == 0 or numRows <= 1:return s
        
        rows = [""] * numRows
        
        down = True;row = 0;
        
        for e in s:
            rows[row] += e
            
            if down:
                row += 1
            else:
                row -= 1
            
            
            if row >= numRows:
                row = numRows - 2
                down = False

            if row < 0:
                row = 1
                down = True
        
        # end for
        
        ret = ""
        for e in rows:
            ret += e
        
        return ret

此處有個(gè)更牛逼的解法：http://www.cnblogs.com/sanghai/p/3632528.html