问题

给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。

注意：整数序列中的每一项将表示为一个字符串。

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

第n项外观数列说明11第一项是数字 1211描述前一项，这个数是 1 即 “一个 1 ”，记作 11321描述前一项，这个数是 11 即 “两个 1 ” ，记作 2141211描述前一项，这个数是 21 即 “一个 2 一个 1 ” ，记作 12115111221描述前一项，这个数是 1211 即 “一个 1 一个 2 两个 1 ” ，记作 111221

示例 1:

输入: 1 输出: “1” 解释：这是一个基本样例。

示例 2:

输入: 4 输出: “1211” 解释：当 n = 3 时，序列是 “21”，其中我们有 “2” 和 “1” 两组，“2” 可以读作 “12”，也就是出现频次 = 1 而 值 = 2；类似 “1” 可以读作 “11”。所以答案是 “12” 和 “11” 组合在一起，也就是 “1211”。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/count-and-say

解法

一、循环计数法

当n为1时，直接返回1；

当n为2时，

记录到上一个字符串是1，直接记录第一个字母的单词为上一个值，数量为1当第i个字母出现时，跟第i-1个字母比较。如果不一致，则保存记录到字符串中 数量.上一个字母 ，数量改为1，并保存当前值为上一个字母；如果一致，则数量+1当不存在第i个字母时，代表字符串已获取结束，将当前的字母和其数量记录到字符长中，再将该字符串改为上个字符串 class Solution { /** * @param Integer $n * @return String */ function countAndSay($n) { if ($n === 1) { return '1'; } //从$n=2开始，默认初始时'1' $perStr = '1'; for ($i = 1; $i < $n; $i++) { $perVal = $perStr[0]; //初始化每一轮外观数列的第1个值 $returnStr = ''; //当前一轮返回的外观数列，每轮开始时清空重来 $ind = 1; //每一轮的计算从第二个字符开始进行比较 $valCount = 1; while (true) { if (!isset($perStr[$ind])) { //当字母不存在，则会跳出循环，来到这里 $perStr = $returnStr . $valCount . $perVal; break; } //第$ind个字母$perStr[$ind]跟上一个字母$perVal比较 if ($perStr[$ind] !== $perVal) { $returnStr .= $valCount . $perVal; $perVal = $perStr[$ind]; $valCount = 1; } else { $valCount++; } $ind++; } } return $perStr; } }

二、正则表达式法

/(\d)\1*/g (反向引用)可以捕获相同数字。使用preg_match函数，如果抓取到数字的话将会返回数组，如：

$perStr = '11111'; preg_match('/(\d)\1*/', $perStr, $result); print_r($result);

输出结果

Array ( [0] => 11111 [1] => 1 )

通过数组下标0的字符串长度，我们就能知道连续数字的个数，而下标1的字符就是连续的数字了。 套用下上面的循环计数法上去：

class Solution { /** * @param Integer $n * @return String */ function countAndSay($n) { if ($n === 1) { return '1'; } $perStr = '1'; for ($i = 1; $i < $n; $i++) { $result_str = ''; while (true) { preg_match('/(\d)\1*/', $perStr, $result); $result_str .= strlen($result[0]) . $result[1]; $perStr = substr($perStr, strlen($result[0])); if (empty($perStr)) { break; } } $perStr = $result_str; } return $perStr; } }

三、递归法

当n=1时，返回结果一定是1，这也就是递归的终止出口。为方便理解递归，将循环体部分提取出来，只做返回结果字符串

class Solution { /** * @param Integer $n * @return String */ function countAndSay($n) { //当$n=1时，返回的结果就是1，递归循环体的唯一返回路径 if ($n === 1) { return '1'; } //循环体，当$n-1=1时，就一定会得到上面的1，然后调用say方法拿到1个1，变成21，在调用本方法，将调用say方法对21进行处理…… return $this->say($this->countAndSay($n - 1)); } /** * @title 获取某字符串的外观数列 * @param $perStr * @return string */ function say($perStr) { $result_str = ''; while (true) { preg_match('/(\d)\1*/', $perStr, $result); $result_str .= strlen($result[0]) . $result[1]; $perStr = substr($perStr, strlen($result[0])); if (empty($perStr)) { break; } } return $result_str; } }