【Leetcode】【python】Arranging Coins
【Leetcode】【python】Arranging Coins
蛮三刀酱
发布于 2019-03-26 17:08:11
发布于 2019-03-26 17:08:11
Arranging Coins
标准答案代码来自书影博客
题目大意
你有n枚硬币，想要组成一个阶梯形状，其中第k行放置k枚硬币。 给定n，计算可以形成的满阶梯的最大行数。 n是非负整数，并且在32位带符号整数范围之内。
解题思路
数学方法
每行想填满需要k*(k+1)/2个硬币
二分枚举答案（Binary Search）
其实还是k*(k+1)/2的思路啊
代码
数学方法
class Solution(object):
def arrangeCoins(self, n):
k = 0
while k*(k+1)/2 <= n:
k += 1
return k-1二分枚举答案（Binary Search）
class Solution(object):
def arrangeCoins(self, n):
"""
:type n: int
:rtype: int
"""
l, r = 0, n
while l <= r:
m = (l + r) / 2
if m * (m + 1) / 2 > n:
r = m - 1
else:
l = m + 1
return r我提交的
class Solution(object):
def arrangeCoins(self, n):
"""
:type n: int
:rtype: int
"""
total = 0
row = 1
if n == 0:
return 0
if n == 1:
return 1
while True:
if n - total < row:
return row - 1
elif n - total == row:
return row
else:
total += row
row += 1总结
题目较为简单，思路都大同小异，我的解法还是比较2B（体现在速度巨慢），主要学习的是二分法。 看了一个二分法详解可以有空多看看。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年07月05日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录