leetcode-38-Count and Say

题目描述:

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     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 term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

要完成的函数:

string countAndSay(int n) 

代码:

#include<string>
#include<sstream>
    string int2str(int &i)//实现从int到string的转换
    {
        string s;
        stringstream ss(s);
        ss << i;
        return ss.str();
    }
    int count(string a,int b,int index)//在a中,从index这个位置开始,有多少个数字为b的,返回这个数量
    {
        int result=0;
        for(int i=index;i<a.size();i++)
        {
            if(a[i]==b)
            result++;
            else
            break;
        }
        return result;
    }
    string countAndSay(int n) //主要函数
    {
            string result="1";
        string result1;
        int result2;
        if(n==1)
        {
            return result;
        }
        while(--n)
        {
            int i=0;
            result1="";
            while(i<result.size())
            {
                result2=count(result,result[i],i);
                result1+=int2str(result2);
                result1+=result[i];
                i+=result2;
            }
            result=result1;
        }
        return result;
    }

说明:

1、这道题可能有的朋友不太明白题目在讲什么,说一下。

首先,n=1的时候,输出“1”的序列。

n=2的时候,上一个序列中,从第一个数字开始,直到最后一个数字。数一下上一个序列有多少个连续的1,答案是“1”个“1”,所以输出“11”的序列。

n=3的时候,上一个序列中,从第一个数字开始,直到最后一个数字。数一下上一个序列有多少个连续的1,答案是“2”个“1”,所以输出“21”的序列。

n=4的时候,上一个序列中,从第一个数字开始,直到最后一个数字。数一下上一个序列有多少个连续的2,答案是“1”个“2”,所以输出12;数一下上一个序列中有多少个连续的1,答案是“1”个“1”,所以输出11。合起来就是“1211”。

n=5的时候,上一个序列中,从第一个数字开始,直到最后一个数字。数一下上一个序列有多少个连续的1,答案是“1”个“1”,所以输出“11”,数一下上一个序列中有多少个连续的2,答案是“1”个“2”,所以输出“12”,数一下上一个序列中有多少个连续的1,答案是“2”个“1”,所以输出“21”。合起来就是“111221”。

看明白之后,本题采用最暴力的方法去做,定义了三个函数。每个函数的功能都在注释中写了。自己跑一遍应该就看出来了。

2、c++的int2str在c++11中可以to_string(int)输出,比如cout<<to_string(123)+"908"<<endl;可以得到123908的输出。

但在c++11之前,就要使用#include<sstream>中的方法,像本文那样使用就可以了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ1562: [NOI2009]变换序列(二分图 匈牙利)

30%的数据中N≤50; 60%的数据中N≤500; 100%的数据中N≤10000。

941
来自专栏chenjx85的技术专栏

leetcode-485-Max Consecutive Ones

1565
来自专栏JetpropelledSnake

Python入门之@classmethod与@staticmethod

本章内容:     1. @classmethond     2. @staticmethod ================================...

3976
来自专栏前端小吉米

JS 完美的 AOP 编程

1624
来自专栏Debian社区

Python的闭包和装饰器

装饰器(Decorator)相对简单,咱们先介绍它:“装饰器的功能是将被装饰的函数当作参数传递给与装饰器对应的函数(名称相同的函数),并返回包装后的被装饰的函数...

1054
来自专栏追不上乌龟的兔子

使用functools.singledispatch装饰器简化复杂的类型判断

这个方案已经算是很简洁了,但还是用了if语句进行类型判断。现在我们借用functools.singledispatch()函数装饰器和类型注解,可以将上面的逻辑...

1252
来自专栏Bingo的深度学习杂货店

Q88 Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one s...

3314
来自专栏http://www.cnblogs.com

装饰器

一。关于装饰器: 定义:本质是函数,(装饰其他函数)就是为其他函数添加附加功能 原则:1.不能修改被装饰函数的源代码 2.不能修改被装饰函数的调用方式 二.实现...

3107
来自专栏散尽浮华

Python内置函数

内置函数之一:lambda表达式 前面知识回顾: 三目运算: #普通条件语句 1: if 1 == 1: 2: name ='曹小贱' 3:...

2155
来自专栏chenjx85的技术专栏

leetcode-645-Set Mismatch

22611

扫码关注云+社区

领取腾讯云代金券