题解 | #丢棋子问题#

丢棋子问题

http://www.nowcoder.com/practice/d1418aaa147a4cb394c3c3efc4302266

class Solution:
    def solve(self , n: int, k: int): # k个棋子进行了t次实验,可以验证的楼高
        if n < 1 or  k < 1: return 0
        if k == 1: return n # 只能从第一层逐层尝试
           
        # 二分,最差的情况
        import math
        b = math.log2(n) + 1
        if k >= b:
            return int(b) # 如果k充分大, 二分的扔即可
        
        # 初始化,j=1,扔一次只能验证一层
        dp = [1] * (k+1) # dp[i]:i个棋子可以验证的楼层数
        
        res = 1 # 最少也要扔1次
        while True:
            res += 1
            # dp[i]依赖左边和左上, 为了防止覆盖, 需要倒着计算
            for i in range(k, 1, -1):
                dp[i]=dp[i]+dp[i-1]+1
                if dp[i] >= n:
                    return res
            dp[1] = res
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-15 17:17
听说过付费实习,没想到这么贵啊我去,要不我给你个腰子吧
哈哈哈,你是老六:这种公司一定要注意啊,不要随便签合同,只要签了后面钱可能回不来,而且你通过法律途径也弄不回
点赞 评论 收藏
分享
一表renzha:手写数字识别就是一个作业而已
点赞 评论 收藏
分享
zzzzhz:兄弟你先猛猛投简历至少三百家,能约到面试就去面。最近可以速成智能小车,智慧家居烂大街的项目,不需要自己写,只需要把里面的代码讲解看明白就行。把其中涉及到的八股文都拿出来单独背一下,我去年找工作就一个智能小车智慧家居找了10k差不多。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务