摘要

Z字形变换工具实现了将字符串按照Z字形（锯齿形）排列，然后按行读取的功能。本文详细解析了输入解析、模拟Z字形排列法、数学计算法、可视化展示等核心功能的代码实现细节。

1. 算法背景

1.1 问题描述

给定一个字符串和一个行数，将字符串按照Z字形排列，然后按行读取。Z字形排列是指字符先从上到下排列，然后从下到上排列，如此反复。

示例：

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

• 排列：

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

• 输出："PAHNAPLSIIGYIR"

1.2 应用场景

• 文本加密
• 数据排列
• 图形显示
• 字符串处理

2. 核心算法原理

2.1 模拟Z字形排列法

使用方向变量控制字符排列的方向，在到达边界时改变方向。时间复杂度 O(n)，空间复杂度 O(n)。

2.2 数学计算法

通过数学公式直接计算每个字符应该放在哪一行，无需实际构建Z字形矩阵。时间复杂度 O(n)，空间复杂度 O(1) 输出空间。

3. 代码实现详细解析

3.1 输入解析模块

var inputString = ""
var numRows = 3

payload.lines()
    .map { it.trim() }
    .filter { it.isNotEmpty() }
    .forEach { line ->
        when {
            line.startsWith("s=", ignoreCase = true) -> {
                inputString = line.substringAfter("=").trim()
                if (inputString.startsWith("\"") && inputString.endsWith("\"")) {
                    inputString = inputString.substring(1, inputString.length - 1)
                }
            }
            line.startsWith("numRows=", ignoreCase = true) || line.startsWith("rows=", ignoreCase = true) -> {
                try {
                    numRows = line.substringAfter("=").trim().toInt()
                } catch (e: Exception) {
                    numRows = 3
                }
            }
        }
    }

代码解析：

这段代码实现了灵活的输入解析机制，支持从输入字符串中提取目标字符串和行数。首先声明两个变量：inputString 是输入字符串，初始值为空；numRows 是行数，默认值为 3。

然后使用函数式编程风格处理输入：payload.lines() 将输入按行分割，map { it.trim() } 去除每行的首尾空白字符，filter { it.isNotEmpty() } 过滤空行。

在 forEach 循环中，使用 when 表达式进行模式匹配。第一个分支处理 s= 格式的输入：提取等号后面的部分作为字符串，然后检查是否被双引号包围。如果字符串以双引号开头和结尾，则去除这些引号，这样可以支持带引号的输入格式。

第二个分支处理行数的输入：支持 numRows= 或 rows= 格式。提取等号后面的部分并转换为整数。使用 try-catch 块捕获可能的异常，如果转换失败，保持默认值 3。

这种设计提高了输入格式的灵活性，用户可以输入 s=PAYPALISHIRING\nnumRows=3 或 s="PAYPALISHIRING"\nnumRows=3 等多种格式。

3.2 模拟Z字形排列法实现

fun convertZigzag(s: String, numRows: Int): String {
    if (numRows == 1 || s.length <= numRows) {
        return s
    }

    val rows = Array(numRows) { StringBuilder() }
    var currentRow = 0
    var goingDown = false

    for (char in s) {
        rows[currentRow].append(char)

        if (currentRow == 0 || currentRow == numRows - 1) {
            goingDown = !goingDown
        }

        currentRow += if (goingDown) 1 else -1
    }

    return rows.joinToString("") { it.toString() }
}

代码解析：

这是模拟Z字形排列法的核心实现，通过方向变量控制字符排列的方向。函数接受一个字符串和行数作为参数，返回Z字形排列后按行读取的字符串。

首先处理特殊情况：如果行数为 1 或者字符串长度小于等于行数，直接返回原字符串。这是因为在这些情况下，Z字形排列就是原字符串本身。

然后初始化数据结构：创建一个大小为 numRows 的数组 rows，每个元素是一个 StringBuilder，用于存储每一行的字符。currentRow 表示当前应该放置字符的行索引，初始值为 0（第一行）。goingDown 是一个布尔变量，表示当前方向是否为向下，初始值为 false（向上）。

接下来遍历字符串的每个字符。对于每个字符，首先将其添加到当前行的 StringBuilder 中（rows[currentRow].append(char)）。

然后检查是否到达边界（第一行或最后一行）。如果 currentRow == 0（第一行）或 currentRow == numRows - 1（最后一行），说明到达了边界，需要改变方向。通过 goingDown = !goingDown 来切换方向。

最后根据方向更新当前行索引：如果 goingDown 为 true（向下），则 currentRow 加 1（移动到下一行）；如果 goingDown 为 false（向上），则 currentRow 减 1（移动到上一行）。

这个算法的关键点是方向的控制。初始时 goingDown = false，表示向上，但因为 currentRow = 0（第一行），所以下一个字符会移动到第一行，实际上是从第一行开始向下排列。当到达最后一行时，方向改变为向上，字符开始向上排列。如此反复，就形成了Z字形的排列。

循环结束后，所有字符都已经按照Z字形排列到对应的行中。最后使用 rows.joinToString("") { it.toString() } 将所有行的字符连接起来，得到最终结果。这个操作按顺序将第一行、第二行、第三行等的字符连接，形成按行读取的结果。

这个算法的时间复杂度是 O(n)，其中 n 是字符串的长度，因为需要遍历字符串的每个字符。空间复杂度是 O(n)，因为需要使用数组存储每一行的字符。

3.3 数学计算法实现

