count-and-say

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

<ul>
	<li><code>countAndSay(1) = &quot;1&quot;</code></li>
	<li><code>countAndSay(n)</code> is the run-length encoding of <code>countAndSay(n - 1)</code>.</li>
</ul>

<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>&quot;3322251&quot;</code> we replace <code>&quot;33&quot;</code> with <code>&quot;23&quot;</code>, replace <code>&quot;222&quot;</code> with <code>&quot;32&quot;</code>, replace <code>&quot;5&quot;</code> with <code>&quot;15&quot;</code> and replace <code>&quot;1&quot;</code> with <code>&quot;11&quot;</code>. Thus the compressed string becomes <code>&quot;23321511&quot;</code>.

Given a positive integer <code>n</code>, return the <code>nth</code> element of the count-and-say sequence.

&nbsp;
Example 1:

<div class="example-block">
Input: n = 4

Output: &quot;1211&quot;

Explanation:

<pre>
countAndSay(1) = &quot;1&quot;
countAndSay(2) = RLE of &quot;1&quot; = &quot;11&quot;
countAndSay(3) = RLE of &quot;11&quot; = &quot;21&quot;
countAndSay(4) = RLE of &quot;21&quot; = &quot;1211&quot;
</pre>
</div>

Example 2:

<div class="example-block">
Input: n = 1

Output: &quot;1&quot;

Explanation:

This is the base case.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 30</code></li>
</ul>

&nbsp;
Follow up: Could you solve it iteratively?

countAndSay

Count and Say

Encode and Decode Strings

encode-and-decode-strings

字符串的编码与解码

String Compression

string-compression

压缩字符串

String

「外观数列」是一个数位字符串序列，由递归公式定义：

<ul>
	<li><code>countAndSay(1) = "1"</code></li>
	<li><code>countAndSay(n)</code> 是&nbsp;<code>countAndSay(n-1)</code> 的行程长度编码。</li>
</ul>

&nbsp;

<ul>
</ul>

<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）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。例如，要压缩字符串&nbsp;<code>"3322251"</code>&nbsp;，我们将&nbsp;<code>"33"</code>&nbsp;用&nbsp;<code>"23"</code>&nbsp;替换，将&nbsp;<code>"222"</code>&nbsp;用&nbsp;<code>"32"</code>&nbsp;替换，将&nbsp;<code>"5"</code>&nbsp;用&nbsp;<code>"15"</code>&nbsp;替换并将&nbsp;<code>"1"</code>&nbsp;用&nbsp;<code>"11"</code>&nbsp;替换。因此压缩后字符串变为 <code>"23321511"</code>。

给定一个整数&nbsp;<code>n</code>&nbsp;，返回&nbsp;外观数列&nbsp;的第&nbsp;<code>n</code>&nbsp;个元素。

示例 1：

<div class="example-block">
输入：n = 4

输出："1211"

解释：

countAndSay(1) = "1"

countAndSay(2) = "1" 的行程长度编码 = "11"

countAndSay(3) = "11" 的行程长度编码 = "21"

countAndSay(4) = "21" 的行程长度编码 = "1211"
</div>

示例 2：

<div class="example-block">
输入：n = 1

输出："1"

解释：

这是基本情况。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 30</code></li>
</ul>

&nbsp;
进阶：你能迭代解决该问题吗？