[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博客阅读原文】。感谢您的支持!

您可能感兴趣的

leetcode题解(数组问题) 面试中的算法问题,有很多并不需要复杂的数据结构支撑。就是用数组,就能考察出很多东西了。其实,经典的排序问题,二分搜索等等问题,就是在数组这种最基础的结构中处理问题的,今天主要学习常见的数组中处理问题的方法。 数组中的问题其实最常见。 ...
【LeetCode题解】206_反转链表 目录 206_反转链表 描述 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL...
关于校招的疑难解答 你好,我看了你写的 秋招总结 ,对整个过程的经验和遇到的问题都有很深入的思考,回顾我当年进入前端这个职业方向同样也遇到相似的问题,如今觉得尤其需要对自己的每一步都要做好计划和准备,才会在面临挑战的时候不乱阵势,胸有成竹。现在我通过对每个我...
LeetCode 628. Maximum Product of Three Numbers Maximum Product of Three Numbers 题目描述: Given an integer array, find three numbers whose product is maximum and ...
Leetcode: Insert into a Binary Search Tree Insert into a Binary Search Tree Similar Problems: Tag:#binarytree Given the root n...