分类: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"
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;
}
};
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;
}
};