【LeetCode】441.排列硬币

题目

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

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

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

示例 1:
n = 5
硬币可排列成以下几行:

¤
¤ ¤
¤ ¤

因为第三行不完整,所以返回2.
示例 2:
n = 8

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

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

代码

题目描述:第 i 行摆 i 个,统计能够摆的行数。
返回 h 而不是 l,因为摆的硬币最后一行不能算进去。

public int arrangeCoins(int n) {
    int l = 0, h = n;
    while(l <= h){
        int m = l + (h - l) / 2;
        long x = m * (m + 1L) / 2;
        if(x == n) return m;
        else if(x < n) l = m + 1;
        else h = m - 1;
    }
    return h;
}

可以不用二分查找,更直观的解法如下:

public int arrangeCoins(int n) {
    int level = 1;
    while (n > 0) {
        n -= level;
        level++;
    }
    return n == 0 ? level - 1 : level - 2;
}
版权声明:本文(除特殊标注外)为原创文章,版权归 Geekerstar 所有。

本文链接:http://www.geekerstar.com/problem/583.html

除了有特殊标注文章外欢迎转载,但请务必标明出处,格式如上,谢谢合作。

本作品采用 知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议 进行许可。

最后修改:2018 年 03 月 18 日 07 : 21 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论