凌云的博客

LeetCode 算法题 38. 外观数列

分类：algorithm| 发布时间：2016-09-30 10:15:00

---

题目

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 被读作  "one 1"  ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2",  "one 1" （"一个二" ,  "一个一") , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。

注意：整数序列中的每一项将表示为一个字符串。

示例 1:

输入: 1
输出: "1"

示例 2:

输入: 4
输出: "1211"

解法 1

class Solution {
public:
    string countAndSay(int n) {
        static map<int,char> m{{1,'1'},{2,'2'},{3,'3'},{4,'4'},{5,'5'},{6,'6'},{7,'7'},{8,'8'},{9,'9'}};
        queue<int>q;
        q.push(1);
        string result;
        int temp = 1,num=0,length;
        for(int i=2;i<=n;i++) {
            length = q.size();
            while(length>0) {
                num = 0;
                while(q.front() == temp && length>0) {
                    num++;
                    q.pop();
                    length--;
                }
                q.push(num);
                q.push(temp);
                temp = q.front();
            }
        }

        while(!q.empty()) {
            result += m[q.front()];
            q.pop();
        }
        return result;
    }
};

解法 2

class Solution {
public:
    string countAndSay(int n) {
        string ret = "1";
        stringstream ss;
        char c;
        int count, size;
        while (--n > 0) {
            c = ret[0];
            count = 1;
            size = ret.size();
            ss.str("");
            for (int i = 1; i < size; ++i) {
                if (c != ret[i]) {
                    ss << count << c;
                    c = ret[i];
                    count = 1;
                } else {
                    ++count;
                }
            }

            ss << count << c;
            ret = ss.str();
        }

        return ret;
    }
};