综合技术

[Leetcode]_38 Count and Say

微信扫一扫,分享到朋友圈

[Leetcode]_38 Count and Say
0
/**
 *  Index: 38
 *  Title: Count and Say
 *  Author: ltree98
 **/

题目意思是,输出某序列的值。

这个序列,有些类似于 斐波那契数列 —— 后面的值由前面的值决定。

index   ->      ans     |   规则(后面的根据上一个,连续的数字做组合)
1       ->      1       |   第一个 
2       ->      11      |   前一个 1,只有一部分,1个1 即 11
3       ->      21      |   前一个,就是 11; 连续的数字看做一组来读, 所以只有一部分, 2个1 即 21
4       ->      1211    |   两部分, 2 和 1; 1个2 即 12, 1个1 即 11; 连起来 1211
5       ->      111221  |   分成3部分, 1 和 2 和 11; 1个1 即 11, 1个2 即 12, 2个1 即 21; 连起来 111221
6       ->      312211  |   分成3部分, 111 和 22 和 1; 3个1 即 31,2个2 即 22, 1个1 即 11; 连起来 312211
...

总结起来,就是先把前一个分成几个部分,然后开始读,最后拼起来。

再总结就是,

1、把前一个字符串从前开始读,如果下一个字符和本个字符一样,继续读,并记录数量,直到不一样。

2、读一下,记录到答案中

3、回到第1步

class Solution {
public:
    string countAndSay(int n) {
        if(n <= 1) 
            return "1";

        string pre = countAndSay(n-1);
        string ans = "";

        for(int i = 0; i < pre.length(); )  {
            int j = i+1;
            for(; j < pre.length(); j++)
                if(pre[i] != pre[j])
                    break;
            int n = j-i;
            ans = ans + to_string(n) + pre[i];
            i = j;
        }
        return ans;
    }
};
阅读原文...

CSDN博客

“打假是最大的公益”,阿里首场“神秘抽检”正品拍卖收入超8万,全部捐建“梦想教室”

上一篇

希尔顿酒店集团第二季度销售收入和利润均高于预期,再次上调 2017全年预测

下一篇

您也可能喜欢

评论已经被关闭。

插入图片
[Leetcode]_38 Count and Say

长按储存图像,分享给朋友