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

skys215 - 2022-07-13 00:22:27

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);
    }
}

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

特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。