JYT's Leetcode Solution(2)

2022-07-15

1 题目描述

题6 Z字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

1
2
3
P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”PAHNAPLSIIGYIR”。请你实现这个将字符串进行指定行数变换的函数：

示例1

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

示例2

1
2
3
4
5
6
7
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例3

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

2 问题解法

2.1 暴力求解

（此方法是最愚蠢的方法，首次提交执行用时84ms，内存消耗93MB）

初次见到该题，我们很容易被题目中关于“Z字形”的描述所欺骗。按问题所述，很容易联想到创建一个二维矩阵，然后将待变换字符串每一个字符按要求依次填入该矩阵中（空位用空格字符表示），最后逐行输出结果。显然，此解法的时间复杂度为O(n^2)。

2.2 转换思路

那么，有没有时间复杂度为O(n)的算法呢？答案是显然的。在暴力求解的过程中，我们发现，矩阵每一行字符的前后顺序一定与原字符串的顺序相同，而且最终字符串由矩阵逐行输出而得。因此，我们将舍弃二维矩阵，在c++中为二维字符数组，转而使用一维字符串数组。当我们确认原字符串每一位字符所在的行数时，直接接在数组对应字符串元素之后即可。最后，我们将各字符串逐行连接，即可得到正确结果。

3 求解代码

  • 代码行数较少，无注释
  • c++代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution {
    public:
        string convert(string s, int numRows) {
            if(numRows == 1){
                return s;
            }
            int l = s.length();
            int blockSize = 2 * (numRows - 1);
            string ss[numRows];
            for(int i = 0; i < numRows; i++){
                ss[i] = "";
            }
            for(int i = 0; i < l; i++){
                int loc = i % blockSize;
                if(loc < numRows){
                    ss[loc] += s[i];
                }else{
                    ss[blockSize - loc] += s[i];
                }
            }
            string sRet = "";
            for(int i = 0; i < numRows; i++){
                sRet += ss[i];
            }
            return sRet;
        }
    };
  • python代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution:
        def convert(self, s: str, numRows: int) -> str:
            if numRows == 1:
                return s
            else:
                blockSize = 2 * (numRows - 1)
                ss = []
                for i in range(numRows):
                    ss.append("")
                for i in range(len(s)):
                    loc = i % blockSize
                    if loc < numRows:
                        ss[loc] += s[i]
                    else:
                        ss[blockSize - loc] += s[i]
                sRet = ""
                for i in range(numRows):
                    sRet += ss[i]
                return sRet

4 总结

有时候，优秀的解法并不能直接想出，从最基本的开始做起也不错。