题解 | #牛妹的蛋糕#

牛妹的蛋糕

http://www.nowcoder.com/practice/1f7280d9897d4305b2da6790fe131729

题意

一个值操作n次

每次对一个值减少它的三分之一向下取整再减1

问最终剩余1，初始值是多少

题解

根据样例，最大只有10，所以我们不妨来直接正向模拟

10
10-3-1 = 6
6-2-1 = 3
3-1-1 = 1

把这个数据倒过来看

值	2	$3 = (1+1)\cdot 3//2$	4	5	$6 = (1+3)\cdot 3//2$	7	8	9	$10 = (1+6)\cdot 3//2$	11
次数	1	1	2	2	2	3	3	3	3	4

我们发现题意的解其实不唯一，似乎是让我们求最大的

而，从数学上对其反向操作，即是，每次加1，然后乘上二分之三向下取整即可

把数学变成代码

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
# @return int整型
#
class Solution:
    def cakeNumber(self , n ):
        v = 1
        for i in range(1,n):
            v+=1
            v*=3
            v//=2
        return v

复杂度分析

时间复杂度: 我们执行了n次逆向操作, $O (n)$

空间复杂度: 我们只用了常数个额外变量，因此复杂度为 $O (1)$

打表

代码

因为数据范围实在太小，我们可以尝试所有值把答案记录下来，在求答案时直接返回。

class Solution:
    def cakeNumber(self , n ):
        return [0,
                1,
                3,
                6,
                10,
                16,
                25,
                39,
                60,
                91,
                138,
                208,
                313,
                471,
                708,
                1063,
                1596,
                2395,
                3594,
                5392,
                8089,
                12135,
                18204,
                27307,
                40962,
                61444,
                92167,
                138252,
                207379,
                311070][n]

复杂度分析

时间复杂度: 我们直接从表中读取数据， $O (1)$

空间复杂度: 我们用了表来保存答案，因此复杂度为 $O (n)$

正向枚举

假设我们没有找到这个反向计算的公式，那么我们可以通过逐个尝试数值，找到正向计算后能得到同样结果的值。并且根据题意，需要是最大的一个

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
# @return int整型
#
class Solution:
    
    def daycount(self, v): # 按照题意的正向计算
        cnt = 1
        while v > 1:
            v -= v//3+1;
            cnt +=1
        return cnt
    
    def cakeNumber(self , n ):
        ans = 2;
        while self.daycount(ans) <= n: # 逐个枚举找到合法的最大值
            ans += 1
        return ans - 1