Posts ZigZag转换解法和优化
Post
Cancel

ZigZag转换解法和优化

ZigZag转换问题[Medium]

问题描述

将一个字符串通过ZigZag转换后的结果返回,官网具体描述点这里 .

第一遍看官方的题目描述,没太看懂,要多看几遍,最好自己找几个例子自己画一下。

我们以 ABCDEFGHIJKLMN , rows=4 为例,如下图:

1
2
3
4
A     G      M
B   F H    L N      ->     AGMBFHLNCEIKDJ
C E   I  K  
D     J

可以观察到转换的主要过程为将源字符串按列存放,按行读出。其中:

  1. 两个完整列和中间的对角线构成一个平躺的水平对称的 Z 形状

  2. 两个完整列中间有一个长度为 rows - 2正方形,其中对角线上逆序存放字符

再看下base case:

  1. 当字符串长度不超过2时,无需转换

  2. rows=1 时,无需转换

  3. rows=2 时,正方形 长度为0,逻辑和 rows > 2 保持一致

简单粗暴版解法

根据上述观察和转换特点,可以设计出一个简单粗暴直接的方法:

  1. 用一个二维数组按列存放转换结果,初始填充一个placeholder,比如 -1 或者 0

  2. 通过列索引计算当前列是否在正方形

    1
    
         False if j % (rows - 2 + 1) == 0 else True
    

    2.1 如果列不在正方形中,按列依次存放字符至当前列,当存到最后一行时,移至下一列

    2.2 否则,根据正方形的性质计算出当前列存放数据的行索引 table[rows - 1 - j % (rows - 2 + 1)][j], 存入字符

  3. 转换完成后,按行遍历,过滤掉placeholder,进行拼接返回

实现时注意索引的变化,循环的退出条件

代码实现

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
def convert(self, s: str, numRows: int) -> str:
    # base case
    if not s or len(s) <= 2 or numRows <= 1:
        return s

    # 初始化,字符0填充
    table = [['0' for _ in range(len(s))] for _ in range(numRows)]

    # 源字符串遍历索引
    sIndex = 0
    # 中间正方形长度
    innerLength = numRows - 2

    # 列遍历索引
    j = 0
    while j < len(s):
        # 行遍历索引
        i = 0
        while i < numRows:
            if sIndex >= len(s):
                break
            # 完整列数据填充
            if j % (innerLength + 1) == 0:
                table[i][j] = s[sIndex]
                sIndex += 1
                # 填充到最后列的最后一个元素,移动到下一列
                if i == numRows - 1:
                    j += 1
                i += 1
            # 正方形对角线数据填充
            else:
                table[numRows - 1 - j % (innerLength + 1)][j] = s[sIndex]
                sIndex += 1
                j += 1

        if sIndex >= len(s):
            break
    # 组装结果
    ss = []
    for i in range(numRows):
        for jj in range(len(s)):
            if table[i][jj] != '0':
                ss.append(table[i][jj])

    return ''.join(ss)

复杂度分析

  1. while 循环的访问路径如下图所示,访问数组元素的次数为字符串的长度,时间复杂度为 \( O(n) \)

    路径

  2. 组装结果的双层 for 循环访问了二维数组的所有元素,时间复杂度为 \( O(n^2) \)

  3. 程序用了一个二维数组,空间复杂度为 \( O(n^2) \)

综上所述,时间复杂度为 \( O(n^2) \), 空间复杂度为 \( O(n^2) \) .

在leetcode上的运行结果如下图所示,和分析结果一致,时间和空间消耗都很大。

提交结果1

优化

仔细分析实现代码和问题,可以发现

  1. 二维数组中正方形的非对角线部分和上下方元素都是无用的空间,因为组装结果按行拼接时会跳过这些元素。如果用手在两边向中间挤一下这个二维数组,那么使用 \( O(n) \) 的空间就可以实现转换。

    数组的每一行长度不一定相同,实现时采用动态扩展的数组

    push

  2. 元素在二维数组中按列的填充方向遇到天花板时就会改变方向,可以从上文的路径图看出。天花板则是数组的第一行和最后一行

优化实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def convert(self, s: str, numRows: int) -> str:
    if not s or len(s) <= 2 or numRows <= 1:
        return s

    table = [[] for _ in range(numRows)]

    i = 0
    goingDown = False
    for c in s:
        table[i].append(c)
        # 碰到天花板,改变填充方向
        if i == 0 or i == numRows - 1:
            goingDown = not goingDown
        i += 1 if goingDown else -1

    # 组装数据
    ss = []
    for row in table:
        ss.extend(row)

    return ''.join(ss)

该实现基于leetcode的 solution1

复杂度分析

  1. 转换for循环和组装结果的for循环各自访问了数组中的所有元素,时间复杂度为 \( O(2n) = O(n) \)

  2. 二维数组的元素个数最多为 n + rows - 1, 空间复杂度为 \( O(n) \)

在leetcode上的再次提交结果,可以明显的看到时间和空间消耗都减少了很多

提交结果2

重构

第一次实现明显不如优化后的,暂不考虑第一次实现的重构,使用java语法。

  1. 对天花板的判断使用 ExtractMethod,方法签名建议如下

    1
    
     boolean directionChange(int i, int rows)
    
  2. 组装数据的逻辑使用 ExtractMethod,方法签名建议如下

    1
    
     String makeResult(List<String> convertTable)
    

总结

两次实现给我最大的感受是,先入为主的第一次自己对题目理解真的很重要。如果第一次看题,就能意识到二维数组的行可以压缩,那么会直接想到优化后的实现。

This post is licensed under CC BY 4.0 by the author.

-

Reverse-Integer解法和分析

Comments powered by Disqus.