[LeetCode]Arranging Coins

题目描述:

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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