题解 | #牛妹的蛋糕#

算法思想一：迭代

解题思路：

由题可知，每天的蛋糕数量等于前一天蛋糕数量去除三分之一再加一个；反过来，每天的蛋糕数量等于后一天数量加1的 3/2 倍计算

因此可以采用迭代从n-1天到第一天的蛋糕数量

图解：

步骤	n	计算	蛋糕数量
1	4		1
2	3	(1+1)*3/2	3
3	2	(3+1)*3/2	6
4	1	(6+1)*3/2	10

最后返回：第一天吃蛋糕时一共有10个

代码展示：

JAVA版本

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
     * @return int整型
     */
    public int cakeNumber (int n) {
        // write code here
        int x = 1;
        // 迭代计算n-1天到第1天蛋糕数量
        for (int i = 0; i < n-1; i++){
            // 每一天由后一天的+1 的3/2倍得来
            x = (x+1)*3/2;
        }
        return x;
    }
}

复杂度分析

时间复杂度 $O(N)$ ：迭代计算时间 $O(N)$

空间复杂度O(1)：仅使用常数级变量空间

算法思想二：递归

解题思路：

由方法一可知：每天的蛋糕数量等于后一天数量加1的 3/2 倍计算

因此可以采用递归计算的方式来计算每天的蛋糕数量

1、特殊情况：当n == 1直接返回1

2、递归返回 $(cakeNumber(n-1) + 1) * 3 / 2$

代码展示：

Python版本

class Solution:
    def cakeNumber(self , n ):
        # write code here
        if n == 1:
            return 1
        # 递归计算前一天的蛋糕数量
        return (self.cakeNumber(n-1) + 1) * 3 / 2

复杂度分析

时间复杂度 $O(N)$ ：递归时间 $O(N)$

空间复杂度 $O(N)$ ：递归栈占用时间