Z 字形变换

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L      C        I     R
E  T  O  E  S  I  I  G
E      D       H    N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

 

方法一：按行排序

1、先定义一个len为numRows的list；

2、遍历字符串中的每一个字符，并把它们添加到 相应的list元素中；

a.z字形排列首先是竖着排一列，第一列排满之后我们需要逆序倒回去把字符添加到相应的元素中（也有可能不添加）

b.设定一个不添加的条件判断当前是否添加字符，并且确定list的index是递增还是递减；

3、将list中的元素合成一个字符串并return。

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        cur = 0
        out = str()
        ret = []
        flag = False
        if (numRows == 1): return s
        
        for i in range(numRows):
            ret.append("")
        
        for i in s:
            ret[cur] = str(ret[cur]) + str(i)
            if cur == 0 or cur == numRows-1: flag = bool(1-flag)
            if flag == True:
                cur += 1
            else:
                cur -= 1
            
        for S in ret:
            out = out + str(S)
        return out
        

 

方法二：按行访问

思路

按照与逐行读取 Z 字形图案相同的顺序访问字符串。

算法

首先访问 行 0 中的所有字符，接着访问 行 1，然后 行 2，依此类推...

对于所有整数 k，

    行 0 中的字符位于索引 k  (2⋅numRows−2)处;
    行 numRows−1 中的字符位于索引 k  (2⋅numRows−2)+numRows−1处;
    内部的 行 i中的字符位于索引 k  (2⋅numRows−2)+i 以及 (k+1)(2⋅numRows−2)−i处;

class Solution {
    public String convert(String s, int numRows) {

        if (numRows == 1) return s;

        StringBuilder ret = new StringBuilder();
        int n = s.length();
        int cycleLen = 2 * numRows - 2;

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j + i < n; j += cycleLen) {
                ret.append(s.charAt(j + i));
                if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
                    ret.append(s.charAt(j + cycleLen - i));
            }
        }
        return ret.toString();
    }
}