题目描述中:
等级为 L 的汉堡(L≥0)按如下方式定义:
等级 0 汉堡:只有 一层肉饼(记作 P)。
等级 L 汉堡(L≥1):自下而上依次为:面包 B、等级 L−1 汉堡、肉饼 P、等级 L−1 汉堡、面包 B。
据此描述:
等级0汉堡:P
等级1汉堡:BPPPB,前1层0个肉饼(测试样例2)
等级2汉堡:BBPPPBPBPPPB,前7层4个肉饼(测试样例1)
这样就理顺了。
样例解释中提示:等级 50 汉堡的层数已经大到无法用 32 位整数表示。
显然依靠存储等级N的汉堡样式再进行输出是一定会超出存储范围的。因此不能存储实际样式,只能使用数据关系推断。
等级 n (n≥1)汉堡:面包 B、等级 n−1 汉堡、肉饼 P、等级 n−1 汉堡、面包 B。
查找前x层的肉饼(字符P)数量。
如果x的数值小于等于等级n汉堡层数的一半,则可将问题转化为:等级 n−1 汉堡的前x-1层中肉饼的数量;否则,问题可转化为:等级 n−1 汉堡中肉饼的数量+等级n-1汉堡中前 x-2-(等级 n−1 汉堡的层数)。
显然需要先计算每个等级汉堡的层数。
代码如下:
通过率:70%,没通过的原因是因为超时。分析:递归调用中存在重复计算,会导致超时,但X最大超过int范围,显然也无法用二维数组存储某个等级汉堡下前X层中肉饼数量。突然悟了,虽然无法存储所有情况,但存储某个等级汉堡中总肉饼数量还是可以实现的,应该也可以有效降低重复计算次数。
更新迭代代码如下: