题目描述：

LeetCode 441. Arranging Coins

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

Example 2:

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

题目大意：

你有n枚硬币，想要组成一个阶梯形状，其中第k行放置k枚硬币。

给定n，计算可以形成的满阶梯的最大行数。

n是非负整数，并且在32位带符号整数范围之内。

解题思路：

解法I 解一元二次方程（初等数学）：

x ^ 2 + x = 2 * n

解得：

x = sqrt(2 * n + 1/4) - 1/2

Python代码：

class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        return int(math.sqrt(2 * n + 0.25) - 0.5)

解法II 二分枚举答案（Binary Search）：

等差数列前m项和:m * (m + 1) / 2

在上下界l, r = [0, n]范围内二分枚举答案

Python代码：

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

二分查找的另一种等价实现形式如下

Python代码：

class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        l, r = 0, n + 1
        while l < r:
            m = (l + r) / 2
            if m * (m + 1) / 2 > n:
                r = m
            else:
                l = m + 1
        return l - 1

 

本文链接：http://bookshadow.com/weblog/2016/10/30/leetcode-arranging-coins/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码