Z字形变换

• direction模拟
• 本文介绍的算法直观明了，给出1个固定的解题思路。（如螺旋矩阵也是direction解题思路）

题目描述

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

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

P   A   H   N
A P L S I I G
Y   I   R

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

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

C++实现

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        
        vector<string> dp(numRows);
        vector<int> direction = {1, -1};
        int step = 0;

        int row = 0;
        for (const auto & e : s) {
            dp[row].push_back(e);
            int nextRow = row + direction[step];
            if (nextRow < 0 || nextRow >= numRows) {
                step = (step+1)%direction.size();
            }
            row += direction[step];
        }

        string res;
        for (const auto & e : dp) {
            res += e;
        }
        return res;
    }
};

golang实现

func convert(s string, numRows int) string {
    if numRows == 1 {
        return s
    }

    direction := []int{1, -1}
    step := 0

    dp := make([][]byte, numRows)
    row := 0
    for _, v := range s {
        dp[row] = append(dp[row], byte(v))
        nextRow := row + direction[step]
        if nextRow < 0 || nextRow >= numRows {
            step = (step+1)%len(direction)
        }
        row += direction[step]
    }

    res := []byte{}
    for _, v := range dp {
        res = append(res, v...)
    }
    return string(res)
}