乐趣区

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

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

退出移动版