Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
有query_row层垒起来的玻璃杯,第i层有i个杯子,从第一层开始倒水,倒进去poured杯水,求问第query_row层第query_glass个杯子有多少水
按层往下算,每次减去当前杯子装进的1杯,剩下对半分入下一层相邻两个杯子


 1 #799
 2 #Runtime: 59 ms (Beats 62.50%)
 3 #Memory: 13.3 MB (Beats 45.11%)
 4 
 5 class Solution(object):
 6     def champagneTower(self, poured, query_row, query_glass):
 7         """
 8         :type poured: int
 9         :type query_row: int
10         :type query_glass: int
11         :rtype: float
12         """
13         dp = [[0 for _ in range(x)] for x in range(1, query_row + 2)]
14         dp[0][0] = poured
15         for i in range(query_row):
16             for j in range(len(dp[i])):
17                 tp = (dp[i][j] - 1) / 2.0
18                 if tp > 0:
19                     dp[i + 1][j] += tp
20                     dp[i + 1][j + 1] += tp
21         return dp[query_row][query_glass] if dp[query_row][query_glass] <= 1 else 1

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理