LeetCode 6： Z 字形变换 （模拟） —— 题解

欢迎阅读 欢迎来到「Z 字形变换」题解之旅本文将带你从把字符串按 Z 字形排好后逐行读出这一直观场景出发深入理解周期性规律的巧妙运用并掌握如何用公差 d 2·numRows - 2 直接定位每行字符来在 O(n) 内完成变换。在开始之前建议你先了解题目背景这是 LeetCode 6 题把字符串按 Z 字形蛇形排列成numRows行后逐行读取得到新字符串。本质上Z 字形的字符下标呈固定周期 d 2·numRows - 2循环问题转化为按行找下标规律并直接拼接。明确学习目标掌握首行/末行与中间行的下标规律理解d 2·numRows - 2 的推导与numRows 1 时 d 0 的死循环陷阱并熟练处理字符串短于行数等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如s PAYPALISHIRINGnumRows 3输出PAHNAPLSIIGYIR。本文将从问题转化、周期推导、逐行收集、边界防护到代码实现层层递进。即使你对找规律题还不熟悉我们也会从画一画 Z 字看看每行下标差多少这一直觉出发让你轻松抓住核心思想——一个周期走两列首末行取首尾。现在让我们一起按行收集字符完成 Z 字形变换吧 愿旖旎·个人主页学习专栏《算法专栏》《LangChain学习》《贪心算法》 钱塘江上潮信来今日方知我是我✨当前学习内容《模拟》一.题目6. Z 字形变换 - 力扣LeetCode​二、算法分析一、问题分析前置分析题目要求把字符串按 Z 字形排列成numRows行再逐行读取返回新字符串。关键约束numRows 1时原样返回无变换字符串可能短于行数要求 O(n) 时间。核心思路不真正画二维矩阵那样需要额外空间而是找下标规律一个完整周期含d 2·numRows - 2个字符首行和末行每隔 d 取一个字符中间行每周期取两个字符下标相差d第二个是j d - 2i按行拼接即得答案。 例子为什么下标有规律s PAYPALISHIRINGnumRows 3d 2×3-2 4。Z 字形排列为复制P A H N A P L S I I G Y I R第 0 行下标0, 4, 8, 12公差 4第 2 行下标2, 6, 10公差 4第 1 行中间行下标1, 3, 5, 7, 9, 11——相邻间隔在 2 和 2 之间交替1→3差 2、3→5差 2。规律清楚了就能直接按下标取字符无需真的画矩阵。二、算法策略周期规律 按行收集核心步骤计算公差d 2 * numRows - 2一个 Z 字周期含 2 列共2·numRows - 2个字符。特判d 0numRows 1时d 0会导致下标不前进死循环强制令d 1此时逐字符原样拼接等价于无变换。首行i 0与末行i numRows-1下标i, id, i2d, ...每隔 d 取一个。中间行0 i numRows-1每周期取两个字符下标j与k j d - 2i两者都 d前进各自判断越界后拼接。返回按行依次拼接得到的str。 示例s PAYPALISHIRINGnumRows 3d 4行 i类型下标序列取到的字符拼接结果0首行0, 4, 8, 12P, A, H, NPAHN1中间行(1, 3), (5, 7), (9, 11)A,P / L,S / I,IAPLSIIG2末行2, 6, 10Y, I, RYIR三行依次拼接PAHNAPLSIIGYIRPAHNAPLSIIGYIR✅与题目示例完全一致。三、正确性说明简单版本周期规律成立Z 字形每d 2·numRows-2个字符重复一次形状因此任一行内下标都呈周期性首末行周期为 d中间行每周期含 2 个字符——规律由 Z 字几何结构唯一决定不会错判。中间行第二个下标推导设某周期起点为j该行字符落在第 i 行第 1 列沿斜线走到第 2 列时行号递增 i而字符下标也随之前进推到该行第 2 个字符的下标为j d - 2i两字符之间正好相隔d - 2i下一个周期再各加 d——公式与图形一一对应。循环条件覆盖完整中间行用j n || k n作为循环条件任一下标未越界就继续并在拼接时各自判断if (j n)/if (k n)保证不越界且不遗漏最后一个字符。按行拼接顺序正确外层按行号 0 → numRows-1 遍历正好是逐行读取的顺序结果与题目要求一致。 例子中间行的两个下标为什么相差d - 2inumRows 4、d 6第 1 行i1第一个字符下标j 1第二个下标k 1 6 - 2×1 5——对应字符1和5间隔 4 d - 2i下一周期j 7、k 11。画出 4 行 Z 字可以看到第 1 行的字符确实落在下标1, 5, 7, 11, ...公式精确命中原图位置。四、实现细节边界防护初始化n s.size()、d 2 * numRows - 2、str空串。边界防护d 0必须特判为 1numRows 1时d 0j 0会死循环中间行循环条件用||任一下标有效即继续拼接时分别判越界s短于numRows时各循环自然只取有效下标无需特判。复杂度时间 O(n)每个字符恰好被访问一次空间 O(1)除返回字符串外无额外空间不建二维矩阵。关键操作int d 2 * numRows - 2;周期公差、if (d 0) d 1;防死循环、for (int j i, k d - j; j n || k n; j d, k d)中间行双下标遍历。 例子numRows 1的死循环陷阱s ABC、numRows 1d 2×1 - 2 0。若不特判i 0时走首行分支for (j 0; j n; j 0)——j永远停在 0ABC会被无限拼接 A程序死循环/超时。特判d 1后逐字符取得到ABC1 行的 Z 字形就是原串✅。五、返回值目标映射返回strZ 字形排列后逐行读取的字符串对应题目返回变换后的字符串。三.代码class Solution { public: string convert(string s, int numRows) { int n s.size(); string str; int d 2 * numRows - 2; // 公差一个 Z 字周期含 2*numRows-2 个字符 // 边界numRows 1 时 d 0下标不前进会死循环强制设为 1等价于无变换 if (d 0) { d 1; } // 1. 按行收集字符外层行号即“逐行读取”的顺序 for (int i 0; i numRows; i) { // 2. 首行每隔 d 取一个字符 if (i 0) { for (int j i; j n; j d) { str s[j]; } } // 3. 中间行每周期取两个字符下标相差 d - 2i else if (i ! 0 i ! numRows - 1) { for (int j i, k d - j; j n || k n; j d, k d) { if (j n) { str s[j]; // 周期内第 1 个字符 } if (k n) { str s[k]; // 周期内第 2 个字符下标 j d - 2i } } } // 4. 末行同样每隔 d 取一个字符 else { for (int j i; j n; j d) { str s[j]; } } } return str; // 5. 返回 Z 字形逐行读取的结果 } };四、易错点分析难点1numRows 1时d 0的死循环int d 2 * numRows - 2; if (d 0) { d 1; }numRows 1时公差d 0而所有内层循环都是j d——步长为 0j永远不前进循环条件永真程序死循环LeetCode 上表现为超时。特判d 1后逐字符前进相当于原样返回。这是本题最致命的边界且只有numRows 1一个输入会触发容易被忽略。难点2中间行第二个下标的推导k d - jfor (int j i, k d - j; j n || k n; j d, k d)初始时j i故k d - i。验证numRows 3, d 4, i 1时k 3——第 1 行第 2 个字符下标正是 3 ✅对应PAYPALISHIRING中的 P。下一周期j 4、k 4同时前进保持两字符相差d - 2i的关系。若把k的初始化写成固定值或始终k j 1中间行就会取错字符。难点3中间行的循环条件必须用||且内部各自判越界for (int j i, k d - j; j n || k n; j d, k d) { if (j n) str s[j]; if (k n) str s[k]; }两个下标不同步到达边界第二个通常更早或更晚越界。若条件写成会在其中一个越界时提前退出漏掉另一下标仍在范围内的字符若不写内部if判越界则可能在j n时访问越界UB。条件用||、取值各判是双下标遍历的标准写法。难点4为什么要找规律而不是真的建矩阵// 建矩阵vectorstring rows(numRows); 按 Z 字走位填充最后拼接模拟法走位填充矩阵代码更直观但需要O(numRows) 额外空间且走位逻辑方向切换、边界折返也易错。找规律法直接按公式取字符空间 O(1)、逻辑更纯粹——变换类题目优先找下标规律是重要经验尤其当变换具有周期性时。五、流程图 闭幕 恭喜你完成了「Z 字形变换」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考代码中定义周期d 2 * numRows - 2。为什么一个 Z 字周期的字符数是2 * numRows - 2请结合numRows 3和numRows 4画出周期结构验证。对于中间行非首末行每个周期取两个字符第二个字符的下标是j d - 2 * i。这个偏移量是如何推导出来的为什么首行和末行每周期只取一个字符当numRows 1时d 0代码强制将d设为1。如果不这样处理程序会发生什么这种边界情况体现了什么编程习惯代码采用按行读取的方式直接构造结果而不是模拟 Z 字形填充矩阵。这种“找规律”的方法相比模拟法有什么优势在什么情况下模拟法可能更直观如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案周期长度2 * numRows - 2因为 Z 字形从第一行向下走到第numRows行再斜向上回到第二行共经历numRows个下降步和numRows - 2个上升步合计2 * numRows - 2个字符。例如numRows3时周期为 4如0,1,2,1numRows4时周期为 6如0,1,2,3,2,1。中间行第二个字符偏移设当前周期起始下标为j该行在周期中的位置为i。第一个字符在j第二个字符出现在从底部返回的斜线上其下标为j d - 2 * i因为从j到下一个周期起点jd之间该行被访问两次间隔为d - 2*i。首行和末行在周期中只出现一次因此只取一个。numRows 1必须特殊处理因为d 0循环中j d会导致j永不前进程序陷入死循环。将d设为 1 后相当于逐字符复制原字符串符合题意。这体现了对边界条件的严谨处理。找规律法的优势直接按行拼接无需模拟二维矩阵节省了空间模拟法需要 O(numRows * n) 或至少 O(n) 的矩阵且代码更简洁、常数更小。模拟法在理解上更直观但实现更繁琐。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