算法模拟实战：Z 字形变换与外观数列详解
本文聚焦于两道经典的算法模拟题，通过代码实现与逻辑推导，深入剖析字符串处理中的周期规律与迭代统计技巧。
Z 字形变换
题目链接： 6. Z 字形变换 - LeetCode
题目描述：
将给定字符串 s 根据给定的行数 numRows，以从上往下、从左到右进行 Z 字形排列。
示例：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
思路分析
这道题的核心在于找到下标的变化规律。当 numRows 为 4 时，字符的排列呈现出明显的周期性。
观察下标序列可以发现，数据是以 2 * numRows - 2 为一个周期进行循环的。我们可以将问题拆解为三部分处理：首行、中间行、末行。
- 首行与末行：这两行的下标间隔固定，均为
2 * numRows - 2。例如第一行是0, d, 2d...（其中d为周期）。 - 中间行：对于第
k行（0 < k < numRows - 1），每个周期内包含两个字符。第一个字符的下标是i + k，第二个字符的下标是i + (d - k)。我们需要交替添加这两个位置的字符。
这种分情况讨论的方法避免了复杂的数学映射，直接模拟了读取过程，逻辑清晰且易于实现。
C++ 代码实现
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s;
string ret;
int d = 2 * numRows - 2;
int n = s.size();
// 1. 处理第一行
for (int i = 0; i < n; i += d) {
ret += s[i];
}
// 2. 处理中间的几行
for (int k = 1; k < numRows - 1; k++) {
for (int i = k, j = d - k; i < n || j < n; i += d, j += d) {
if (i < n) ret += s[i];
if (j < n) ret += s[j];
}
}
// 3. 处理最后一行
for (int i = numRows - 1; i < n; i += d) {
ret += s[i];
}
return ret;
}
};
解题笔记
手写推导过程有助于理解边界条件，特别是中间行双指针的同步移动逻辑。
外观数列
题目链接： 38. 外观数列 - LeetCode
题目描述： 「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
示例：
输入：n = 4
输出："1211"
解释：
- 第 1 项：
1 - 第 2 项：
11（读作 "1 个 1"） - 第 3 项：
21（读作 "2 个 1"） - 第 4 项：
1211（读作 "1 个 2，1 个 1"）
思路分析
外观数列的本质是模拟。我们需要遍历当前字符串，统计连续相同字符的个数，并将'个数'和'字符本身'拼接成下一项。
具体步骤如下：
- 初始化结果为
"1"。 - 循环
n - 1次生成后续项。 - 在每次循环中，使用双指针（或单指针配合计数）扫描当前字符串。
- 当遇到不同字符或到达末尾时，记录当前字符出现的次数，拼接到临时结果中。
- 更新当前字符串为新生成的结果。
注意处理字符串拼接时的效率问题，虽然本题数据规模不大，但养成使用 string 累加的习惯很重要。
C++ 代码实现
class Solution {
public:
string countAndSay(int n) {
string ret = "1";
for (int i = 1; i < n; i++) {
string tmp;
int left = 0, right = 0, count = 0;
while (right < ret.size()) {
while (right < ret.size() && ret[left] == ret[right]) {
right++;
}
tmp += to_string(right - left);
tmp += ret[left];
left = right;
}
ret = tmp;
}
return ret;
}
};
解题笔记
通过双指针快速定位连续区间的结束位置，能显著简化逻辑判断。
总结
这两道题虽然难度适中，但非常考验对字符串操作和规律发现的敏感度。
- Z 字形变换：关键在于识别周期性，避免使用二维数组模拟，直接计算下标更节省空间。
- 外观数列：核心在于准确统计连续字符，注意边界条件的判断。
掌握这类模拟思想，对于解决更多涉及状态转换的问题大有裨益。