歡迎光臨
每天分享高質量文章

一個今日頭條筆試題的答題思路

(點擊上方快速關註並設置為星標,一起學Python)

來源:JeannieLi    鏈接:

http://www.cnblogs.com/xdliyin/p/10778583.html

頭條筆試題:

母牛從3-7歲初每年會生產1頭小母牛,10歲後死亡(10歲仍然存活),假設初始有1頭剛出生的母牛,請問第n年有多少頭母牛?(年從第一年開始計數)

解題思路:

在沒有任何思路的情況下,可以先暴力分析,順著題意將給出的示例推匯出來,然後再從中觀察規律,找到更為便捷的方法;

1. 先暴力分析:從第一年開始,計算每年的母牛個數;

基本思路:以最開始的母牛為基準進行分析,分析每年它生產的孩子的個數,最後加1 就是每年牛的個數;

觀察上述分析結果,我們會發現:有很多重覆地方,即母牛這題含有重覆子結構,最常用的方法就是:用陣列變數,將重覆的地方記錄下來。

(1)sum:記錄每次的求和部分

(2)opt[ i ]:記錄第 i 年母牛的個數, opt[ -1] :表示最終的輸出結果

(3)一次迴圈遍歷,記錄 sum 和 opt[ i ],時間複雜度:O(n)

Python代碼:

# 母牛生產
import sys
for line in sys.stdin:
    n = int(line)
    if n < 3:
        print('1')
    else:
        opt = [0 for i in range(n + 1)]
        opt[0] = -1
        opt[1] = 1
        opt[2] = 1

        sum = 0
        for i in range(3, n+1):
            if i >=  3 and i <=7:
                sum = sum + opt[i - 2]
                opt[i] = sum + 1

            elif i >= 8 and i <= 10:
                sum = sum - opt[i-7] + opt[i-2]
                opt[i] = sum + 1

            else:
                sum = sum - opt[i-7] + opt[i-2]
                opt[i] = sum

        print(opt[-1])


    已同步到看一看
    赞(0)

    分享創造快樂