【Leetcode】【python】Arranging Coins

超、凢脫俗 2022-06-13 10:25 114阅读 0赞

# Arranging Coins #

标准答案代码来自[书影博客][Link 1]

## 题目大意 ##

你有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（体现在速度巨慢），主要学习的是二分法。  
看了一个[二分法详解][Link 2]可以有空多看看。

[Link 1]: http://bookshadow.com/weblog/2016/10/30/leetcode-arranging-coins/
[Link 2]: http://blog.csdn.net/nzfxx/article/details/51615439