首页 > 代码库 > LeetCode: Count and Say [037]

LeetCode: Count and Say [037]

【题目】


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规则生成。
          所谓count-and-say就是数数然后读出来,按照读法来组织新的数。举个例子来说
          1     读成“1个1” ==>  11
          11    读成“2个1” ==> 21
          21    读成“1个2,1个1” ==> 1211
          
          目标是返回序列中的第n个数


【思路】

          按规则顺序生成序列中的前n个数


【代码】

class Solution {
public:
    string getNext(string integer){
        int count=0;
        char digit=‘\0‘;
        string newInteger="";
        for(int i=0; i<integer.length(); i++){
            if(integer[i]!=digit){
                if(digit!=‘\0‘){
                    char countChar=‘0‘+count;
                    newInteger+=countChar;
                    newInteger+=digit;
                }
                count=1;
                digit=integer[i];
            }
            else{
                count++;
            }
        }
        if(digit!=‘\0‘){
            char countChar=‘0‘+count;
            newInteger+=countChar;
            newInteger+=digit;
        }
        return newInteger;
    }
    string countAndSay(int n) {
        int count=1;
        string integer="1";
        if(n<1)return "";   //考虑一些非法值,题目没有规定,那就设定为空
        if(n==1)return integer;
        
        while(count<n){
            integer=getNext(integer);
            count++;
        }
        return integer;
    }
};