Q38 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"
解题思路:

说实话,第一次看到题目没读懂意思。后来在网上看有人解释才明白。

举个例子就明白了,比如输入6,6的上一个数是5,对应的字符串为 111221,这个111221读作 3个1,2个2,1个1,因此6对应的字符为312211。

观察了一下没有什么规律,因此简单方法就是从1一直找到要求的数字,不断的更新上一个字符串,然后生成当前的字符串。

因为要数多少个1、2,因此要有变量统计相同字符个数。

Python实现:
class Solution:
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        if n == 1:
            return '1'
        i = 1          # 从1开始构造
        lastStr = '1'  # 上一个字符串随着迭代次数更新
        while n > i:
            temp = ''  # 临时子串
            count = 0  # 统计相同字符的个数
            for j in range(len(lastStr)):  # 找出上一个字符串的特点,如 5 -> 111221
                if j > 0 and lastStr[j] != lastStr[j-1]:
                    temp += str(count) + lastStr[j-1] 
                    count = 1  # 重置count
                else:
                    count += 1              
            lastStr = temp + str(count) + lastStr[j]  # 构造当前字符串,如 6 -> 312211
            i += 1
        return lastStr

a = 7
b = Solution()
print(b.countAndSay(a))  # 13112221,因为6对应的字符串为312211

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏五分钟学算法

每天一算:Evaluate Reverse Polish Notation

我们会在每天早上8点30分准时推送一条LeetCode上的算法题目,并给出该题目的动画解析以及参考答案,每篇文章阅读时长为五分钟左右。

721
来自专栏恰童鞋骚年

剑指Offer面试题:13.调整数组顺序使奇数位于偶数前面

  例如有以下一个整数数组:12345,经过调整后可以为:15342、13542、13524等等。

1146
来自专栏desperate633

详解排序算法--堆排序选择排序堆排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩...

1203
来自专栏技术沉淀

Python: 函数式编程

1704
来自专栏数据结构与算法

P3373 【模板】线段树 2 区间求和 区间乘 区间加

题目描述 如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数加上x 2.将某区间每一个数乘上x 3.求出某区间每一个数的和 输入输出格式 输...

39911
来自专栏人工智能LeadAI

Python中对字节流/二进制流的操作:struct模块简易使用教程

前言 前段时间使用Python解析IDX文件格式的MNIST数据集,需要对二进制文件进行读取操作,其中我使用的是struct模块。查了网上挺多教程都写的挺好的,...

5385
来自专栏mathor

位与进制

 这里我假设读者有二进制的思维,知道(3)~10~=(011)~2~将十进制转换为二进制的方法

581
来自专栏数据结构与算法

06:整数奇偶排序

06:整数奇偶排序 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给定10个整数的序列,要求对其重新排序。排序要求: 1...

3936
来自专栏Python爬虫与算法进阶

Leetcode-Solutions 1.two-sum (Python&Golang)

恩,最后找队友一起刷题。喜欢可以联系我 ,来公众号“Python爬虫与算法进阶”找我哦

4119
来自专栏来自地球男人的部落格

[LeetCode] 523. Continuous Subarray Sum

【原题】 Given a list of non-negative numbers and a target integer k, write a fun...

2388

扫码关注云+社区

领取腾讯云代金券