[数据结构与算法][Leetcode] 每日两题 458 590 -day21

458. 可怜的小猪

可怜的小猪，这题一拿到就想到用动态规划做， 那要怎么用动态规划呢 。

从最简单的case开始：

先假设只有 一次机会，一只小猪 显然就是最多两瓶

那两只小猪呢 两只小猪喝完一次药的结果可以分 四种 都死 、A死 B不死、B死A不死，都不死

那么就可以对应4瓶药中找出一瓶，如果要给出具体的分配情况 :

都死 要对应一种信息 那 1 给 A B 都吃 ； 分别死 得对应一种信息 可以 2 3 分别给A,B吃； 都不死得对应一种信息 那4 就不给他们吃。 这样两种猪一次就可以对应4瓶。

问题到三只小猪 同样可以给出分配 A :1256 B：1357 C：1467 | 8

这样就可以发现 x 只小猪 一次喝药之后 可能出现 $2^X$ 种可能表现，就对应着 $2^X$瓶药

这样dp(x,1) 就求出来了 x 表示小猪数目， 1 表示一次机会

那么到两次呢 ：对于两次 机会 x只小猪 就等于 第一次喝药之后 加入还活着y 只小猪 ，接着y只小猪又回到第一次的情况 dp(x,2) = $\sum$dp(y,1)* $C_x^y$

对于n次机会也同样如此 dp(x,n) = $\sum$dp(y,n-1)* $C_x^y$

class Solution:
    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
        time = minutesToTest//minutesToDie
        dp = [[0] *int(log(buckets,2)+1) for _ in range(time + 1)]
        for i  in range (1,time+1):
            for j  in range(int(log(buckets,2)+1)):
                if i == 1:
                    dp[i][j] = 1<< j
                else:
                    for k in range(j+1):
                        dp[i][j] += dp[i-1][k]*comb(j,k) 
                if dp[time][j] >= buckets:
                            return j        
        return -1

然后通过上面的答案发现dp如下所示

[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512], 
[1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683],
[1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144], 
[1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125]]

x 小猪 n次 的话就是 $(n+1{)}^x$

这样一想就发现 原来 n次机会的话 每只小猪可能的表现就是 在第x 次死亡或者没死 这 n+1 种表现，

那么x只小猪就一共是 $(n+1{)}^x$ 种表现 所以就对应 着这么多瓶药。

妈的 小猪真可怜

class Solution:
    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
        return ceil(log(buckets, minutesToTest//minutesToDie + 1))

590. N 叉树的后序遍历

用一个list 用于储存节点 一个list用于储存访问值，后序遍历就相当于先右后左反过来，

对于节点列表中每个节点 释放之前，将其孩子节点都加入，同时将其值放入另一个list 然后重复以上过程

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if not root :
            return []  
        li =[root,]
        re = []
        while li :
            root = li.pop()
            if root.children:
                for children in root.children:
                    li.append(children)    
            re.append(root.val)
        return re[::-1]