JAVA练习373- 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 1000s由英文字母小写和大写、,和.组成1 numRows 1000来源6. Z 字形变换 - 力扣LeetCode解题分析方法模拟 Z 字形排列标识法这种方法的核心思想是模拟 Z 字形排列的过程。我们为每一行创建一个字符串构建器StringBuilder然后按照 Z 字形的遍历顺序将每个字符添加到对应的行中。算法思路边界情况处理如果行数numRows为 1直接返回原字符串因为不需要变换。初始化行容器创建numRows个StringBuilder每个对应 Z 字形的一行。模拟遍历过程使用变量i表示当前所在的行索引从 0 开始。使用变量flag表示移动方向1 表示向下移动-1 表示向上移动。遍历字符串s的每个字符将当前字符添加到第i行的StringBuilder中。判断是否到达边界第一行或最后一行如果到达边界则反转方向flag -flag。更新行索引i flag。合并结果遍历所有行的StringBuilder将它们的内容依次拼接起来得到最终结果。代码实现带详细注释class Solution { public String convert(String s, int numRows) { // 边界情况如果只有一行直接返回原字符串 if (numRows 1) { return s; } // 1. 为每一行创建一个 StringBuilder 来存储该行的字符 ListStringBuilder rows new ArrayList(); for (int i 0; i numRows; i) { rows.add(new StringBuilder()); } // 2. 初始化当前行索引和移动方向 int currentRow 0; // 当前所在行从第 0 行开始 int direction -1; // 移动方向-1 表示向下1 表示向上初始设为 -1第一次会反转 // 3. 遍历字符串中的每个字符 for (char c : s.toCharArray()) { // 将当前字符添加到对应行的 StringBuilder 中 rows.get(currentRow).append(c); // 如果到达第一行或最后一行需要改变方向 if (currentRow 0 || currentRow numRows - 1) { direction -direction; // 反转方向 } // 根据方向更新当前行索引 currentRow direction; } // 4. 合并所有行的字符串得到最终结果 StringBuilder result new StringBuilder(); for (StringBuilder row : rows) { result.append(row.toString()); } return result.toString(); } }复杂度分析时间复杂度O(n)其中 n 是字符串 s 的长度。我们只需要遍历一次字符串每个字符只被处理一次。空间复杂度O(n)用于存储所有行的字符最坏情况下需要存储整个字符串。算法示意图以s PAYPALISHIRINGnumRows 3为例行 0: P A H N → PAHN 行 1: A P L S I I G → APLSIIG 行 2: Y I R → YIR 遍历顺序P(行0) → A(行1) → Y(行2) → P(行1) → A(行0) → L(行1) → I(行1) → S(行2) → H(行0) → I(行1) → R(行2) → I(行1) → N(行0) → G(行1) 最终结果PAHN APLSIIG YIR PAHNAPLSIIGYIR