P006-ZigZagConversion

Mar 15, 2017 | LeetCode

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)

1
2
3

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:

1	string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return “PAHNAPLSIIGYIR”.

思路分析

最终结果就是将上图中每一行的内容去掉中间间隔连接起来

所以最直观的方法就是：

生成类似上图的结构(二维数组？？？)
去掉间隔
连接每一行

另外：

若使用二维数组，最终连接的时候还得去掉空白。所以可以使用特殊的二维数组–一维字符串数组来保存上述结构的同时去掉间隔。

代码

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) {
			//不是减一，因为第一行行最后一行都是一个元素
				row = numRows - 2;
				down = false;
			}
			if (row < 0) {
			//不是零,因为第一行行最后一行都是一个元素
				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

此处有个更牛逼的解法：http://www.cnblogs.com/sanghai/p/3632528.html

LeetCode