乐趣区

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

jiezi

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

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

退出移动版