[Leetcode]_38 Count and Say

综合技术 2017-07-30 阅读原文

/**
 *  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博客

责编内容by:CSDN博客阅读原文】。感谢您的支持!

您可能感兴趣的

3个月用python刷完leetcode600题!-hash table简单题(一)... 十五天的时间,刷完了所有的简单题,避免遗忘,所以开始简单题的二刷,第一遍刷题的时候过得速度比较快,因为我觉得基础不好的我,不要硬着头皮去想最优的方法,而是应该尽量去学一些算法思想,所以每道题只给自己5-10分钟的时间想,想不出来的就去...
Hand of Straights 题目描述: LeetCode 846. Hand of Straights Alice has a hand of cards, given as an array of integer...
每日一则 LeetCode: Add Two Numbers 描述 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in revers...
LeetCode–Add Binary Given two binary strings, return their sum (also a binary string).For example, a = “11” b = “1” Return...
LeetCode solution – Rotate Image This is my own solution to the LeetCode problem – Rotate Image. Difficulty: medium.The idea is next: take each c...