03
05/2015
[LeetCode] Count and Say
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.
解题思路：
这道题的题意就是按某种顺序产生某一位的字符串，其规则是：
若n=1，那么为s[n]="1"
若n>0，那么逐个读取s[n-1]中相同的字符，然后说k个这个字符，直到s[n-1]读玩为止。比如111221可以这么读，3个1，2个2，1个1，于是下一个字串为312211。
显然用递归最合适。
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 27 | class Solution {public: string countAndSay(int n) { if(n==1){ return "1"; } string s=countAndSay(n-1); int len=s.length(); string result=""; char lastChar=s[0]; int count=1; char charNum; for(int i=1; i<len; i++){ if(s[i]==lastChar){ count++; continue; } charNum = count + '0'; result = result + charNum + lastChar; lastChar=s[i]; count=1; } charNum = count + '0'; result = result + charNum + lastChar; //注意这里有个陷阱，在循环外需要这么加 return result; }}; |
二次刷题（update in 2015-07-31）
非递归算法：
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 27 28 29 30 31 32 | class Solution {public: string countAndSay(int n) { if(n==0){ return ""; } string result = "1"; for(int i = 1; i<n; i++){ string temp = ""; int len = result.length(); char preChar = result[0]; int count = 1; int j=1; while(j<len){ if(preChar == result[j]){ count++; }else{ temp += std::to_string(count) + preChar; count = 1; preChar = result[j]; } j++; } //最后一个别忘了 temp += std::to_string(count) + preChar; result = temp; } return result; }}; |
转载请注明：康瑞部落 » [LeetCode] Count and Say
0 条评论