LeetCode 6. Z 字形变换（中）

双指针控制数组

题目

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

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

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

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

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

1
string convert(string s, int numRows);

示例

1
2
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
1
2
3
4
5
6
7
8
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

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

考察知识点

指针、数组

核心思想

通过从左向右迭代字符串，我们可以轻松地确定字符位于 Z 字形图案中的哪一行。

题目理解：字符串 s 是以 Z字形为顺序存储的字符串，目标是按行打印。设 numRows行字符串分别为 \(s\_{1}\)、 \(s\_{2}\)、\(s\_{3}\)、......\(s\_{n}\) 则容易发现：按顺序遍历字符串 s 时，每个字符 c 在 Z 字形中对应的 行索引 先从 \(s\_{1}\)增大至 \(s\_{n}\) ，再从 \(s\_{n}\) 减小至\(s\_{1}\)，如此反复。重点是发现这个规律。

因此，解决方案为：模拟这个行索引的变化，在遍历 s 中把每个字符填到正确的行 res[i] 。类似于构造了一个指针确定应该将字符串放到那个位置。 - 算法流程： 按顺序遍历字符串 s； 1. res[i] += c： 把每个字符 c 填入对应行 \(s_{i}\) 2. i += flag： 更新当前字符 c 对应的行索引； 3. flag = - flag：在达到 Z字形转折点时，执行反向。 - 复杂度分析： 时间复杂度 \(O(n)\) ：遍历一遍字符串 s； 空间复杂度 \(O(n)\) ：各行字符串共占用 \(O(n)\) 额外空间。

参考连接

指针方法解决

python版本

一个失败的例子

时间复杂度和空间复杂度都是\(O(n^2)\)，系统判定超出时间限制。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if len(s) <= numRows:
            return s
        matrix = []
        inter = numRows - 2
        start = 0
        end = numRows
        all_in = True
        while end<=len(s):
            if all_in:
                _segment = s[start:end]
                # all_in之后 加进去
                if len(_segment) < numRows:
                    _segment += "#" * (numRows-len(_segment))
                matrix.append(list(_segment))
                # 更新start end
                start += numRows
                if end == len(s):
                    break
                if end+inter <= len(s):
                    end += inter
                else:
                    end = len(s)
                all_in = False
            else:
                _segment = s[start:end]
                
                for j in range(len(_segment)):
                    # 创造一个str
                    tmp_str = "#"*(numRows-j-2) + _segment[j] + "#"*(j+1)
                    # 再转成list
                    matrix.append(list(tmp_str))
                # 为all_in做准备
                start = end
                if end == len(s):
                    break
                if end+numRows < len(s):
                    end += numRows
                else:
                    end = len(s)
                all_in = True
        
        return_str = ""
        for i in range(numRows):
            for j in range(len(matrix)):
                return_str += matrix[j][i]
        return_str = return_str.replace("#", "")
        return return_str

print("leet code accept!!!")
s = ["PAYPALISHIRING", "PAYPALISHIRING", "A"]
numRows = [3, 4, 2]
Answer = ["PAHNAPLSIIGYIR", "PINALSIGYAHRPI", "A"]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(s)):
        print("-"*50)
        result = solution.convert(s[i], numRows[i])
        print(result==Answer[i])

数组方法，十分简洁且高效。

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
28
29
30
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows < 2: return s  # 只分成一行的话，直接返回就好  注意添加边界控制
        res = ["" for _ in range(numRows)]  # res十分巧妙 输入时刚好按照要输出的位置进行设置 最后直接调用str.join拼接res即可
        i, flag = 0, -1  # i的作用是标记当前在那一行上添加 flag的作用是标记转移范围是向上还是向下并控制i的变化是增大还是变小
        for c in s:
            # 这三行代码的顺序不能变化
            res[i] += c  # 先将当前char安置在正确的行
            if i == 0 or i == numRows - 1: flag = -flag  # 再判断是第一行还是最后一行 决定是否要反转
            i += flag  # 更新要填入的目标行
        
        tmp_res = ''
        for i in res:
            tmp_res += i
       
        return tmp_res
    	# return "".join(res)

print("leet code accept!!!")
s = ["PAYPALISHIRING", "PAYPALISHIRING", "A"]
numRows = [3, 4, 2]
Answer = ["PAHNAPLSIIGYIR", "PINALSIGYAHRPI", "A"]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(s)):
        print("-"*50)
        result = solution.convert(s[i], numRows[i])
        print(result==Answer[i])

时间复杂度和空间复杂度都是\(O(n)\)

用时 内存 区别
56 ms 13.2 MB return "".join(res)
88 ms 13 MB return tmp_res

这说明尽量不调用API做字符串处理，会减少耗时。

有效语法糖