6. Z 字形变换

题意

解题思路：

• 题目理解：
  1. 字符串 s 是以 ZZ 字形为顺序存储的字符串，目标是按行打印。
  2. 设 numRows 行字符串分别为 S1,S2,,,,,Sn,则容易发现：按顺序遍历字符串 S 时,每个字符 c 在 Z字形中对应的行索引先从 S1增大至Sn,再从Sn减小至S1，，，如此反复
  3. 因此，解决方案为：模拟这个行索引的变化，在遍历 s 中把每个字符填到正确的行 res[i]
• 算法流程：按顺序遍历字符串 s；
  1. res[i] += c： 把每个字符 c 填入对应行 si；
  2. i += flag： 更新当前字符 c 对应的行索引；
  3. flag = - flag： 在达到 ZZ 字形转折点时，执行反向。
• 复杂度分析：
  1. 时间复杂度 O(N) ：遍历一遍字符串 s；
  2. 空间复杂度 O(N) ：各行字符串共占用 O(N) 额外空间。

PHP代码实现：

class Solution {
    /**
     * @param String $s
     * @param Integer $numRows
     * @return String
     */
    function convert($s, $numRows) {
        $res = array_fill(0, $numRows, '');
        $falg = -1;
        $j = 0;
        for ($i = 0; $i < strlen($s); $i++) {
            $res[$j] .= $s[$i];
            //开头=》增大，结尾=》减小
            if ($j == 0 || $j == $numRows - 1) {
                $falg = 0 - $falg;
            }
            $j += $falg;
        }
        return implode('', $res);
    }
    //1 使用二维数组存储对应字符的位置，最后输出整理结果字符串
    //2 采用标志位，标识存入方向的向上向下，注意边界条件
    function convert($s, $numRows) {
        $len = strlen($s);
        if ($len == 1 && $len == $numRows) return $s;
        $arr = [];
        $sign = 'down';
        $pre = -1;
        for ($i = 0; $i < $len; $i++) {
            if ($sign == 'down') {
                // 方向向下
                $arr[++$pre][] = $s[$i];
                // 到底部了，改方向为向上
                if ($pre == $numRows-1) $sign = 'up';
            } else {
                // 方向向上
                $arr[--$pre][] = $s[$i];
                // 到顶部了，改方向为向下
                if ($pre == 0) $sign = 'down';
            }
        }
        // 整理为字符串
        $resStr = '';
        foreach ($arr as $v) {
            foreach ($v as $vv) {
                $resStr .= $vv;
            }
        }
        return $resStr;
}

GO代码实现：

func convert(s string, numRows int) string {
    if len(s) <= 2  || numRows == 1{
        return s
    }
    res := make([]string, numRows)
    flag := -1
    j := 0
    for _, v := range s {
        res[j] += string(v)
        if j == 0 || j == numRows-1 {
            flag  = -flag
        }
        j += flag
    } 
    return strings.Join(res, "")
}

参考资料：

Leetcode