关于leetcode:Leetcode-PHP题解D139-38-Count-and-Say

D139 38. Count and Say

题目链接

38. Count and Say

题目剖析

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

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

至此应该了解了吧？

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

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

解题思路

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

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

1. 有始就是本人调本人，要在本人的娃外面再放个一样的娃
2. 有终就是要有终止条件，套到最小的娃之后再也套不上来了

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

他给定了一个数字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);
    }
}

若感觉本文章对你有用，欢送用爱发电赞助。