外观数列

Question

  The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

• countAndSay(1) = "1"
• countAndSay(n) is the way you would “say” digit string from countAndSay(n-1),which is then converted into a different digit string.

  To determine how you “say” a digit string, split it into the minimal number of groups so that each group is a contiguous section all of the same character.
  Then for each group, say the number of characters,then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.

For example, the saying and conversion for digit string "3322251":

Given a positive integer n, return the nth term of the count-and-say sequence.

Example 1:

Input: n = 1
Output: "1"
Explanation: This is base case

Example 2:

Input: n = 4 Output: "1211" Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" two 1's = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"

Answer

思路一

  暴力破解法: 首先确定基础case “1”, ans用于存储输出的字符。count用于计数,如果想要知道4所对应的值，那么知道了3所对应的数值就行了。如果出现了重复就通过while语句来增加对应的值。时间复杂度为O(n),具体代码如下:

  class Solution {
public:
    string countAndSay(int n) {
        string res = "1";
        
        while (--n) {
            string ans = "";
            for (int i = 0 ;i < res.size() ;i++) {
                int count = 1;
                while ( (i+1 < res.size()) && (res[i] == res[i+1]))
                    i++,count++;
                ans += to_string(count) + res[i];
            }
            res = ans;
        }
        return res;
    }
};