首页 > 代码库 > [LeetCode] Count and Say 字符串
[LeetCode] Count and Say 字符串
The count-and-say sequence is the sequence of integers beginning as follows:1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.11 is read off as "two 1s" or 21.21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth sequence.
Note: The sequence of integers will be represented as a string.
Hide Tags
String 这题其实就是字符串操作，题目有点难懂，意思翻译下，有那么一个数列，第一个为1，后面的结果是基于前一个的，规律如上面的描述，那么第二个便是统计第一个的个数，因为第一个只有1，所以第二个是21，然后第三个是统计第二个的，便是12 11，这样连起来为第三个的1211，第四个是基于第3个的，统计后便是 11 12 21，这样第四便是111221，如此下去，返回第n个的结果，使用string 返回。算法中涉及到int 转换成string 。
我的思路便是按上面那样一个一个算，其实有更好的实现，需要点额外空间，观察规律可知每项是固定的，所以可以将已经知道的记录下来，这样便能够提升时间效率。
#include <string>#include <iostream>#include <sstream>using namespace std;class Solution {public: string countAndSay(int n) { if(n<=0) return "0"; if(n==1) return "1"; string curStr="1",retStr=""; for(int i=1;i<n;i++){ int cnt = 1; retStr=""; for(int j=1;j<curStr.size();j++){ if(curStr[j-1]==curStr[j]) cnt++; else{ stringstream ss; ss<<cnt<<curStr[j-1]; retStr+=ss.str(); cnt=1; } } stringstream ss; ss<<cnt<<curStr[curStr.size()-1]; retStr+=ss.str(); curStr=retStr; } return retStr; }};int main(){ Solution sol; for(int i=0;i<10;i++){ string ret=sol.countAndSay(i); cout<<"i:"<<ret<<endl; } return 0;}
[LeetCode] Count and Say 字符串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。