[leetcode] Count and Say


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.

tag: string

不难,关键是理解题意。我觉得这个题意不太清楚……

比如,对于序列111221,我们会把它读成:3个1,2个2,1个1.于是就写成312211.

对于序列312211,我们会把它读成:1个3,1个1,2个2,2个1,。于是就写成13112221

以此类推。

向优化过的动态规划一样,该算法维护动态规划矩阵的两行lastRow 和row。每次从lastRow中推演出row,然后把row存进lastRow中,不断迭代。

class Solution {
public:
    string countAndSay(int n) {
        string lastRow;
        string row("1");
        for(int i = 1; i < n; i++){
            int j = 0;
            lastRow = row;
            row.clear();
            while(j < lastRow.size()){
                int count = 0;
                char c = lastRow[j];
                while(lastRow[j] == c && j < lastRow.size()){
                    count++;
                    j++;
                }
                row.append(to_string(count));
                row.push_back(c);
            }
        }
        return row;
    }
};

Untitled

 

 

 

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.