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

链接：https://leetcode.com/problems/zigzag-conversion/

一刷

python

先算s里有多少波峰，然后两轮循环，外循环为numRows，内循环为波峰数量，每一步均计算左右两侧分别是否valid，每个group波谷的范围为左开右闭。

算法边界条件太多，runtime只beat不到10%

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if len(s) <= numRows or numRows == 1:
            return s
        num_group = (len(s) + numRows - 1 ) // (2 * (numRows - 1)) + 1
        zigzag_chars = []
        for row in range(numRows):
            for i in range(num_group):
                left_index = 2 * (numRows - 1) * i - row
                right_index = 2 * (numRows - 1) * i + row
                if left_index >= 0 and left_index < len(s):
                    if left_index % (2 * (numRows - 1)) != 0 and left_index % (numRows - 1) == 0:
                        pass
                    else:
                        zigzag_chars.append(s[left_index])
                if left_index != right_index and right_index < len(s):
                    zigzag_chars.append(s[right_index])
        return ''.join(zigzag_chars)

也可以外循环遍历row，内遍历zigzag group。

内循环里先validate index，加入output array，再validate zag(斜线)上元素的距离，以及是否valid。pair_distance可以用直角等腰三角形来计算距离，直角边和斜边的距离相应元素的距离为zig_size - 2*row

class Solution(object):
    def convert(self, s, numRows):
        if numRows == 1 or len(s) <= numRows:
            return s
        zig_size = 2 * (numRows - 1)
        num_group = len(s) / zig_size + 1
        zigzag_chars = []
        for row in range(numRows):
            for group_idx in range(num_group):
                index = group_idx * zig_size + row
                if index < len(s):
                    zigzag_chars.append(s[index])
                    if row != 0 and row != numRows - 1:
                        pair_distance = zig_size - 2 * row
                        pair_index = index + pair_distance
                        if pair_index < len(s):
                            zigzag_chars.append(s[pair_index])
        return ''.join(zigzag_chars)

还有只用一个循环的算法，留给二刷