leetcode 441 排列硬币
z
 2019-06-30 15:24:13  

你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。给定一个数字 n，找出可形成完整阶梯行的总行数。n 是一个非负整数，并且在32位有符号整型的范围内。

1
2
3
4
5
6
7
示例 1:
n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整，所以返回2.
1
2
3
4
5
6
7
8
示例 2:
n = 8
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因为第四行不完整，所以返回3.
  • 二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 1:
            return n
        left = 1
        right = n
        while left < right:
            mid = (left + right) >> 1
            if mid*(mid+1)//2 == n:
                return mid
            if mid*(mid+1)//2 < n:
                left = mid + 1
            else:
                right = mid
        return left-1 # 考虑有n=4的情况，这个时候，left==right==3
  • Math
    $$
    \frac{k\times(k+1)}{2} = n \
    k^2 \times k - 2n = 0 \
    k_1 = \frac{-b + \sqrt{b^2-4ac}}{2a} = \frac{-1+\sqrt{1+8n}}{2} \
    k_2 = \frac{-b + \sqrt{b^2-4ac}}{2a} = \frac{-1-\sqrt{1+8n}}{2} <0
    $$
1
2
3
4
5
6
7
8
class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        return int((math.sqrt(1+8*n)-1)//2)