Nav: << previous: 37.解数独 | next: 39.组合总和 >>
Description
tab: English
<p>The <strong>count-and-say</strong> sequence is a sequence of digit strings defined by the recursive formula:</p>
<ul>
<li><code>countAndSay(1) = "1"</code></li>
<li><code>countAndSay(n)</code> is the run-length encoding of <code>countAndSay(n - 1)</code>.</li>
</ul>
<p><a href="http://en.wikipedia.org/wiki/Run-length_encoding" target="_blank">Run-length encoding</a> (RLE) is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string <code>"3322251"</code> we replace <code>"33"</code> with <code>"23"</code>, replace <code>"222"</code> with <code>"32"</code>, replace <code>"5"</code> with <code>"15"</code> and replace <code>"1"</code> with <code>"11"</code>. Thus the compressed string becomes <code>"23321511"</code>.</p>
<p>Given a positive integer <code>n</code>, return <em>the </em><code>n<sup>th</sup></code><em> element of the <strong>count-and-say</strong> sequence</em>.</p>
<p> </p>
<p><strong class="example">Example 1:</strong></p>
<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 4</span></p>
<p><strong>Output:</strong> <span class="example-io">"1211"</span></p>
<p><strong>Explanation:</strong></p>
<pre>
countAndSay(1) = "1"
countAndSay(2) = RLE of "1" = "11"
countAndSay(3) = RLE of "11" = "21"
countAndSay(4) = RLE of "21" = "1211"
</pre>
</div>
<p><strong class="example">Example 2:</strong></p>
<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 1</span></p>
<p><strong>Output:</strong> <span class="example-io">"1"</span></p>
<p><strong>Explanation:</strong></p>
<p>This is the base case.</p>
</div>
<p> </p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>1 <= n <= 30</code></li>
</ul>
<p> </p>
<strong>Follow up:</strong> Could you solve it iteratively?
> [!tip]- Hint 1
>
> Create a helper function that maps an integer to pairs of its digits and their frequencies. For example, if you call this function with "223314444411", then it maps it to an array of pairs [[2,2], [3,2], [1,1], [4,5], [1, 2]].
> [!tip]- Hint 2
>
> Create another helper function that takes the array of pairs and creates a new integer. For example, if you call this function with [[2,2], [3,2], [1,1], [4,5], [1, 2]], it should create "22"+"23"+"11"+"54"+"21" = "2223115421".
> [!tip]- Hint 3
>
> Now, with the two helper functions, you can start with "1" and call the two functions alternatively n-1 times. The answer is the last integer you will obtain.
---
[submissions](https://leetcode.com/problems/count-and-say/submissions/) | [solutions](https://leetcode.com/problems/count-and-say/solutions/)
tab: 中文
<p>「外观数列」是一个数位字符串序列，由递归公式定义：</p>
<ul>
<li><code>countAndSay(1) = "1"</code></li>
<li><code>countAndSay(n)</code> 是 <code>countAndSay(n-1)</code> 的行程长度编码。</li>
</ul>
<p> </p>
<ul>
</ul>
<p><a href="https://baike.baidu.com/item/%E8%A1%8C%E7%A8%8B%E9%95%BF%E5%BA%A6%E7%BC%96%E7%A0%81/2931940">行程长度编码</a>（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。例如，要压缩字符串 <code>"3322251"</code> ，我们将 <code>"33"</code> 用 <code>"23"</code> 替换，将 <code>"222"</code> 用 <code>"32"</code> 替换，将 <code>"5"</code> 用 <code>"15"</code> 替换并将 <code>"1"</code> 用 <code>"11"</code> 替换。因此压缩后字符串变为 <code>"23321511"</code>。</p>
<p>给定一个整数 <code>n</code> ，返回 <strong>外观数列</strong> 的第 <code>n</code> 个元素。</p>
<p><strong>示例 1：</strong></p>
<div class="example-block">
<p><strong>输入：</strong>n = 4</p>
<p><strong>输出：</strong>"1211"</p>
<p><strong>解释：</strong></p>
<p>countAndSay(1) = "1"</p>
<p>countAndSay(2) = "1" 的行程长度编码 = "11"</p>
<p>countAndSay(3) = "11" 的行程长度编码 = "21"</p>
<p>countAndSay(4) = "21" 的行程长度编码 = "1211"</p>
</div>
<p><strong class="example">示例 2：</strong></p>
<div class="example-block">
<p><strong>输入：</strong><span class="example-io">n = 1</span></p>
<p><strong>输出：</strong><span class="example-io">"1"</span></p>
<p><strong>解释：</strong></p>
<p>这是基本情况。</p>
</div>
<p> </p>
<p><strong>提示：</strong></p>
<ul>
<li><code>1 <= n <= 30</code></li>
</ul>
<p> </p>
<strong>进阶：</strong>你能迭代解决该问题吗？
> [!tip]- 提示 1
>
> Create a helper function that maps an integer to pairs of its digits and their frequencies. For example, if you call this function with "223314444411", then it maps it to an array of pairs [[2,2], [3,2], [1,1], [4,5], [1, 2]].
> [!tip]- 提示 2
>
> Create another helper function that takes the array of pairs and creates a new integer. For example, if you call this function with [[2,2], [3,2], [1,1], [4,5], [1, 2]], it should create "22"+"23"+"11"+"54"+"21" = "2223115421".
> [!tip]- 提示 3
>
> Now, with the two helper functions, you can start with "1" and call the two functions alternatively n-1 times. The answer is the last integer you will obtain.
---
[提交记录](https://leetcode.cn/problems/count-and-say/submissions/) | [题解](https://leetcode.cn/problems/count-and-say/solution/)
Solutions & Notes
properties:
note.updated:
displayName: Last Updated
note.relative_links:
displayName: Related Links
note.desc:
displayName: Description
note.grade:
displayName: Rating
note.program_language:
displayName: Language
note.time_complexity:
displayName: TC
note.space_complexity:
displayName: SC
views:
- type: table
name: Solutions & Notes
filters:
and:
- file.hasLink(this.file)
- file.tags.containsAny("leetcode/solution", "leetcode/note")
order:
- file.name
- desc
- program_language
- time_complexity
- space_complexity
- grade
- relative_links
- updated
sort:
- property: grade
direction: ASC
- property: time_complexity
direction: ASC
- property: program_language
direction: ASC
columnSize:
file.name: 104
note.space_complexity: 65
note.grade: 126
Similar Problems
properties:
note.lcTopics:
displayName: Topics
note.lcAcRate:
displayName: AC Rate
note.favorites:
displayName: Favorites
note.grade:
displayName: Rating
note.translatedTitle:
displayName: Title (CN)
note.lcDifficulty:
displayName: Difficulty
views:
- type: table
name: Similar Problems
filters:
and:
- file.hasLink(this.file)
- similarQuestions.contains(this.file)
order:
- file.name
- translatedTitle
- lcTopics
- lcDifficulty
- lcAcRate
- grade
- favorites
sort:
- property: file.name
direction: ASC
- property: lcTopics
direction: DESC
columnSize:
note.translatedTitle: 240
note.lcTopics: 347
note.lcAcRate: 75
note.grade: 122