当前位置:聪少自媒体网 > 今日头条 > 正文

一个今日头条笔试题的答题思路

2020-10-05 今日头条 聪少自媒体

原标题:一个今日头条笔试题的答题思路

头条笔试题:

母牛从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])

本分分享自网络,原文地址:http://www.cnblogs.com/xdliyin/p/10778583.html返回搜狐,查看更多

责任编辑:

聪少爱学堂聪少
聪少爱学堂创始人,梅州市鹏鑫网络科技有限公司CEO,09年开始踏入互联网,10年互联网行业经验,资深自媒体人,自媒体优秀导师,咪挺微商团对营销引流顾问,业务包含:精准引流技术/代引流精准粉,专业小红书,知乎,微博代运营。
  • 38988文章总数
  • 1491133访问次数
  • 建站天数
  • 合作伙伴