首页 > 其他分享 >38.外观数列(中等)

38.外观数列(中等)

时间:2023-10-29 13:12:29浏览次数:45  
标签:pre 外观 38 end 数列 start countAndSay 描述 cur

目录

题目

  • 给定一个正整数 n ,输出外观数列的第 n 项。

「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列:

countAndSay(1) = "1"
countAndSay(n) 是对 countAndSay(n-1) 的描述,然后转换成另一个数字字符串。
前五项如下:

  1. 1
    
  2. 11
    
  3. 21
    
  4. 1211
    
  5. 111221
    

第一项是数字 1
描述前一项,这个数是 1 即 “ 一 个 1 ”,记作 "11"
描述前一项,这个数是 11 即 “ 二 个 1 ” ,记作 "21"
描述前一项,这个数是 21 即 “ 一 个 2 + 一 个 1 ” ,记作 "1211"
描述前一项,这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ,记作 "111221"

要 描述 一个数字字符串,首先要将字符串分割为 最小 数量的组,每个组都由连续的最多 相同字符 组成。然后对于每个组,先描述字符的数量,然后描述字符,形成一个描述组。要将描述转换为数字字符串,先将每组中的字符数量用数字替换,再将所有描述组连接起来。

例如,数字字符串 "3322251" 的描述如下图:

示例 1:

输入:n = 1
输出:"1"
解释:这是一个基本样例。

示例 2:

输入:n = 4
输出:"1211"
解释:
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"

法一、双指针

class Solution:
    def countAndSay(self, n: int) -> str:
        pre = ''#前一个串
        cur = '1'#初始化当前串

        # 从第 2 项开始
        for _ in range(1, n):
            # 这里注意要将 cur 赋值给 pre
            pre = cur
            # 这里 cur 初始化为空,重新拼接
            cur = ''
            # 定义双指针 start,end
            start = 0
            end = 0
            # 开始遍历前一项,开始描述
            while end < len(pre):
                # 统计重复元素的次数,出现不同元素时,停止
                # 记录出现的次数,
                while end < len(pre) and pre[start] == pre[end]:
                    end += 1
                # 元素出现次数与元素进行拼接
                cur += str(end-start) + pre[start]
                # 这里更新 start,开始记录下一个元素
                start = end
        
        return cur

法二、递归

def countAndSay(self, n: int) -> str:
    if n == 1:
        return '1'
    s = self.countAndSay(n-1)
    
    i, cur = 0, ''
    for j, c in enumerate(s):
        if c != s[i]:#当前字符不等于i指针指向的字符
            cur += str(j-i) + s[i] # 元素出现次数与元素进行拼接
            i = j#更新,记录下一个元素
    cur += str(len(s) - i) + s[-1]  # 最后一个元素莫忘统计
    return cur

标签:pre,外观,38,end,数列,start,countAndSay,描述,cur
From: https://www.cnblogs.com/lushuang55/p/17794603.html

相关文章

  • python---数列内元素正倒相加实例
    a=list([1,21,5,3,1,23])b=list([7,4,6,3,2,1])x=int(input("请输入想从第几个数开始:"))y=int(input("请输入想到第几个数结束:"))c=[0,0,0,0,0,0]m=input("想要正着加吗?(T/F)")foriinrange(x-1,y):ifm=="T":c=a[i]+b[i]......
  • 斐波那契数列 (指针)
    //指针#include<bits/stdc++.h>usingnamespacestd;intsum(int*a){intb=*a-1,c=*a-2;if(*a<=2){return1;}else{returnsum(&b)+sum(&c);}}intmain(){intx,a;cin>>a;x=sum(&a);......
  • 斐波那契数列--按值--地址--指针
    //按值#include<bits/stdc++.h>usingnamespacestd;intsum(inta){ if(a<=2){ return1; }else{ returnsum(a-1)+sum(a-2); } }intmain(){ intx,c,d; cin>>c; x=sum(c); cout<<x; return0;}//地址#include<bits/stdc++.h&g......
  • 斐波那契数列(指针传递)
    #include<bits/stdc++.h>usingnamespacestd;intNUM(int*a){intb=*a-1;intc=*a-2;if(*a<=2)return1;elsereturnNUM(&b)+NUM(&c);}intmain(){intNUMx,NUMy;cin>>NUMx;cout<<N......
  • 斐波那契数列&数值传递
    #include<iostream>usingnamespacestd;intp1(inta){ if(a<=2){ return1; }else{ returnp1(a-1)+p1(a-2); }}intmain(){ intn; cin>>n; cout<<p1(n); return0;} #include<iostream>usingnamespacestd;int......
  • 斐波那契数列 (地址)
    //地址#include<bits/stdc++.h>usingnamespacestd;intsum(int&a){intb,c;b=a-1;c=a-2;if(a<=2){return1;}else{returnsum(b)+sum(c);}}intmain(){intx,a;cin>>a;x=sum(a);......
  • 聊城申请外观专利需要的时间
    聊城申请外观专利需要的时间恒标知产刘经理1、咨询确定发明创造的内容是否属于可以申请专利的内容;对此咨询,建议多咨询几家专利代理机构后对比确定正确的结论。因为当前很多的专利代理机构的资讯接待员是的工资都是提成制的,为了业务量,有时对咨询会有不恰当的回复。确定发明创造的内......
  • c语言代码练习38
    问:实现字符串的拷贝#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>#include<assert.h>#include<string.h>intmain(){chararr1[]="abcdef";chararr2[]="bit";strcpy(arr1,arr2);printf("%s&q......
  • 结构型模式(三) 外观模式
    外观模式:是为了给子系统中的一组接口提供一个一致的界面,外观模式定义了一个高层接口,这个接口使得子系统更加容易使用。减少系统之间的耦合性,提高了灵活性和安全性角色:外观类、子系统类classCpu:defstart(self):print('cpustart')defstop(self):......
  • centos7 tar包安装jdk-8u381
    1、解压包tar-zxvfjdk-8u381-linux-x64.tar.gz-C/usr/local/2、配置环境变量cat<<EOF>>/etc/profileexportJAVA_HOME=/usr/local/jdk/jdk1.8.0_381exportJRE_HOME=/usr/local/jdk/jdk1.8.0_381/jreexportPATH=$PATH:$JAVA_HOME/bin:$JRE_HOME/binEOFs......