您现在的位置是:首页 > 正文

Count and Say --leetcode

2024-02-01 05:48:19阅读 2

Count and Say --leetcode

题目如下

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 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 sequence.

Note: The sequence of integers will be represented as a string.

题目的意思是要递推,求第N词出现的字符串.(提取句子中出现的数字,如下解析)

如第一次: 1 (1个1)

第二次,在一次的基础上1求: 1个1 11(2个1)

第三次在第二次的基础上11求: 2个1 21(1个2,1个1)

第四次在第三次的基础上21求: 1个2,1个1 1211(1个1,1个2,2个1)

第五次在第四次基础上1211求:1个1,1个2,2个1 111221

注意,如果出现相同的 ,如第四次有1211 ,后面两位11出现了重复,那么需要统计总次数2,就是2个1,没有出现重复的就用1个表示

代码思路就是采用递推的方法,初始为“1”,然后递推求的下一个字符串result,然后替换掉初始字符串,中间需要用一个count记录出现的重复次数,我们用上面的第四次求的第五次为例:

对于

  temp="1211"  此时初始的值

  result=”“  此时的值,中间值

然后用 j=0;while(j<temp.length())循环遍历 temp,用 t=j+1指向j的下一个字符,看看是不是相等,求的count的个数

第一次:  t指向2  此时 不 相等  那么count=1,  result=count+temp[j]=11;  令j=t;
第二次:j指向2,t指 向 1 , 此时不相等,那么count=1;result=count+temp[j]=11+12=1112;
第三次:j指向1,t指向1,相等,那么t继续往前,count+1,直到字符结束,count=2,result=1112+count+temp[j]=1112+2+1=111221

如下:


class Solution {
public:
    string countAndSay(int n) {

        if(n<1)
            return "";

        string temp="1";
        string result;

        for(int i=2;i<=n;i++)
        {
            result="";
            int j=0;
            while(j<temp.length())
            {
                int t=j+1;
                int count=1;

                while(t<temp.length()&&temp[j]==temp[t])
                {
                    count++;
                    t++;
                }

                result+=(count+'0');
                result+=temp[j];
                j=t;
            }

            temp=result;
        }

        return temp;

    }
};

网站文章

  • paddle-serving docker部署,dockerfile一键打镜像,一键启动容器

    一、服务端dockfile编写 节省镜像空间,此处在python的镜像基础上构建,最终镜像2.38G FROM python:3.7.4 COPY . /deploy WORKDIR /deploy ...

    2024-02-01 05:48:13
  • 2D空间求一点是否在多边形内

    2D空间求一点是否在多边形内

    转自:https://www.cnblogs.com/hont/p/6105997.html大致流程:1.随便选取多边形上任意一条边,以比较点和边的中心点做一条射线(这里用的伪射线)。2.用这条射线与...

    2024-02-01 05:47:43
  • docker化笔记二、镜像应用服务日志输出到宿主机器

    本章以日志为例进行说明,仅作抛砖引玉,实际项目不应该以这种方式去搜集日志(常用Syslog日志驱动类型,再用日志分析工具,比如ELK,进行获取搜集)。如果容器重新启动,使用docker logs看到的...

    2024-02-01 05:47:38
  • Java 限制前端重复请求

    Java 限制前端重复请求

    2024-02-01 05:47:33
  • Java:常用类解析5(正则表达式)

    正则表达式不仅仅是Java的技术,在任何一门编程语言中都会存在,是一种通用的IT技术。除了有一些由于语言不同而导致的一些语法不同,其理念和用法在任何编程语言中基本一致。正则表达式,主要用于匹配(查找 ...

    2024-02-01 05:47:00
  • 现在.net的web框架有哪些?

    https://www.zhihu.com/question/366937369

    2024-02-01 05:46:53
  • 【Linux】CentOS7 常用命令集合 热门推荐

    【Linux】CentOS7 常用命令集合 热门推荐

    这两天一直在对CentOS 7.2进行初体验,各种学习命令肿么用,不过其实大多和DOS是一样的,只是命令的表达上可能有点儿不一样,毕竟这些都不是一家出来的嘛~这里就分享一些近期我常用的CentOS命令给大家,方便学习~

    2024-02-01 05:46:24
  • 使用jdom获取xml中多个相同标签的值

    使用jdom获取xml中多个相同标签的值

    1.导入的maven包 <dependency> <groupId>dom4j</groupId> <artifactId>dom4j</artifactId> <version>1.6.1</version> </dependency> <dependency...

    2024-02-01 05:46:17
  • C温故补缺(九):字节对齐与排序

    C温故补缺(九):字节对齐与排序

    这样就可以把几个不同的对象用一个字节的二进制位域来表示。因为C语言有默认的对齐方式,段内按4字节对齐,所以虽然Data只用了两位,仍要申请4字节的内存。一般说,一个位域只能在一个字节中,一个字节可以有...

    2024-02-01 05:46:10
  • Android实现金额输入小数点

    Android实现金额输入小数点

    Android实现金额输入小数点。

    2024-02-01 05:46:03