22.Z字形转换

题目

将一个给定字符串 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);

示例 1:

• 输入：s = "PAYPALISHIRING", numRows = 3
• 输出："PAHNAPLSIIGYIR"

示例 2:
- 输入：s = "PAYPALISHIRING", numRows = 4 - 输出："PINALSIGYAHRPI" - 解释：

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

示例 3:

• 输入：s = "A", numRows = 1
• 输出："A"

提示:

• 1 <= s.length <= 1000
• s 由英文字母（小写和大写）、',' 和 '.' 组成
• 1 <= numRows <= 1000

思路

找规律，假设s = "PAYPALISHIRING", numRows = 3

• 从前往后遍历s
• s[0] : 第一行
• s[1] : 第二行
• s[2] : 第三行， 大于等于numRows了，行要开始递减了
• s[3] : 第二行，
• s[4] : 第一行， 到最小行了，行要开始递加了
• s[5] : 第二行
• ...

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if len(s) < 3 or numRows < 2:
            return s
        row = 1
        add = True
        # 用一个数组记录每一行的字符内容
        rowArray = [""] * numRows
        for i in s:
            rowArray[row - 1] += i

            if add:
                row += 1
            else:
                row -= 1
            if row > numRows:
                add = False
                # 本来要减1因为上面刚加了1，所以这里要减2
                row -= 2
            elif row < 1:
                add = True
                row += 2

        result = ""
        for i in rowArray:
            result += i
        return result

class Solution {
    fun convert(s: String, numRows: Int): String {
        if (numRows == 1 || numRows > s.length) {
            return s
        }
        val length = s.length
        // 当前行
        var row = 0
    // 行是要递增还是递减
        var add = true
        // 每一行都是一个sb，记录每一行的数据 
        val rowsArray = Array(numRows) {
            StringBuilder()
        }
        for (i in 0 until length) {
            rowsArray[row].append(s[i])

            if (row == 0) {
                add = true
            } else if (row == numRows - 1) {
                add = false
            }
            if (add) {
                row++
            } else {
                row--
            }
        }
        val result = StringBuilder()
        for (i in rowsArray) {
            result.append(i)
        }

        return result.toString()
    }
}

复杂度分析:

• 时间复杂度 O(N) ：遍历一遍字符串 s；

• 空间复杂度 O(N) ：各行字符串共占用 O(N) 额外空间。

• 下一篇

• 邮箱 ：charon.chui@gmail.com
• Good Luck!