题目来源

• leetcode：38. 外观数列

题目描述

class Solution {
public:
    string countAndSay(int n) {

    }
};

总的来讲，就是对前1个数进行报数

题目解析

看懂题目的第一个想法：需要递归，因为后一项都和前一项有关

class Solution {
public:
    string countAndSay(int n) {
        if(n == 1){
            return "1";
        }

        std::string lastStr = countAndSay( n - 1);
        std::string ans;
        int  len = lastStr.size(), left = 0;
        for (int read = 0; read < len; ++read) {
            if(read == len - 1 || lastStr[read] != lastStr[read + 1]){  //到了末尾或者到了边缘
                ans.append(std::to_string(read - left + 1)).push_back(lastStr[left]);
                left = read + 1;
            }
        }
        return ans;
    }
};

class Solution {
public:
	string countAndSay(int n) {
	    if(n == 1){
	        return "1";
	    }
	    string lastStr = countAndSay(n - 1);
	    string ans;
	    int i = 0, j = 1, len = lastStr.size();
	    while(j < len) {
	        if(lastStr[i] != lastStr[j]){
	            ans.append(to_string(j - i)).push_back(lastStr[i]);
	            // ans = ans + to_string(j - i) + lastStr[i];
	            i = j;
	        }
	        j++;
	    }
	    ans.append(to_string(j - i)).push_back(lastStr[i]);
	    return ans;
	}

}

class Solution {
    std::string helper(std::string s){
        std::string  ans;
        int len = s.length();
        int  i = 0;
        while (i < len){
            char ch = s[i];
            int k = i + 1, cnt = 1;
            while (k < len && s[k] == ch){
                ++cnt;
                ++k;
            }
            ans.append(std::to_string(cnt)).push_back(ch);
            i = k;
        }

        return ans;
    }
public:
    string countAndSay(int n){
        std::string  ans = "1";
        for (int i = 1; i < n; ++i) {
            ans = helper(ans);
        }
        return ans;
    }
};

类似题目