跳转至

LeetCode: 441. 排列硬币

1、题目描述

你总共有 n 枚硬币,你需要将它们摆成一个阶梯形状,第 k 行就必须正好有 k 枚硬币。

给定一个数字 n,找出可形成完整阶梯行的总行数。

n 是一个非负整数,并且在32位有符号整型的范围内。

示例 1:

n = 5

硬币可排列成以下几行:
¤
¤ ¤
¤ ¤

因为第三行不完整,所以返回2.

示例 2:

n = 8

硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

因为第四行不完整,所以返回3.

2、解题思路

​ 这个问题可以用减值法,也可以用二分法,还能够用计算法

2.1 计算法

​ 正常情况下,我们想到的是下面的公式 $$ k*(k+1) \le 2n\ k^2+k \le 2n\ $$ 直接开方有问题,所以先来分解因式,先乘以4,得到 $$ 4*k^2 + 4*k \le 8n\

(2k+1)^2 -1 \le 8n\

k\le (\sqrt{8n+1}-1)/2 $$

int arrangeCoins(int n) {
    return (int)((-1 + sqrt(1 + 8 * (long double)n)) / 2);
}

2.2 遍历

int arrangeCoins(int n) {

    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (n >= i) {
            n -= i;
            count++;
        } else {
            break;
        }
    }

    return count;

}