ARTS-8

Algorithm

引言

按照之前没有完成的题目顺序往下找的。

Description

题目

38. Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     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 where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

大意

count-and-say (数-说)序列大意是这样的, 给出一个数字, 数数连续数字有几个, 然后写出 count-num , 例如 1 就是 1个1, 那么, 写作 11, 它是2个1, 那么下一项为21, 再下一项为1个2和1一个1, 即为1211 .... 如此这般。

思路

这种问题思路就很清晰了, 有一个起始条件, 每一个后续项都依赖于前一项, 典型的递归解决思路, 稍复杂就用DP, (最高效的方式应该是按照索引找规律, 到那时这个题目我没找到什么明显规律) 那么, 这个题目甚简单, 就直接简单递归即可。

Code

class Solution {
public:
    string countAndSay(int n) {
        if (n==1) 
            return "1";
        
        string res = "";
        string r = countAndSay(n-1);
        char lastC = r[0];
        int remainSize = 0;
        for (auto c : r) {
            if (lastC==c) {
                remainSize += 1;
            } else {
                res.append(1, (char)(remainSize+'0'));
                res.append(1, lastC);
                lastC = c;
                remainSize = 1;
            }
        }
        res.append(1, (char)(remainSize+'0'));
        res.append(1, lastC);
        return res;
    }
};

Result

Success Details 

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Count and Say.

Memory Usage: 9.1 MB, less than 38.74% of C++ online submissions for Count and Say.

Time Submitted	Status	Runtime	Memory	Language
a few seconds ago	Accepted	0 ms	9.1 MB	cpp

---

Review

暂缺

---

Tips

暂缺

---

Share

引言

本次内容是我自己写的, 因为前几天生病,这次准备仓促,还只是写了一半, 后面一半还没写出来, 先发一半吧, 下次把后面一半补上

Synchronized

---

End