LeetCode441-排列硬币

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/arranging-coins/

中文链接：https://leetcode-cn.com/problems/arranging-coins/

题目详述

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

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

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

示例 1:

1
2
3
4
5
6
7
8
n = 5

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

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

示例 2:

n = 8

1
2
3
4
5
6
7
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

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

题目详解

实际上就是求满足 i * (i + 1) / 2 <= n 的最大的那个 i，运用二分查找即可。

1
2
3
4
5
6
7
8
9
10
11
12
public class LeetCode_00441 {

    public int arrangeCoins(int n) {
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r + 1 >>> 1;
            if (1L * mid * (mid + 1) / 2 <= n) l = mid;
            else r = mid - 1;
        }
        return r;
    }
}

也可以解二元一次方程直接求出结果。

1
2
3
4
5
6
public class LeetCode_00441 {

    public int arrangeCoins(int n) {
        return (int) ((-1 + Math.sqrt(1 + 8L * n)) / 2);
    }
}