外观数列——描述数字序列

"外观数列是一个有趣的数学概念，它通过描述前一项生成新的数列项。这个数列从数字1开始，每一项都是对前一项的描述，形成了一种递归关系。例如，1（一个1）变为11（二个1），再变为21（一个2和一个1），接着是1211（一个1、一个2和二个1），最后是111221（一个1、一个1、一个2和二个1）。在生成外观数列时，我们需要将字符串分割成连续的相同字符组，并记录每个组的长度和字符，然后将这些描述组合成一个新的数字字符串。例如，数字字符串"3322251"可以描述为'三个3、两个2、两个2和一个5、一个1'。" 在这个问题中，我们被要求实现一个`countAndSay`函数，它接受一个正整数`n`作为参数，返回外观数列的第`n`项。这个问题可以通过迭代或递归的方式来解决。给定的参考答案使用了迭代的方法： ```cpp class Solution { public: string countAndSay(int n) { string ans = "1"; while (n != 1) { string temp; int count = 1; for (int i = 0; i < ans.size(); ++i) { if (i == ans.size() - 1 || ans[i] != ans[i + 1]) { temp.push_back(count + '0'); temp.push_back(ans[i]); } else { ++count; } } ans = temp; --n; } return ans; } }; ``` 在这个代码中，我们首先初始化结果字符串`ans`为"1"，然后在一个循环中处理直到找到第`n`项。在每次循环中，我们创建一个新的临时字符串`temp`来存储当前项的描述。遍历`ans`中的每个字符，计算连续相同字符的个数（`count`），并在`temp`中添加对应的描述（`count`的数字形式和字符本身）。当遍历完成后，`ans`被更新为`temp`，然后减小`n`的值，直到`n`等于1，表示找到了第`n`项。 注意，由于题目限制`1 <= n <= 30`，所以这个解决方案在可接受的时间复杂度内。对于更大的`n`值，可能需要更优化的算法，因为这个简单的迭代方法会导致指数级的增长。 外观数列是一个既有趣又具有挑战性的算法问题，它涉及到字符串处理、递归和动态构建新字符串的概念。在实际编程中，这种问题可以帮助我们锻炼逻辑思维和字符串操作技巧。