D139 38. Count and Say

題目鏈接

38. Count and Say

題目分析

這道題有點(diǎn)裴波那切數(shù)列：

1. 先從數(shù)字?jǐn)?shù)字1開始，因?yàn)橛?個(gè)1，所以記作”11“；
2. 第二個(gè)呢，就把上面的”11“，再”轉(zhuǎn)換“成文字，即：兩個(gè)1，記作”21“；
3. 如此類推下去，第三個(gè)就是1個(gè)2，1個(gè)1，記作”1211“；
4. 繼續(xù)，1個(gè)1，1個(gè)2，2個(gè)1，111221；
5. 繼續(xù)，3個(gè)1，2個(gè)2，1個(gè)1，312211；
6. 繼續(xù)，13112221；
7. 繼續(xù)，1113213111；

至此應(yīng)該理解了吧？

為說像什么裴波那切數(shù)列呢，因?yàn)橄乱粋€(gè)的結(jié)果和上一個(gè)的結(jié)果是有關(guān)的。

題目會(huì)給一個(gè)數(shù)字n，要返回第n個(gè)的數(shù)字對應(yīng)的讀法。即，上面的列表序號是n，要返回”記作“的部分。

解題思路

既然像裴波那切數(shù)列，那就得需要用到遞歸了。

遞歸套娃有兩個(gè)特點(diǎn)不能忘記：有始有終

1. 有始就是自己調(diào)自己，要在自己的娃里面再放個(gè)一樣的娃
2. 有終就是要有終止條件，套到最小的娃之后再也套不下去了

終止條件需要先寫，要不然就無限套娃了。

他給定了一個(gè)數(shù)字n后，我們需要知道前一個(gè)數(shù)字是什么，所以我們需要先自己調(diào)用自己。調(diào)用自己的時(shí)候參數(shù)就需要n-1。

如果傳入的是數(shù)字1，那么我們要返回的就是數(shù)字1，或者字符串1。因?yàn)槲覀冞€沒有處理數(shù)字對應(yīng)的念法，因此不能返回”1個(gè)1"對應(yīng)的數(shù)字”11“。

好了，拿到數(shù)字1之后要得到它的念法，就需要知道元素個(gè)數(shù)和元素內(nèi)容。遍歷是跑不掉的了。

如果當(dāng)前數(shù)字和前一個(gè)數(shù)字相同，那么我們要計(jì)數(shù)。

當(dāng)和前面的數(shù)字不同時(shí)，結(jié)束計(jì)數(shù)，并把念法拼接到最終念法的末尾中。

由于第一個(gè)數(shù)字并沒有”前一個(gè)數(shù)字“，因此先記為NULL。只有當(dāng)前一個(gè)數(shù)字不是NULL時(shí)，才把念法拼接到最終念法的末尾。

最終代碼

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

若覺得本文章對你有用，歡迎用愛發(fā)電資助。