跳转至

441. 排列硬币

题目描述

你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。

给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。

 

示例 1：

输入：n = 5
输出：2
解释：因为第三行不完整，所以返回 2 。

示例 2：

输入：n = 8
输出：3
解释：因为第四行不完整，所以返回 3 。

 

提示：

  • 1 <= n <= 231 - 1

解法

方法一：数学推导

思考

第 \(x\) 行用 \(x\) 枚硬币，完整行数满足 \(x(x+1)/2\le n\)。枚举 \(x\) 是线性的，\(n\) 可达 \(2^{31}-1\)。

解不等式得到 \(x\le \sqrt{2}\,\sqrt{n+1/8}-1/2\)，直接取整。把 \(2n\) 拆成 \(\sqrt{2}\sqrt{n+1/8}\)，减轻中间溢出。

闭式一次求值，代价为常数次浮点运算。

(1 + x) * x / 2 <= n，求解 x。

(x + 1/2)² <= 2n + 1/4，即 x <= sqrt(2n + 1/4) - 1/2。

由于 2n 可能溢出，故转换为 x <= sqrt(2) * sqrt(n + 1/8) - 1/2。

1
2
3
class Solution:
    def arrangeCoins(self, n: int) -> int:
        return int(math.sqrt(2) * math.sqrt(n + 0.125) - 0.5)

1
2
3
4
5
class Solution {
    public int arrangeCoins(int n) {
        return (int) (Math.sqrt(2) * Math.sqrt(n + 0.125) - 0.5);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
using LL = long;

class Solution {
public:
    int arrangeCoins(int n) {
        LL left = 1, right = n;
        while (left < right) {
            LL mid = left + right + 1 >> 1;
            LL s = (1 + mid) * mid >> 1;
            if (n < s)
                right = mid - 1;
            else
                left = mid;
        }
        return left;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func arrangeCoins(n int) int {
    left, right := 1, n
    for left < right {
        mid := (left + right + 1) >> 1
        if (1+mid)*mid/2 <= n {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return left
}

方法二：二分查找

思考

方法一依赖浮点开方，极大 \(n\) 时精度可能偏差。对行数二分：判断 \(mid(mid+1)/2\le n\)，上取整更新左界，只用整数运算。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def arrangeCoins(self, n: int) -> int:
        left, right = 1, n
        while left < right:
            mid = (left + right + 1) >> 1
            if (1 + mid) * mid // 2 <= n:
                left = mid
            else:
                right = mid - 1
        return left

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int arrangeCoins(int n) {
        long left = 1, right = n;
        while (left < right) {
            long mid = (left + right + 1) >>> 1;
            if ((1 + mid) * mid / 2 <= n) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return (int) left;
    }
}

评论