leetcode with python:441. Arranging Coins

题目:

You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete.

Given the integer n, return the number of complete rows of the staircase you will build.

给定金币的数量,开始排列,第一行排一个,第二行排两个,第三行排三个......
判断总共能排出完整的几行金币

这题我用二分搜来做

class Solution:    def arrangeCoins(self, n: int) -> int:        if n==1: #防止n为1            return 1                l=0        r=n        while l+1!=r:            mid=(l+r)//2            x=((1+mid)*mid)//2            if x==n:                return mid                        if x<n:                l=mid            elif x>n:                r=mid                return l

我们知道1+2+3+.....+n的公式为( (1+n) * n )//2

设好左右边界(l=0,r=n),mid设为(l+r)//2
若((1+mid) * mid)//2等于n
表示该金币数可以刚好排mid行,所以直接回传mid
而((1+mid) * mid)//2 大于n则r下降至mid,反之l上升至mid
直到l,r相邻
表示该金币数可以排l余行,所以回传l
最后执行时间39ms(faster than 91.95%)

那我们下题见