Leetcode PHP题解--D139 38. Count and Say

D139 38. Count and Say

题目链接

38. Count and Say

题目分析

这道题有点裴波那切数列：

先从数字数字1开始，因为有1个1，所以记作”11“；
第二个呢，就把上面的”11“，再”转换“成文字，即：两个1，记作”21“；
如此类推下去，第三个就是1个2，1个1，记作”1211“；
继续，1个1，1个2，2个1，111221；
继续，3个1，2个2，1个1，312211；
继续，13112221；
继续，1113213111；

至此应该理解了吧？

为说像什么裴波那切数列呢，因为下一个的结果和上一个的结果是有关的。

题目会给一个数字n，要返回第n个的数字对应的读法。即，上面的列表序号是n，要返回”记作“的部分。

解题思路

既然像裴波那切数列，那就得需要用到递归了。

递归套娃有两个特点不能忘记：有始有终

有始就是自己调自己，要在自己的娃里面再放个一样的娃
有终就是要有终止条件，套到最小的娃之后再也套不下去了

终止条件需要先写，要不然就无限套娃了。

他给定了一个数字n后，我们需要知道前一个数字是什么，所以我们需要先自己调用自己。调用自己的时候参数就需要n-1。

如果传入的是数字1，那么我们要返回的就是数字1，或者字符串1。因为我们还没有处理数字对应的念法，因此不能返回”1个1"对应的数字”11“。

好了，拿到数字1之后要得到它的念法，就需要知道元素个数和元素内容。遍历是跑不掉的了。

如果当前数字和前一个数字相同，那么我们要计数。

当和前面的数字不同时，结束计数，并把念法拼接到最终念法的末尾中。

由于第一个数字并没有”前一个数字“，因此先记为NULL。只有当前一个数字不是NULL时，才把念法拼接到最终念法的末尾。

最终代码

<?php
class Solution {

    /**
     * @param Integer $n
     * @return String
     */
    function countAndSay($n) {
        if($n == 1){
            return '1';
        }
        $str = $this->countAndSay($n-1);
        $arr = str_split($str);
        $counts = [];
        $prev = NULL;
        $count = 0;
        foreach($arr as $key => $val){
            if($val == $prev){
                $count++;
            }
            else{
                if(!is_null($prev)){
                    $counts[] = $count.$prev;
                }
                $prev = $val;
                $count = 1;
            }
        }
        $counts[] = $count.$prev;
        return implode($counts);
    }
}

若觉得本文章对你有用，欢迎用爱发电资助。