The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 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, generate the nth sequence.
Note: The sequence of integers will be represented as a string.
逐个构建序列——根据第i-1个序列构建后第i个。理解题目意思后便知道在扫描前一个序列ret时,需要一个计数变量count记录当前字符重复的次数,以及需要一个字符变量prev记录上一个字符的值。当ret[i] = prev,则先不写入结果,而增加count。当ret[i] != prev时,说明prev的重复结束,需要将count和prev都写入结果,然后重置count为1,prev为ret[i]。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | class Solution { public: string countAndSay(int n) { if(n<1) return ""; string ret = "1"; for(int i=2; i<=n; i++) { string temp = ""; int count = 1; char prev = ret[0]; for(int j=1; j<ret.size(); j++) { if(ret[j]==prev) count++; else { temp += to_string(count); temp.push_back(prev); count = 1; prev = ret[j]; } } temp += to_string(count); temp.push_back(prev); ret = temp; } return ret; } }; |
事实上可以证明count不会超过4,所以这里的to_string(count)改成'0'+count也可以:
https://oj.leetcode.com/discuss/6762/how-to-proof-the-count-is-always-less-than-10
No comments:
Post a Comment