leetcode-38-外观数列
目录
leetcode 38 外观数列
一、题目描述
二、解题思路
整体思路
可以采用模拟+双指针的方法来解决这个题目。
具体思路
(1)返回数列的第n项，需要描述n-1次；
(2)定义变量left和right充当双指针，ret[left]就是字符的种类，right-left就是该字符出现的次数，将二者转成字符串，然后加入tmp字符串；
(3)ret字符串遍历完成后，将ret更新为tmp字符串，直到描述完n-1次，返回ret即可。
三、代码实现
class Solution {
public:
string countAndSay(int n) {
//模拟+双指针
string ret="1";
//描述n-1次
for(int i=1;i<n;i++){
string tmp;
for(int left=0,right=0;right!=ret.size();){
while(ret[left]==ret[right]) right++;
tmp+=to_string(right-left)+ret[left];
left=right;
}
ret=tmp;
}
return ret;
}
};