fun convertZigzagMath(s: String, numRows: Int): String {
    if (numRows == 1 || s.length <= numRows) {
        return s
    }

    val result = StringBuilder()
    val cycleLen = 2 * numRows - 2

    for (i in 0 until numRows) {
        var j = 0
        while (j + i < s.length) {
            result.append(s[j + i])

            if (i != 0 && i != numRows - 1 && j + cycleLen - i < s.length) {
                result.append(s[j + cycleLen - i])
            }

            j += cycleLen
        }
    }

    return result.toString()
}

代码解析：

这是数学计算法的实现，通过数学公式直接计算每个字符应该放在哪一行，无需实际构建Z字形矩阵。函数接受一个字符串和行数作为参数，返回Z字形排列后按行读取的字符串。

首先处理特殊情况：如果行数为 1 或者字符串长度小于等于行数，直接返回原字符串。

然后计算周期长度：cycleLen = 2 * numRows - 2。这个公式的含义是：一个完整的Z字形周期包含从第一行到最后一行的向下移动（numRows - 1 步）和从最后一行到第一行的向上移动（numRows - 1 步），所以总长度是 2 * (numRows - 1) = 2 * numRows - 2。

接下来按行遍历。对于每一行 i（从 0 到 numRows - 1），使用一个循环变量 j，从 0 开始，每次增加 cycleLen，表示遍历每个周期。

在循环中，首先添加周期中的第一个字符：result.append(s[j + i])。这个字符位于周期中的第 i 个位置（因为第一行对应索引 0，第二行对应索引 1，以此类推）。

然后检查是否需要添加周期中的第二个字符。如果当前行不是第一行（i != 0）也不是最后一行（i != numRows - 1），并且第二个字符的索引在字符串范围内（j + cycleLen - i < s.length），则添加第二个字符：result.append(s[j + cycleLen - i])。

第二个字符的索引计算是：j + cycleLen - i。这是因为在一个周期中，第一行的字符在位置 j，最后一行（第 numRows - 1 行）的字符在位置 j + numRows - 1。对于第 i 行，第二个字符的位置应该是 j + cycleLen - i，这是因为从最后一行向上数，第 i 行的第二个字符距离最后一行有 numRows - 1 - i 个位置，所以索引是 j + numRows - 1 + (numRows - 1 - i) = j + 2 * numRows - 2 - i = j + cycleLen - i。

最后将 j 增加 cycleLen，移动到下一个周期。循环会一直执行，直到当前行的所有字符都处理完毕。

这个算法的时间复杂度是 O(n)，其中 n 是字符串的长度。空间复杂度是 O(1) 输出空间（不考虑输出字符串的存储空间），因为只使用了固定数量的变量，不需要存储中间矩阵。

3.4 Z字形排列可视化

val zigzagMatrix = Array(numRows) { Array(inputString.length) { ' ' } }
var col = 0

for (i in inputString.indices) {
    zigzagMatrix[currentRow][col] = inputString[i]

    if (currentRow == 0 || currentRow == numRows - 1) {
        goingDown = !goingDown
    }

    currentRow += if (goingDown) 1 else -1
    col++
}

代码解析：

这段代码实现了Z字形排列的可视化功能，通过二维数组构建Z字形矩阵，然后按行显示。首先创建一个二维字符数组 zigzagMatrix，大小为 numRows × inputString.length，初始值都是空格字符。

然后使用与模拟法相同的逻辑遍历字符串，将每个字符放置到矩阵的对应位置：zigzagMatrix[currentRow][col] = inputString[i]。currentRow 是当前行索引，col 是当前列索引。每处理一个字符后，col 增加 1，移动到下一列。

方向控制和行索引更新的逻辑与模拟法相同：在到达边界时改变方向，根据方向更新当前行索引。

构建完矩阵后，可以按行显示，将Z字形的排列可视化出来。对于每个位置，如果不是空格，显示字符；如果是空格，显示点号（.）表示空位。

4. 算法复杂度分析

4.1 时间复杂度

• 模拟Z字形排列法：O(n)，需要遍历字符串的每个字符
• 数学计算法：O(n)，需要遍历字符串的每个字符
• 总体时间复杂度：O(n)

4.2 空间复杂度

• 模拟Z字形排列法：O(n)，需要使用数组存储每一行的字符
• 数学计算法：O(1) 输出空间，只使用固定数量的变量
• 可视化：O(n × numRows)，需要使用二维数组存储矩阵

5. 算法优化建议

5.1 空间优化

数学计算法在空间复杂度上更优，不需要存储中间矩阵。

5.2 边界条件处理

代码已经处理了各种边界情况：行数为 1、字符串长度小于等于行数等情况。

5.3 可视化优化

可视化功能仅对较短字符串和较少行数启用，避免内存消耗过大。

6. 应用场景扩展

1. 文本加密：将文本按照Z字形排列，然后按行读取，实现简单的加密
2. 数据排列：将数据按照特定形状排列，便于显示或处理
3. 图形显示：在图形界面中按照Z字形排列元素
4. 字符串处理：各种字符串变换和处理场景
5. 算法竞赛：LeetCode 等平台的经典问题

7. 总结

Z字形变换工具实现了两种变换方法，核心要点：

1. 模拟Z字形排列法：时间复杂度 O(n)，空间复杂度 O(n)，通过方向变量控制字符排列方向
2. 数学计算法：时间复杂度 O(n)，空间复杂度 O(1) 输出空间，通过数学公式直接计算
3. 方向控制：在到达边界时改变方向，实现Z字形的排列效果
4. 边界处理：正确处理行数为 1、字符串长度小于等于行数等情况

通过深入理解代码实现，可以更好地应用这个算法解决实际问题，如文本加密、数据排列、图形显示等场景。模拟法的思想也可以扩展到其他形状的排列（如N字形、S字形等）。

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net