[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;
    }
};

您可能感兴趣的

_39 Combination Sum /** * Index: 39 * Title: Combination Sum * Author: ltree98 **/给一组数字 和 目标值;然后找出所有能组合成目标值的数字组合。 用一个简单的回溯就够了。 注意两点: 1. 给定的数字按...
直播预告|硅谷之路 – 程序员硬实力进阶... 是否看我的直播,已经从开始的新鲜而过渡到疲倦了呢?就仿佛回到高中,要按时上课写作业一样...恭喜你,再次进入了非舒适区。 不知不觉《硅谷之路》系列已经过去一个月,谢谢大家持续关注我的直播。因为准备要讲的内容还有很多,所以从本周开始,每周直播两次,每次时间会严格控制在一个半小时,尽量给大...
LeetCode 198 House Robber(基础DP) You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping y...
653. Two Sum IV – Input is a BST Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target...
Longest Continuous Increasing Subsequence 题目描述: LeetCode 674. Longest Continuous Increasing Subsequence Given an unsorted array of integers, find the length of longest...