欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

38-Count And Say

程序员文章站 2022-07-15 12:06:17
...

类别:string

题目描述

38-Count And Say

算法分析

1:“1”(有1个1)
2:“11”(表示上一个即第一个有1个1,而当前有2个1)
3:“21”(表示上一个即第二个有2个1,而当前有1个2,1个1)
3:“1211”(表示上一个即第三个有1个2和1个1,而当前有1个1,1个2,2个1)
4:“111221”……
给定数字n,需要从第一个数推到n,初始化strs[1] = “1”,然后用一个循环计算之后的每一个序号对应的字符串,对于每一个序号对应的字符串,需要用其前面一个字符串进行计算,遍历字符串,并且计算每一个数字出现的次数然后转换为字符串即可。

代码实现

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string countAndSay(int n) {
    vector<string> readStr;
    readStr.push_back("1");
    string str = "", generateStr = "";
    int n1 = 0, count = 0;
    char pre = ' ';

    for (int i = 1; i < n; ++i) {
        generateStr = "";
        str = readStr[i - 1];
        n1 = str.length();
        count = 1;
        pre = str[0];

        for (int j = 1; j < n1; ++j) {
            //  count the continous same char
            if (str[j] == pre) {
                count++;
            } else {
                //  add chars
                generateStr += count + '0';
                generateStr += pre;
                count = 1;
                pre = str[j];
            }
        }
        // add last chars
        generateStr += count + '0';
        generateStr += pre;
        readStr.push_back(generateStr);
    }

    return readStr[n - 1];
}

int main() {
    int n;
    cin >> n;
    cout << countAndSay(n) << endl;
    return 0;
}