算法实战：Z 字形变换与外观数列解析

外观数列

题目链接： 38. 外观数列 - LeetCode

题目描述： 给定一个正整数 n，返回外观数列的第 n 项。外观数列每一项都是对前一项的描述。

示例： 输入：n = 4 输出："1211" 解释：

1. 第 1 项："1"
2. 第 2 项："11" （前一项是 1 个 1）
3. 第 3 项："21" （前一项是 2 个 1）
4. 第 4 项："1211" （前一项是 1 个 2，1 个 1）

解题思路

这是一个典型的模拟问题。我们需要迭代地生成下一项。核心逻辑是'读'出上一项的数字序列。

对于每一项字符串，使用双指针扫描：

• 左指针 left 标记当前连续相同字符的起始位置。
• 右指针 right 向后移动，直到遇到不同字符或到达末尾。
• 统计个数 count = right - left，拼接 to_string(count) 和字符本身 ret[left]。
• 更新 left = right，继续处理下一段。

重复此过程 n - 1 次即可得到最终结果。注意边界条件，当 n=1 时直接返回 "1"。

C++ 代码实现

class Solution {
public:
    string countAndSay(int n) {
        string ret = "1";
        for (int i = 1; i < n; i++) {
            string tmp;
            for (int left = 0, right = 0, count = 0; right < ret.size(); ) {
                while (right < ret.size() && ret[left] == ret[right]) {
                    right++;
                }
                tmp += to_string(right - left) + ret[left];
                left = right;
            }
            ret = tmp;
        }
        return ret;
    }
};

总结

这两道题都考察了对字符串操作的熟练度以及对规律的敏感度。

• Z 字形变换的关键在于发现周期性，避免使用二维数组模拟，从而降低空间开销。
• 外观数列则是简单的模拟过程，重点在于如何高效地统计连续字符并拼接新字符串。

在实际面试中，这类题目常作为考察基础编码能力的入口，建议多练习边界条件的处理，例如空串、单行、n=1 等情况。