首页 > 代码库 > Count and Say

Count and Say

2024-07-17 08:25:09   224人阅读

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.

分析：Count and Say的意思就是对于(n-1)th string，从左到右，count连续相同数字并且say，所以解决此问题的关键是得到第(n-1)个string，并且从左到右统计连续相同数字的个数并将结果存储在一个string中。既可以用递归也可以用迭代。

递归代码如下：

 1 class Solution { 2 public: 3     string countAndSay(int n) { 4         string res; 5         if(n <= 0) return res; 6         if(n == 1) res = "1"; 7         else{ 8             string last = countAndSay(n-1); 9             int count = 0;10             char pre = ‘ ‘, cur = ‘ ‘;11             12             for(int i = 0; i < last.length(); i++){13                 cur = last[i];14                 if(pre != cur) {15                     if(i > 0){16                         res.push_back(‘0‘+count);17                         res.push_back(pre);18                     }19                     count = 1;20                 }else count++;21                 pre = cur;22             }23             //push back last character24             res.push_back(‘0‘+count);25             res.push_back(cur);26         }27         return res;28     }29 };

在上面的代码中，是用pre和cur是否相等来判断是否是连续相同数字的，当pre与cur不同时，将pre的统计结果加入到result中。在这里需要注意cur是第一个和最后一个的情况。当cur是第一个时, pre 不等于 cur，但这时并不能将cur的统计结果加到res string中。当cur是最后一个时，因为cur后面没有字符，所以在for循环结束后需要将最后一个字符的统计结果加入到res string中。

迭代版代码：

 1 class Solution { 2 public: 3     string countAndSay(int n) { 4         string res; 5         if(n <= 0) return res; 6         string pre = "1"; 7         res="1"; 8         for(int i = 2; i <= n; i++){ 9             char cpre = ‘ ‘, ccur = ‘ ‘;10             int count = 0;11             pre = res;12             res.clear();13             for(int j = 0; j < pre.length(); j++){14                 ccur = pre[j];15                 if(cpre != ccur){16                     if(j > 0){17                         res.push_back(‘0‘+count);18                         res.push_back(cpre);19                     }20                     count = 1;21                 }else count++;22                 cpre = ccur;23             }24             res.push_back(‘0‘+count);25             res.push_back(ccur);26         }27         return res;28     }29 };

 


联系
我们