leetcode 排列硬币

总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。

给定一个数字 n，找出可形成完整阶梯行的总行数。n 是一个非负整数，并且在32位有符号整型的范围内。

示例 1:

n = 5

硬币可排列成以下几行:
¤
¤ ¤
¤ ¤

因为第三行不完整，所以返回2.
示例 2:

n = 8

硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

因为第四行不完整，所以返回3.
链接：https://leetcode-cn.com/problems/arranging-coins
 

暴力法

class Solution:
    def arrangeCoins(self, n: int) -> int:
        rows = 0
        num = 0
        while True:
            if num>n:
                return (rows-1)
            if num==n:
                return rows
            rows += 1
            num += rows

二分查找

class Solution:
    def arrangeCoins(self, n: int) -> int:
        l,r=0,n
        while l<=r:
            m=(l+r)//2
            if (m**2+m)*0.5<=n and (m**2+3*m+2)*0.5>n:
                return m
            elif (m**2+m)*0.5<n:
                l=m+1
            elif (m**2+m)*0.5>n:
                r=m-1

解方程

class Solution:
    def arrangeCoins(self, n: int) -> int:
        import math
        return math.floor((math.sqrt(1+8*n)-1)/2)

解方程的方法出乎意料的并不比二分法快多少。