LeetCode每日一题: 排列硬币(No.441)

682 阅读1分钟

题目:排列硬币


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

示例:


n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整,所以返回2.

n = 8
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因为第四行不完整,所以返回3.

思考:


    定义一个curCoins记录当前行硬币数,residual表示剩余硬币数。
    当满足residual >= curCoins + 1即剩余硬币数足够排列满下一行,循环递增curCoins,再在residual中减去当前行的硬币数,
    直至不满足条件,就是到了最后一行,此时curCoins不会+1,即为最后行结果。

实现:


    class Solution {
    public int arrangeCoins(int n) {
        int curCoins = 1, residual = n - 1;
        while (residual >= curCoins + 1) {
            ++curCoins;
            residual -= curCoins;
        }
        return n == 0 ? 0 : curCoins;
    }
}