题解 | #牛妹的蛋糕#

题目：牛妹的蛋糕
描述：众所周知，牛妹非常喜欢吃蛋糕。第一天牛妹吃掉蛋糕总数三分之一（向下取整）多一个，第二天又将剩下的蛋糕吃掉三分之一（向下取整）多一个，以后每天吃掉前一天剩下的三分之一（向下取整）多一个，到第n天准备吃的时候只剩下一个蛋糕。
牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？
示例1：输入：2，返回值：3
示例2：输入：4，返回值：10

解法一：
思路分析：这道题应该典型的属于一道数学分析题，告诉你第n天准备吃的时候只剩下一个蛋糕，那么刚开始吃的时候一共有多少个蛋糕呢，以实例1为例，当第二天只剩下一个蛋糕，那么第一天就应该是3个，因为第一天吃掉蛋糕总数的三分之一向下取整1还多1个，所以1 + 1 = 2。既然该题已知了最后一天只剩一个，所以我们可以采用反推法进行分析。
实例分析：输入：4
——既然第一天吃掉蛋糕总数三分之一（向下取整）多一个，那么只需要将第二天 + 1乘以3/2即可得到最终的结果，下面我们进行分析：
图片说明
C++核心代码为：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
     * @return int整型
     */
    int cakeNumber(int n) {
        // write code here
        int temp = 1;//最后一天剩的一个
        if(n > 1){
            for(int i = 1;i < n;i++){
                temp = ((temp + 1)*3)/2;//循环n天反推法
            }
        }
        return temp;
    }
};

java核心代码为：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
     * @return int整型
     */
    public int cakeNumber (int n) {
        // write code here
        int temp = 1;
        if(n > 1){
            for(int i = 1;i < n;i++){
                temp = ((temp + 1)*3)/2;//循环n天反推法
            }
        }
        return temp;
    }
}

——因为有n天的话，按照公式法，就应该循环n次，所以其时间复杂度为 $O(N)$ ，没有额外的内存空间，所以其空间复杂度为 $O(1)$ 。

解法二：
思路分析：我们还可以采用递归法进行分析，还是按照公式法的形式进行书写，由题目可知，第n天的蛋糕数是由第n-1天所决定的，所以代码也可以这样进行递归运算。
递归法java核心代码：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
     * @return int整型
     */
    public int cakeNumber (int n) {
        // write code here
        if(n == 1)//特殊情况直接返回
            return 1;
        else
            return (cakeNumber(n - 1) + 1)*3/2;//递归
    }
}

——采用递归法的时间复杂度也是由天数决定的，在递归的过程中，因为有n天，首先在考虑第n的时候就需要递归的计算 $n - 1$ 天，计算 $n - 1$ 的时候就需要递归到 $n - 2$ 天，当递归到第一天的时候，就将1返回后再进行计算，所以其时间复杂度为 $O(N)$ ，因为在递归的过程中需要采用递归调用栈来存储数据，所以其空间复杂度为 $O(N)$ 。